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.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Jee Hea An, Michel Abdalla, Mihir Bellare, and Chanathip Namprempre. From identification to signatures via the Fiat-Samir transform: Minimizing assumptions for security and forward-security. In Knudsen [Knu02].
Giuseppe Ateniese, Jan Camenisch, Marc Joye, and Gene Tsudik. A practical and provably secure coalition-resistant group signature scheme. In Mihir Bellare, editor, Advances in Cryptology-CRYPTO 2000, volume 1880 of Lecture Notes in Computer Science, pages 255–270. Springer-Verlag, 2000.
Ross Anderson. Invited lecture. In Fourth Annual Conference on Computer and Communications Security. ACM, 1997. Summary appears in [And01].
Ross Anderson. Two remarks on public key cryptology. http://www.cl.cam.ac.uk/users/rja14/, 2001.
Michel Abdalla and Leonid Reyzin. A new forward-secure digital signature scheme. In Tatsuaki Okamoto, editor, Advances in Cryptology-ASIACRYPT 2000, volume 1976 of Lecture Notes in Computer Science.
Mihir Bellare and Oded Goldreich. On defining proofs of knowledge. In Ernest F. Brickell, editor, Advances in Cryptology-CRYPTO’ 92, volume 740 of Lecture Notes in Computer Science, pages 390–420. Springer-Verlag, 1993, 16–20 August 1992.
Mihir Bellare and Sara Miner. A forward-secure digital signature scheme. In Michael Wiener, editor, Advances in Cryptology-CRYPTO’ 99, volume 1666 of Lecture Notes in Computer Science, pages 431–448. Springer-Verlag, 15–19 August 1999.
Niko Barić and Birgit Pfitzmann. Collision-free accumulators and failstop signature schemes without trees. In Walter Fumy, editor, Advances in Cryptology-EUROCRYPT 97, volume 1233 of Lecture Notes in Computer Science, pages 480–494. Springer-Verlag, 11–15 May 1997.
Mihir Bellare and Phillip Rogaway. Random oracles are practical: A paradigm for designing efficient protocols. In Proceedings of the 1st ACM Conference on Computer and Communication Security, pages 62–73, November 1993.
Don Coppersmith and Markus Jakobsson. Almost optimal hash sequence traversal. In 6th International Financial Cryptography Conference, 2002.
Jan Camenisch and Markus Michels. A group signature scheme based on an RSA-variant. Technical Report RS-98-27, BRICS, University of Aarhus, November 1998.
Ronald Cramer and Victor Shoup. Signature schemes based on the strong RSA assumption. ACM Transactions on Information and System Security, 3(3):161–185, 2000.
I. B. Damgård, editor. Advances in Cryptology-EUROCRYPT 90, volume 473 of Lecture Notes in Computer Science. Springer-Verlag, 1991.
Eiichiro Fujisaki and Tatsuaki Okamoto. Statistical zero knowledge protocols to prove modular polynomial relations. In Burton S. Kaliski Jr., editor, Advances in Cryptology-CRYPTO’ 97, volume 1294 of Lecture Notes in Computer Science, pages 16–30. Springer-Verlag, 17–21 August 1997.
Amos Fiat and Adi Shamir. How to prove yourself: Practical solutions to identification and signature problems. In Andrew M. Odlyzko, editor, Advances in Cryptology-CRYPTO’ 86, volume 263 of Lecture Notes in Computer Science, pages 186–194. Springer-Verlag, 1987, 11–15 August 1986.
Marc Girault. An identity-based identification scheme based on discrete logarithms modulo a composite number. In [Dam90], pages 481–486.
Marc Girault. Self-certified public keys. In D. W. Davies, editor, Advances in Cryptology-EUROCRYPT 91, volume 547 of Lecture Notes in Computer Science, pages 490–497. Springer-Verlag, 8–11 April 1991.
Shafi Goldwasser, Silvio Micali, and Ronald L. Rivest. A digital signature scheme secure against adaptive chosen-message attacks. SIAM Journal on Computing, 17(2):281–308, April 1988.
Louis Claude Guillou and Jean-Jacques Quisquater. A “paradoxical” indentity-based signature scheme resulting from zero-knowledge. In Shafi Goldwasser, editor, Advances in Cryptology-CRYPTO’ 88, volume 403 of Lecture Notes in Computer Science, pages 216–231. Springer-Verlag, 1990.
Gene Itkis and Leonid Reyzin. Forward-secure signatures with optimal signing and verifying. In Joe Kilian, editor, Advances in Cryptology-CRYPTO 2001, volume 2139 of Lecture Notes in Computer Science, 2001.
Gene Itkis and Leonid Reyzin. Forward-secure signatures with optimal signing and verifying. Cryptobytes, 5(2), 2002.
Markus Jakobsson. Fractal hash sequence representation and traversal. In 2002 IEEE International Symposium on Information Theory, 2002.
Lars Knudsen, editor. Advances in Cryptology-EUROCRYPT 2002, volume 2332 of Lecture Notes in Computer Science. Springer-Verlag, 2002.
Hugo Krawczyk. Simple forward-secure signatures from any signature scheme. In Seventh ACM Conference on Computer and Communication Security. ACM, November 1–4 2000.
Ueli Maurer, editor. Advances in Cryptology-EUROCRYPT 96, volume 1070 of Lecture Notes in Computer Science. Springer-Verlag, 1996.
Tal Malkin, Daniele Micciancio, and Sara Miner. Efficient generic forwardsecure signatures with an unbounded number of time periods. In [Knu02].
Heidroon Ong and Claus P. Schnorr. Fast signature generation with a Fiat Shamir-like scheme. In Damgård [Dam90], pages 432–440.
David Pointcheval and Jacques Stern. Security proofs for signature schemes. In Maurer [Mau96], pages 387–398.
Guillaume Poupard and Jacques Stern. Security analysis of a practical “on the fly” authentication and signature generation. In Nyberg, editor, Advances in Cryptology-EUROCRYPT 98, volume 1403 of LNCS.
Claus-Peter Schnorr. Efficient signature generation by smart cards. Journal of Cryptology, 4(3):161–174, 1991.
Adi Shamir. On the generation of cryptographically strong pseudorandom sequences. ACM Transactions on Computer Systems, 1(1):38–44, 1983.
Victor Shoup. On the security of a practical identification scheme. In Maurer [Mau96], pages 344–353.
Dawn Xiaodong Song. Practical forward secure group signature schemes. In Eighth ACM Conference on Computer and Communication Security, 2001.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kozlov, A., Reyzin, L. (2003). Forward-Secure Signatures with Fast Key Update. In: Cimato, S., Persiano, G., Galdi, C. (eds) Security in Communication Networks. SCN 2002. Lecture Notes in Computer Science, vol 2576. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-36413-7_18
Download citation
DOI: https://doi.org/10.1007/3-540-36413-7_18
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-00420-2
Online ISBN: 978-3-540-36413-9
eBook Packages: Springer Book Archive