Consider two questions that may be asked by a computer user as he or she views a digital document or on-line record. (1) Who is the author of this record - who wrote it, approved it, or consented to it? (2) When was this record created or last modified?
In both cases, the question is one about exactly this record-exactly this sequence of bits - whether it was first stored on this computer or was created somewhere else and then copied and saved here. An answer to the first question tells who & what: who approved exactly what is in this record? An answer to the second question tells when & 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 3). Such a system was first proposed in [DH76] and there is a wide variety of accepted designs for an implementation of this kind of system [NIS94b][RSA78].
A system for answering the second question is called a digital timestamping scheme. Such systems were described in [BHS93][HS91], and an implementation is commercially available from Surety Technologies (<http://www.surety.com/>).
Any system allowing users to answer these questions reliably for all their records must include two different sorts of procedures. First, there must be a certification 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 small certifying file, a certificate if you will, that captures the result of this procedure. Second, there must be a verification procedure by which any user can check a record and its accompanying certificate to make sure it correctly answers (1) who and what? or (2) when and what? about the record in question.
The "certificate" returned by the certification procedure of a digital signature system is usually called a signature ; it is a signature for a particular signer (specifying whom) and for a particular record (specifying what). In order to be able to "sign" documents, a user registers with the system by using special software to compute a pair of numbers called keys - a public key and a corresponding private key. The private key should only be available to the user to whom it belongs, and is used (by the certification or "signing" procedure) in order to sign documents; it is by employing the user's private key that the signature and the record are tied to that particular user. The public key may be available to many users of the system, and is used by the verification procedure. That is, the verification procedure takes a particular record, a particular user's public key, and a putative signature for that record and that user, and uses this information to check whether the would-be signature was correctly computed using that record and the corresponding private key.
Special computational methods are employed for signing documents and for verifying documents and signatures; when these methods are carefully implemented, they have the remarkable property that the knowledge of a user's public key does not enable an attacker or hacker to figure out the user's corresponding private key. Of course, if, either through carelessness or deliberate intent, someone else - a hacker, for example - gains access to the user's private key, then this person will be able to "forge" the legitimate user's signatures on documents of the hacker's choice. At that point, even the value of legitimately signed records can be called into question.
The "certificate" returned by the certification procedure of a digital timestamping system is a certificate for a particular record (specifying what) at a particular time (specifying when). The procedure 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.
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, if the user's secure access to the private key is accidentally compromised; or when the key belongs 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-repudiability 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 one-way hash functions (see Question 94). (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.