[GK03] On the (In)security of the Fiat-Shamir Paradigm

Authors: Shafi Goldwasser, Yael Tauman Kalai | Venue: FOCS 2003 | Source

Abstract

We show that the Fiat-Shamir transform is not sound in the standard model in general. Specifically, we construct a 3-round public-coin identification scheme that is secure in the random oracle model, yet for which the Fiat-Shamir signature scheme (obtained by replacing the random oracle with any concrete hash function) is existentially forgeable. More precisely, we show that for any concrete hash function $H$, the resulting signature scheme can be broken by an efficient adversary. Our techniques use non-black-box methods and demonstrate that the random oracle cannot be instantiated in general.

BibTeX

Copy

@Inproceedings{FOCS:GolKal03,
  author = {Shafi Goldwasser and Yael Tauman Kalai},
  title = {On the (In)security of the {Fiat}-{Shamir} Paradigm},
  pages = {102--115},
  booktitle = {44th Annual Symposium on Foundations of Computer Science},
  address = {Cambridge, MA, USA},
  month = {oct~11--14},
  publisher = {{IEEE} Computer Society Press},
  year = {2003},
  doi = {10.1109/SFCS.2003.1238185},
}