"Time-lock puzzles and timed release Crypto"
https://people.csail.mit.edu/rivest/pubs/RSW96.pdf
FWIW it took me about 3.3 years of computation (on one core, it's not parallelizable), from about 2015/2016ish to 2019, to find the solution to Rivest' LCS35 problem (which he created in 1999, so I found the solution 20 years after he created that LCS35 puzzle):
https://en.wikipedia.org/wiki/LCS35
An article on WIRED for anyone interested (I'm still rocking the same monitor and same keyboard!):
https://www.wired.com/story/a-programmer-solved-a-20-year-ol...
Why is that? From what I see on Wikipedia ("n is a specific 616-digit (or 2048-bit) integer that is the product of two large primes (which are not given)" sounds like a textbook RSA public key), it's an offline brute force challenge, a guessing game, so different computers (or cores) could independently take different slices of the guessing space. I will admit that prime factorization is one of my weak spots and I'll just resort to a few minutes of running pari-gp for that, since I know it uses some algorithm that is much better than brute force (it was orders of magnitude faster than alternatives for a CTF challenge involving a 512-bit RSA key).
Even if the factorization process' time spent is dominated by finding the next prime to try, rather than testing a prime for correctness for example, why couldn't you start anywhere in the 2048-bit space and find the next primes from there? Is there something you can use from the ciphertext that makes you need to start at a certain point and generate (single core) from there onwards? It sounds like the holy grail for key strengthening without memory trade-off options like scrypt and argon2 both struggle with
Note that the puzzle can be solved by performing t successive squarings modulo n, beginning with the value 2. That is, set
W(0) = 2
W(i+1) = (W(i) ^ 2) (mod n) for i=1, 2, ...
and compute W(t).
There is no known way to perform this computation more quickly than to perform the t squarings sequentially, unless the factorization of n is known.
Time lock puzzles take variable time depending on hardware. You can’t really set an accurate specific release time.
Any change in the universe that a computer can detect is just another spoofable input.
Blockchain tries to solve essentially the same problem but the best it can reliably do is establish a chronology. That’s not a specific time. And it has fundamental vulnerabilities, however unlikely you think they are to be exploited in established systems.
Intel is building proof of elapsed time into their chips but that’s not trustless.
Timelock puzzles and blockchain are imo hacky solutions to one of the most important outstanding problems in cryptography: securely and trustlessly agreeing on elapsed time.
If it can't be measured then it can't be said to clearly exist.
Imagine a cellular automata where particles have lots of "slots" that could be used for moving or interacting. As the particle speeds up and more slots are used for moving, there are fewer slots for the kind of interaction change that we use to measure time. At the highest speed, with all possible slots used for motion, the particle would experience no change, which is indistinguishable from no time passing.
Does that sound familiar to anything? It's certainly possible that light being a speed limit, time dilation, relativity, and so on are in some way actually describing change rather than time.
Digital cryptography will always being a cat and mouse. DES, RSA, Elliptic curve... With intro of quantum computing, it will just fasten up the pace. Some government has start experimenting with quantum entanglement (https://apnews.com/article/china-google-justice-department-6...)
It is all about your threat model. Even that I'm sure someday some smart guy will also figure out how to figure out how to beat that.
*if the League of Entropy shuts down, members will delete their keys*
The world is unpredictable (just like drand randomness... heh), and it's possible that the League of Entropy will all hang up their coats at some point in the future. Should that happen, members would have two choices with their private keys: release them to the world or delete them entirely. The former would mean that ciphertexts created for some time after the cessation of the network would be decryptable to everybody. The latter would mean that ciphertexts created for some time after the cessation of the network would be unencryptable forever (/until quantum computers can break them). In the interests of privacy, we felt the latter option was preferable. That said, if you encrypt the private key to your [insert cryptocurrency name] fortune to stop yourself from spending it now and the network stops... you're going to have a bad time.The website's implementation is this:
> A group of [orgs] holds the keys. There are 18 separate organizations running a total of 22 nodes, with a threshold of 12 needed to release a secret.
> You can’t hide secrets from the future with math
> You can try, but I bet that in the future they laugh
> At the half-assed schemes and algorithms amassed
> To enforce cryptographs in the past
The Rivest, Shamir, and Wagner time lock algorithm is an example of one that can't be parallelized.
In theory the NSA and Google can't brute force it much faster than you can on a laptop.
I'm not an expert on DeFi but could we do something more time-precise using the Ethereum blockchain and a smart contract?
This is basically weaponized (and possibly automated) enforcement of a rule. It's not crypto, it's just "agree to this or you get the lead pipe". Lead pipes are extremely useful and valuable and this is a completely reasonable tradeoff in a huge amount of situations, but it's not a true barrier.
To get around the lead pipe requirement, you need some kind of data that exists but is technologically or physically inaccessible until time Y. Ethereum has no primitives like that because nobody has primitives like that. About the closest you get is to say "crack this public key to get the reward" and, yea, that's effectively time-lock encryption (it'll Y years with all the hardware in the world so it's "locked" for at least that long at 99% confidence or something) but nobody really considers it "time locked" unless you are intentionally designing a key to take Y time under Z hardware assumptions (which does exist, but a 1-PC-year key takes seconds with enough hardware).
I think only if you want a transaction to move forward at a certain time, and are confident that a majority of network members will not conspire to alter your smart contract.
Hiding information in a smart contract: I don't know of a way that could be done, but I'm not up-to-date on this stuff either (I left that scene after Bitcoin outgrew the tech demo phase and became popular as a "so long as a majority keeps buying and holding, everyone's coins are worth insane amounts!" scheme)
The oracles could be financially incentivized to behave properly. E.g. they post a bond, which is confiscated if they don't post a private key on time or if a whistleblower discovers and reports a key early. In return for correct behavior they can earn some fees paid by users of the service.
The financial incentive still flips if the secret's value is sufficiently large, but it would require coordination of many unprincipled oracles.
But it occurred to me that you can sort of do something like this with a proof of work-like algorithm, though the time to solve would still be variable.
Essentially you'd need a network of "miners" and instead of a block, you'd have a node encrypt a message with an encryption key of a set difficulty (decryption key length), based on the target decryption time and the network hash rate (hash rate probably is not the correct term, but I'll use it for conciseness).
The miners would then work to decrypt the data using the knowledge of the key length.
I'm not sure how you would incentivize the miners to work on decrypting it though, and the node which encrypted it would of course have knowledge of the message, so I don't see how this could be used in practice.
In theory if your miners were running something like a tamper-proof secure enclave (I'm not even sure if these truly exist) perhaps there's a way to attest their own hashrate, and then an encrypted message can be proposed by a node to a subset of miners which collectively have the assumed hashrate. The secret-encrypted data can then be re-encrypted for each miner, with their public key.
This ensures other miners not participating in the challenge can't attempt to decrypt the data.
The problem here is incentivization over a long period of attempting to decrypt the data. You'd have to offer a reward large enough to incentivize the miners to cooperatively work to decrypt the message for the longest possible amount of time it could take to decrypt the message.
edit: I think for this to work you'd first need to encrypt the data for each miner which should participate in the challenge, and then encrypt it with the secret key. That way a miner which solves this can publish the decryption key and the still-encrypted payload, which only they can decrypt, and all the other miners can apply the same solution to verify the published solution and solved message with their own private keys.
edit 2: I suspect there's something potentially useful here, but I don't know enough about secure enclaves to really know if it's feasible to implement in a way that prevents gaming, so if someone knows more about such things, feel free to take the idea and run with it.
> it’s become a reliable and production-ready core Internet service, relied upon by applications ranging from distributed file storage to online gaming to timestamped proofs to timelock encryption
Details: https://drand.love/docs/timelock-encryption/
Thread on the cited Cloudflare blog: https://news.ycombinator.com/item?id=39641475
> Each organization contributes its own unique source of randomness into the joint pool of entropy used to seed the drand network – with Cloudflare using randomness from LavaRand, of course!
It leads you to think that the each round's random value comes from "combining" local sources of entropy that each node contributes, but skimming the actual Drand protocol used, isn't it closer to something like using AES-CTR as a PRNG, except instead of AES it's some particular threshold-signature scheme. From another cloudflare post
>To instantiate the required threshold signature scheme, drand uses the (t,n)-BLS signature scheme of Boneh, Lynn and Shacham. In particular, we can instantiate this scheme in the elliptic curve setting using Barreto-Naehrig curves. Moreover, the BLS signature scheme outputs sufficiently large signatures that are randomly distributed, giving them enough entropy to be sources of randomness. Specifically the signatures are randomly distributed over 64 bytes.
So "real-world randomness" only is mixed in during the very initial distributed key generation phase, and after that everything is purely deterministic right? Or put another way those fancy lava lamps are a non-sequitur since this scheme doesn't seem to rely on their values beyond the initial key generation?
You're correct -- after the initial distributed key generation, the values produced by the drand network are deterministic (this is one of the properties that allows for timelock encryption). The security properties of drand rely on a threshold of nodes remaining uncompromised, but mixing in fresh randomness isn't necessary. (Although you could imagine having some drand chains that incorporate fresh randomness for properties like post-compromise security.)
> isn't the following quote from the Cloudflare blog misleading? >> > Each organization contributes its own unique source of randomness into the joint pool of entropy used to seed the drand network
If this is misleading it wasn't intentional! We used the word "seed" since the randomness from LavaRand is only mixed in when the network is initialized, but perhaps that could have been phrased better. Or perhaps we should have split it into separate blogs talking about LavaRand and drand since they're only tangentially related :).
I don't think the 'proxy' approach is timelock encryption, because it doesn't actually rely on the passage of time. Cloudflare is relying on a network of trusted agents that 'tick' at a predictable rate.
I think I wouldn't want to rely on this network of trusted agents to preserve a long-lived secret. There's no guarantee that the network will still exist when it's time to reveal thw secret.
Is there a way to do timelock encryption that doesn't involve reliance on a third-party, and that really depends on the actual time, rather than on a proxy for time? I cn't see it, but I'm not very clever.
So, in a sense, in my opinion, if you want to encrypt a message and send it to someone and make it timelocked without a third-party, you might as well just keep the message secret until the desired amount of time has passed and just give it to him.
There's no point in encrypting a secret to protect it from my own eyes; I already know the secret.
- If you use repeated hashing (or other measures of lengthy computation to derive a key) there's no guarantee that future computers won't be able to run your algorithm much faster than you did. A problem that will probably show up quite early with schemes of this nature.
- If you use the threshold approach listed here. Can you guarantee that the machines providing the service are still available when you need decryption? Moreso: that they don't end up being hacked between the encryption and decryption time-frames through some 0-day.
- You could use a hardware device to protect the keys. But this would mean that the devices weren't compromised by hardware attacks. We have seen Bitcoin wallets fall to hardware attacks and trusted computing environments like enclaves have numerous attacks that can be used to compromise their contents.
What makes time-lock encryption so challenging is you need a scheme that is intentionally weak so that's it's broken after a certain point. In cryptography that level of specificity isn't needed because schemes are designed to be well and truly secure past the life-times of all the subjects who use them. Even greater than the life of planets.
In these two options, you need to make a very long sequence of calculations to decrypt the message. Since the calculations cannot be parallized and since the sequence can be as long as you choose, it creates a time lock on the message.
But no, they just use some kind of regular multi-sig/secret sharing.
How does the math work? The decryption key is some kind of exponentiation you can compute directly with a trapdoor, but without the trapdoor you have to repeatedly multiply instead?
Start with some random 256-bit string as the seed. Iterate on it for t time using sha256 CPU instructions - by either repeatedly hashing the seed or increasing the number of rounds to an arbitrary value (and do something about the round constants, such as removing them).
After t time you stop and use the result to encrypt a message.
You then publish the encrypted message and seed + number of rounds you ended up using.
It will take t time before anyone can decrypt it. They will have to redo what you did, having multiple machines will not help in this task.
https://link.springer.com/article/10.1007/s00145-020-09364-x
Every pageview and API call is an invocation. You get 100,000 calls per day for free.
I operate a BitTorrent tracker I wrote for fun, and it receives around ~1500req/s (100mil+ a day)
This would be ~US$18/day with CF workers, but costs me €3.8/mo on my VPS
Paper: https://docs.google.com/document/d/e/2PACX-1vQe-OF0Lw9lutf6a...
I’m really not convinced that solution is better is any way. If your adversary has the resources to coerce the “leave of entropy” in the OP, cracking that blockchain implementation will be trivial.
Their design has the benefit over yours that people don't need to send data to peers in order to timelock some data. The timelock only needs to be sent to the peers for decryption.
ICANN is a cancer.
Who knows if this service will go down or something?
Might aswell just do this with one entity m
Even with some corrupted nodes, the message would still be secret, the only issue would be if the last nodes are corrupted : your message would be distributed too soon. But with enough layers and enough nodes to go through, you could mitigate this risk.
The network could even detect corrupted nodes if other nodes received the message too soon.
for robustness, the message should include the decrypt algorithm what about integrity and time travelers? i.e., can decrypt but just messing around with time
Step 1: Generate a large number of named public/private keypairs and put the private keys on a spacecraft. Also give the spacecraft a communication system and a long-lived RTG (an energy source getting its energy from the decay of some radioactive materials).
Step 2: Send the spacecraft to land on the surface a distant body in the solar system, such as one of the moons of Neptune.
Step 3: To encrypt a message such that it's guaranteed to not be cracked in less than some specified time, encrypt it several times, using the known named public keys.
To decrypt the message, you've got to send it out to the distant spacecraft and ask it to decrypt the outer layer of encryption, using the private key corresponding to the outer layer's public key. It does that and you get back a message but it might still have several layers of encryption. Repeat until all those layers are removed.
There are tricks to speed things up by sending a spacecraft out towards Neptune, but they don't speed things up too much (because spacecraft travel much slower than light). The amount of speedup possible is left as an exercise for the reader. There's still a lower bound on the required time until full decryption.
Inspired by the TOR network.
But, while fun, your idea is not that stupid.
If the spacecraft continuously generate key pairs, you could even avoid landing it and "just" throw it in some direction, Voyager style (if you can afford rebuilding some every few decades) or on some orbit in the solar system. You don’t have to pay for the landing tech.
I wouldn’t even be surprised that this could be viable economically. It doesn’t sound that much technologically difficult
My thinking now is that you could send the spacecraft out to Neptune and do a gravity-assist maneuver there, sending the spacecraft into a large orbit around the Sun, with a high perihelion.
Do you imagine there's a large market for physically-based time locked encryption?
Hard to imagine there's a ton of paying customers lol
Because it has such high delays? Basically revealing the information which the onion service or exit node encrypted for you only after, potentially, a few trips around the globe?
That makes me think this can be achieved without spacecraft, by just having geographically distributed private keys (even just a few kilometers; you just need the light delays to dominate over processing delays).
And I don't think you need more than two keys: if you wrap it in A(B(A(B(message)))), then party B cannot work on the first layer but first needs to send it to A, party A cannot decrypt the second layer but first needs to sent it back to B, etc. One of the parties could be your recipient, so that would also work with an expensive one-off spacecraft.
> land on the surface a distant body in the solar system
landing is a lot more difficult than staying in Neptune's orbit (notice how many moon-bound spacecraft crashed, even only in recent years!); you'll get the same characteristics by just going out to a desired orbit.
Also note that the amount of delay between Earth and <your orbit, such as Neptune's> will vary wildly
The problem that arise is (and which is solved by the spacecraft to Neptune) is that with any earth based system, someone could secretly move copies of both ends closer together, secretly, and decrypt the lock faster than expected. Putting a spacecraft on a trajectory with no realistic chance of ever coming back makes this possibility impossible (as long as the layers of keys are encrypted only when the spacecraft arrived at its destination. Even if the delay between earth and neptune vary wildly, it is predictable, and any local system could piggyback a larger scale system like this for safety
Neptune is about 30AU from the Sun. The Earth's distance from Neptune will presumably vary somewhere between 28AU and 32AU. Light travels 1AU in about 8 minutes, 28AU in about 224 minutes, 30AU in about 240 minutes, and 32AU in about 256 minutes. Depending on your use-case, that's not a particularly wild variation.
Your other critiques are all valid. There's still a lower bound on the total time required for full decryption. I was just trying to show that that is possible.
If I want my secret exposed in 20 years, I will need to wrap it in 18,000 layers of encryption, and then start the decryption process immediately.
The duration of one decryption step depends on the distance to the spaceship; it would be difficult (but not impossible?) to rely on a spaceship whose distance is always changing. It needs to be somewhere faraway, and also to be somewhere that's always going to be roughly the same distance away. A moon of Neptune is a reasonable candidate.
I checked your calculations and I get similar numbers. I don't think that tens of thousands of layers of encryption is a problem: a modern computer can store that many private keys with no problems. In fact, it should probably store three copies of each one, or do something to account for random bit flips.
Next, instead of pre-seeding the ship with keys, you have it generate them (using its RTG for both power and a source of entropy) and send them back to earth at a fixed rate, possibly with the size of the keys increasing over time.
On earth, when you want to encrypt a payload to be decrypted at a future date, you calculate how many round trips it would require, then encrypt the data with that many keys from the stream, interleaved with keys generated locally. As the time will unlikely be an exact round trip time (which is ever-increasing), each end can delay the decrypt and re-transmission for some proportion of the remaining time.
I suppose, more practically, you could just put the private key in an envelope and bury it deep in a shipping container with a destination across the ocean. While in transit it's pretty damn hard to get to it.
If you want your secret to last for decades, a shipping container is too vulnerable.
Sunken chest / mysterious treasure map
Beacon of high gamma radiation / undesirable to approach for many half lives
USB key in Jimmy Hoffas pocket
If the spacecraft is trusted by the person with the secret, it's much simpler to instruct the spacecraft to only disclose the secret after a set date. You don't seem to gain anything from the carded complexity.
If the spacecraft isn't trusted, there's nothing it stopping it disclosing all the key pairs at once.
I think the best bet at the moment is something like Rivest-Shamir-Wagner time lock puzzles, which requires a fixed number of sequential computations to perform.
The economics of your proposal strike me as a tad weak at the knee.
In any case, I just wanted to show that working timelock encryption system is theoretically possible. Some people claimed it wasn't.