On the (In)-Security of the Fiat-Shamir “Paradigm”

986, research suggested a general method for transforming secure 3-round public-coin identification schemes into digital signature schemes. The significance of this method is as a way to design efficient digital signatures, while hopefully achieving security against chosen message attacks. All other known constructions that achieve security against chosen message attacks are substantially more inefficient and complicated in design. In 1996, further studies 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”? We show that there exist secure 3-round public-coin identification schemes for which the Fiat-Shamir methodology produces insecure digital signature schemes for any implementation of the ‘Random Oracle Model’ in the ‘real-world’ by a function ensemble.