Der Fiat-Shamir-Algorithmus

Ein Zero-Knowledge Protokoll


Seminararbeit, 2010

16 Seiten, Note: 0,7


Leseprobe

Inhaltsverzeichnis

1. Einleitung

2. Interaktive Zero-Knowledge Beweise
2.1 Interaktive Beweissysteme
2.2 Zero-Knowledge Beweise

3. Die Magische Tür

4. Der Fiat-Shamir Algorithmus
4.1 Schlüsselerzeugung
4.2 Anwendungsphase
4.3 Rechenbeispiel

5. Man in the middle – Problem

6. Anwendungsmöglichkeiten

7. Anhang
7.1 Verwendete Variablen
7.2 Abbildungsverzeichnis
7.3 Literaturverzeichnis

1. Einleitung

In nahezu allen Bereichen des menschlichen Lebens gibt es immer wieder problematische Situationen, die durch reine Überzeugungskraft nicht gelöst werden können. Besonders wenn diese im Zusammenhang mit geheimen Informationen auftreten, gewinnen alternative Vorge­hensweisen an Bedeutung. Ein derartiges Problem kann zum Beispiel das Bewahren eines Geheimnisses unter folgender Fragestellung darstellen:

„Wie beweise ich, dass ich ein Geheimnis besitze, ohne Informationen über das Geheimnis selbst preiszugeben?“

Hierbei handelt es sich auch um die zu Grunde liegende Thematik, mit der sich Zero-Knowledge-Beweise auseinandersetzen.

Ein passendes Beispiel, das auch in die Geschichte der Mathematik Einzug fand, betrifft Niccolò Tartaglia, der ca. von 1500 bis 1557 lebte. Er entdeckte in einem Wettstreit mit sei­nen Fachkollegen eine Lösungsformel zur Berechnung von Gleichungen dritten Grades (Abbildung in dieser Leseprobe nicht enthalten), die er aber zunächst als Druckmittel im beruflichen Konkurrenzkampf für sich behielt. Da er seine Entdeckung dennoch beweisen musste, legte man ihm 30 derartige Gleichungen zur Berechnung vor. Da seine Formel wirklich funktionierte, stellten ihn jene Aufgaben natürlich vor keine weiteren Probleme und immer wenn er die einzelnen Lösungen für eine Gleichung veröffentlichte konnte jeder mit einer simplen Probe überprüfen, ob die Ergebnisse stimmten.

Allerdings waren sie außerstande nur mit den Ergebnissen seinen Rechenweg zu rekon-struieren. Außerdem führte er seine Rechnungen alleine, ohne weitere Beobachter durch, worauf­hin seine Formel vorerst nicht nachvollziehbar blieb. Dieser Umstand änderte sich erst, als der erfolgreiche Wissenschaftler Geronimo Cardano dem mittellosen Tartaglia anbot, ihm sein Geheimnis abzukaufen. Tartaglia willigte unter der Bedingung ein, dass jener ebenfalls das Geheimnis für sich behielte. In seinem nächsten Buch „Ars magna“ veröffentlichte Cardano allerdings dennoch sein neues Wissen und obwohl er erwähnte, woher er die Formel ursprünglich erworben hatte, wird Tartaglias Rechenweg heute immer noch als Cardanosche Formel bezeichnet.[1]

2. Interaktive Zero-Knowledge Beweise

2.1 Interaktive Beweissysteme

Zur Erläuterung eines Zero-Knowledge Beweises ist es zunächst notwendig, die Eigenschaf­ten eines interaktiven Beweises zu klären. In unserem Fall handelt es sich um einen Dialog, bei dem ein beweisender Teilnehmer P (Prover) einen unwissenden Teilnehmer V (Verifier) von der Richtigkeit einer Behauptung überzeugen will. Allgemein beinhaltet ein mathema­tischer Beweis eine Argumentationskette, die logisch und vollständig eine Aussage herleitet. Dies könnte nun implizieren, dass P eine Argumentationskette bildet, aus der am Ende seine Behauptung hervorgeht. Hierbei erfährt V allerdings deutlich mehr als notwendig ist und kommt letztlich nicht nur zu der Überzeugung, dass ein Geheimnis existiert, sondern er könnte sogar selber die Beweisführung nachvollziehen. Er kann sogar jederzeit zu Unrecht den Besitz des Geheimnisses für sich beanspruchen. Entlässt man V aus seiner passiven Rolle und führt eine echte Interaktivität ein, ist es aber möglich Beweise zu konstruieren, die auf keine weiteren Informationen des Geheimnisses außer seiner Existenz selbst schließen las­sen.[2]

Der Aufbau[3] eines interaktiven Beweissystemes besteht grundsätzlich aus zwei Berechnungs­schritten, dem Produzieren eines Beweises durch P und dem Überprüfen der Korrektheit durch V, und einem aus folgenden Schritten bestehenden Dialog:

1. Empfangen einer Nachricht
2. Notwendige Rechnung/Aufgabe durchführen
3. Zurücksenden der Ergebnisse

Der Dialog wird gewöhnlich durch P begonnen, während V ihn beendet. Die einzelnen Schritte werden mehrere Male wiederholt. Der Verifier akzeptiert hierbei nur, wenn P alle Fragen richtig beantwortet.

Besonders wichtig, auch in Hinblick auf die interaktiven Zero-Knowledge Beweise, sind fol­gende Eigenschaften eines interaktiven Beweises:

Durchführbarkeit

Wenn die Behauptung richtig ist, d.h. wenn P ein Geheimnis und einen entsprechenden Beweis kennt, kann der Prover den Verifier immer von der Richtigkeit der Behauptung überzeugen.

Nur dann wird die Behauptung verifiziert.

Korrektheit

Ist die Behauptung allerdings nicht richtig oder kennt P keinen Beweis, so darf V nur mit sehr geringer Wahrscheinlichkeit überzeugt werden.

Die Wahrscheinlichkeit ist in unseren Fällen von der Anzahl der Durchläufe t abhängig.[4]

2.2 Zero-Knowledge Beweise

Sind Durchführbarkeit und Korrektheit gegeben, bedeutet das noch nicht, dass das Geheimnis durch die Interaktion nicht ausgekundschaftet werden kann. Das ist allerdings eine Grund­voraussetzung für einen interaktiven Zero-Knowledge Beweis. Folglich ist es notwendig, eine weitere Eigenschaft zu definieren:

Zero-Knowledge Eigenschaft

Formal: „Es gibt einen Simulator, der ohne Kenntnis des Beweises mit mehreren Versuchen einen interaktiven Beweis erstellen kann, der für den Außenstehenden nicht von einem echten interaktiven Be­weis zu unterscheiden ist.“

Einfacher gesagt bedeutet diese Aussage, dass der Verifier keine weiteren Informationen er­langt, die er vor dem Ausführen des Beweises noch nicht hatte, außer der Überzeugung, dass die Behauptung des Provers richtig ist.[5]

[...]


[1] [Beu07] S.79

[2] [BNS05] S.195

[3] [Kuz05]

[4] [Cle05]

[5] [BNS05] S.196

Ende der Leseprobe aus 16 Seiten

Details

Titel
Der Fiat-Shamir-Algorithmus
Untertitel
Ein Zero-Knowledge Protokoll
Veranstaltung
Wissenschaftspropädeutisches Seminar
Note
0,7
Autor
Jahr
2010
Seiten
16
Katalognummer
V269526
ISBN (eBook)
9783656606734
ISBN (Buch)
9783656606710
Dateigröße
1020 KB
Sprache
Deutsch
Schlagworte
Kryptologie, fiat-shamir, zero knowledge, man-in-the-middle, Interaktive Beweissysteme, Magische Tür, Schlüsselerzeugung
Arbeit zitieren
Maximilian Eckel (Autor), 2010, Der Fiat-Shamir-Algorithmus, München, GRIN Verlag, https://www.grin.com/document/269526

Kommentare

  • Noch keine Kommentare.
Im eBook lesen
Titel: Der Fiat-Shamir-Algorithmus



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