🥋 Vertrauen ⚜ ein Beweis 🤼 Selbstschutzprogramm Zero-Knowledge-Proo †📱♁📲†

[★ Ronald Johannes deClaire Schwab]

 ♁ Die fabelhafte Welt der Mathematik: Vertrauen ist gut – ein Beweis ist besser
 .. Zero-Knowledge-Proofs†📱♁📲†
Täglich übergeben wir Online-Anbietern unsere Daten.
♁ Glücklicherweise gibt es Zero-Knowledge-Proofs, die es erlauben, etwas zu beweisen, ohne Informationen preiszugeben.♁

Zero-Knowledge-Proof
Zero-Knowledge Proof (ZKP) ist ein kryptografisches Protokoll, das es einer Partei, dem sogenannten Beweiser, ermöglicht, einer anderen Partei, dem sogenannten Verifizierer, zu beweisen, dass eine bestimmte Aussage wahr ist, ohne zusätzliche Informationen über die Aussage preiszugeben. Mit anderen Worten: Der Prüfer überzeugt den Prüfer davon, dass er etwas weiß, ohne preiszugeben, was er weiß.
Das Konzept der wissensfreien Beweise wurde erstmals in den 1980er Jahren von Shafi Goldwasser, Silvio Micali und Charles Rackoff eingeführt. Seitdem hat es sich zu einem wichtigen Werkzeug in der Kryptographie entwickelt und findet Anwendung in verschiedenen Bereichen, wie z. B. sichere Authentifizierung, Protokolle zum Schutz der Privatsphäre und Blockchain-Technologie.
Um zu verstehen, wie Zero-Knowledge-Proofs funktionieren, betrachten wir ein einfaches Beispiel: das „Färbungsproblem“. Angenommen, der Prüfer behauptet, eine Karte mit nur vier Farben einfärben zu können, sodass keine zwei benachbarten Regionen dieselbe Farbe haben. Der Prüfer möchte den Prüfer davon überzeugen, dass dies möglich ist, ohne das tatsächliche Farbschema preiszugeben.
Bei einem wissensfreien Beweis führen der Prüfer und der Prüfer einen interaktiven Prozess durch. Der Prüfer demonstriert sein Wissen, indem er eine Reihe von Schritten oder „Beweisen“ bereitstellt, die den Prüfer von der Gültigkeit der Aussage überzeugen. Im Falle des Farbproblems könnte der Prüfer eine Folge von Farbwechseln zwischen benachbarten Regionen präsentieren, um zu zeigen, dass es möglich ist, die gewünschte Farbgebung zu erreichen.
Während dieser Interaktion kann der Prüfer den Prüfer wiederholt dazu auffordern, sein Wissen nachzuweisen. Wenn der Prüfer wirklich sachkundig ist, kann er stets die richtigen Antworten geben. Allerdings erhält der Verifizierer auch nach mehreren Interaktionsrunden keine zusätzlichen Informationen über das spezifische Farbschema.
Wissensfreie Beweise basieren auf den Eigenschaften kryptografischer Funktionen wie Einwegfunktionen und Kollisionsresistenz, um die Sicherheit und den Datenschutz des Protokolls zu gewährleisten. Sie sind so konzipiert, dass sie recheneffizient sind, sodass der Verifizierungsprozess auch bei komplexen Problemen durchführbar ist.
Wissensfreie Beweise haben zahlreiche praktische Anwendungen. Beispielsweise können sie zur Authentifizierung von Identitäten verwendet werden, ohne dass sensible Informationen wie Passwörter oder biometrische Daten preisgegeben werden. Sie werden auch in Blockchain-Systemen verwendet, wo sie es Benutzern ermöglichen, die Gültigkeit einer Transaktion nachzuweisen, ohne die Details der Transaktion selbst preiszugeben.
Insgesamt stellen Zero-Knowledge-Beweise einen leistungsstarken Mechanismus zum Nachweis von Wissen oder zum Nachweis von Aussagen unter Wahrung von Privatsphäre und Vertraulichkeit dar.

..
Mit einem Zero-Knowledge-Proof lässt sich beweisen, dass man ein Geheimnis kennt, ohne dass man den Inhalt des Geheimnisses preisgeben muss.
Angenommen, ich zeige Ihnen ein Wimmelbild aus der Comicreihe »Wo ist Walter?«. Ich behaupte, die Figur mit ihrem rot-weiß geringelten Pulli innerhalb der etlichen Details gefunden zu haben. Weil Sie mir nicht glauben, möchte ich Ihnen beweisen, dass ich tatsächlich weiß, wo Walter sich befindet – allerdings ohne darauf zu zeigen, da ich Ihnen sonst den Spaß verderben würde, ihn selbst zu finden. Haben Sie eine Idee, wie mir das gelingen kann?
Eine einfache Lösung des Problems besteht darin, ein großes Stück Pappe zu nehmen und die exakte Silhouette von Walter auszuschneiden. Die Pappe muss deutlich größer sein als die Buchseite. Ich lege die Pappe dann – ohne dass Sie hinsehen – so auf das Bild, dass nur Walter sichtbar wird. Es dürfen keine weiteren Umgebungsdetails zu erkennen sein. Nun wissen Sie, dass ich die Figur gefunden habe, ohne jedoch zu erfahren, wo sich Walter genau auf der Seite befindet.
Es gibt zahlreiche weitere Beispiele für solche »Zero-Knowledge-Proofs«: Das sind Beweise, die keine Informationen preisgeben. Zum Beispiel könnten Sie eine Karte aus einem Stapel mit 52 Spielkarten ziehen und mir bloß beweisen, dass die gezogene Karte rot ist, ohne weitere Details darüber zu verraten. Würden Sie mir die Karte direkt zeigen, wüsste ich auch, welche Zahl oder Figur darauf abgebildet ist. Daher sortieren Sie aus dem Stapel einfach nur alle schwarzen Karten heraus. Wenn es 26 Stück sind, muss Ihre Karte folglich rot sein. Ich habe auf diese Weise aber keinerlei weitere Informationen darüber gewonnen, welche Karte Ihnen vorliegt.
Zugegeben, die zwei genannten Beispiele wirken sehr konstruiert. Im echten Leben geht es selten darum, die Farbe einer Spielkarte zu nennen oder Walter in einem Wimmelbild zu suchen. Wenn es aber um digitale Authentifizierung geht, erweisen sich Zero-Knowledge-Proofs (ZKP) als hilfreich: So kann man sich beispielsweise bei einem Anbieter einloggen, ohne diesem sensible Daten zu überlassen. Auch die Bereitstellung von persönlichen Dokumenten wie Führerschein, Pass, Lohnnachweis oder Steuerdokumenten lässt sich damit sicher anonymisieren. Und man kann ZKP bei elektronischen Wahlsystemen verwenden: So kann nicht einmal der Systemadministrator nachvollziehen, wie eine bestimmte Person gewählt hat. 2016 schlugen Kryptografen sogar vor, Zero-Knowledge-Proofs für die nukleare Abrüstung zu nutzen: Ohne die Details über den Aufbau eines nuklearen Sprengkopfs zu verraten, könnte ein Staat einer Behörde wie der IAEA beweisen, dass eine Waffe inaktiv ist.
Ein Beweis, der keinerlei Informationen überliefert
Die zwei vorgestellten Beispiele für Zero-Knowledge-Proofs lassen sich allerdings nicht wirklich verallgemeinern. Damit stellt sich die Frage, für welche Fälle sich überhaupt ein ZKP führen lässt. 1989 stellte sich die Kryptografin Shafi Goldwasser mit ihren Kollegen Silvio Micali und Charles Rackoff ebendiese Frage. Bereits zwei Jahre später fand Micali zusammen mit Oded Goldreich und Avi Wigderson eine Antwort auf die Frage: Erstaunlicherweise lässt sich zu jeder beweisbaren Aussage auch ein Zero-Knowledge-Proof führen. Das heißt: Egal, was Sie beweisen möchten, Sie können es tun, ohne irgendwelche Informationen preiszugeben.
Angenommen, Sie sind auf eine Lösung der riemannschen Vermutung gestoßen – eines der hartnäckigsten Probleme der Mathematik, das mit der Verteilung von Primzahlen zu tun hat. Nun möchten Sie einen Profi davon überzeugen, dass Sie den Beweis kennen, ohne ihn jedoch preiszugeben. (Sie könnten beispielsweise Angst haben, dass die Person ihn vor Ihnen publiziert). Kein Problem: Denn Goldreich, Micali und Wigderson haben gezeigt, dass es einen ZKP gibt, der zweifelsfrei belegt, dass Sie die riemannsche Vermutung beweisen können – ohne irgendwelche Details zu Ihrer Vorgehensweise zu enthüllen.
    Startseite
    Mathematik
    Aktuelle Seite: Zero-Knowledge-Proof: Wie man etwas Geheimes beweist
     ♁ Die fabelhafte Welt der Mathematik

    Lesedauer ca. 9 Minuten
    Drucken
    Teilen (PN: Bitte teilen mit deinen besten Freunden; Danke!)

Die fabelhafte Welt der Mathematik: Vertrauen ist gut – ein Beweis ist besser
 ..
Täglich übergeben wir Online-Anbietern unsere Daten. Glücklicherweise gibt es Zero-Knowledge-Proofs, die es erlauben, etwas zu beweisen, ohne Informationen preiszugeben.
Zwei Hände, die sich halten, in digitaler Darstellung
Mit einem Zero-Knowledge-Proof lässt sich beweisen, dass man ein Geheimnis kennt, ohne dass man den Inhalt des Geheimnisses preisgeben muss.
..
Angenommen, ich zeige Ihnen ein Wimmelbild aus der Comicreihe »Wo ist Walter?«. Ich behaupte, die Figur mit ihrem rot-weiß geringelten Pulli innerhalb der etlichen Details gefunden zu haben. Weil Sie mir nicht glauben, möchte ich Ihnen beweisen, dass ich tatsächlich weiß, wo Walter sich befindet – allerdings ohne darauf zu zeigen, da ich Ihnen sonst den Spaß verderben würde, ihn selbst zu finden.
Haben Sie eine Idee, wie mir das gelingen kann?
Eine einfache Lösung des Problems besteht darin, ein großes Stück Pappe zu nehmen und die exakte Silhouette von Walter auszuschneiden. Die Pappe muss deutlich größer sein als die Buchseite. Ich lege die Pappe dann – ohne dass Sie hinsehen – so auf das Bild, dass nur Walter sichtbar wird. Es dürfen keine weiteren Umgebungsdetails zu erkennen sein. Nun wissen Sie, dass ich die Figur gefunden habe, ohne jedoch zu erfahren, wo sich Walter genau auf der Seite befindet.
Es gibt zahlreiche weitere Beispiele für solche »Zero-Knowledge-Proofs«: Das sind Beweise, die keine Informationen preisgeben. Zum Beispiel könnten Sie eine Karte aus einem Stapel mit 52 Spielkarten ziehen und mir bloß beweisen, dass die gezogene Karte rot ist, ohne weitere Details darüber zu verraten. Würden Sie mir die Karte direkt zeigen, wüsste ich auch, welche Zahl oder Figur darauf abgebildet ist. Daher sortieren Sie aus dem Stapel einfach nur alle schwarzen Karten heraus. Wenn es 26 Stück sind, muss Ihre Karte folglich rot sein. Ich habe auf diese Weise aber keinerlei weitere Informationen darüber gewonnen, welche Karte Ihnen vorliegt.
Das könnte Sie auch interessieren: Spektrum Kompakt Statistik – Zahlenspiele mit Mehrwert
♁ Statistik – Zahlenspiele mit Mehrwert
Zugegeben, die zwei genannten Beispiele wirken sehr konstruiert. Im echten Leben geht es selten darum, die Farbe einer Spielkarte zu nennen oder Walter in einem Wimmelbild zu suchen. Wenn es aber um digitale Authentifizierung geht, erweisen sich Zero-Knowledge-Proofs (ZKP) als hilfreich: So kann man sich beispielsweise bei einem Anbieter einloggen, ohne diesem sensible Daten zu überlassen. Auch die Bereitstellung von persönlichen Dokumenten wie Führerschein, Pass, Lohnnachweis oder Steuerdokumenten lässt sich damit sicher anonymisieren. Und man kann ZKP bei elektronischen Wahlsystemen verwenden: So kann nicht einmal der Systemadministrator nachvollziehen, wie eine bestimmte Person gewählt hat. 2016 schlugen Kryptografen sogar vor, Zero-Knowledge-Proofs für die nukleare Abrüstung zu nutzen: Ohne die Details über den Aufbau eines nuklearen Sprengkopfs zu verraten, könnte ein Staat einer Behörde wie der IAEA beweisen, dass eine Waffe inaktiv ist.
Ein Beweis, der keinerlei Informationen überliefert.
Die zwei vorgestellten Beispiele für Zero-Knowledge-Proofs lassen sich allerdings nicht wirklich verallgemeinern. Damit stellt sich die Frage, für welche Fälle sich überhaupt ein ZKP führen lässt. 1989 stellte sich die Kryptografin Shafi Goldwasser mit ihren Kollegen Silvio Micali und Charles Rackoff ebendiese Frage. Bereits zwei Jahre später fand Micali zusammen mit Oded Goldreich und Avi Wigderson eine Antwort auf die Frage: Erstaunlicherweise lässt sich zu jeder beweisbaren Aussage auch ein Zero-Knowledge-Proof führen. Das heißt: Egal, was Sie beweisen möchten, Sie können es tun, ohne irgendwelche Informationen preiszugeben.
Angenommen, Sie sind auf eine Lösung der riemannschen Vermutung gestoßen – eines der hartnäckigsten Probleme der Mathematik, das mit der Verteilung von Primzahlen zu tun hat. Nun möchten Sie einen Profi davon überzeugen, dass Sie den Beweis kennen, ohne ihn jedoch preiszugeben. (Sie könnten beispielsweise Angst haben, dass die Person ihn vor Ihnen publiziert). Kein Problem: Denn Goldreich, Micali und Wigderson haben gezeigt, dass es einen ZKP gibt, der zweifelsfrei belegt, dass Sie die riemannsche Vermutung beweisen können – ohne irgendwelche Details zu Ihrer Vorgehensweise zu enthüllen.
Die drei haben aber nicht nur bewiesen, dass sich stets ein ZKP formulieren lässt – sie haben auch beschrieben, wie man ihn führt. Ihre Idee bestand darin, einen Zero-Knowledge-Proof für eine bestimmte Klasse von Problemen zu finden. Und dann zu zeigen, dass sich jede mathematische Aussage auf Probleme dieser Art übertragen lässt. Möchte man also einen ZKP für eine Aussage führen, übersetzt man sie zunächst in eine andere Form und wendet dort die Methode
†📱📲† Künstliche Gespräche – Kommunikation mit KI-Chatbots
Das konkrete Beispiel, für das die drei Kryptografen den ZKP entwickelt haben, ist das Färben von Graphen. Die Aufgabe leitet sich von dem Färben einer Landkarte ab, bei der benachbarte Länder unterschiedliche Farben aufweisen sollen. Mathematiker abstrahieren diese Aufgabe, indem sie statt Ländern ein Netzwerk betrachten: Die Punkte darin stellen die Länder dar; sie sind miteinander durch eine Kante verbunden, falls sie in der Landkarte aneinandergrenzen.
In den 1970er Jahren haben die Mathematiker Heinrich Heesch, Kenneth Appel und Wolfgang Haken gezeigt, dass sich jede Karte durch bloß vier Farben kolorieren lässt (der berühmte Vier-Farben-Satz). Tatsächlich war das einer der ersten computergestützten Beweise der Mathematik und führte deshalb zu vielen Diskussionen, ab wann man von einem Beweis sprechen könne. Auch wenn bekannt ist, dass sich jeder Graph mit vier Farben so färben lässt, dass keine zwei verbundenen Punkte gleich koloriert sind, gibt es viele Netzwerke, die mit bloß drei Farben auskommen. Herauszufinden, ob ein Graph eine Färbung mit nur drei Farben zulässt, gehört zu den so genannten NP-vollständigen Problemen. Darunter versteht man jene mathematischen Aufgaben, die sich mit wachsender Größe kaum noch berechnen lassen, aber deren Lösung leicht zu überprüfen ist.
♁ Ein Zero-Knowledge-Proof für einen Graphen mit drei Farben
Hat man eine Färbung mit bloß drei Farben gefunden, lässt sich, wie Micali, Goldreich und Wigderson gezeigt haben, ein Zero-Knowledge-Proof führen. Das heißt, man kann beweisen, dass sich das Netzwerk mit nur drei Farben kolorieren lässt, ohne die Färbung selbst preiszugeben. Das lässt sich am besten anhand von zwei Personen demonstrieren, die sich gegenseitig herausfordern: Peggy, die eine Färbung gefunden hat, und Victor, dem sie das beweisen möchte. Zunächst nummeriert Peggy alle Punkte ihres Graphen. Zu jedem Punkt notiert sie auf einem Zettel die dazugehörige Farbe (etwa: Rot, Blau oder Grün) und steckt diesen Zettel in einen Umschlag mit der entsprechenden Nummer des Punkts. Dann gehen sie folgende Schritte durch:
    Victor sucht zwei miteinander verbundene Punkte im Graphen heraus und bittet Peggy, die entsprechenden Umschläge zu öffnen.
    Sind die darin enthaltenen Farben gleich, dann hat Peggy gelogen: Sie hat keine gültige Färbung gefunden. Enthalten die Umschläge hingegen unterschiedliche Farben, geht das Spiel weiter.
    Peggy bekommt nun die Chance, alle Farben im Geheimen umzusortieren, zum Beispiel: Alle roten Punkte werden grün, alle grünen blau und alle blauen rot. Damit bleibt die Färbung an sich erhalten, aber Victor erfährt durch die folgenden Schritte nicht, wie Peggy den Graphen koloriert hat.
    Die beiden wiederholen die Schritte.
Bei jedem Durchgang erhöht sich die Wahrscheinlichkeit dafür, dass Peggy wirklich eine gültige Färbung gefunden hat. Hätte sie die Punkte zufällig eingefärbt, würde Victor irgendwann auf ein Punktepaar stoßen, das gleichfarbig ist. Gleichzeitig ist durch die Ersetzung der Farben in jeder Runde sichergestellt, dass Victor nichts über die Färbung erfährt. Er kann Peggy noch so oft abfragen, er wird auf diese Weise niemals erfahren, wie sie den Graphen eingefärbt hat.
Der ZKP für das Färbeproblem erweist sich als extrem nützlich. Denn wie der Informatiker Richard Karp 1972 herausfand, folgt aus einer Lösung des Drei-Farben-Problems automatisch eine Lösung für eine ganz andere Klasse von mathematischen Aufgaben: die »Satisfiability«-Probleme (kurz: SAT). Dabei geht es darum, zu beurteilen, ob eine Verkettung logischer Ausdrücke korrekt ist – oder zu einem Widerspruch führt.
Ein Beispiel für eine solche Verkettung ist: x ∧ ¬x. Auf den ersten Blick sieht das kompliziert aus. Die Aussage lässt sich aber schnell übersetzen, wenn man weiß, dass »∧« für »und gleichzeitig« steht sowie »¬« eine Negation darstellt. Damit lässt sich die Aussage übersetzen zu: x und gleichzeitig nicht x. Die Aufgabe besteht nun darin, der Variablen x den Wert »wahr« oder »falsch« zuzuordnen, damit die Gesamtaussage wahr wird (also keinen Widerspruch erzeugt). In diesem Fall ist das unmöglich, denn entweder man erhält: wahr und gleichzeitig nicht wahr (für x = wahr) oder falsch und gleichzeitig nicht falsch (für x = falsch). Beide Aussagen ergeben keinen Sinn: Etwas kann nicht wahr und falsch zugleich sein. Daher ist diese Verkettung von Ausdrücken nicht erfüllbar.
Ein etwas komplizierteres Beispiel für eine erfüllbare Verkettung ist: (x1 ∨ ¬x2) ∧ (¬x1 ∨ x2) ∧ ¬x1. Hier taucht auch ein neues Symbol auf: »∨« steht für ein logisches »oder«. Die Aussage bedeutet also: (x1 oder nicht x2) und gleichzeitig (nicht x1 oder x2) und gleichzeitig nicht x1. Finden Sie eine Möglichkeit, den Variablen xi die Werte »wahr« oder »falsch« zuzuordnen, damit die Gesamtaussage wahr wird? Eine Lösung besteht darin, dass sowohl x1 als auch x2 falsch sind, denn dann gilt: (falsch oder wahr) und gleichzeitig (wahr oder falsch) und gleichzeitig wahr. Daraus lässt sich konstruieren: wahr und gleichzeitig wahr und gleichzeitig wahr, also wahr.
Tatsächlich lässt sich jede mathematische Aussage in die folgende Form übertragen: (a1 ∨ b1 ∨ c1) ∧ (a2 ∨ b2 ∨ c2) ∧ … ∧ (an ∨ bn ∨ cn). Das entspricht der Art und Weise, wie Computer rechnen: Man übergibt ihnen eine Aussage (etwa »3 + 5 = 5«), sie wandeln das in Einsen und Nullen (in unserem Beispiel entspricht 1 = wahr und 0 = falsch) sowie logische Verknüpfungen um und prüfen so die Eingabe.
Damit stellt jede mathematische Aussage im Grunde ein SAT-Problem dar: Man kann sie theoretisch in eine lange Verkettung von logischen Ausdrücken umschreiben, die ein Computer dann auf seine Richtigkeit hin überprüfen kann. Gibt es eine geeignete Kombination von »wahr« und »falsch« (beziehungsweise 1 und 0), dann ist die Aussage korrekt – und somit auch bewiesen (es liegt kein Widerspruch vor). Wie Sie aber wahrscheinlich schon erahnen können, ist es bereits aufwändig, einfachste Rechenoperationen auf diese Weise auszudrücken. Eine folgenschwere Aussage wie »Die riemannsche Vermutung ist wahr!« lässt sich kaum in eine solche Form bringen – geschweige denn alle Kombinationen von Wahr/falsch-Werten für alle benötigten Variablen durchspielen.
Jede beweisbare Aussage lässt sich in einen Graphen mit drei Farben übertragen.
Doch Goldreich, Micali und Wigderson konnten die Tatsache, dass jede beweisbare Aussage sich auf ein SAT-Problem zurückführen lässt, nutzen, um mehr über Zero-Knowledge-Proofs zu erfahren. Denn wie der Informatiker Karp bereits herausgefunden hatte, lässt sich jede Aussage der Form (a1 ∨ b1 ∨ c1) ∧ (a2 ∨ b2 ∨ c2) ∧ … ∧ (an ∨ bn ∨ cn) in einen Graphen verwandeln: Jede Variable entspricht dann einem Punkt, den man ähnlich wie bei logischen Gattern mit anderen Punkten im Graphen verknüpft. Das lässt sich am einfachsten an »a ∨ b« veranschaulichen:
 Graph für »a oder b« | Oben der allgemeine Graph für die logische Aussage. Eine Färbung für a und b (rot = falsch, grün = wahr) liefert automatisch das richtige Ergebnis für die Aussage »a oder b«.
Nun identifiziert man die Farbe Rot mit falsch, Grün mit wahr und verwendet Blau als Hilfsfarbe ohne direkten Wahrheitsbezug. Sie dürfen a und b also nur grün oder rot färben – durch diese Wahl ist dann festgelegt, welche Farbe der Punkt »a ∨ b« hat: Rot, falls die Aussage falsch ist, oder Grün, falls sie richtig ist. Das heißt: Am Ende kann nur »Rot« herauskommen, falls sowohl a als auch b rot eingefärbt sind. In allen anderen Fällen besteht die Möglichkeit, den Graphen ohne Probleme mit den drei verfügbaren Farben einzufärben, so dass am Ende Grün herauskommt.
Um sicherzustellen, dass eine Aussage (etwa: »a ∨ b«) am Ende wahr ist, kann man einfach folgendes Dreieck an den letzten Punkt hängen:
 Graph für »a oder b« mit Anhängsel | Durch das am Ende angehängte Dreieck besteht die Aufgabe nun darin, eine wahre Aussage zu erzeugen – »a oder b« muss grün (also wahr) sein.
Auf diese Weise lässt sich jede mathematische Aussage in einen – zugegebenermaßen – komplizierten Graphen übertragen. Falls es gelingt, diesen ohne Fehler mit nur drei Farben zu färben, dann ist die Aussage nach allen Regeln der Logik korrekt.
Und genau das ist der Schlüssel, um einen Zero-Knowledge-Proof für alle beweisbaren Aussagen zu formulieren. Denn man kann jede davon (zum Beispiel: »Die riemannsche Vermutung ist wahr«) in eine SAT-Form übersetzen. Daraus lässt sich dann ein Graph konstruieren, der der ursprünglichen Aussage entspricht. Und das Beste: Kennt man den Beweis zu der Aussage, dann kann man diesen in eine Anweisung übersetzen, den Graphen mit nur drei Farben zu kolorieren. Wäre die riemannsche Vermutung also falsch, würde sich der dazugehörige Graph nicht mit bloß drei Farben kolorieren lassen – man bräuchte dafür zwingend vier Farben.
Da Micali, Goldreich und Wigderson einen Zero-Knowledge-Proof für das Drei-Farben-Problem präsentiert haben, lässt sich ein ZKP für jede mathematisch beweisbare Aussage vorlegen. Damit lässt sich die Methode auch auf weniger abstrakte Probleme anwenden: etwa den Nachweis, dass man eine gültige Versicherungsnummer hat, ohne diese direkt preisgeben zu müssen. Weil die Umwandlung in ein SAT-Problem nicht immer ganz einfach ist, gibt es inzwischen viele weitere Protokolle, um effizientere Zero-Knowledge-Proofs für bestimmte Probleme zu entwerfen – und damit unsere Privatsphäre zu schützen.
https://de.wikipedia.org/w/index.php?search=Zero-Knowledge-Proof&title=Spezial%3ASuche&profile=advanced&fulltext=1&ns0=1
      ♁            ♁♁