Proof: Das Ende offener Wissenschaft?

Zero-Knowledge-Proofs Stellen Sie sich vor, Sie hätten die ultimative Geheimwaffe entwickelt – eine Waffe, die die Welt ins Chaos stürzen kann. Sie möchten die Menschheit jedoch vor der Gefahr warnen, damit sie sich davor schützen kann. Aber wieso sollte man Ihnen glauben? Sie stehen nun vor einem Dilemma: Falls Sie Ihre Waffe vorstellen, um die Welt von Ihrer Warnung zu überzeugen, geben Sie Ihr Wissen preis – und das könnte ein Dritter nutzen, um die Waffe tatsächlich zu bauen und einzusetzen. Falls Sie aber nichts sagen, könnte eine andere Person auf dieselbe Idee wie Sie kommen und die Waffe ebenfalls entwickeln. Und die Welt wäre ihr schutzlos ausgeliefert. Wie die Informatikerin Shafi Goldwasser und ihre beiden Kollegen Silvio Micali und Charles Rackoff 1985 bewiesen, gibt es einen mathematischen Ausweg aus diesem Dilemma. Denn die Annahme, dass man Informationen preisgeben muss, um jemanden zu überzeugen, erweist sich als falsch. Zero-Knowledge-Proofs ermöglichen es, Gewissheit zu schaffen und dabei Geheimnisse zu bewahren. Überzeugung durch Interaktion Um zu verstehen, wie ein Zero-Knowledge-Proof funktioniert, kann man sich eine Person vorstellen, die in einer Welt voller Farbenblinder behauptet, Farben erkennen und voneinander unterscheiden zu können. Wie kann sie Sie von ihrer besonderen Fähigkeit überzeugen? Eine Möglichkeit besteht darin, ihr zwei identische Kugeln zu zeigen, die – angeblich – unterschiedliche Farben haben. Nun können Sie die Kugeln hinter Ihrem Rücken entweder vertauschen oder nicht, ohne dass die Person es sieht. Anschließend zeigen Sie ihr die Kugeln und fragen, welche Kugel welche ist. Indem Sie diesen Versuch wiederholen, können Sie sich davon überzeugen, ob die Person gelogen hat oder nicht. Falls sie die Farben der Kugeln nur zufällig benennt, ist die Wahrscheinlichkeit hoch, dass sie nach mehreren Durchläufen einen Fehler macht. Falls die Person aber die Wahrheit sagt, wird sie immer richtigliegen. Dieses Gedankenexperiment offenbart die drei Kerneigenschaften eines Zero-Knowledge-Proofs: Wer die Wahrheit kennt, kann andere davon überzeugen. Wer lügt, wird irgendwann erwischt. Wer überprüft, lernt nichts über das Geheimnis. Nachdem die mathematische Grundlage für Zero-Knowledge-Proofs gelegt war, stellte diese Form von Beweisen jedoch nur einen interessanten wissenschaftlichen Trick dar. Es gab zwar vereinzelte Anwendungsbeispiele, für die man einen Zero-Knowledge-Proof führen konnte, aber das Konzept ließ sich zunächst nicht großflächig nutzen. Das änderte sich allerdings, als Fachleute einen Zero-Knowledge-Proof für ein klassisches Problem der Mathematik entwickelten: das Färben eines Graphen. Zu jeder wahren Aussage existiert ein Zero-Knowledge-Proof Ein Graph besteht aus Punkten, die durch Kanten miteinander verbunden sind. Mathematikerinnen und Mathematiker ziehen in den verschiedensten Bereichen ihres Fachs solche Netzwerke heran, um Aufgaben zu lösen – etwa um kürzeste Routen zu bestimmen oder Raumbelegungen zu planen. Eine besondere Rolle nehmen in der Graphentheorie sogenannte Färbeprobleme ein. Dabei besteht die Aufgabe darin, die Knoten des Graphen mit möglichst wenigen unterschiedlichen Farben einzufärben, sodass miteinander verbundene Knoten stets verschieden koloriert sind. Hat man eine solche optimale Färbung gefunden – etwa mit drei verschiedenen Farben –, lässt sich ein Zero-Knowledge-Beweis führen: Mit diesem lässt sich ein Gegenüber davon überzeugen, dass man eine Färbung mit nur drei Farben gefunden hat, ohne die genaue Färbung preiszugeben. Die Vorgehensweise ist recht simpel. Hierzu kann man sich vorstellen, dass man die Knoten des Graphen nummeriert und zu jedem Knoten einen zugehörigen Briefumschlag hat, in den man die Farbe des Knotens packt. Um sich von einer gültigen Färbung zu überzeugen, kann eine Person eine Kante des Graphen auswählen, die zwei Knoten miteinander verbindet, und die entsprechenden Umschläge der Knoten öffnen. So kann sie prüfen, ob beide Farben tatsächlich verschieden sind. Wie beim Beispiel mit den Farbenblinden und den Kugeln genügt ein einzelner Durchlauf nicht, um jemanden zu überzeugen. Doch bevor die Person eine zweite Kante zum Testen der Behauptung auswählt, muss man die Farben innerhalb der Briefumschläge permutieren: So wird etwa Rot zu Blau, Blau zu Grün und Grün zu Rot. Nur auf diese Weise stellt man sicher, dass die Person keine Information über die Färbung des Graphen erhält. Anschließend wählt die Person eine weitere Kante des Graphen aus und öffnet wieder die zugehörigen Umschläge. Dann folgt erneut eine Permutation der Farben und das Spiel beginnt von vorn. Dieser Ablauf lässt sich beliebig oft wiederholen – und mit jedem erfolgreichen Abschluss erhöht sich die Wahrscheinlichkeit dafür, dass tatsächlich eine Färbung des Graphen mit bloß drei Farben vorliegt. Diese Vorgehensweise dient als Basis für die universelle Anwendung von Zero-Knowledge-Proofs. Denn wie sich herausstellt, lässt sich jede wahre Aussage in der Mathematik als Graph darstellen, der mit nur drei Farben koloriert werden kann. Das heißt: Jeder Beweis einer Aussage entspricht einer konkreten Färbungsanweisung eines Graphen mit nur drei Farben. Und da bekannt ist, wie ein Zero-Knowledge-Proof für solche Färbungen aussieht, lässt sich zu jeder beweisbaren Aussage ein Zero-Knowledge-Proof konstruieren.