Cryptology ePrint Archive: Report 2002/104

Forward-Secure Signatures with Fast Key Update

Anton Kozlov and Leonid Reyzin

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.

Category / Keywords: public-key cryptography / forward-secure signatures, strong RSA assumption, identification protocols

Publication Info: Security In Communication Networks '02

Date: received 1 Aug 2002, last revised 13 Aug 2002

Contact author: reyzin at bu edu

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Version: 20020813:152406 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]