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-12-31 23:59:59, others can verify this document is really, truly signed at 2011-12-31 23:59:59.

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

Answer 2

I don't think there is a pure-cryptography solution to this. Suppose you built a chip, and it time-stamped whatever message you wanted, using an internal atomic clock. For the sake of argument, let's say that it's unhackable, and totally tamper-proof.

Well, there's still a loophole. Put the chip on a spacecraft and speed it up to 99% the speed of light for a few years. Now you can back-date messages from it.

Answer 3

A cryptographically secure Lamport clock (perhaps done using homomorphic encryption) would have a lot of the same properties though, and doesn't require a trusted timesource.

Answer 4

OP wanted to "ask nature to sign our documents" and PulpSpy suggested there should be a long-running computation that started from the time of signage - Blockchain is both.

Simple timestamp verification protocol:

1. Create new bitcoin address and keys.
2. Transfer any amount to that address.
3. Transfer it back to your wallet using the private key you created.
4. Attach said private key to the signature of the document you wanted to sign and time-validate.

At the cost of 2 (bitcoin?) transactions - you have achieved your "signed by nature" protocol.

(minor improvement - if you transfer less money than the cost of the transaction - you can just leave it there. Anyone could get it, but no-one would due to cost)