From Identification to Signatures via the Fiat-Shamir Transform: Minimizing Assumptions for Security and Forward-Security

Michel Abdalla; Jee Hea An; Mihir Bellare; Chanathip Namprempre

Paper 2002/022

From Identification to Signatures via the Fiat-Shamir Transform: Minimizing Assumptions for Security and Forward-Security

Michel Abdalla, Jee Hea An, Mihir Bellare, and Chanathip Namprempre

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.

Metadata

Available format(s): PDF PS
Category: Public-key cryptography
Publication info: Published elsewhere. An extended abstract of this paper appears in the proceedings of EUROCRYPT 2002. This is the full version.
Keywords: Signatures identification Fiat-Shamir random oracle model
Contact author(s): mihir @ cs ucsd edu
History: 2007-05-19: revised; 2002-02-24: received; See all versions
Short URL: https://ia.cr/2002/022
License: CC BY

BibTeX

@misc{cryptoeprint:2002/022,
      author = {Michel Abdalla and Jee Hea An and Mihir Bellare and Chanathip Namprempre},
      title = {From Identification to Signatures via the Fiat-Shamir Transform: Minimizing Assumptions for Security and Forward-Security},
      howpublished = {Cryptology {ePrint} Archive, Paper 2002/022},
      year = {2002},
      url = {https://eprint.iacr.org/2002/022}
}