Fiat-Shamir-Heuristik

Die Fiat-Shamir-Heuristik oder Fiat-Shamir-Transformation 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.

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 $y$ abhängt, wird die Sicherheit des Algorithmus kompromittiert, da ein böswilliger Beweiser den Wert $c$ 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.

↑ 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 (englisch).
↑ 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 (englisch).
↑ 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 (englisch).
↑ 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 (englisch, uclouvain.be [PDF]).

[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 (englisch).

[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 (englisch).

[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 (englisch).

[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 (englisch, uclouvain.be [PDF]).