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: ia.cr/2002/104 Discussion forum: Show discussion | Start new discussion