AuthentifikationAuthentifikation

ErichProtokollProtokoll

Wie kann AliceAlice zweifelsfrei ihre Identität beweisen?Durch den Nachweis eines nur ihr bekannten

GeheimnissesGeheimnisses!

Ideal: BobBob kennt das Geheimnis weder vorher noch nachher.

Erich

Zero-Knowledge ProtokolleZero-Knowledge Protokolle

Unsicherer KanalUnsicherer Kanal

Alice‘ Geheimnis:Alice‘ Geheimnis:

Zahlencode zum Öffnen der magischen Tür

Alice geht durch die linkelinke oder rechterechte Tür.

Zero-Knowledge ProtokolleZero-Knowledge Protokolle

Vorraum

Linke Linke TürTür

Rechte Rechte TürTür

Magische Magische TürTür

ProtokollProtokoll

Bob ruft: „Links!“„Links!“ oder „Rechts!“„Rechts!“

Alice kommt durch die gewünschte Tür; eventuell benutzt sie ihr Geheimnis.

Was ist Zero-Knowledge?Was ist Zero-Knowledge?

Zero-Knowledge Eigenschaft:Zero-Knowledge Eigenschaft:

Simulator MSimulator M kann (ohne das Geheimnis zu kennen) ein simuliertes Protokollsimuliertes Protokoll erstellen, das vom OriginalprotokollOriginalprotokoll nicht zu unterscheiden ist.

Das heißt:

Da Simulator MSimulator M keine Information hineinsteckt, kann ErichErich auch keine Information herausholen.

Im Beispiel der magischen Tür:• BobBob zeichnet das OriginalprotokollOriginalprotokoll auf VideoVideo auf.• Simulator MSimulator M erstellt einen identischen Videofilmidentischen Videofilm, in dem die

„schlechten“ Szenen gelöscht werden.

Alice‘ SchlüsselerzeugungAlice‘ Schlüsselerzeugung

• wählt große Primzahlen p und q

• veröffentlicht n = pq

• wählt ‚Geheimnis‘ s

• veröffentlicht v = s mod n 2

Fiat-Shamir-ProtokollFiat-Shamir-Protokoll

x

• wählt zufälliges Bit bb

• berechnet y = r s mod nby

• wählt Zufallszahl r

• berechnet x = r mod n2

• überprüft, ob

y = x v mod nb2

ProtokollProtokoll

Analyse von Fiat-ShamirAnalyse von Fiat-Shamir

Das Protokoll ist durchführbardurchführbar, denn

y = (r s ) = r s = r v = x v mod n2 b 2 2 2b 2 b b

Protokoll ist korrektkorrekt: Die BetrugswahrscheinlichkeitBetrugswahrscheinlichkeit ist

• pro Runde höchstens ½:pro Runde höchstens ½:

Erich kann nur eine der Fragen ,b=0‘ und ,b=1‘ beantworten,

da aus y = x und y = xv folgt (y / y ) = v.

Somit ist y / y eine Wurzel von v modulo n.

• pro Runde mindestens ½:pro Runde mindestens ½:

Erich rät Bit b und präpariert seine Antworten mit

x = r v mod n und y = r.

• nach t Runden genau (½) .nach t Runden genau (½) .

Bei t = 20 ist die Chance zu betrügen unter 1 zu 1 000 000.Bei t = 20 ist die Chance zu betrügen unter 1 zu 1 000 000.

tt

02 2

1 1 02

1 0

2 - b

M kennt:

• das öffentliche n = pq

• aber nicht p und qaber nicht p und q

• das öffentliche v = s mod n

• aber nicht das ‚Geheimnis‘ saber nicht das ‚Geheimnis‘ s

2

Fiat-Shamir ist Zero-KnowledgeFiat-Shamir ist Zero-Knowledge

x

• wählt zufälliges Bit bb

• ist b = c, so sei y = r y

• Überprüfung klappt

Simuliertes ProtokollSimuliertes Protokoll

SimulatoSimulatorrMM

• ist b ist b c, so wiederhole c, so wiederhole

• wählt zufälliges Bit c

• wählt Zufallszahl r

• berechnet x = r v mod n2 -c

Praxis:Praxis:• Mit dem Fiat-Shamir-Protokoll werden heute Pay-Mit dem Fiat-Shamir-Protokoll werden heute Pay-

TV-Programme decodiert.TV-Programme decodiert.• Denn Fiat-Shamir ist:Denn Fiat-Shamir ist:

• ein Public-Key-Protokoll,ein Public-Key-Protokoll,• effizienter als die meisten anderen Protokolle,effizienter als die meisten anderen Protokolle,• auf einer Chipkarte implementierbar.auf einer Chipkarte implementierbar.

Theorie:Theorie:• Interaktive Beweissysteme:Interaktive Beweissysteme: IP = PSPACE.IP = PSPACE.• Jedes Problem in Jedes Problem in NP NP ist Zero-Knowledge (unter ist Zero-Knowledge (unter

vernünftigen Annahmen).vernünftigen Annahmen).

Anwendung von Zero-KnowledgeAnwendung von Zero-Knowledge

EpilogEpilog

„Computer Science is not only about computers...

... but also about how to make TV-setsnot functioning.“

Zero-KnowledgeZero-Knowledge