Here's one way such a system could work. Suppose Alice signs a document and
wants it time-stamped. She computes a message digest of the document using
a secure hash function (see Question 3.8.2) and then sends the
message digest (but not the document itself) to the DTS, which sends her in
return a digital time-stamp consisting of the message digest, the date and
time it was received at the DTS, and the signature of the DTS. Since the
message digest does not reveal any information about the content of the
document, the DTS cannot eavesdrop on the documents it time-stamps. Later,
Alice can present the document and time-stamp together to prove when the
document was written. A verifier computes the message digest of the
document, makes sure it matches the digest in the time-stamp, and then
verifies the signature of the DTS on the time-stamp.
To be reliable, the time-stamps must not be forgeable. Consider the
requirements for a DTS of the type just described. First, the DTS
itself must have a long key if we want the time-stamps to be reliable
for, say, several decades. Second, the private key of the DTS must be
stored with utmost security, as in a tamperproof box. Third, the date
and time must come from a clock, also inside the tamperproof box, which
cannot be reset and which will keep accurate time for years or perhaps
for decades. Fourth, it must be infeasible to create time-stamps
without using the apparatus in the tamperproof box.
A cryptographically strong DTS using only software has been implemented by
Bellcore; it avoids many of the requirements just described, such as
tamperproof hardware. The Bellcore DTS essentially combines hash values of
documents into data structures called binary trees, whose ``root'' values
are periodically published in the newspaper. A time-stamp consists of a set
of hash values which allow a verifier to recompute the root of the tree.
Since the hash functions are one-way (see Question 3.8.2), the
set of validating hash values cannot be forged. The time associated with
the document by the time-stamp is the date of publication.
The use of a DTS would appear to be extremely important, if not essential,
for maintaining the validity of documents over many years (see Question
3.3.17). Suppose a landlord and tenant sign a twenty-year lease.
The public keys used to sign the lease will expire after, say, two years;
solutions such as recertifying the keys or resigning every two years with
new keys require the cooperation of both parties several years after the
original signing. If one party becomes dissatisfied with the lease, he or
she may refuse to cooperate. The solution is to register the lease with the
DTS at the time of the original signing; both parties would then receive a
copy of the time-stamp, which can be used years later to enforce the
integrity of the original lease.
In the future, it is likely that a DTS will be used for everything from long-term corporate contracts to personal diaries and letters. Today, if an historian discovers some lost letters of Mark Twain, their authenticity is checked by physical means. But a similar find 100 years from now may consist of an author's computer files; digital time-stamps may be the only way to authenticate the find.