Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
add comment

3 Answers

up vote 8 down vote accepted

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
share|improve this answer
add comment

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.

share|improve this answer
    
I guess the assumption was that time remained linear. Obviously if you can manipulate time through the laws of physics all bets are off... damn physics, always telling us "yes, but..." :p –  Thomas Nov 2 '13 at 9:23
add comment

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.

share|improve this answer
2  
Actually a Lamport clock does use a trusted time source. The time in a Lamport clock is constructed from cooperating peers. In the scenario of this question, the peers participating in the Lamport clock would have to be trusted to some extent. –  Gilles Aug 14 '13 at 9:06
    
There are various Lamport clock protocol variants that are resilient against untrustworthy peers. If you combine the protocol of cs.dartmouth.edu/~sws/pubs/thesis.pdf with the encryption primatives of fkerschbaum.org/icpads07.pdf you get something that is a lot like cryptographically signed timestamps and that doesn't require a whole lot of trust of the peers. –  user8007 Aug 15 '13 at 0:15
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.