# Is there any problem that is hard to solve, can produce N equiprobable outputs and is easy to verify?

I'm looking for a problem that allows me to generate random instances which:

1. Take arbitrary time to compute (i.e., I can generate an instance that I know would take at least 10 days to solve in an Intel I7);

2. Is inherently sequential (no matter how many processors you throw at it, it won't be solved faster than 10 days);

3. Can produce N (say, 2^256) equiprobable outputs;

4. Given an output, it is easy to verify it is correct.

Example:

1. Find the smallest N such that sha256^N(seed) < K. You can configure K so that it would take no less than X days given current hardware. The final hash can be any one of 2^256 possible values. But verifying is hard: the only way to prove an N is correct is re-doing the whole computation, so it doesn't really fit.

2. Find an N such that sha256(seed+N) < K. You can configure K so that it would take no less than X days given current hardware. The final hash can be any one of 2^256 possible values. It is easy to verify the output is correct. But it is embarrassingly parallel.

• Base your method on some NP-complete problem. This is exactly the set of problems which is easy to verify but conjectured to be hard to compute. In particular, something like planted clique or planted SAT might work. – Yuval Filmus Jan 25 '17 at 15:54
• But all NP-complete problems I know aren't inherently sequential. The TSP decision problem, for example; you can try as many instances in parallel as you want. – MaiaVictor Jan 25 '17 at 15:57
• If your problem is easy to verify, you could always solve it by just searching for the solution together with the witness, and that parallelizes. – Yuval Filmus Jan 25 '17 at 16:01
• Yep, I think you're right. So what I want is clearly impossible. – MaiaVictor Jan 25 '17 at 16:14

Requirements 1-3 describe a timelock puzzle, also known as timed-release cryptography or time capsule cryptography. For instance, https://crypto.stackexchange.com/q/606/351.

Requirement 4 says it also has to be easy to verify a correct solution. I don't know of any standard scheme for timelock puzzles that happens to satisfy all four requirements, but you can invent one.

For instance, here is one simple approach that works, if you trust the creator of the puzzle to not try to play games with you. The creator picks a random AES key $k$, encrypts $k$ using the timed-release cryptography / timelock puzzle, and publishes the ciphertext as well as a SHA256 hash of $k$. Now requirements 1-3 are satisfied (it'll take a precisely-controllable amount of time for anyone else to recover $k$), and once you've found $k$, it is easy to verify that you found it correctly by hashing it and comparing the result to the publicly known hash.