Chapter 4
Intermediate Protocols

4.1 Timestamping Services

In many situations, people need to certify that a document existed on a certain date. Think about a copyright or patent dispute: The party that produces the earliest copy of the disputed work wins the case. With paper documents, notaries can sign and lawyers can safeguard copies. If a dispute arises, the notary or the lawyer testifies that the letter existed on a certain date.

In the digital world, it’s far more complicated. There is no way to examine a digital document for signs of tampering. It can be copied and modified endlessly without anyone being the wiser. It’s trivial to change the date stamp on a computer file. No one can look at a digital document and say: “Yes, this document was created before November 4, 1952.”

Stuart Haber and W. Scott Stornetta at Bellcore thought about the problem [682, 683, 92]. They wanted a digital timestamping protocol with the following properties:

— The data itself must be timestamped, without any regard to the physical medium on which it resides.

— It must be impossible to change a single bit of the document without that change being apparent.

— It must be impossible to timestamp a document with a date and time different from the present one.

Arbitrated Solution

This protocol uses Trent, who has a trusted timestamping service, and Alice, who wishes to timestamp a document.

(1)  Alice transmits a copy of the document to Trent.

(2)  Trent records the date and time he received the document and retains a copy of the document for safekeeping.

Now, if anyone calls into question Alice’s claim of when the document was created, she just has to call up Trent. He will produce his copy of the document and verify that he received the document on the date and time stamped.

This protocol works, but has some obvious problems. First, there is no privacy. Alice has to give a copy of the document to Trent. Anyone listening in on the communications channel could read it. She could encrypt it, but still the document has to sit in Trent’s database. Who knows how secure that database is?

Second, the database itself would have to be huge. And the bandwidth requirements to send large documents to Trent would be unwieldy.

The third problem has to do with the potential errors. An error in transmission, or an electromagnetic bomb detonating somewhere in Trent’s central computers, could completely invalidate Alice’s claim of a timestamp.

And fourth, there might not be someone as honest as Trent to run the timestamping service. Maybe Alice is using Bob’s Timestamp and Taco Stand. There is nothing to stop Alice and Bob from colluding and timestamping a document with any time that they want.

Improved Arbitrated Solution

One-way hash functions and digital signatures can clear up most of these problems easily:

(1)  Alice produces a one-way hash of the document.

(2)  Alice transmits the hash to Trent.

(3)  Trent appends the date and time he received the hash onto the hash and then digitally signs the result.

(4)  Trent sends the signed hash with timestamp back to Alice.

This solves every problem but the last. Alice no longer has to worry about revealing the contents of her document; the hash is sufficient. Trent no longer has to store copies of the document (or even of the hash), so the massive storage requirements and security problems are solved (remember, one-way hash functions don’t have a key). Alice can immediately examine the signed timestamped hash she receives in step (4), so she will immediately catch any transmission errors. The only problem remaining is that Alice and Trent can still collude to produce any timestamp they want.

Linking Protocol

One way to solve this problem is to link Alice’s timestamp with timestamps previously generated by Trent. These timestamps will most probably be generated for people other than Alice. Since the order that Trent receives the different timestamp requests can’t be known in advance, Alice’s timestamp must have occurred after the previous one. And since the request that came after is linked with Alice’s timestamp, then hers must have occurred before. This sandwiches Alice’s request in time.

If A is Alice’s name, the hash value that Alice wants timestamped is H_n, and the previous time stamp is T_{n - 1}, then the protocol is:

(1)  Alice sends Trent H_n and A.

(2)  Trent sends back to Alice:

T_n = S_K(n,A,H_n,t_n,I_{n - 1},H_{n - 1},T_{n - 1},L_n)

where L_n consists of the following hashed linking information:

L_n = H(I_{n - 1},H_{n - 1},T_{n - 1},L_{n - 1})

S_K indicates that the message is signed with Trent’s private key. Alice’s name identifies her as the originator of the request. The parameter n indicates the sequence of the request: This is the nth timestamp Trent has issued. The parameter t_n is the time. The additional information is the identification, original hash, time, and hashed timestamp of the previous document Trent stamped.

(3)  After Trent stamps the next document, he sends Alice the identification of the originator of that document: I_{n + 1}.

If someone challenges Alice’s timestamp, she just contacts the originators of the previous and following documents: I_{n - 1} and I_{n + 1}. If their documents are called into question, they can get in touch with I_{n - 2} and I_{n + 2}, and so on. Every person can show that their document was timestamped after the one that came before and before the one that came after.