Abstract
The Fiat-Shamir paradigm for transforming identification schemes into signature schemes has been popular since its introduction because it yields efficient signature schemes, and has been receiving renewed interest of late as the main tool in deriving forward-secure signature schemes. We find minimal (meaning necessary and sufficient) conditions on the identification scheme to ensure security of the signature scheme in the random oracle model, in both the usual and the forward-secure cases. Specifically we show that the signature scheme is secure (resp. forward-secure) against chosen-message attacks in the random oracle model if and only if the underlying identification scheme is secure (resp. forward-secure) against impersonation under passive (i.e.. eavesdropping only) attacks, and has its commitments drawn at random from a large space. An extension is proven incorporating a random seed into the Fiat-Shamir transform so that the commitment space assumption may be removed.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
M. Abdalla, J. H. An, M. Bellare, and C. Namprempre. From identification to signatures via the Fiat-Shamir transform: Minimizing assumptions for security and forward-security. Full version of this paper, available via http://www-cse.ucsd.edu/users/mihir.
M. Abdalla and L. Reyzin. A new forward-secure digital signature scheme. In T. Okamoto, editor, Advances in Cryptology-ASIACRYPT 2000, volume 1976 of Lecture Notes in Computer Science, pages 116–129, Berlin, Germany, Dec. 2000. Springer-Verlag.
M. Bellare and O. Goldreich. On defining proofs of knowledge. In E. Brickell, editor, Advances in Cryptology-CRYPTO’ 92, volume 740 of Lecture Notes in Computer Science, pages 390–420, Berlin, Germany, Aug. 1992. Springer-Verlag.
M. Bellare and S. Miner. A forward-secure digital signature scheme. In M. Wiener, editor, Advances in Cryptology-CRYPTO’ 99, volume 1666 of Lecture Notes in Computer Science, pages 431–448, Berlin, Germany, Aug. 1999. Springer-Verlag.
M. Bellare and P. Rogaway. Random oracles are practical: A paradigm for designing efficient protocols. In V. Ashby, editor, 1st ACM Conference on Computer and Communications Security. ACM Press, Nov. 1993.
T. Beth. Efficient zero-knowledge identification scheme for smart cards. In C. Guenther, editor, Advances in Cryptology-EUROCRYPT’ 1988, volume 330 of Lecture Notes in Computer Science, pages 77–86, Berlin, Germany, May 1988. Springer-Verlag.
E. Brickell and K. McCurley. An interactive identification scheme based on discrete logarithms and factoring. In I. Damgård, editor, Advances in Cryptology-EUROCRYPT’ 90, volume 473 of Lecture Notes in Computer Science, pages 63–71, Berlin, Germany, May 1991. Springer-Verlag.
B. Chor and O. Goldreich. Unbiased bits from sources of weak randomness and probabilistic communication complexity. In 26th Annual Symposium on Foundations of Computer Science, pages 429–442, Los Angeles, CA, USA, Oct. 1985. IEEE Computer Society Press.
R. Cramer and I. Damgård. Secure signature schemes based on interactive protocols. In D. Coppersmith, editor, Advances in Cryptology-CRYPTO’ 95, volume 963 of Lecture Notes in Computer Science, pages 297–310, Berlin, Germany, 1995. Springer-Verlag.
U. Feige, A. Fiat, and A. Shamir. Zero knowledge proofs of identity. Journal of Cryptology, 1(2):77–94, 1988.
A. Fiat and A. Shamir. How to prove yourself: Practical solutions to identification and signature problems. In A. Odlyzko, editor, Advances in Cryptology-CRYPTO’ 86, volume 263 of Lecture Notes in Computer Science, pages 186–194, Berlin, Germany, Aug. 1986. Springer-Verlag.
M. Girault. An identity-based identification scheme based on discrete logarithms modulo a composite number. In I. Damgård, editor, Advances in Cryptology-EUROCRYPT’ 90, volume 473 of Lecture Notes in Computer Science, pages 481–486, Berlin, Germany, May 1991. Springer-Verlag.
S. Goldwasser, S. Micali, and R. Rivest. A digital signature scheme secure against adaptive chosen-message attacks. SIAM Journal of Computing, 17(2):281–308, Apr. 1988.
L. Guillou and J. J. Quisquater. A “paradoxical” identity-based signature scheme resulting from zero-knowledge. In S. Goldwasser, editor, Advances in Cryptology-CRYPTO’ 88, volume 403 of Lecture Notes in Computer Science, pages 216–231, Berlin, Germany, 21-25 Aug. 1988. Springer-Verlag.
G. Itkis and L. Reyzin. Forward-secure signatures with optimal signing and verifying. In J. Kilian, editor, Advances in Cryptology-CRYPTO’ 01, volume 2139 of Lecture Notes in Computer Science, pages 332–354, Berlin, Germany, Aug. 2001. Springer-Verlag.
S. Micali and L. Reyzin. Improving the exact security of digital signature schemes. Journal of Cryptology, 15(1):1–18, 2002.
S. Micali and A. Shamir. An improvement of the Fiat-Shamir identification and signature scheme. In S. Goldwasser, editor, Advances in Cryptology-CRYPTO’ 88, volume 403 of Lecture Notes in Computer Science, pages 244–248, Berlin, Germany, Aug. 1990. Springer-Verlag.
K. Ohta and T. 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–370, Berlin, Germany, Aug. 1998. Springer-Verlag.
T. Okamoto. Provably secure and practical identification schemes and corresponding signature schemes. In E. Brickell, editor, Advances in Cryptology-CRYPTO’ 92, volume 740 of Lecture Notes in Computer Science, pages 31–53, Berlin, Germany, Aug. 1993. Springer-Verlag.
H. Ong and C. Schnorr. Fast signature generation with a Fiat Shamir-like scheme. In I. Damgård, editor, Advances in Cryptology-EUROCRYPT’ 90, volume 473 of Lecture Notes in Computer Science, pages 432–440, Berlin, Germany, May 1990. Springer-Verlag.
D. Pointcheval. A new identification scheme based on the perceptrons problem. In J. Quisquater and L. Guillou, editors, Advances in Cryptology-EUROCRYPT’ 95, volume 921 of Lecture Notes in Computer Science, pages 319–328, Berlin, Germany, May 1995. Springer-Verlag.
D. Pointcheval and J. Stern. Security proofs for signature schemes. In U. Maurer, editor, Advances in Cryptology-EUROCRYPT’ 96, volume 1070 of Lecture Notes in Computer Science, pages 387–398, Berlin, Germany, May 1996. Springer-Verlag.
D. Pointcheval and J. Stern. Security arguments for digital signatures and blind signatures. Journal of Cryptology, 13(3):361–396, 2000.
C. Schnorr. Efficient signature generation by smart cards. Journal of Cryptology, 4(3):161–174, 1991.
V. Shoup. On the security of a practical identification scheme. In U. Maurer, editor, Advances in Cryptology-EUROCRYPT’ 96, volume 1070 of Lecture Notes in Computer Science, pages 344–353, Berlin, Germany, May 1996. Springer-Verlag.
J. Stern. A new identification scheme based on syndrome decoding. In D. Stinson, editor, Advances in Cryptology-CRYPTO’ 93, volume 773 of Lecture Notes in Computer Science, pages 13–21, Berlin, Germany, 1994. Springer-Verlag.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Abdalla, M., An, J.H., Bellare, M., Namprempre, C. (2002). From Identification to Signatures via the Fiat-Shamir Transform: Minimizing Assumptions for Security and Forward-Security. In: Knudsen, L.R. (eds) Advances in Cryptology — EUROCRYPT 2002. EUROCRYPT 2002. Lecture Notes in Computer Science, vol 2332. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-46035-7_28
Download citation
DOI: https://doi.org/10.1007/3-540-46035-7_28
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-43553-2
Online ISBN: 978-3-540-46035-0
eBook Packages: Springer Book Archive