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