Zero-Knowledge < Krypt.+Kod.+Compalg. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 12:39 So 30.04.2006 | | Autor: | sibl |
hallo.
bin grade dabei eine präsentation über das zero-knowledge verfahren zu verfassen. habe dazu das buch vom beutelspacher (moderne verfahren der kryptographie) was ich als sehr gut empfinde. nur bin ich im moment etwas verwirrt. im buch wird von folgenden anforderungen/eigenschaften an ein zero-knowledge-proof gestellt, nämlich:
1)Durchfürhbarkeit (Prover konnte Fragen beantworten u Verifier kontrollieren)
2)Korrektheit (ohne Lösungsformel ist nur raten möglich, daher geratene Antworten nicht korrekt und abzulehnen)
3)Zero-Knowledge-Eigenschaft (das Geheimnis wurde nicht preisgegeben)
nun habe ich haber auf verschieden web sites auch noch die folgenden beiden gefunden, nämlich:
Completness
Soundness
sind diese beiden äquivalent zu den beiden oben genannten? also zB
Completness = Durchführbarkeit
Soundness = Korrektheit
????
oder sind das unterschiedliche sachen gemeint?
Wär echt super wenn mir da jemand den Knoten in meinem Hirn öffnen könnte :)
Lg
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Hallo und guten Morgen,
die Begriffe Completeness und Soundness werden allgemein für interaktive Beweissysteme verwandt,
also zB für die Klasse IP (welche ja identisch mit PSPACE ist):
Completeness: Für jedes x in der Sprache akzeptiert der Verifier (am Ende des Ablaufes des Protocols bei Eingabe x).
Soundness: Es gibt ein Polynom p(n), so dass für jedes x nicht in der Sprache und jeden (ressourcenunbeschr.) Prover [mm] P^{\star}
[/mm]
der Verifier mit Wahrscheinlichkeit höchstens [mm] 1\slash [/mm] p(|x|) akzeptiert.
Wenn ich die Dinge recht zusammenlege, ist dann Zero Knowledge eine mögliche Zusatzeigenschaft eines solchen interaktiven Beweissystems,
nämlich eine zusätzliche Eigenschaft des Provers: Grob gesagt nämlich, dass für jeden polytime probabilistic verifier es eine probabilistische polyzeit Maschine gibt, so
dass deren Ausgabe (ohne Interaktivität mit dem Prover) von der Ausgabe des Verifiers (bei Interaktivität mit Prover) ''computationally indistinguishable'' ist.
Insofern ein vorsichtiges '' JA ''.
Gruss,
Mathias
|
|
|
|
