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.

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 von Micali, Goldreich und Wigderson an.

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:

1. Victor sucht zwei miteinander verbundene Punkte im Graphen heraus und bittet Peggy, die entsprechenden Umschläge zu öffnen.
2. 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.
3. 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.
4. 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: (x₁ ∨ ¬x₂) ∧ (¬x₁ ∨ x₂) ∧ ¬x₁. Hier taucht auch ein neues Symbol auf: »∨« steht für ein logisches »oder«. Die Aussage bedeutet also: (x₁ oder nicht x₂) und gleichzeitig (nicht x₁ oder x₂) und gleichzeitig nicht x₁. Finden Sie eine Möglichkeit, den Variablen x_i die Werte »wahr« oder »falsch« zuzuordnen, damit die Gesamtaussage wahr wird? Eine Lösung besteht darin, dass sowohl x₁ als auch x₂ 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: (a₁ ∨ b₁ ∨ c₁) ∧ (a₂ ∨ b₂ ∨ c₂) ∧ … ∧ (a_n ∨ b_n ∨ c_n). 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 (a₁ ∨ b₁ ∨ c₁) ∧ (a₂ ∨ b₂ ∨ c₂) ∧ … ∧ (a_n ∨ b_n ∨ c_n) 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:

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:

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.

​​Was ist euer Lieblingsmathetheorem? Schreibt es gerne in die Kommentare – und vielleicht ist es schon bald das Thema dieser Kolumne!