Inhaltsverzeichnis

1  Die magische T ur  3

1.1  Aufbau des Beweises  3

1.2  Effektivit at des Beweises  4

2  Allgemeine Definition  6

2.1  Interaktive Beweise  6

2.2  Kriterien von Zero-Knowledge-Beweisen  6

2.2.1  Vollst andigkeit  6

2.2.2  Zuverl assigkeit  7

2.2.3  Zero-Knowledge-Eigenschaft  7

3  Historischer Hintergrund  9

3.1  L osungsformel f ur Gleichungen dritten Grades  9

3.2  G ultigkeit des Beweises  10

4  Graphenisomorphie  11

4.1  Was ist ein Graph?  11

4.2  Was bedeutet Isomorphie?  12

4.3  Zero-Knowledge-Protokoll  13

4.4  G ultigkeit des Beweises  15

5  Schlussbetrachtung  16

Literaturverzeichnis   17

Kapitel 1

Die ” magische” T ¨ ur

Null-Wissen-Beweise” - so lautet die deutsche ¨ Ubersetzung des Titels dieser Semi-”

nararbeit. Was verbirgt sich nun aber hinter diesem sonderbaren Begriff? Manch einer k¨ onnte vermuten, es handle sich dabei um ein Verfahren, welches beweist, dass eine Person ¨ uber ” null Wissen” verf¨ ugt (also eine Art ” Idiotentest”). Allerdings sei

bereits an dieser Stelle gesagt, dass eine solche Vermutung reinen Gewissens wieder verworfen werden kann.

1.1 Aufbau des Beweises

Um das wahre Wesen von Zero-Knowledge-Beweisen zu erfassen, lohnt es sich, einen detaillierten Blick auf das recht anschauliche Beispiel der ” magischen” T¨ ur zu werfen. Dieses in der Literatur sehr zahlreich beschriebene Beispiel soll im Folgenden in einer eigenen Version vorgef¨ uhrt werden. ^1,2,3 Hierf¨ ur stellen wir uns eine in Abbildung 1.1 dargestellte H¨ ohle mit einem Eingang sowie einem Gang, der von zwei Seiten aus betreten werden kann, vor. In der Mitte dieses Ganges befindet sich eine magische” T¨ ur, die nur mithilfe einer geheimen Zauberformel passiert werden kann.

”

Vor dieser H¨ ohle stehen nun die zwei Personen Vera und Bert, wobei Bert seine Freundin Vera ¨ uberzeugen will, dass er die besagte Zauberformel tats¨ achlich kennt. Nun k¨ onnte Bert einfach die Zauberformel aufsagen und beide k¨ onnten nachsehen, ob sich die magische T¨ ur ¨ offnet. Dem steht allerdings entgegen, dass Bert ein sehr argw¨ onischer Mensch ist, der niemandem vertraut und deshalb auch die Zauber-formel nicht verraten will.

¹ Vgl. Arnold, Zero-Knowledge-Verfahren, 2005, S. 6 - 7

² Vgl. Beutelspacher u.a., Verfahren der Kryptographie, 2010, S. 44 - 46

³ Vgl. o. V., Zero Knowledge, 2010, S. 2

3

Gibt es nun aber dennoch eine M¨ oglichkeit, Vera zu ¨ uberzeugen, dass Bert

tats¨ achlich Kenntnis von jener hat? Um dies zu erreichen, begibt sich Bert zun¨ achst ins Innere der H¨ ohle und betritt anschließend - unbeobachtet von Vera - den Gang von einer der beiden Seiten aus - nehmen wir einmal an, von der rechten. Im n¨ achsten Schritt betritt auch Vera, die Berts Wahl nicht kennt, die H¨ ohle. Sie entscheidet sich ebenfalls f¨ ur eine der beiden Seiten, aus der Bert den Gang wieder verlassen soll.

Es w¨ aren nun folgende zwei Szenarien denkbar:

• In Szenario 1 entscheidet sich Vera f¨ ur dieselbe Seite, von welcher aus Bert den Gang bereits betreten hat (also in unserem Beispiel f¨ ur die rechte). In diesem Fall k¨ onnte sich Bert gl¨ ucklich sch¨ atzen, da er die Zauberformel gar nicht kennen muss, um Veras Forderung nachzukommen.

• Im zweiten Szenario hingegen w¨ ahlt Vera die linke Seite aus. In diesem Fall muss Bert tats¨ achlich die Zauberformel wissen, um die magische T¨ ur passieren und somit auf der richtigen Seite wieder in die H¨ ohle treten zu k¨ onnen.

1.2 Effektivit¨ at des Beweises

Betrachtet man dieses Beweissystem genauer, so erscheint es als nicht befriedigend, da nur mit einer Wahrscheinlichkeit von 50 Prozent bewiesen wurde, dass Bert wirklich Kenntnis von jener Zauberformel hat. Es ist daher einleuchtend, dass sich die skeptische Vera hiervon wohl kaum ¨ uberzeugen l¨ asst. Der raffinierte Bert hingegen

sieht eine einfache M¨ oglichkeit, diese Wahrscheinlichkeit rapide zu erh¨ ohen - n¨ amlich im wiederholten Durchf¨ uhren dieses Experiments. Angenommen, es gel¨ ange Bert

4

ein zweites Mal, auf der richtigen von Vera geforderten Seite wieder aus dem Gang heraus in die H¨ ohle zu treten, so betr¨ uge jene Wahrscheinlichkeit bereits 75 Prozent (also mehr als die H¨ alfte).

Denn hinter diesem Zusammenhang verbirgt sich folgende mathematische Funktion f¨ ur die Wahrscheinlichkeit P, dass Bert die Zauberformel tats¨ achlich kennt, in Abh¨ angigkeit von der Anzahl n der Durchf¨ uhrungen dieses Versuchs:

P (n) = 1 − (2) ⁻ⁿ (1.1)

Hier wird also von 1 (= 100 %) die Wahrscheinlichkeit des Gegenereignisses - n¨ amlich dass Bert nur Gl¨ uck hatte und die geheime Zauberformel gar nicht wirklich kenntabgezogen. Da diese Wahrscheinlichkeit, die in der obigen Gleichung als Subtrahend auftritt, aber mit steigendem n immer kleiner wird und der Minuend konstant bleibt, nimmt der Wert der Differenz mit steigender Anzahl an Durchf¨ uhrungen immer weiter zu. Diese Relation l¨ asst sich ebenfalls am zugeh¨ origen Funktionsgraphen, der eigentlich nur aus einzelnen (endlichen) Punkten besteht, hier aber durchgehend dargestellt ist, erkennen:

Abbildung 1.2: Wahrscheinlichkeit f¨ ur Berts Kenntnis der Zauberformel

Hier zeigt sich deutlich, dass sich der Graph immer mehr der Gerade P = 1 ann¨ ahert, es gilt: lim P (n) = 1 (1.2)

n→∞

Zur Verdeutlichung dieses Zusammenhangs nehmen wir beispielhaft f¨ unf Durchf¨ uhrungen dieses Versuchs an, wir w¨ ahlen also n = 5:

Wie wir sehen, betr¨ agt die Wahrscheinlichkeit, dass Berts Behauptung, er kenne die geheime Zauberformel, wahr ist, nach vier Wiederholungen bereits nahezu 97 Prozent - ein Wert, der auch die skeptische Vera ¨ uberzeugen d¨ urfte.

5