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.
Category / Keywords: cryptographic protocols / forward security, digital signatures Date: received 5 May 2001 Contact author: sminer at cs ucsd edu Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | BibTeX Citation Version: 20010506:014101 (All versions of this report) Short URL: ia.cr/2001/034 Discussion forum: Show discussion | Start new discussion