Fiat-Shamir-Heuristik

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

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.[1] 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[2] 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.[3] 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.[4]

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.

Dies ist ein interaktiver Beweis des Wissens eines diskreten Logarithmus.[5]

  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.[6]

  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 .

Einzelnachweise

[Bearbeiten | Quelltext 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.