Efficient Generic Forward-Secure Signatures with an Unbounded Number of Time Periods

We construct the first efficient forward-secure digital 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.