Zero-Knowledge-Beweise: Es ist wie Magie, aber ich werde es erklären

Angenommen, Peggy muss Victor beweisen, dass sie im Besitz eines Geheimnisses ist, ohne das Geheimnis preiszugeben. Kann sie dies auf eine Weise tun, die Victor davon überzeugt, dass sie das Geheimnis wirklich kennt? Dies ist die Kernfrage eines der leistungsstärksten kryptografischen Verfahren, die wir in Identitätssystemen einsetzen können: Zero-Knowledge-Proofs (ZKPs) .

Angenommen, Peggy besitzt einen digitalen Führerschein und möchte Victor, dem Barkeeper, beweisen, dass sie über 21 Jahre alt ist, ohne ihm einfach ihren Führerschein auszuhändigen oder ihm ihr Geburtsdatum zu zeigen. Mit ZKPs kann Peggy nachweisen, dass ihr Führerschein besagt, dass sie mindestens 21 Jahre alt ist, und zwar auf eine Art und Weise, die Victor überzeugt, ohne dass Peggy noch etwas preisgeben muss (dh es gibt keinen Wissensüberschuss ).

Dieses Problem wurde erstmals in den 1980er Jahren von den MIT-Forschern Shafi Goldwasser, Silvio Micali und Charles Rackoff untersucht, um Informationslecks zu bekämpfen. Ziel ist es, die Menge an zusätzlichen Informationen zu reduzieren, die der Prüfer Victor über die Prüferin Peggy erfahren kann.

Eine Möglichkeit, die Funktionsweise von ZKPs zu verstehen, ist die Geschichte der Höhle von Alibaba, die erstmals von den Kryptographen Quisquater, Guillou und Berson1 veröffentlicht wurde. Das folgende Diagramm dient zur Veranschaulichung.

Die Höhle von Alibaba verfügt über zwei Gänge mit der Bezeichnung A und B, die einen einzigen Durchgang abspalten, der mit dem Eingang verbunden ist. Peggy besitzt einen Geheimcode, mit dem sie eine Tür zwischen A und B aufschließen kann. Victor möchte den Code kaufen, zahlt aber erst, wenn er sicher ist, dass Peggy ihn kennt. Peggy wird es nicht mit Victor teilen, bis er bezahlt hat.

Der Algorithmus, mit dem Peggy beweisen kann, dass sie den Code kennt, läuft wie folgt ab:

• Victor steht vor der Höhle, während Peggy hereinkommt und einen der Gänge auswählt. Victor darf nicht sehen, welchen Weg Peggy einschlägt.
• Victor betritt die Höhle und ruft nach dem Zufallsprinzip „A“ oder „B“.
• Peggy verlässt den richtigen Durchgang, weil sie die Tür problemlos aufschließen kann, unabhängig davon, welche Wahl sie beim Betreten getroffen hat.
• Natürlich hätte Peggy einfach Glück haben und richtig geraten können, also wiederholen Peggy und Victor das Experiment viele Male.

Wenn Peggy immer über den von Victor gewählten Durchgang zurückkommen kann, steigt die Wahrscheinlichkeit, dass Peggy den Code wirklich kennt. Nach 20 Versuchen liegt die Wahrscheinlichkeit, dass Peggy einfach nur errät, welchen Buchstaben Victor anrufen wird, bei weniger als einer von einer Million. Dies ist ein probabilistischer Beweis dafür, dass Peggy das Geheimnis kennt.

Dieser Algorithmus ermöglicht es Peggy nicht nur, Victor davon zu überzeugen, dass sie den Code kennt, sondern er tut dies auch auf eine Weise, die sicherstellt, dass Victor niemanden davon überzeugen kann, dass Peggy den Code kennt. Angenommen, Victor zeichnet die gesamte Transaktion auf. Das Einzige, was ein Beobachter sieht, ist, dass Victor Briefe ruft und Peggy aus dem rechten Tunnel kommt. Der Beobachter kann nicht sicher sein, dass Victor und Peggy sich nicht im Voraus auf eine Buchstabenfolge geeinigt haben, um Beobachter zu täuschen.

Während also Peggy gegenüber Victor nicht leugnen kann, dass sie das Geheimnis kennt, kann sie gegenüber anderen Dritten leugnen, dass sie das Geheimnis kennt. Dadurch wird sichergestellt, dass alles, was sie Victor beweist, zwischen ihnen bleibt und Victor es nicht preisgeben kann – zumindest nicht auf kryptografische Weise, die beweist, dass es von Peggy stammt. Peggy behält die Kontrolle über ihr Geheimnis und die Tatsache, dass sie es weiß.

Wenn wir „null Wissen“ sagen und davon sprechen, dass Victor nichts über die fragliche Aussage hinaus gelernt hat, ist das nicht ganz richtig. In der Höhle von Alibaba beweist Peggy im Null-Wissen, dass sie das Geheimnis kennt. Aber es gibt noch viele andere Dinge, die Victor über Peggy erfährt, an denen die ZKPs nichts ändern können. Victor weiß zum Beispiel, dass Peggy ihn hören kann, seine Sprache spricht, gehen kann und kooperativ ist. Möglicherweise erfährt er auch Dinge über die Höhle, etwa wie lange es ungefähr dauert, die Tür aufzuschließen. Peggy erfährt Ähnliches über Victor. Die Realität ist also, dass der Beweis ungefähr Nullwissen und nicht vollkommen Nullwissen ist.

ZKP-Systeme

Das Beispiel von Alibaba's Cave ist ein sehr spezifischer Einsatz von ZKPs, ein sogenannter Zero-Knowledge-Proof of Knowledge . Peggy beweist, dass sie etwas weiß (oder besitzt). Generell möchte Peggy Victor möglicherweise viele Fakten beweisen. Dies können Satzphrasen oder sogar Werte sein. ZKPs können das auch.

Um zu verstehen, wie wir Aussagen ohne Wissen beweisen können, betrachten wir ein anderes Beispiel, das manchmal als „Sozialistisches Millionärsproblem“ bezeichnet wird. Angenommen, Peggy und Victor möchten wissen, ob sie einen angemessenen Lohn erhalten. Konkret möchten sie wissen, ob sie den gleichen Lohn erhalten, ihren konkreten Stundensatz aber weder untereinander noch einem vertrauenswürdigen Dritten mitteilen. In diesem Fall beweist Peggy nicht, dass sie ein Geheimnis kennt, sondern sie beweist eine Behauptung der Gleichheit (oder Ungleichheit).

Nehmen Sie der Einfachheit halber an, dass Peggy und Victor einen Stundenlohn von 10, 20, 30 oder 40 US-Dollar erhalten.

Der Algorithmus funktioniert folgendermaßen:

• Peggy kauft vier Schließfächer und beschriftet sie mit 10, 20, 30 und 40 US-Dollar.
• Sie wirft die Schlüssel zu jeder Kiste weg, außer der, auf der ihr Lohn steht.
• Peggy gibt Victor alle verschlossenen Kisten, der privat einen Zettel mit einem „+“ in den Schlitz oben in der Kiste steckt, auf dem sein Gehalt steht. In alle anderen Kästchen steckt er einen Zettel mit einem „-“.
• Victor gibt Peggy die Kisten zurück, die privat ihren Schlüssel benutzt, um die Kiste mit ihrem Gehalt darauf zu öffnen.
• Wenn sie ein „+“ findet, erhalten sie den gleichen Betrag. Ansonsten machen sie einen anderen Betrag. Damit kann sie Victor die Tatsache beweisen.

Dies wird als ahnungslose Übertragung bezeichnet und beweist, dass die Aussage VictorSalary = PeggySalary im Nullwissen wahr oder falsch ist (dh ohne Offenlegung anderer Informationen).

Damit dies funktioniert, müssen Peggy und Victor darauf vertrauen, dass der andere entgegenkommend ist und ihr tatsächliches Gehalt angeben. Victor muss darauf vertrauen, dass Peggy die drei anderen Schlüssel wegwirft. Peggy muss darauf vertrauen, dass Victor nur einen Zettel mit einem „+“ in die Kisten legt.

So wie digitale Zertifikate eine PKI benötigen, um Vertrauen aufzubauen, das über das hinausgeht, was mit selbst ausgestellten Zertifikaten allein möglich wäre, sind ZKPs in einem System leistungsfähiger, das es Peggy und Victor ermöglicht, Fakten anhand von Dingen zu beweisen, die andere über sie sagen, und nicht nur anhand dessen, worüber sie sagen sich. Nehmen wir zum Beispiel an, dass Peggy und Victor ihr Gehalt nicht selbst angeben, sondern dass sie sich bei ihrer Aussage auf ein unterschriebenes Dokument der Personalabteilung verlassen könnten, sodass beide wissen, dass der andere ihr wahres Gehalt angibt. Verifiable Credentials bieten ein System zur Verwendung von ZKPs, um viele verschiedene Fakten allein oder gemeinsam zu beweisen, und zwar auf eine Weise, die Vertrauen in die Methode und Vertrauen in die Daten schafft.

Nicht interaktive ZKPs

In den vorherigen Beispielen konnte Peggy Victor durch eine Reihe von Interaktionen Dinge beweisen. Damit ZKPs praktisch sind, sollten die Interaktionen zwischen dem Prüfer und dem Prüfer minimal sein. Glücklicherweise ermöglicht eine Technik namens SNARK nicht-interaktive, wissensfreie Beweise.

SNARKs haben die folgenden Eigenschaften (daher leiten sie ihren Namen ab):

• Prägnant: Die Größe der Nachrichten ist im Vergleich zur Länge des eigentlichen Beweises gering.
• Nicht interaktiv : Abgesehen von einigen Einstellungen sendet der Prüfer nur eine Nachricht an den Prüfer.
• Argumente: Dies ist wirklich ein Argument dafür, dass etwas richtig ist, kein Beweis, wie wir ihn mathematisch verstehen. Insbesondere könnte der Beweiser theoretisch falsche Aussagen beweisen, wenn er über genügend Rechenleistung verfügt. SNARKs sind also „rechnerisch fundiert“ und nicht „perfekt fundiert“.
• des Wissens: Der Prüfer kennt die fragliche Tatsache.

Normalerweise ist auf der Vorderseite „zk“ (für Zero-Knowledge) angebracht, um anzuzeigen, dass der Prüfer während dieses Prozesses nichts anderes erfährt als die zu beweisenden Fakten.

Die Mathematik, die zkSNARKs zugrunde liegt, umfasst homomorphe Berechnungen über Polynome höheren Grades. Aber wir können verstehen, wie zkSNARKs funktionieren, ohne die zugrunde liegende Mathematik zu kennen, die sicherstellt, dass sie solide sind. Wenn Sie mehr Details zur Mathematik wünschen, empfehle ich Christian Reitwiessners „zkSNARKs in a Nutshell“ .

Als einfaches Beispiel nehmen wir an, Victor erhält einen sha256 Hash, H , von gewissem Wert. Peggy möchte beweisen, dass sie einen Wert s mit sha265(s) == H kennt, ohne Victor s preiszugeben. Wir können eine Funktion C definieren, die die Beziehung erfasst:

 C(x, w) = ( sha256(w) == x )

Also C(H, s) == true , während andere Werte für w false zurückgeben.

Für die Berechnung eines zkSNARK sind drei Funktionen G , P und V erforderlich. G ist der Schlüsselgenerator, der einen geheimen Parameter namens lambda und die Funktion C verwendet und zwei öffentliche Schlüssel generiert, den Prüfschlüssel pk und den Verifizierungsschlüssel vk . Sie müssen für eine gegebene Funktion C nur einmal generiert werden. Der Parameter lambda muss nach diesem Schritt zerstört werden, da er nicht mehr benötigt wird und jeder, der ihn hat, gefälschte Beweise generieren kann.

Die Beweisfunktion P nimmt als Eingabe den Beweisschlüssel pk , eine öffentliche Eingabe x und einen privaten (geheimen) Zeugen w . Das Ergebnis der Ausführung von P(pk,x,w) ist ein Beweis, prf , dass der Beweiser einen Wert für w kennt, der C erfüllt.

Die Prüffunktion V berechnet V(vk, x, prf) , was wahr ist, wenn der Beweis prf korrekt ist, andernfalls falsch.

Zurück zu Peggy und Victor wählt Victor eine Funktion C aus, die darstellt, was Peggy beweisen soll, erstellt eine Zufallszahl lambda und führt G aus, um die Beweis- und Verifizierungsschlüssel zu generieren:

 (pk, vk) = G(C, lambda)

Peggy darf den Wert von lambda nicht lernen. Victor teilt C , pk und vk mit Peggy.

Peggy möchte beweisen, dass sie den Wert s kennt, der C für x = H erfüllt. Sie führt die Beweisfunktion P aus und verwendet diese Werte als Eingaben:

 prf = P(pk, H, s)

Peggy präsentiert Victor den Proof prf , der die Verifizierungsfunktion ausführt:

 V(vk, H, prf)

Wenn das Ergebnis wahr ist, kann der Sieger sicher sein, dass Peggy den Wert s kennt.

Die Funktion C muss nicht auf einen Hash beschränkt sein, wie wir es in diesem Beispiel getan haben. Innerhalb der Grenzen der zugrunde liegenden Mathematik kann C recht kompliziert sein und eine beliebige Anzahl von Werten umfassen, die Peggy Victor gleichzeitig beweisen möchte.

Dieser Artikel ist ein Auszug aus meinem Buch Learning Digital Identity , veröffentlicht von O'Reilly Media.

Anmerkungen

1. Quisquater, Jean-Jacques; Guillou, Louis C.; Berson, Thomas A. (1990). So erklären Sie Ihren Kindern Zero-Knowledge-Protokolle (PDF). Fortschritte in der Kryptologie – CRYPTO '89: Proceedings. Vorlesungsskript in Informatik. 435. S. 628–631. doi:10.1007/0-387-34805-0_60. ISBN 978-0-387-97317-3.