(Beweise ohne Wissenspreisgabe - Verallgemeinerung des Prinzips der digitalen Signatur)

Idee

Erfinder: Goldwasser, Micali & Rackoff 1985.

Prinzip: A hat ein Geheimnis und kann B davon überzeugen, dass sie es hat, ohne das Geheimnis preiszugeben (auch nicht teilweise).

Beispiel (historisch): Tartaglia (»Formel von Cardano«).

• Tartaglia bewies den Besitz der Lösungsformel, indem er beliebige, ihm vorgelegte kubische Gleichungen löste und die Lösung bekannt gab.

Hauptanwendung: Identifikation und Zugangskontrolle, implementiert mit Hilfe von Chipkarten. (Elektronischer Ausweis, starke Authentisierung.)

Anforderungen:

• Vollständigkeit - Jeder echte Besitz des Geheimnisses wird als echt erkannt.
• Korrektheit - Jeder vorgetäuschte Besitz des Geheimnisses wird als Täuschungsversuch erkannt.
• Keine Wissenspreisgabe - Der Kontrolleur (Verifizierer) erwirbt keinerlei Wissen über das Geheimnis. (Z. B. kann er einen Ausweis nicht kopieren oder nachmachen.) [Diese Anforderung lässt sich beweisfähig formalisieren.]

Zero-Knowledge-Protokolle - Ablauf

a) Initialisierungsphase

Vertrauenswürdige Zentrale C vergibt an Teilnehmer:

• Identitätsbezeichner (öffentlich sichtbar),
• zugehöriges Geheimnis.

b) Anwendungsphase

Ein Prüfer B prüft die Teilnehmerin A;

• er stellt fest, ob A das zu ihrem Identitätsbezeichner gehörige Geheimnis kennt,
• ohne das geringste über es zu erfahren.

Das Fiat/Shamir-Identifikationsschema

a) Initialisierung

Die Zentrale C besitzt

• eine Blum-Zahl n, die öffentlich bekannt ist,
• die Primzerlegung n = pq als großes Zentralgeheimnis.

Die Zentrale erzeugt für die Teilnehmerin A

• eine Identifikationsnummer I_A (große ganze Zahl),
• als zugehöriges Geheimnis die Quadratwurzel s (mod n) aus I_A.

b) Anwendung

• A wählt Zufallszahl r, bildet x = r² mod n, sendet x an B.
• B wählt zufälliges Bit b, sendet b an A.
• Falls b = 0, wählt A die Zahl y = r; falls b = 1, wählt A die Zahl y = rs mod n. A sendet y an B.
• Falls b = 0, prüft B, ob x = y² mod n; falls b = 1, prüft B, ob x = y²I_A mod n.

c) Eigenschaften

Vollständigkeit: Falls A das Geheimnis s kennt, kann sie immer korrekt antworten.

Korrektheit: Falls A in Wirklichkeit à ist, also das Geheimnis s nicht kennt, kann sie höchstens eine der beiden Fragen richtig beantworten. [Sonst könnte sie die Quadratwurzel aus I_A ziehen: s = y₀/y₁ mod n.] à kann also die zufällige Frage (abhängig von b) nur mit Wahrscheinlichkeit höchstens gleich 1/2 richtig beantworten. Nach t Runden des Protokolls hat à also nur eine Erfolgswahrscheinlichkeit von höchstens 1/2^t.

Bemerkung: Falls B immer b = 1 wählt, sendet à stets x' = x/I_A statt x und stets y = r. Die Prüfung ergibt dann stets y² [= r² = x] = x'I_A.