A New Forward-Secure Digital Signature Scheme

by Michel Abdalla and Leonid Reyzin

We improve the Bellare-Miner (Crypto '99) construction of signature schemes with forward security in the random oracle model. Our scheme has significantly shorter keys and is, therefore, more practical. By using a direct proof technique not used for forward-secure schemes before, we are able to provide better security bounds for the original construction as well as for our scheme.

Bellare and Miner also presented a method for constructing such schemes without the use of the random oracle. We conclude by proposing an improvement to their method and an additional, new method for accomplishing this.

This work appears in Advances in Cryptology -- Asiacrypt 2000, Tatsuaki Okamoto, editor, Lecture Notes in Computer Science 1976, Springer-Verlag, 2000. © IACR.