Consider two questions that may be asked by a computer user as he or she views a digital document or on-line record:
- Who is the author
of this record - who wrote it, approved it, or consented to it?
- When was this record created or last modified?
In both cases, the question is about exactly this record - exactly this sequence of bits. An answer to the first question tells who and what: Who approved exactly what is in this record? An answer to the second question tells when and what: When exactly did the contents of this record first exist?
Both of the above questions have good solutions. A system for answering the first question is called a digital signature scheme (see Question 2.2.2). A system for answering the second question is called a digital timestamping scheme. Such systems are described in [BHS93] and [HS91].
Any system allowing users to answer these questions must include two procedures. First, there must be a signing procedure with which (1) the author of a record can ``sign'' the record, or (2) any user can fix a record in time. The result of this procedure is a string of bytes that serves as the signature. Second, there must be a verification procedure by which any user can check a record and its purported signature to make sure it correctly answers (1) who and what? or (2) when and what? about the record in question.
The signing procedure of a digital timestamping system often works by mathematically linking the bits of the record to a ``summary number'' that is widely witnessed by and widely available to members of the public - including, of course, users of the system. The computational methods employed ensure that only the record in question can be linked, according to the ``instructions'' contained in its timestamp certificate, to this widely witnessed summary number; this is how the particular record is tied to a particular moment in time. The verification procedure takes a particular record and a putative timestamp certificate for that record and a particular time, and uses this information to validate whether that record was indeed certified at the time claimed by checking it against the widely available summary number for that moment.
One nice thing about digital timestamps is that the document being timestamped does not have to be released to anybody to create a timestamp. The originator of the document computes the hash values himself, and sends them in to the timestamping service. The document itself is only needed for verifying the timestamp. This is very useful for many reasons (like protecting something that you might want to patent).
Two features of a digital timestamping system are particularly helpful in enhancing the integrity of a digital signature system. First, a timestamping system cannot be compromised by the disclosure of a key. This is because digital timestamping systems do not rely on keys, or any other secret information, for that matter. Second, following the technique introduced in [BHS93], digital timestamp certificates can be renewed so as to remain valid indefinitely.
With these features in mind, consider the following situations.
It sometimes happens that the connection between a person and his or her public signature key must be revoked. For example, the user's private key may accidentally be compromised, or the key may belong to a job or role in an organization that the person no longer holds. Therefore the person-key connection must have time limits, and the signature verification procedure should check that the record was signed at a time when the signer's public key was indeed in effect. And thus when a user signs a record that may be checked some time later - perhaps after the user's key is no longer in effect - the combination of the record and its signature should be certified with a secure digital timestamping service.
There is another situation in which a user's public key may be revoked. Consider the case of the signer of a particularly important document who later wishes to repudiate his signature. By dishonestly reporting the compromise of his private key, so that all his signatures are called into question, the user is able to disavow the signature he regrets. However, if the document in question was digitally timestamped together with its signature (and key-revocation reports are timestamped as well), then the signature cannot be disavowed in this way. This is the recommended procedure, therefore, in order to preserve the non-reputability desired of digital signatures for important documents.
The statement that private keys cannot be derived from public keys is an over-simplification of a more complicated situation. In fact, this claim depends on the computational difficulty of certain mathematical problems. As the state of the art advances - both the current state of algorithmic knowledge, as well as the computational speed and memory available in currently available computers - the maintainers of a digital signature system will have to make sure that signers use longer and longer keys. But what is to become of documents that were signed using key lengths that are no longer considered secure? If the signed document is digitally timestamped, then its integrity can be maintained even after a particular key length is no longer considered secure.
Of course, digital timestamp certificates also depend for their security on the difficulty of certain computational tasks concerned with hash functions (see Question 2.1.6). (All practical digital signature systems depend on these functions as well.) The maintainers of a secure digital timestamping service will have to remain abreast of the state of the art in building and in attacking one-way hash functions. Over time, they will need to upgrade their implementation of these functions, as part of the process of renewal [BHS93]. This will allow timestamp certificates to remain valid indefinitely.