International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Forward-Secure Signatures with Fast Key Update

Authors:
Anton Kozlov
Leonid Reyzin
Download:
URL: http://eprint.iacr.org/2002/104
Search ePrint
Search Google
Abstract: In regular digital signatures, once the secret key is compromised, all signatures, even those that were issued by the honest signer before the compromise, will not be trustworthy any more. Forward-secure signatures have been proposed to address this major shortcoming. We present a new forward-secure signature scheme, called KREUS, with several advantages. It has the most efficient Key Update of all known schemes, requiring just a single modular squaring. Our scheme thus enables more frequent Key Update and hence allows shorter time periods, enhancing security: fewer signatures might become invalid as a result of key compromise. In addition, the on-line component of signing is also very efficient, consisting of a single multiplication. We precisely analyze the total signer costs and show that they are lower when the number of signatures per time period is small; the advantage of our scheme increases considerably as the number of time periods grows. Our scheme's security relies on the Strong-RSA assumption and the random-oracle-based Fiat-Shamir transform.
BibTeX
@misc{eprint-2002-11627,
  title={Forward-Secure Signatures with Fast Key Update},
  booktitle={IACR Eprint archive},
  keywords={public-key cryptography / forward-secure signatures, strong RSA assumption, identification protocols},
  url={http://eprint.iacr.org/2002/104},
  note={Security In Communication Networks '02 reyzin@bu.edu 11912 received 1 Aug 2002, last revised 13 Aug 2002},
  author={Anton Kozlov and Leonid Reyzin},
  year=2002
}