www.wikidata.de-de.nina.az

Fiat Shamir Heuristik Die ist eine kryptographische Technik mit deren Hilfe man aus einem interaktiven Beweis eine Digit

Fiat-Shamir-Heuristik

Die Fiat-Shamir-Heuristik ist eine kryptographische Technik, mit deren Hilfe man aus einem interaktiven Beweis eine Digitale Signatur erzeugen kann. Auf diese Weise kann eine bestimmte Tatsache (zum Beispiel das Wissen über eine bestimmte Zahl) bewiesen werden, ohne dass die zugrundeliegende Information erkennbar wird. Diese Technik wurde 1986 von Amos Fiat und Adi Shamir entwickelt. Der ursprüngliche interaktive Beweis muss die Öffentliche-Münze-Eigenschaft haben, damit die Methode greift. Für den unten angegebenen Algorithmus sollte der Leser mit modularer Arithmetik vertraut sein, besonders mit jener in den so genannten P-Gruppen.

Die Heuristik wurde ursprünglich ohne Sicherheitsbeweis präsentiert, später zeigten Pointcheval und Stern ihre Sicherheit gegenüber dem Chosen-Plaintext-Angriff im Zufallsorakel-Modell, das bedeutet, unter der Annahme, dass solche Zufallsorakel existieren. Für den Fall, dass diese nicht existieren, wurde die Fiat-Shamir-Heuristik durch Goldwasser und Kalai als unsicher bewiesen. Wenn der unten berechnete Hashwert nicht vom (öffentlichen) Wert von abhängt, wird die Sicherheit des Algorithmus kompromittiert, da ein böswilliger Beweiser den Wert in einem gewissen Rahmen festlegen könnte.

Allgemein kann man die Fiat-Shamir-Heuristik als einen Weg betrachten, einen interaktiven Beweis mit öffentlichen Münzen in einen nicht-interaktiven null-Wissen-Beweis umzuwandeln. Wenn der interaktive Beweis ein Identifikationsprotokoll ist, kann die nicht-interaktive Version als digitale Signatur verwendet werden.

Beispiel Bearbeiten

Dies ist ein interaktiver Beweis des Wissens eines diskreten Logarithmus.

  1. Alice will Bob beweisen, dass sie kennt, den diskreten Logarithmus von zur Basis .
  2. Sie wählt ein , berechnet und schickt an Bob.
  3. Bob wählt ein zufälliges und schickt es an Alice.
  4. Alice berechnet und schickt an Bob.
  5. Bob überprüft, ob (diese Aussage ist wahr, da ).

Die Fiat-Shamir-Heuristik besteht daraus, Schritt 3 durch einen nicht-interaktiven Zugriff auf ein Zufallsorakel zu ersetzen. In der Praxis wird stattdessen eine kryptographische Hash-Funktion verwendet.

  1. Alice will Bob beweisen, dass sie kennt, den diskreten Logarithmus von zur Basis .
  2. Sie wählt ein und berechnet .
  3. Alice berechnet , mit einer kryptographischen Hashfunktion .
  4. Sie berechnet . Der Beweis ist das Paar . Da ein Exponent von ist, ist der Modulus .
  5. Jeder kann überprüfen, ob .

Siehe auch Bearbeiten

Einzelnachweise Bearbeiten

  1. Amos Fiat, Adi Shamir: How To Prove Yourself: Practical Solutions to Identification and Signature Problems. In: Andrew M. Odlyzko (Hrsg.): Advances in Cryptology – CRYPTO’ 86 (= Lecture notes in computer science. Band 263). Springer, Berlin / Heidelberg 1987, ISBN 3-540-18047-8, S. 186–194.
  2. David Pointcheval, Jacques Stern: Security Proofs for Signature Schemes. In: Ueli Maurer (Hrsg.): Advances in Cryptology – EUROCRYPT ’96. Springer, Berlin / Heidelberg 1996, ISBN 3-540-61186-X, S. 387–398.
  3. S. Goldwasser, Y.T. Kalai: On the (In)security of the Fiat-Shamir paradigm. In: Proceedings 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. 2003, S. 102–113, doi:10.1109/SFCS.2003.1238185.
  4. David Bernhard, Olivier Pereira, Bogdan Warinschi: Advances in Cryptology – ASIACRYPT 2012. Hrsg.: Xiaoyun Wang, Kazue Sako. How not to Prove Yourself: Pitfalls of the Fiat-Shamir Heuristic and Applications to Helios, S. 626–643 (uclouvain.be [PDF]).
  5. Jan Camenisch, Markus Stadler: Proof Systems for General Statements about Discrete Logarithms. In: Technical Report (Dept. of Computer Science, ETH Zurich). Nr. 260, 1997 (@1@2Vorlage:Toter Link/ftp.inf.ethz.chFehler (Seite nicht mehr abrufbar. Suche in Webarchiven)).
  6. Mihir Bellare, Phillip Rogaway: Random Oracles Are Practical: A Paradigm for Designing Efficient Protocols. In: Proceedings of the 1st ACM Conference on Computer and Communications Security. ACM, New York, NY, USA 1993, ISBN 0-89791-629-8, S. 62–73, doi:10.1145/168588.168596.
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Die Fiat Shamir Heuristik ist eine kryptographische Technik mit deren Hilfe man aus einem interaktiven Beweis eine Digitale Signatur erzeugen kann Auf diese Weise kann eine bestimmte Tatsache zum Beispiel das Wissen uber eine bestimmte Zahl bewiesen werden ohne dass die zugrundeliegende Information erkennbar wird Diese Technik wurde 1986 von Amos Fiat und Adi Shamir entwickelt 1 Der ursprungliche interaktive Beweis muss die Offentliche Munze Eigenschaft haben damit die Methode greift Fur den unten angegebenen Algorithmus sollte der Leser mit modularer Arithmetik vertraut sein besonders mit jener in den so genannten P Gruppen Die Heuristik wurde ursprunglich ohne Sicherheitsbeweis prasentiert spater zeigten Pointcheval und Stern 2 ihre Sicherheit gegenuber dem Chosen Plaintext Angriff im Zufallsorakel Modell das bedeutet unter der Annahme dass solche Zufallsorakel existieren Fur den Fall dass diese nicht existieren wurde die Fiat Shamir Heuristik durch Goldwasser und Kalai als unsicher bewiesen 3 Wenn der unten berechnete Hashwert nicht vom offentlichen Wert von y displaystyle y abhangt wird die Sicherheit des Algorithmus kompromittiert da ein boswilliger Beweiser den Wert c displaystyle c in einem gewissen Rahmen festlegen konnte 4 Allgemein kann man die Fiat Shamir Heuristik als einen Weg betrachten einen interaktiven Beweis mit offentlichen Munzen in einen nicht interaktiven null Wissen Beweis umzuwandeln Wenn der interaktive Beweis ein Identifikationsprotokoll ist kann die nicht interaktive Version als digitale Signatur verwendet werden Beispiel BearbeitenDies ist ein interaktiver Beweis des Wissens eines diskreten Logarithmus 5 Alice will Bob beweisen dass sie x displaystyle x nbsp kennt den diskreten Logarithmus von y gx displaystyle y g x nbsp zur Basis g displaystyle g nbsp Sie wahlt ein v Zq displaystyle v in mathbb Z q nbsp berechnet t gv displaystyle t g v nbsp und schickt t displaystyle t nbsp an Bob Bob wahlt ein zufalliges c Zq displaystyle c in mathbb Z q nbsp und schickt es an Alice Alice berechnet r v cx displaystyle r v cx nbsp und schickt r displaystyle r nbsp an Bob Bob uberpruft ob t gryc displaystyle t equiv g r y c nbsp diese Aussage ist wahr da gryc gv cxgxc gv t displaystyle g r y c g v cx g xc g v t nbsp Die Fiat Shamir Heuristik besteht daraus Schritt 3 durch einen nicht interaktiven Zugriff auf ein Zufallsorakel zu ersetzen In der Praxis wird stattdessen eine kryptographische Hash Funktion verwendet 6 Alice will Bob beweisen dass sie x displaystyle x nbsp kennt den diskreten Logarithmus von y gx displaystyle y g x nbsp zur Basis g displaystyle g nbsp Sie wahlt ein v Zq displaystyle v in mathbb Z q nbsp und berechnet t gv displaystyle t g v nbsp Alice berechnet c H g y t displaystyle c H g y t nbsp mit einer kryptographischen Hashfunktion H displaystyle H nbsp Sie berechnet r v cx displaystyle r v cx nbsp Der Beweis ist das Paar t r displaystyle t r nbsp Da r displaystyle r nbsp ein Exponent von g displaystyle g nbsp ist ist der Modulus q 1 displaystyle q 1 nbsp Jeder kann uberprufen ob t gryc displaystyle t equiv g r y c nbsp Siehe auch BearbeitenZufallsorakel Interaktives BeweissystemEinzelnachweise Bearbeiten Amos Fiat Adi Shamir How To Prove Yourself Practical Solutions to Identification and Signature Problems In Andrew M Odlyzko Hrsg Advances in Cryptology CRYPTO 86 Lecture notes in computer science Band 263 Springer Berlin Heidelberg 1987 ISBN 3 540 18047 8 S 186 194 David Pointcheval Jacques Stern Security Proofs for Signature Schemes In Ueli Maurer Hrsg Advances in Cryptology EUROCRYPT 96 Springer Berlin Heidelberg 1996 ISBN 3 540 61186 X S 387 398 S Goldwasser Y T Kalai On the In security of the Fiat Shamir paradigm In Proceedings 44th Annual IEEE Symposium on Foundations of Computer Science 2003 2003 S 102 113 doi 10 1109 SFCS 2003 1238185 David Bernhard Olivier Pereira Bogdan Warinschi Advances in Cryptology ASIACRYPT 2012 Hrsg Xiaoyun Wang Kazue Sako How not to Prove Yourself Pitfalls of the Fiat Shamir Heuristic and Applications to Helios S 626 643 uclouvain be PDF Jan Camenisch Markus Stadler Proof Systems for General Statements about Discrete Logarithms In Technical Report Dept of Computer Science ETH Zurich Nr 260 1997 1 2 Vorlage Toter Link ftp inf ethz ch Fehler Seite nicht mehr abrufbar Suche in Webarchiven Mihir Bellare Phillip Rogaway Random Oracles Are Practical A Paradigm for Designing Efficient Protocols In Proceedings of the 1st ACM Conference on Computer and Communications Security ACM New York NY USA 1993 ISBN 0 89791 629 8 S 62 73 doi 10 1145 168588 168596 Abgerufen von https de wikipedia org w index php title Fiat Shamir Heuristik amp oldid 240463472