Is there an algorithm or hardware that can sign/verify natural time?

Question

PGP/GPG can used to sign text, others use public key to verify them. So one could say, that these cryptographic algorithms deal with space.

Are there any algorithms that can deal with time? E.g. I sign a document at 2011-10-10 10:10:10, others can verify this document is really, truly signed at 2011-10-10 10-10-10.

I know there are solutions based on a common trusted time source (a notary), but is it possible that a pure algorithm solution exists?

Or perhaps some amazing dedicated piece of hardware can do this? (E.g. half-life of certain well-known material, etc.)

In a simple way: Can we give nature a private key and ask nature to sign our documents using a natural timestamp?

Answer 1

A pure algorithmic approach does exist, however it only provides a fuzzy bound. It is related to the proof of work / client puzzles I described in this answer.

The signer will sign the message using a normal digital signature, and use the message and signature to instantiate a "cryptographic puzzle." A cryptographic puzzle is a moderately hard function that takes a certain number of CPU cycles (or memory accesses) to compute. The signer will then immediately begin to solve the puzzle.

Later, if a dispute arrises as to when the message was signed, the dispute can be resolved when the signer eventually produces the solution to the puzzle. The verifier checks that the solution is correct and then backdates the creation of the puzzle according to how hard it is (e.g. a solution to a puzzle that takes a year to solve means the puzzle must have been created at least a year ago). Since the exact puzzle being solved is specific to the message and signature, the message and signature must have been created before the puzzle.

Conceptually, the scheme is neat but it has a number of practical drawbacks:

• You can't put an exact bound on the resources available to the signer and therefore cannot timestamp accurately
• No puzzle of this type is known that is (a) inherently sequential (parallel computing does not help) and (b) can be created with the solver not knowing (or efficiently computing) the solution. For example, time-release crypto has (a) but not (b). Hash-based proof of works (like in Bitcoin) have (b) and not (a).
• The signer must devote an entire CPU to solving the problem for as long as it takes