Abstract
We put forward a new method of constructing Fiat-Shamir-like signature schemes that yields better “exact security” than the original Fiat-Shamir method. (We also point out, however, that such tight security does not make our modified schemes always preferable to the original ones. Indeed, there exist particularly efficient Fiat-Shamir-like schemes that, though only enjoying “loose security,” by using longer keys may provably provide more security at a lower computational cost than their “tight-security” counterparts.)
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Mihir Bellare and Phillip Rogaway. Random oracles are practical: a paradigm for designing efficient protocols. In Proceedings of the 1st ACM Conference on Computer and Communication Security, November 1993, pages 62–73. Revised version appears in http://www-cse.ucsd.edu/users/mihir/papers/crypto-papers.html.
Mihir Bellare and Phillip Rogaway. The exact security of digital signatures: how to sign with RS A and Rabin. In [Ma], pages 399–416. Revised version appears in http://www-cse.ucsd.edu/users/mihir/paperscrypto-papers.html.
Uriel Feige, Amos Fiat, and Adi Shamir. Zero-knowledge proofs of identity. Journal of Cryptology, 1(2):77–94, 1988.
Amos Fiat and Adi Shamir. How to prove yourself: practical solutions to identification and signature problems. In [Od], pages 186–194.
Shafi Goldwasser, Silvio Micali, and Ronald L. Rivest. A digital signature scheme secure against adaptive chosen-message attacks. SIAM Journal on Computing, 17(2):281–308, April 1988.
Oded Goldreich. Two remarks concerning the Goldwasser-Micali-Rivest signature scheme. In [Od], pages 104–110.
Shafi Goldwasser, editor. Advances in Cryptology—CRYPTO ’88, volume 403 of Lecture Notes in Computer Science. Springer-Verlag, Berlin, 1990.
Louis Claude Guillou and Jean-Jacques Quisquater. A “paradoxical” indentity-based signature scheme resulting from zero-knowledge. In [Go2], pages 216–231.
Arjen K. Lenstra and Hendrik W. Lenstra, editors. The Development of the Number Field Sieve, volume 1554 of Lecture notes in Mathematics. Springer-Verlag, Berlin, 1993.
Ueli Maurer, editor. Advances in Cryptology—EUROCRYPT 96, volume 1070 of Lecture Notes in Computer Science. Springer-Verlag, Berlin, 1996.
Silvio Micali. A secure and efficient digital signature algorithm. Technical Report MIT/LCS/TM-501, Massachusetts Institute of Technology, Cambridge, MA, March 1994.
Silvio Micali and Leonid Reyzin. Improving the exact security of Fiat-Shamir signature schemes. In R. Baumgart, editor, Secure Networking—CQRE [Secure] ’99, volume 1740 of Lecture Notes in Computer Science, pages 167–182. Springer-Verlag, Berlin, 1999.
Silvio Micali and Adi Shamir. An improvement of the Fiat-Shamir identification and signature scheme. In [Go2], pages 244–247.
Andrew M. Odlyzko, editor. Advances in Cryptology—CRYPTO ’86, volume 263 of Lecture Notes in Computer Science. Springer-Verlag, Berlin, 1987.
Tatsuaki Okamoto. Provably secure and practical identification schemes and corresponding signature schemes. In E. F. Brickell, editor, Advances in Cryptology—CRYPTO ’92, volume 740 of Lecture Notes in Computer Science, pages 31–53. Springer-Verlag, Berlin, 1993.
Kazuo Ohta and Tatsuaki Okamoto. A modification of the Fiat-Shamir scheme. In [Go2], pages 232–243.
Kazuo Ohta and Tatsuaki Okamoto. On concrete security treatment of signatures derived from identification. In H. Krawczyk, editor, Advances in Cryptology—CRYPTO ’98, volume 1462 of Lecture Notes in Computer Science, pages 354–369. Springer-Verlag, Berlin, 1998.
H. Ong and Claus P. Schnorr. Fast signature generation with a Fiat-Shamir-like scheme. In I. B. Damgård, editor, Advances in Cryptology—EUROCRYPT 90, volume 473 of Lecture Notes in Computer Science, pages 432–440. Springer-Verlag, Berlin, 1991.
David Pointcheval and Jacques Stern. Security proofs for signature schemes. In [Ma], pages 387–398.
David Pointcheval and Jacques Stern. Security arguments for digital signatures and blind signatures. Journal of Cryptology, 13(3):361–396, 2000.
Claus P. Schnorr. Efficient identification and signatures for smart cards. In J.-J. Quisquater and J. Vandewalle, editors, Advances in Cryptology—EUROCRYPT 89, volume 434 of Lecture Notes in Computer Science, pages 688–689. Springer-Verlag, Berlin, 1990.
Claus P. Schnorr. Security of 2t-root identification and signatures. In N. Koblitz, editor, Advances in Cryptology—CRYPTO ’96, volume 1109 of Lecture Notes in Computer Science, pages 143–156. Springer-Verlag, Berlin, 1996.
Victor Shoup. On the security of a practical identification scheme. In [Ma], pages 344–353.
Hugh C. Williams. A modification of the RSA public-key encryption procedure. IEEE Transactions on Information Theory, IT-26(6):726–729, November 1980.
Author information
Authors and Affiliations
Additional information
Communicated by Jaques Stern
Online publication 9 April 2001
This material is based upon work supported in part under a National Science Foundation Graduate Fellowship. A preliminary extended abstract of this work appears in [MR]. A version with more complete proofs is available from http://theory.lcs.mit.edu/~reyzin.
Rights and permissions
About this article
Cite this article
Micali, S., Reyzin, L. Improving the exact security of digital signature schemes. J. Cryptology 15, 1–18 (2002). https://doi.org/10.1007/s00145-001-0005-8
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00145-001-0005-8