Forward-Secure Signatures with Optimal Signing and Verifying

Gene Itkis; Leonid Reyzin

Paper 2001/048

Forward-Secure Signatures with Optimal Signing and Verifying

Gene Itkis and Leonid Reyzin

Abstract

Ordinary digital signatures have an inherent weakness: if the secret key is leaked, then all signatures, even the ones generated before the leak, are no longer trustworthy. Forward-secure digital signatures were recently proposed to address this weakness: they ensure that past signatures remain secure even if the current secret key is leaked. We propose the first forward-secure signature scheme for which both signing and verifying are as efficient as for one of the most efficient ordinary signature schemes (Guillou-Quisquater): each requiring just two modular exponentiations with a short exponent. All previously proposed forward-secure signature schemes took significantly longer to sign and verify than ordinary signature schemes. Our scheme requires only fractional increases to the sizes of keys and signatures, and no additional public storage. Like the underlying Guillou-Quisquater scheme, our scheme is provably secure in the random oracle model.

Metadata

Available format(s): PDF PS
Category: Public-key cryptography
Publication info: Published elsewhere. to appear in Crypto-2001
Contact author(s): itkis @ bu edu
History: 2001-06-18: received
Short URL: https://ia.cr/2001/048
License: CC BY

BibTeX

@misc{cryptoeprint:2001/048,
      author = {Gene Itkis and Leonid Reyzin},
      title = {Forward-Secure Signatures with Optimal Signing and Verifying},
      howpublished = {Cryptology {ePrint} Archive, Paper 2001/048},
      year = {2001},
      url = {https://eprint.iacr.org/2001/048}
}