Stellen Sie sich vor, Sie hätten ein nützliches Wissen – vielleicht ein Geheimrezept oder den Schlüssel zu einer Chiffre. Könnten Sie einem Freund beweisen, dass Sie dieses Wissen hatten, ohne etwas darüber preiszugeben? Informatiker haben vor über 30 Jahren bewiesen, dass dies möglich ist, wenn man einen sogenannten Zero-Knowledge-Beweis verwendet.
Um diese Idee einfach zu verstehen, nehmen wir an, Sie möchten Ihrem Freund zeigen, dass Sie wissen, wie man durch ein Labyrinth kommt, ohne Details über den Pfad preiszugeben. Sie konnten das Labyrinth einfach innerhalb eines Zeitlimits durchqueren, während Ihr Freund das Zuschauen untersagte. (Das Zeitlimit ist notwendig, da jeder mit genügend Zeit schließlich durch Versuch und Irrtum einen Weg finden kann.) Ihr Freund würde wissen, dass Sie es schaffen könnten, aber er wüsste nicht, wie.
Zero-Knowledge-Proofs sind hilfreich für Kryptographen, die mit geheimen Informationen arbeiten, aber auch für Forscher der Rechenkomplexität, die sich mit der Klassifizierung der Schwierigkeit verschiedener Probleme befassen. „Ein Großteil der modernen Kryptografie beruht auf Komplexitätsannahmen – auf der Annahme, dass bestimmte Probleme schwer zu lösen sind, also gab es immer einige Verbindungen zwischen den beiden Welten“, sagte er Claude Crepeau, Informatiker an der McGill University. „Aber [diese] Beweise haben eine ganze Welt der Verbindung geschaffen.“
Zero-Knowledge-Proofs gehören zu einer Kategorie, die als interaktive Proofs bekannt ist. Um also zu lernen, wie die ersteren funktionieren, hilft es, die letzteren zu verstehen. Zuerst beschrieben in einer 1985 erschienenen Arbeit der Informatiker Schafi Goldwasser, Silvio Micali und Charles Rackoff funktionieren interaktive Beweise wie ein Verhör: Über eine Reihe von Nachrichten versucht eine Partei (der Beweiser) die andere (der Prüfer) davon zu überzeugen, dass eine bestimmte Aussage wahr ist. Ein interaktiver Beweis muss zwei Eigenschaften erfüllen. Erstens wird eine wahre Aussage einen ehrlichen Verifizierer letztendlich immer überzeugen. Zweitens, wenn die gegebene Aussage falsch ist, kann kein Beweiser – selbst einer, der vorgibt, bestimmtes Wissen zu besitzen – den Prüfer überzeugen, außer mit einer vernachlässigbar kleinen Wahrscheinlichkeit.
Interaktive Beweise sind probabilistischer Natur. Der Beweiser könnte ein oder zwei Fragen einfach durch Glück richtig beantworten, also braucht es eine genügend große Anzahl von Herausforderungen, die der Beweiser alle richtig machen muss, damit der Prüfer sicher ist, dass der Beweiser tatsächlich weiß, dass die Aussage wahr ist.
Diese Idee der Interaktionen entstand, als Micali und Goldwasser – damals Doktoranden an der University of California, Berkeley – sich mit der Logistik des Pokerspiels über ein Netzwerk beschäftigten. Wie können alle Spieler überprüfen, ob das Ergebnis zufällig ist, wenn einer von ihnen eine Karte aus dem virtuellen Stapel erhält? Interaktive Beweise könnten den Weg weisen. Aber wie können die Spieler dann überprüfen, ob das gesamte Protokoll – das gesamte Regelwerk – korrekt befolgt wurde, ohne dabei die Hand jedes Spielers zu enthüllen?
Um dieses Ziel zu erreichen, fügten Micali und Goldwasser den beiden für einen interaktiven Beweis erforderlichen Eigenschaften eine dritte hinzu: Der Beweis sollte nichts über das Wissen selbst aussagen, sondern nur den Wahrheitsgehalt der Aussage. „Es gibt die Vorstellung, ein Protokoll durchzugehen, an dessen Ende man glaubt, dass [die Pokerspieler] nicht mehr wissen, als sie wissen sollen“, sagte Goldwasser.
Betrachten wir das klassische Beispiel. Alice will Bob beweisen, dass es einen bestimmten Graphen gibt G – eine einzigartige Sammlung von Scheitelpunkten (Punkten), die durch Kanten (Linien) verbunden sind – hat einen „Hamiltonschen Zyklus“. Das bedeutet, dass der Graph einen Pfad hat, der jeden Punkt genau einmal besucht und an demselben Punkt endet, an dem er begonnen hat. Alice könnte dies tun, indem sie Bob einfach den Pfad zeigt, der dies tut, aber dann würde er natürlich auch den Pfad kennen.
So kann Alice Bob davon überzeugen, dass sie weiß, dass es einen solchen Pfad gibt, ohne ihn ihm zu zeigen. Zuerst zeichnet sie einen neuen Graphen, H, das sieht nicht danach aus G aber in entscheidender Weise ähnlich: Es hat die gleiche Anzahl von Scheitelpunkten, die auf die gleiche Weise verbunden sind. (Wenn G hat wirklich einen Hamiltonkreis, bedeutet diese Ähnlichkeit H wird auch.) Dann, nachdem alle Kanten abgedeckt wurden H mit Klebeband sperrt sie H in eine Kiste und gibt die Kiste Bob. Dies hindert ihn daran, es direkt zu sehen, hindert sie aber auch daran, es zu ändern. Dann trifft Bob eine Wahl: Entweder kann er Alice bitten, das zu zeigen H ist wirklich ähnlich G, oder er kann sie bitten, ihm den Hamilton-Zyklus in zu zeigen H. Beide Anfragen sollten für Alice einfach sein, das vorausgesetzt H ist wirklich ähnlich genug zu G, und dass sie den Weg wirklich kennt.
Natürlich, auch wenn Alice den Hamilton-Zyklus nicht kennt G, kann sie versuchen, Bob zu täuschen, indem sie entweder Diagramme zeichnet, die denen nicht ähnlich sind G, oder indem sie Diagramme einreicht, für die sie den Pfad nicht kennt. Aber nachdem sie mehrere Runden gespielt haben, wird die Chance, dass Alice Bob jedes Mal täuscht, verschwindend gering. Wenn sie alles richtig macht, wird Bob schließlich davon überzeugt sein, dass Alice einen Hamilton-Zyklus in Graphen kennt G, ohne dass Bob es jemals gesehen hat.
Nach der ersten Veröffentlichung, in der solche Beweise erstmals beschrieben wurden, entdeckten Micali und zwei Mathematiker – Oded Goldreich und Avi Wigderson – eine unerwartete Konsequenz mit weitreichenden Auswirkungen. Es hat mit einer Hauptkategorie von Problemen mit ungefähr gleicher Schwierigkeit zu tun, die als NP bekannt sind. Diese Probleme sind schwer zu lösen, aber ihre Lösungen sind leicht zu überprüfen. Die drei Forscher festgestellt, dass, wenn wirklich sichere Verschlüsselung ist möglich, dann kann die Lösung jedes Problems in NP auch mit einem Zero-Knowledge-Beweis bewiesen werden. Diese Studie half Forschern begreifen Varianten von Zero-Knowledge-Beweisen, die gar keine sichere Verschlüsselung erfordern; diese sind als interaktive Multi-Prover-Beweise bekannt.
Und 1988 Micali und andere zeigte dass, wenn ein Beweiser und ein Verifizierer eine kurze Folge zufälliger Bits teilen, keine Interaktion notwendig ist. Dies bedeutete theoretisch, dass Zero-Knowledge-Beweise nicht interaktiv sein müssen, was implizieren würde, dass eine ständige Kommunikation zwischen zwei Parteien nicht erforderlich ist. Dies würde sie für Forscher viel nützlicher machen, aber erst nach der Wende zum 21. Jahrhundert wurden solche Beweise erfolgreich.
„In den späten 2000er Jahren begannen wir, die Entwicklung effizienter Techniken zum Erstellen von Zero-Knowledge-Beweisen zu sehen“, sagte er Matthew D. Grün, ein Kryptograf an der John Hopkins University. „Wir kamen an den Punkt, an dem uns klar wurde: ‚Moment mal, es könnte tatsächlich eine Möglichkeit geben, dies in der Praxis anzuwenden.'“
Jetzt konnte ein Beweiser eine einzige Nachricht an einen Prüfer senden, ohne dass beide online sein mussten, und Forscher konnten einen sehr kurzen Beweis erstellen, der selbst für sehr komplizierte Probleme schnell verifiziert werden konnte. Dies hat zu mehreren praktischen Anwendungen geführt, wie z. B. der Möglichkeit, die Blockchain nach einer Kryptowährungstransaktion schnell zu überprüfen und gleichzeitig die Details der Transaktion zu verbergen. Und 2016 eine Gruppe von Physikern zeigte wie Zero-Knowledge-Beweise bei der nuklearen Abrüstung helfen können: Ohne ein Geheimnis über das Design seines Atomsprengkopfs preiszugeben, könnte ein Land den Nuklearinspektoren nun beweisen, ob der Sprengkopf aktiv oder inaktiv ist.
In jüngerer Zeit haben Fortschritte im Quantencomputing Crépeau dazu gezwungen, frühere Forschungen einem Stresstest zu unterziehen, um sicherzustellen, dass Zero-Knowledge-Protokolle immer noch brauchbar sind. 2021 half er zeigen dass interaktive Multi-Prover-Proofs ihre Geheimhaltung behalten, selbst wenn Quantencomputer beteiligt sind, aber das Erreichen des gleichen Sicherheitsniveaus das Protokoll viel langsamer macht. Der Befund sei eine gute Nachricht, sagte er, aber mit fortschreitender Technologie würden neue Bedenken aufkommen.
„Jede Art von Berechnung, die wir in Zukunft durchführen werden, wird Quantencomputer beinhalten“, sagte Crépeau. „Als gute paranoide Kryptographen wollen wir also immer dann, wenn wir die Sicherheit eines Systems bewerten, sicherstellen, dass unser System sicher ist.“
Anmerkung der Redaktion: Shafi Goldwasser hat eine Förderung von der Simons Foundation erhalten, die dies auch finanziert redaktionell unabhängige Veröffentlichung. Förderentscheidungen der Simons Foundation haben keinen Einfluss auf unsere Berichterstattung.
