10
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ What if you were to hash the document, then push the hash onto some hypothetical blockchain model. If the push is successful, it will be added to the next block in the blockchain. Each block will have a corresponding time stamp. $\endgroup$
    – aiwl
    Mar 23, 2021 at 5:04

4 Answers 4

12
$\begingroup$

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
$\endgroup$
1
  • $\begingroup$ I don't want to be that guy, but this legitimately sounds like a good use for a technology similar to blockchain/public ledger. $\endgroup$ Oct 18, 2018 at 8:38
4
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ 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 $\endgroup$
    – Thomas
    Nov 2, 2013 at 9:23
2
$\begingroup$

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.

$\endgroup$
2
  • 2
    $\begingroup$ 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. $\endgroup$ Aug 14, 2013 at 9:06
  • 2
    $\begingroup$ 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. $\endgroup$
    – user8007
    Aug 15, 2013 at 0:15
0
$\begingroup$

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)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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