Paper 2002/104

Forward-Secure Signatures with Fast Key Update

Anton Kozlov and Leonid Reyzin


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.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. Security In Communication Networks '02
forward-secure signaturesstrong RSA assumptionidentification protocols
Contact author(s)
reyzin @ bu edu
2002-08-13: revised
2002-08-02: received
See all versions
Short URL
Creative Commons Attribution


      author = {Anton Kozlov and Leonid Reyzin},
      title = {Forward-Secure Signatures with Fast Key Update},
      howpublished = {Cryptology ePrint Archive, Paper 2002/104},
      year = {2002},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.