Ein Zero-Knowledge-Beweis oder Zero-Knowledge-Protokoll ist ein Protokoll aus dem Bereich der Kryptografie. Bei einem Zero-Knowledge-Protokoll kommunizieren zwei Parteien (der Beweiser und der Verfizierer) miteinander. Der Beweiser überzeugt dabei den Verifizierer mit einer gewissen Wahrscheinlichkeit davon, dass er ein Geheimnis kennt, ohne dabei Informationen über das Geheimnis selbst bekannt zu geben.

Zero-Knowledge-Protokolle werden in der Kryptografie zur Identifikation eingesetzt. Ein bekanntes Verfahren ist das Fiat-Shamir-Protokoll.

Zero-Knowledge-Protokolle stellen eine Erweiterung von interaktiven Beweissystemen dar. Zu den Bedingungen Vollständigkeit und Zuverlässigkeit der interaktiven Beweissysteme tritt noch die Zero-Knowledge-Eigenschaft, die dafür sorgt, dass der Verifizierer keine Information über das Geheimnis erlangt.

Bei einem Zero-Knowledge-Protokoll soll immer gezeigt werden, dass eine Eingabe einer formalen Sprache angehört. Dazu muss ein Zero-Knowledge-Protokoll drei Bedingungen erfüllen:

Vollständigkeit

Ist die Eingabe ein Element der Sprache , dann soll der Verifizierer nach Ablauf des Protokolls immer akzeptieren.

Zuverlässigkeit

Ist die Eingabe kein Element der Sprache , dann soll der Verifizierer nach Ablauf des Protokolls ablehnen. Dabei ist jedoch eine geringe Fehlerwahrscheinlichkeit erlaubt.

Zero-Knowledge-Eigenschaft

Aus der Interaktion zwischen dem Beweiser und dem Verifizierer darf nicht mehr Wissen als die (Un-)Gültigkeit der zu beweisenden Aussage gewonnen werden.

Im 16. Jahrhundert bewies Niccolo Fontana Tartaglia im Besitz der Lösungsformel für Gleichungen dritten Grades zu sein, indem er Nullstellen von Funktionen dritten Grades berechnete. Er musste die Lösungsformel selbst nicht publizieren, da er die Nullstellen berechnen konnte und dadurch darauf geschlossen werden konnte, dass er im Besitz eines Lösungsweges sein musste.

Eine Zero-Knowledge-Authentifizierung zwischen zwei Instanzen kann mit Hilfe des Graphenisomorphieproblems stattfinden. Dazu muss von dem Beweiser zunächst einmalig ein öffentliches Schlüsselpaar erstellt werden:

• Der Beweiser erzeugt einen sehr großen Graphen .
• nummeriert mit einer zufällig und gleichförmig gewählten Permutationsfunktion um. Der resultierende Graph sei also .
• Das Paar wird veröffentlicht und ist damit nun auch dem Verifizierer bekannt. Die Permutation hält geheim.

Nun erfolgt die Authentifizierung bei dem Verifizierer durch den folgenden Ablauf:

1. Der Beweiser wählt zufällig ein . Außerdem wird der Graph durch die zufällig gewählte Permutationsfunktion umnummeriert. Der resultierende Graph sei . sendet schließlich an den Verifizierer .
2. Der Verifizierer empfängt den Graphen und wählt zufällig ein . Dann fordert er auf, ihm eine Permutation mit der Eigenschaft zu senden.
3. Nun muss zwischen drei Fällen unterschieden werden:

   

   schickt die entsprechend konstruierte Permutation an zurück.

4. empfängt das von gesendete und prüft ob wirklich gilt.

Wir betrachten nun die drei notwendigen Bedingungen für ein Zero-Knowledge Protokoll:

• Das obige Protokoll ist offensichtlich vollständig, weil gerade so konstruiert wird, dass es die geforderte Gleichung erfüllt.
• Ein unehrlicher Beweiser bzw. eine dritte Person, die sich als ausgeben möchte, kann ohne Kenntnis von den Verifizierer nur mit einer Wahrscheinlichkeit von 0.5 (durch richtiges Raten des Wertes im ersten Schritt) überzeugen. Falls das Protokoll hinreichend oft wiederholt wird und unter der Annahme, dass die Bestimmung von aus schwer ist, ist das Protokoll also stichhaltig.
• Die Kommunikation zwischen Beweiser und Verifizierer in einer Runde (Schritt 1 bis 4) ist von der Form . Erzeugt nun ein Simulator zufällig und gleichförmig und und berechnet damit den Graphen , dann ist die resultierende Wahrscheinlichkeitsverteilung identisch zu der Verteilung, welche durch die echten Protokollinstanzen impliziert wird. Folglich kann kein geheimes Wissen (hier die Permutation ) übertragen worden sein (Zero-Knowledge).

• Jean-Jacques Quisquater, Louis Guillou: How to explain zero-knowledge protocols to your children. Advances in Cryptology - CRYPTO '89, Lecture Notes in Computer Science 435, pp. 628-631, 1990.

  Kommentar: Äußerst unterhaltsame und theoriearme Einführung anhand eines mittlerweile klassischen Beispiels.

• Applied Kid Cryptography – Eine sehr anschauliche Darstellung eines Zero-Knowledge Protokolls anhand eines Spiels.
• Zero-Knowledge Tutorial – Hervorragende Einführung von Oded Goldreich (in Englisch)