4 ms·
I'm curious why some people think that something like this would even be possible in principle. My first intuition was that this is impossible (at least not wi
by Padding 12y ago
I'm curious why some people think that something like this would even be possible in principle.
My first intuition was that this is impossible (at least not with math alone). I have no (proper) proof however.
Ultimately anything could be infinitely parallelized, by brute-forcing the answer itself. If we put the answer safely out of reach for brue forcing, then all that remains is a number of methods of actually calculating it. Those methods can either be arduous but applicable by everyone or fast but requiring some pre-known secret.
For a puzzle that could be solvable by more than one ardous method, it is to be expected that ultimately everyone would be using the fastest one of those - i.e. the author and the public alike, since the methods would be applicable by everyone.
For a puzzle that would be solvable by a fast method requiring some secret, the solution would always be brute-forcable on that secret, and thus have a wide timesrange in which it could be solved, depending on the level of parallelism.
The only way out I see here is to construct a puzzle with more than one arduous method - one of them obviously faster than the other, but only publish one of the methods and use the other one yourself to calculate the time-locked data. This may or may not be possible - but I don't think it's something that can be automated, since it requires creative input, considering how a new kind of puzzle would need to be created for every new piece (or at least every new author) of time-locked data, since otherwise the less-arduous methods would become public knowledge too.
(And of course there's always the risk of there being other smart people searching for and eventually discorvering that other less-arduous method, before the desired timespan has elapsed.)
- lmm 12y agoOf course it's possible to try all possible keys, and by definition that's parallelizable, but the idea is that that should be hard enough to be infeasible. Let me give an example that should be impossible according to your reasoning: Imagine I (magically) had a method that allowed one to disclose information that would allow someone to figure out an RSA private key after two years. That would clearly satisfy gwern's original requirements - it's easy to encrypt my data, publish the public key and the "magic hint". Yes, an attacker could just try all possible RSA private keys in parallel - but that's not a realistic attack.
- ZoFreX 12y ago> My first intuition was that this is impossible Isn't that the case for so many problems in cryptography, though? DH key exchange, zero-knowledge proofs, secure multi-party computation, fully homomorphic encryption - all achieve things you could be forgiven for assuming were impossible.
- Nursie 12y agoDid you read the part of the article about forcing serialisation of a parallel task by using hash chaining? That seems to provide a good way of making the encryption process fast but decryption very slow.