|Previous||Table of Contents||Next|
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, its 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. Its 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:
This protocol uses Trent, who has a trusted timestamping service, and Alice, who wishes to timestamp a document.
Now, if anyone calls into question Alices 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 Trents 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 Trents central computers, could completely invalidate Alices claim of a timestamp.
And fourth, there might not be someone as honest as Trent to run the timestamping service. Maybe Alice is using Bobs 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:
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 dont 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.
One way to solve this problem is to link Alices 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 cant be known in advance, Alices timestamp must have occurred after the previous one. And since the request that came after is linked with Alices timestamp, then hers must have occurred before. This sandwiches Alices request in time.
If A is Alices name, the hash value that Alice wants timestamped is Hn, and the previous time stamp is Tn - 1, then the protocol is:
If someone challenges Alices timestamp, she just contacts the originators of the previous and following documents: In - 1 and In + 1. If their documents are called into question, they can get in touch with In - 2 and In + 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.
|Previous||Table of Contents||Next|