Paper 2001/034

Composition and Efficiency Tradeoffs for Forward-Secure Digital Signatures

Tal Malkin, Daniele Micciancio, and Sara Miner

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. As an extension of our techniques, we also construct the first efficient forward-secure signature scheme where the total number of time periods for which the public key is used 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 overall, is very competitive with previous schemes with respect to all parameters, and outperforms each of the previous schemes in at least one parameter. 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.