trusted time stamping

To: cypherpunks@toad.com

-----BEGIN PGP SIGNED MESSAGE-----

I thought my idea about having trusted entities digitally sign a document in
order to establish its existence at a particular time was a new idea, but I
just read about it in _Applied Cryptography_.  Anyway, I wrote some C code to
do automatic time stamping with PGP (source code is in the next e-mail).

If you just want to try it, simply send an e-mail to weidai@eskimo.com
with the subject "Time Stamp This Mail".  The body of the mail will
be signed with a PGP private key (public key is at the end of this message)
and returned to the sender.  E-mail with any other subject will be piped
to my regular mailbox.

What's the use of this?  Well, here is an interesting application of
time stamping that wasn't covered in _Applied Cryptography_.

Let's say Alice would like to publish an article anonymously but retain the
ability to claim authorship some time later.  She can follow this protocol:

1. Alice signs her article with RSA
2. She encrypts her signed article with IDEA
3. She sends the encrypted article to several trusted time stamping servers
4. She places the signatures she gets back along with the encrypted article
   in a safe place
5. She waits a random length of time
6. She posts the plain article (without encryption or signature) anonymously
7. When Alice wants to claim authorship, she publishes the encrypted article,
   the IDEA key, and the signatures she got back from the time servers

Now, people can be reasonably sure that Alice actually wrote the original
article because the time server signatures prove that she signed the
article before it was made public.  One problem here is that at
least one of the time servers she used must have remained secure until step 7.

Comments?

Wei Dai
PGP Public Key avaliable

-----BEGIN PGP SIGNATURE-----
Version: 2.3a

iQCVAgUBLlRtiTl0sXKgdnV5AQFr+gQAsymOrN/Zd3C94NebWZOVFcl2tCkd/cSW
EehvHxJMD1qO5fmmsDelhA+YKqqjLz8Dyp94pIqZXtWSu+kx/p5OUjB173PdAyN0
TSNaVMyZX266B/JIRqHI6+/5F2EWysFTXXH23v0mEH/us82Dvdb8rcqyKwQvjGZf
mOvhObHf8Fo=
=w0Q+
-----END PGP SIGNATURE-----

-----BEGIN PGP PUBLIC KEY BLOCK-----
Version: 2.3a

mQBNAi5UWcgAAAECALp+QU9dtN2N4BjVr8OSxRPXtZ6UX4bLGq8PxpXru6WpsBD/
SJUl6jK4YcnatNJmjkl9oEHC6fjTpwMbZVOWJE0ABRG0MFdlaSdzIFBHUCBUaW1l
IFN0YW1wIFNlcnZpY2UgPHdlaWRhaUBlc2tpbW8uY29tPokAVQIFEC5UWpenAxtl
U5YkTQEBzDQB/3+eNgnW22sRaZFpBY3Wfzj4uEVXXcYU4vrdS1fsSRixJSEKta/N
uyvmkeiB4GyyahhtHTtybywrRzD1y9IlwMmJAJUCBRAuVFmZOXSxcqB2dXkBAYNZ
A/4/KHOQ1gjPEkdLhdPJ/yaXyQilqWV+MWiHblrqcDOrsFu1dKizJrBdWa5+vuIX
nCu5DSq9cd3/cGrMOYK3OJGQC8JkPc6LNw7siuRGuVn413JBlM3wnCEXnFsAUhpG
hDLTPUC2JqmiCwQP6OpxwqlTxPmZk8wKE0Sh/iaGRwZnBg==
=vpgO
-----END PGP PUBLIC KEY BLOCK-----


PGP Public Key available

Wei Dai wrote:

> I thought my idea about having trusted entities digitally sign a document in
> order to establish its existence at a particular time was a new idea, but I
> just read about it in _Applied Cryptography_.  Anyway, I wrote some C code to
> do automatic time stamping with PGP (source code is in the next e-mail).

Stu Haber (who reads this list, sometimes) and Scott Stornetta of
Bellcore developed a system which solves the more important problem of
the time stamper reliability, which I don't think W.D. has addressed.

I've written up a couple of summaries, the last of which got a
favorable reaction from Stu on. So I'll mail it later today, when I
fire up my off-line archives and retrieve it.

The hard part is time stamper reliability, i.e., how does the world
(and the courts) know that the time stamper(s) did not simply reset
his clock and thus fake the times?

Haber and Stornetta came up with two clever ideas:

1. Publish a one-way hash of the text to be stamped in a very public place,
e.g., one's latest bestselling novel or the "New York Times." This is
similar to the crypto methods used by scientists through the ages to
prove ownership. H & S call this a "widely witnessed event," the idea
being that millions of copies of archived issued of the NYT (or the
novel!) would have to be retrieved and reprinted in order to change at
a later date the text. Economically impractical.

2. But it may also be economically impractical for the NYT to print
page after page of such hashes...they may choose not to,
understandably. So H & S developed a "tree"-like way to merge
customer-provided hashes with many other hashes (and earlier hashes,
to, thus adding to the difficulty of faking) and so to only have to
publish a comparatively small number.

These two clevernesses are the crux of time-stamping.

They are trying to build a company to do this; perhaps Stu can update
us on the status.

--Tim May


-- 
..........................................................................
Timothy C. May         | Crypto Anarchy: encryption, digital money,  
tcmay@netcom.com       | anonymous networks, digital pseudonyms, zero
408-688-5409           | knowledge, reputations, information markets, 
W.A.S.T.E.: Aptos, CA  | black markets, collapse of governments.
Higher Power: 2^859433 | Public Key: PGP and MailSafe available.
"National borders are just speed bumps on the information superhighway."

They are trying to build a company to do this; perhaps Stu can update
   us on the status.

I don't know if Stu's on the list right now or not, but I saw him
Tuesday in Manhattan.  They're in the middle of development, which
includes much more than simply writing the crypto protocol that's at
the core of any real business.

Eric