Kryptologie: Zero-Knowledge-Beweise


Seminararbeit, 2010
17 Seiten, Note: 14

Leseprobe

Inhaltsverzeichnis

1 Die „magische” Tür
1.1 Aufbau des Beweises
1.2 Effektivität des Beweises

2 Allgemeine Definition
2.1 Interaktive Beweise
2.2 Kriterien von Zero-Knowledge-Beweisen
2.2.1 Vollständigkeit
2.2.2 Zuverlässigkeit
2.2.3 Zero-Knowledge-Eigenschaft

3 Historischer Hintergrund
3.1 Läsungsformel fär Gleichungen dritten Grades
3.2 Gültigkeit des Beweises

4 Graphenisomorphie
4.1 Was ist ein Graph?
4.2 Was bedeutet Isomorphie?
4.3 Zero-Knowledge-Protokoll
4.4 Gältigkeit des Beweises

5 Schlussbetrachtung

Literaturverzeichnis

Kapitel 1 Die „magische” Tür

„Null-Wissen-Beweise” - so lautet die deutsche Übersetzung des Titels dieser Semi­nararbeit. Was verbirgt sich nun aber hinter diesem sonderbaren Begriff? Manch einer könnte vermuten, es handle sich dabei um ein Verfahren, welches beweist, dass eine Person öber „null Wissen” verfögt (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

Üm das wahre Wesen von Zero-Knowledge-Beweisen zu erfassen, lohnt es sich, einen detaillierten Blick auf das recht anschauliche Beispiel der „magischen” Tör zu wer­fen. Dieses in der Literatur sehr zahlreich beschriebene Beispiel soll im Folgenden in einer eigenen Version vorgeföhrt werden.1 2 3 Hierför stellen wir uns eine in Ab­bildung 1.1 dargestellte Höhle 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ör, die nur mithilfe einer geheimen Zauberformel passiert werden kann.

Vor dieser Hoöhle stehen nun die zwei Personen Vera und Bert, wobei Bert seine Freundin Vera öberzeugen will, dass er die besagte Zauberformel tatsächlich kennt. Nun koönnte Bert einfach die Zauberformel aufsagen und beide koönnten nachsehen, ob sich die magische Tör öffnet. Dem steht allerdings entgegen, dass Bert ein sehr argwönischer Mensch ist, der niemandem vertraut und deshalb auch die Zauber­formel nicht verraten will.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 1.1: Die Hohle (mit Gang und magischer Tür)

Gibt es nun aber dennoch eine Möglichkeit, Vera zu überzeugen, dass Bert tatsächlich Kenntnis von jener hat? Um dies zu erreichen, begibt sich Bert zunöchst ins Innere der Höhle und betritt anschließend - unbeobachtet von Vera - den Gang von einer der beiden Seiten aus - nehmen wir einmal an, von der rechten. Im nächs­ten Schritt betritt auch Vera, die Berts Wahl nicht kennt, die Höhle. Sie entscheidet sich ebenfalls fur eine der beiden Seiten, aus der Bert den Gang wieder verlassen soll.

Es waren nun folgende zwei Szenarien denkbar:

- In Szenario 1 entscheidet sich Vera fur dieselbe Seite, von welcher aus Bert den Gang bereits betreten hat (also in unserem Beispiel fär die rechte). In diesem Fall könnte sich Bert glucklich schatzen, da er die Zauberformel gar nicht kennen muss, um Veras Forderung nachzukommen.
- Im zweiten Szenario hingegen wöhlt Vera die linke Seite aus. In diesem Fall muss Bert tatsöchlich die Zauberformel wissen, um die magische Tur passieren und somit auf der richtigen Seite wieder in die Höhle treten zu können.

1.2 Effektivität 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 wirk­lich Kenntnis von jener Zauberformel hat. Es ist daher einleuchtend, dass sich die skeptische Vera hiervon wohl kaum uberzeugen lösst. Der raffinierte Bert hingegen sieht eine einfache Möglichkeit, diese Wahrscheinlichkeit rapide zu erhöhen - namlich im wiederholten Durchführen dieses Experiments. Angenommen, es gelönge Bert ein zweites Mal, auf der richtigen von Vera geforderten Seite wieder aus dem Gang heraus in die Hohle zu treten, so betrüge jene Wahrscheinlichkeit bereits 75 Prozent (also mehr als die Halfte).

Denn hinter diesem Zusammenhang verbirgt sich folgende mathematische Funk­tion für die Wahrscheinlichkeit P, dass Bert die Zauberformel tatsachlich kennt, in Abhüngigkeit von der Anzahl n der Durchführungen dieses Versuchs:

Abbildung in dieser Leseprobe nicht enthalten

Hier wird also von 1 (= 100 %) die Wahrscheinlichkeit des Gegenereignisses - nümlich dass Bert nur Glück hatte und die geheime Zauberformel gar nicht wirklich kennt - abgezogen. 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ührungen immer weiter zu. Diese Relation lüsst sich ebenfalls am zugehürigen Funktionsgraphen, der eigentlich nur aus einzelnen (endlichen) Punkten besteht, hier aber durchgehend dargestellt ist, erkennen:

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 1.2: Wahrscheinlichkeit fur Berts Kenntnis der Zauberformel

Hier zeigt sich deutlich, dass sich der Graph immer mehr der Gerade P = 1 annähert, es gilt:

Abbildung in dieser Leseprobe nicht enthalten

Zur Verdeutlichung dieses Zusammenhangs nehmen wir beispielhaft fünf Durchführun­gen dieses Versuchs an, wir waühlen also n = 5:

Abbildung in dieser Leseprobe nicht enthalten

Wie wir sehen, betrügt 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 überzeugen dürfte.

[...]


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

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

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

Ende der Leseprobe aus 17 Seiten

Details

Titel
Kryptologie: Zero-Knowledge-Beweise
Hochschule
Das Rupert-Ness-Gymnasium, Ottobeuren
Note
14
Autor
Jahr
2010
Seiten
17
Katalognummer
V179604
ISBN (eBook)
9783656019954
ISBN (Buch)
9783656021827
Dateigröße
672 KB
Sprache
Deutsch
Reihe
Aus der Reihe: e-fellows.net stipendiaten-wissen
Schlagworte
kryptologie, zero-knowledge-beweise
Arbeit zitieren
Philipp Brader (Autor), 2010, Kryptologie: Zero-Knowledge-Beweise, München, GRIN Verlag, https://www.grin.com/document/179604

Kommentare

  • Noch keine Kommentare.
Im eBook lesen
Titel: Kryptologie: Zero-Knowledge-Beweise


Ihre Arbeit hochladen

Ihre Hausarbeit / Abschlussarbeit:

- Publikation als eBook und Buch
- Hohes Honorar auf die Verkäufe
- Für Sie komplett kostenlos – mit ISBN
- Es dauert nur 5 Minuten
- Jede Arbeit findet Leser

Kostenlos Autor werden