Authors: Tal Malkin, Daniele Micciancio and Sara Miner
Advances in Cryptology - Eurocrypt 2002. Amsterdam, The Netherlands, April 28-May 2, 2002. Lectture Notes in Computer Science 2332, Springer-Verlag, pp. 400-417.
Abstract: Forward-secure digital signatures, initially proposed by Anderson in CCS 97 and formalized by Bellare and Miner in Crypto 99, are signature schemes which enjoy the additional guarantee that a compromise of the secret key at some point in time does not help forge signatures allegedly signed in an earlier time period. Consequently, if the secret key is lost, then the key can be safely revoked without invalidating previously issued signatures. Since the introduction of the concept, several forward-secure signature schemes have been proposed, with varying performance both in terms of space and time. Which scheme is most useful in practice, typically depends on the requirements of the specific application. In this paper we propose and study some general composition operations that can be used to combine existing signature schemes (whether forward-secure or not) into new forward-secure signature schemes. Our schemes offer interesting trade-offs between the various efficiency parameters, achieving a greater flexibility in accommodating the requirements of different applications. In particular, we use our techniques to construct the first efficient forward-secure signature scheme where the total number of time periods for using the public key does not have to be fixed in advance. The scheme can be used for practically unbounded time, and the performance depends (minimally) only on the time elapsed so far. Our scheme achieves excellent performance, which is very competitive with all previous schemes with respect to all parameters, and outperforms each of the previous schemes in at least one of the parameters. Moreover, the scheme can be based on any underlying digital signature scheme, and does not rely on specific assumptions. Its forward security is proven in the standard model (without using a random oracle).