### On the (In)security of the Fiat-Shamir Paradigm

Shafi Goldwasser and Yael Tauman

##### Abstract

In 1986, Fiat and Shamir suggested a general method for transforming secure 3-round public-coin identification schemes into digital signature schemes. The significant contribution of this method is a means for designing efficient digital signatures, while hopefully achieving security against chosen message attacks. All other known constructions which achieve such security are substantially more inefficient and complicated in design. In 1996, Pointcheval and Stern proved that the signature schemes obtained by the Fiat-Shamir transformation are secure in the so called Random Oracle Model'. The question is: does the proof of the security of the Fiat-Shamir transformation in the Random Oracle Model, imply that the transformation yields secure signature schemes in the real-world"? In this paper we answer this question negatively. We show that there exist secure 3-round public-coin identification schemes for which the Fiat-Shamir methodology produces {\bf insecure} digital signature schemes for {\bf any} implementation of the Random Oracle Model' in the real-world' by a function ensemble.

Note: Minor corrections.

Available format(s)
Category
Foundations
Publication info
Published elsewhere. Unknown where it was published
Keywords
Fiat-Shamir
Contact author(s)
yael @ theory lcs mit edu
History
2004-02-03: revised
See all versions
Short URL
https://ia.cr/2003/034

CC BY

BibTeX

@misc{cryptoeprint:2003/034,
author = {Shafi Goldwasser and Yael Tauman},
title = {On the (In)security of the Fiat-Shamir Paradigm},
howpublished = {Cryptology ePrint Archive, Paper 2003/034},
year = {2003},
note = {\url{https://eprint.iacr.org/2003/034}},
url = {https://eprint.iacr.org/2003/034}
}
`
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.