Most digital-signature systems include, as part of the procedure for validating a document and its signature, a mechanism for verifying some properties of the signer's public key. Typically, this involves the validation of another digital signature on an assertion that these properties hold during a specified period of validity. Therefore, the validator needs to be able to check that the signature was computed during this period. We propose that the easiest way to do this, especially for long-lived documents, is to accompany the document and its signature by a time-stamp certificate for the document-signature pair, computed immediately after the signature is computed, and to include the validation of this certificate as part of the validation of the signature. This would allow, for example, the continued attribution of trustworthiness to a particular RSA digital signature, even if a significant later advance in factoring algorithms made the signer's choice of key-length completely insecure for the computation of new signatures.
But what about advances in attacking one-way hash functions? In fact, time-stamp certificates can be renewed so as to remain valid indefinitely---as long as the maintainers of a secure digital time-stamping service keep abreast of the state of the art in constructing and in attacking cryptographic hash functions. The renewing process works as follows. Suppose that c is a valid time-stamp certificate, in the current system, for a document x. Further suppose that a new time-stamping system is implemented, for example by replacing the hash function used in the old system. Now let c' be the new-system time-stamp certificate for the compound time-stamp request (x, c). Even if the old system is compromised at a definite later date, the new certificate c' provides trustworthy evidence that x existed at the time stated in the original certificate.
This digital time-stamping scheme can also be adapted so as to assign a succint, meaningful and cryptographically verifiable name or "serial number" to any digital document.
The time-stamping scheme was described in: D. Bayer, S. Haber, and W.S. Stornetta, "Improving the efficiency and reliability of digital time-stamping." In Sequences II: Methods in Communication, Security, and Computer Science, ed. R.M. Capocelli, A. De Santis, U. Vaccaro, pp. 329-334, Springer-Verlag (New York, 1993).
A commercial implementation is available from Surety Technologies, a Bellcore spin-off.
For more information, contact stuart@bellcore.com, or see http://www.surety.com.