2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Jan 25 '17 at 15:54
  • $\begingroup$ 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. $\endgroup$ – MaiaVictor Jan 25 '17 at 15:57
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Jan 25 '17 at 16:01
  • $\begingroup$ Yep, I think you're right. So what I want is clearly impossible. $\endgroup$ – MaiaVictor Jan 25 '17 at 16:14
2
$\begingroup$

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.

For more on timelock puzzles, see also:

and papers in the cryptographic research literature.

$\endgroup$
  • $\begingroup$ Is there anything you don't know? Recommend me resources to download your brain, please... $\endgroup$ – MaiaVictor Jan 25 '17 at 18:23
  • $\begingroup$ @MaiaVictor, oh, there are lots of people who know far more than me -- I suspect you've just managed to hit a few topics that I do know a little bit about. Glad it helped! $\endgroup$ – D.W. Jan 25 '17 at 18:34
  • $\begingroup$ But really, if you're not too busy, could I ask you personal opinions about some things? I'd honestly love to, but I understand you're probably a very busy person. $\endgroup$ – MaiaVictor Jan 25 '17 at 18:45
  • $\begingroup$ I'm wondering if there is some similar scheme that could easily prove that some document is old? For example, if I keep hashing the same document consecutively for a long, long time, after a few years I'll have a proof it is really old. Sadly that proof will take the same amount of CPU time to verify :) $\endgroup$ – MaiaVictor Feb 9 '17 at 17:10
  • $\begingroup$ @MaiaVictor, want to ask that a separate question, so that others wondering the same thing can also find the question and any answers, and so that others can contribute answers? $\endgroup$ – D.W. Feb 9 '17 at 17:57

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.