Efficient Generic Forward-Secure Signatures With an Unbounded Number of Time Periods
Tal Malkin, Daniele Micciancio and Sara Miner
Abstract:
We 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 number of time periods for
which our scheme can be used is bounded only by an exponential function of the
security parameter (given this much time, any scheme can be broken by exhaustive
search), and its 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. As an intermediate step in designing our scheme, we propose and
study two general composition operations that can be used to combine any
existing signature schemes (whether standard or forward-secure) into new
forward-secure signature schemes.