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.
Category / Keywords: foundations / Fiat-Shamir Date: received 18 Feb 2003, last revised 2 Feb 2004 Contact author: yael at theory lcs mit edu Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation Note: Minor corrections. Version: 20040203:040805 (All versions of this report) Short URL: ia.cr/2003/034