DocumentCode :
2169401
Title :
On the (In)security of the Fiat-Shamir paradigm
Author :
Goldwasser, Shafi ; Kalai, Yael Tauman
Author_Institution :
Dept. of Comput. Sci. & Appl. Math, Weizamann Inst. of Sci., Rehovot, Israel
fYear :
2003
fDate :
11-14 Oct. 2003
Firstpage :
102
Lastpage :
113
Abstract :
In 1986, Fiat and Shamir proposed a general method for transforming secure 3-round public-coin identification schemes into digital signature schemes. The idea of the transformation was to replace the random message of the verifier in the identification scheme, with the value of some deterministic hash function evaluated on various quantities in the protocol and on the message to be signed. The Fiat-Shamir methodology for producing digital signature schemes quickly gained popularity as it yields efficient and easy to implement digital signature schemes. The most important question however remained open: are the digital signatures produced by the Fiat-Shamir methodology secure? We answer this question negatively. We show that there exist secure 3-round public-coin identification schemes for which the Fiat-Shamir transformation yields insecure digital signature schemes for any hash function used by the transformation. This is in contrast to the work of Pointcheval and Stern which proved that the Fiat-Shamir methodology always produces digital signatures secure against chosen message attack in the "Random Oracle Model" - when the hash function is modeled by a random oracle. Among other things, we make new usage of Barak\´s technique for taking advantage of nonblack-box access to a program, this time in the context of digital signatures.
Keywords :
message authentication; public key cryptography; theorem proving; 3-round public-coin identification schemes; Fiat-Shamir paradigm; Fiat-Shamir transformation; Random Oracle Model; deterministic hash function; digital signature scheme; nonblack-box access; Computer science; Computer security; Cost function; Cryptography; Design methodology; Digital signatures; Forgery; Law; Legal factors; Protocols;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium on
ISSN :
0272-5428
Print_ISBN :
0-7695-2040-5
Type :
conf
DOI :
10.1109/SFCS.2003.1238185
Filename :
1238185
Link To Document :
بازگشت