# Time Capsule cryptography?

Does there exist any cryptographic algorithm which encrypts data in such a way that it can only be decrypted after a certain period of time?

The only idea that I can think of, is something like this: Seed a PRNG with a public value. Run the PRNG for a week and use the final value it produces to encrypt the message. Now anyone who runs that PRNG for a week starting from the seed value you made public can decrypt the message. Obviously this breaks down since they could use more computational power than you; if the time span was years then Moore's Law would apply, etc.

Is there anything like this other than physically burying a private key on a USB stick in a literal time capsule?

-

5
<tongue-in-cheek> Use the headline from the front page of the New York Times, dated Sept-1-2015 as your encryption key. Your data will remain safe until then.</> For the rest of us - Nick's answer is a good one. =) – Tails Jun 23 '11 at 5:47
Butterflies aside, that would be a good way to prove your time travel machine works. :P – Jake Jun 24 '11 at 16:58
If you had to enter the key into a black box and it was programmed to function as a time lock, then it could wait to decrypt until the time is reached, but no algorithm will do this on its own. – James Black Oct 22 '11 at 0:46
And any "black box" could be reverse engineered. – Chris Lively Oct 22 '11 at 0:51

## 14 Answers

Yes.

There has been a lot of work on "proof of work" protocols or "time-lock puzzles." Typically in cryptography, functions are either easy to compute or intractable. These protocols look at functions that are moderately hard to compute.

To do time-release encryption, you need a puzzle with the following properties:

1. Difficulty of the puzzle can be monotonically increased according to some difficulty parameter
2. Best algorithm to solve it is intrinsically sequential (parallel computing doesn't help)
3. Amortized cost of solving a group of puzzles is the same as a single puzzle
4. There is a trapdoor (shortcut) that allows efficient evaluation of the puzzle

With time-release crypto, the idea is to generate a puzzle that will take a certain amount of time to solve based on an estimate of a person's computational power and how it will grow in the future (e.g., Moore's law). As you can tell, it only gives you a fuzzy indication of how long it will stay secret (see below for a real world example). Property 2 is very important because adding parallel computation is easy and it is hard to estimate how much parallelization is possible.

Note that most proof of work protocols do not care about property 2 because they are used in different ways. These might be based on finding partial collisions/preimages in hash functions or exhaustive search of a small space (e.g., bitcoin), however speedups with parallel computing is trivial in these examples. There are also a number of memory-based puzzles that require lots (more than can be cached) of memory accesses, which is a more predictable measure of time on computers.

Back to time-release crypto. The idea is to instantiate a puzzle $p$ with difficulty $d$: $p=\mathsf{Puzzle}(d)$. A trapdoor $t$ for efficiently solving it is known to the person who generates the puzzle. This person then encrypts her message under key $k$ with a normal encryption function: $c_1=\mathsf{Enc}_k(m)$. She then release an "encryption" of the key she used by combining the key with the solution to the puzzle. Note that she can efficiently solve the puzzle with trapdoor $t$ but the recipient can't. She computes: $c_2=k \oplus \mathsf{Solve}_t(p)$. The ciphertext is $c_1,c_2$ plus a description of the puzzle.

To decrypt, the recipient computes $s=\mathsf{Solve}(p)$, which should take a moderate amount of time. He then recovers the key by $k=c_2\oplus s$, and can then decrypt $c_1$.

The disadvantage to time-release cryptography is that the recipient must devote an entire processor to solving the problem for the period of time that it should remain secret.

The best proposal for a Puzzle with the right properties is due to Rivest, Shamir and Wagner in this paper. It is based on repeated squaring in RSA groups. A recent result precludes any intrinsically sequential time-lock puzzles in the random oracle model (e.g., based on hashing).

In 1999, Rivest created a time capsule message to commemorate the 35th anniversary of MIT's Laboratory for Computer Science. He talks about how he designed it to require 35 years to decrypt. It is an interesting read.

-

1
Interesting. The problem is, of course, that it doesn't guarantee that anyone will decrypt whatever the secret is, only that they could given a certain amount of time. If what you want is for your secret to become public, you might not want to risk nobody trying to break it. Doing it yourself is a non-answer for a couple of reasons. – Steve Dispensa Sep 3 '11 at 17:08
Requiring a certain amount of computation isn't the same as requiring a certain amount of time to pass, though. – Nick Johnson Sep 4 '11 at 13:04
– Ian Boyd May 12 '12 at 19:17
@IanBoyd The puzzle can be efficiently created. It's solving it that's difficult. – Thomas Dec 27 '12 at 13:37

No.

See the following. http://www.gwern.net/Self-decrypting%20files

It has a decent list of ways you might try to do it. However, there is no guaranty that the desired amount of time would actually elapse until the "lock" was broken. In other words, significantly more or significantly less time might be required.

Now, some MIT guys did something in '99 that they hope will be opened in 2034. however, again, they do leave open the possibility that it could be broken earlier.. or not in anywhere near the amount of time they estimate.

http://people.csail.mit.edu/rivest/lcs35-puzzle-description.txt

Most of the ways available depend on needing to run an operation on a computer that will take a certain amount of time before the final decryption key can be obtained. However, you have no control over hardware. Ergo, you have no real control over the amount of time that would elapse before the final decryption key is acquired.

The MIT guys did mention that they took "Moore's Law" into account. However, most people would argue that Moore's Law has very little to do with overall processing performance. The law was about the doubling of transistor counts every 2 years; however processor performance has very much outstripped that.

The info on this site says pretty much the same thing: http://dl.acm.org/citation.cfm?id=888615

The secondary way is to give the key to a trusted third party who will only reveal it at a certain point in time. However, this is just as tricky because they may be forced using any number of mechanisms to release it earlier or they may even lose it somewhere along the way.

So, the answer is that there is no implementation accepted by anyone as "secure". There can't be.

-

I suspect most things encrypted with a scheme such as this will be opened late or never, because nobody is prepared to put that much effort into opening it (eg, nobody cares). – Nick Johnson Oct 24 '11 at 4:52

With neither a trusted third party nor trusted hardware, we know no system with an even mildly accurate delay of release.

If we accept a trusted third party, there are options. For example:
The trusted third party generates a public/private key pair per hour (for an asymmetric cipher such as RSA-OAEP), publish the public $Pub_t$ keys in advance (signed with the long-term public key of the third party), and publish a regularly updated list of all the past private keys $Priv_t$.
To time-lock some information $P$ until $t$: fetch $Pub_t$, and its signature, from the trusted third party; check the signature; draw a random key $K$ for a symmetric cipher such as AES-CTR; encipher $K$ using key $Pub_t$ giving $KT$; encipher $P$ using key $K$ giving $C$; forget $K$ and $P$; publish the time-locked information $KT||C$.
When time $t$ has come, anyone can fetch $Priv_t$ from the trusted third party; decipher $KT$ using key $Priv_t$ giving $K$; decipher $C$ using key $K$ giving $P$.
In a variant, the trusted third party generates deterministically the $Pub_t$/$Priv_t$ pairs from a master key and $t$; this allows arbitrary precision for $t$ with constant storage.

Trusted hardware with a trusted real-time clock (e.g. some HSM) can be used to implement the time lock (or to implement the above trusted third party).

With trusted hardware lacking a trusted real-time clock (e.g. a Smart Card), the clock can be delegated to a trusted third party. I believe (never done it) that buying a certificate from a certification authority also buys a free service, which answers unauthenticated queries "is this certificate still valid?" with a signed answer "this certificate was still valid at time $t$", which the trusted hardware can check (against the trusted third party's long term public key) to determine that the current time is at least $t$ (on the trusted third party's clock), regardless of how this signed answer has reached the trusted hardware.

-

• Ronald Rivest, Adi Shamir, and David Wagner. Time-lock puzzles and timed-release Crypto. March 1996.

That paper describes how to encrypt a message $M$, so that decrypting $M$ requires a controlled amount of computation (say, $T$ CPU cycles).

Here is the gist of the main scheme. To encrypt, Alice chooses large primes $p,q$ and computes a RSA modulus $n=pq$. Alice also picks an integer $t$ large enough that performing $t$ modular squarings (modulo $n$) will take the decryptor about $T$ CPU cycles. Alice then picks a random value $a$ and computes $b = a^{2^t} \bmod n$; she then uses $b$ as a secret key to encrypt her message (e.g., with AES).

Alice gives the RSA modulus $n$ to the decryptor, and the number $t$. The decryptor can recompute $b$ by squaring $a$, repeatedly squaring $t$ times (modulo $n$ each time). Thus, it will take the decryptor about $T$ CPU cycles to decrypt.

In contrast, Alice can encrypt using much less than $T$ CPU cycles, using the following trick. Alice computes $e = 2^t \bmod \varphi(n)$. Here $\varphi(n) = (p-1)(q-1)$, so Alice can compute $\varphi(n)$, but no one else can. Moreover, Alice can compute $e$ using $2 \log t$ squarings and multiplications modulo $\varphi(n)$, which takes vastly less than $T$ CPU cycles. Alice then encrypts using $b = a^e \bmod n$. Thus, Alice can encrypt much more efficiently than the recipient can decrypt.

To put it another way, Alice can create a puzzle whose difficulty she can control very precisely. The only way to decrypt is to solve the puzzle. For instance, she can arrange that it will probably take about 20 years to decrypt. Moreover, creating the puzzle is much quicker than solving it (she can create the puzzle in seconds, even though it will take decades to solve it). This provides a way to send a message that can only be decrypted after performing a certain amount of computation, i.e., after a certain amount of time.

The paper also describes another way to solve the problem, if one has a trusted agent (perhaps implemented using TCG, or perhaps considered trustworthy for other reasons).

-

There is such a kind of primitive in the article about timed commitments from Boneh and Naor. This is a kind of encryption scheme where decryption can be forced, but at a heavy non parallelizable cost, and such that it can be proven in advance, at low cost, that forced decryption will work. It relies on repeated squarings modulo a RSA modulus.

-

The problem with all of these schemes is that someone has to do it. If you tune the work to match your guess at your primary adversary's compute power, and you guess that your adversary has many times your compute power, then you guarantee that nobody but your adversary or someone with more resources than he will be able to decrypt your secret. If you want two things -- 1) it becomes public after time T 2) it becomes public not long after T -- then this system doesn't get you there. You can't do it yourself, and your adversary might decide not to do it. – Steve Dispensa Sep 3 '11 at 20:25

Because there's no inherent sense of time for a computer, there's not really any way to accomplish this. The best you could do would be to require a lot of computation and try to make it have to be as serial as possible. But even if there's a good way to do that, faster computers could do it more quickly.

If you want something to stay encrypted for a fixed amount of time, your best bet would be to encrypt it using any standard scheme and lock the key or keys in a time-lock safe.

-

Set up a relay on alpha centauri and transmit the key to it. Absolutely guaranteed 8 year delay until the key is available.

-

2
But couldn't there side-channel attacks (like someone intercepting the data on the way)? – Paŭlo Ebermann♦ Oct 22 '11 at 22:08
use public key encryption to communicate with your relay site :) – ddyer Dec 23 '11 at 21:29

InfoBiology by printed arrays of microorganism colonies for timed and on-demand release of messages is a recently development method that leverages biological systems to create messages that impose a limit on the amount of time it takes to learn a message.

The idea is simply to encode a message in a pattern of e. coli colonies. The message is released after the e. coli colonies have been growing in a particular growth medium for a certain period of time (the phenotypic expression of the e. coli is designed to have a particular lag time).

-

– Ilmari Karonen Sep 28 '11 at 16:31
– Ethan Heilman Sep 28 '11 at 16:57

Going with the theme of out-of-the-box solutions started by e501, I do recall at least a half-serious suggestion that, with a retransmitter (or just a big mirror) placed in outer space at a suitable distance from Earth, one could use light-speed lag as an effective time capsule mechanism — just encode the message as a laser pulse and send it out for a round trip of as many light years as you want to delay it by in years.

In principle, you could also do this just by bouncing the light off naturally occurring objects in space, like planets or stars or nebulae. However, the transmission losses involved in this would probably make it infeasible without extremely powerful transmitters and sensitive receivers, to the point where it's not at all clear whether it would actually be any more practical than just launching a huge retroreflector out into space. Also, the brighter the outgoing pulse is, the bigger the risk that scattering from gas and dust along the way might provide a side-channel attack.

-

1
Finally a solution involving uncheatable physical time – Tobias Kienzler Aug 13 '12 at 13:09

I'm thinking some sort of Ironkey like device, where the crypto and clock are internal to the device and encapsulated in such a way that if they are physically tampered with, the chip (and the key) self-destructs.

-

Since there's no way to control your execution environment, there's no way to ensure your algorithm is executed as described, with the actual current time. Thus, the only way to ensure something like this is to make it computationally difficult to decrypt, which is a limit on the amount of computational effort spent, not on the amount of real time spent. The easiest way to do this would be to encrypt the data with a short private key, and require people to factor the public key in order to unlock it.

-

1
Maybe clinging to an ongoing factoring effort could be useful - e.g. if you know that some project works on factoring some large composite number, use this number as part of your RSA public key to encrypt your message. (Of course, this might not work at all if the number in question has more prime factors than RSA allows - and if it is a number created by someone, this someone might already know the factors.) – Paŭlo Ebermann♦ Sep 3 '11 at 12:43
Requiring people to factor the public key is not a good basis for a solution, because factoring a public key is a task that can be parallelized, and thus the computation needed to factor cannot be easily related to passage of time. You want an inherently sequential problem. See my answer for one solution. – D.W. Sep 4 '11 at 4:46

I would try an aproach with a web service. Once you own the server you can rely on the date it has. You crypto information should contain a date that the server validates an once this is reach you can provide real decryt key for user.

-

Check out "Time-Lapse Cryptography". Seems like a pretty good system. I doubt the infrastructure is currently in place to support it, but you never know what the authors have out there.

-

Two big problem with the "it will take a computer 20 years to crack it" idea

1. It will only take 2 years for 10 computers to crack it

2. brute force cracking is a random process, so it could be cracked almost instantly, at very low admittedly, but not quite zero , probability.

Oh I suppose you could encode using a really really large key .The brute force crack techqnique might then have the expected crack time of 200 years. But the key is calculable, using a process that must be linearly done, so that no parallism is allowed, and it will take 20 years at 20 Gigaflops to process. Actually the speed limit is around 4 Ghz so recently cpu pwoer is coming from parallelism.. which cannot help a linear algorithm... But there is a risk that someone would divise a way to find the resulting key without doing all the intermediate calculations, and thus turn 20 years into a short time ..

-

2
Point 2 is not a very convincing argument, to be honest. Just because the probability is not zero doesn't mean it's going to happen. Also, speed limit is more like 9GHz, at least to public knowledge. – Thomas Dec 31 '12 at 5:08
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 69, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9466741681098938, "perplexity_flag": "middle"}