Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Follow-up to: Parallel-resistant proof-of-work scheme?

Is there a proof-of-work scheme that:

  • can only be solved serially;
  • given the solution, can be verified in minimal time;
  • deterministically constructs the problem from some input, where the difficulty varies randomly dependent upon the input;
  • can be verified by any third-party.

I've looked into Time-lock puzzles and timed-release crypto (1996) [Rivest & Wagner] and Time-Lock Puzzles in the Random Oracle Model (2011) [Mahmoody, Moran & Vadhan], but I don't believe Rivest (1996) satisfies points 3 and 4, and I don't believe Mahmoody (2011) satisfies point 3.

share|improve this question
1  
I confess I don't understand point 3. What would it mean to violate point 3? Also, what do you want the third party to be able to verify, and would it be OK if verification requires cooperation from the creator of the puzzle? –  D.W. Mar 21 at 6:00
    
I've tried to clarify point 3 with my edit. Basically, the same problem/puzzle should always be generated from the same input. Different inputs should result in problems with different difficulties. I think you can extend Rivest & Wagner to satisfy point four if the encrypted message contains something signed by the puzzle generator - so yes, offline co-operation from the creator of the puzzle is fine. –  studro Mar 21 at 13:40
    
Thanks, that helps! For randomized schemes, can't you always make them deterministic by seeding a deterministic PRNG with some seed and using its output everywhere that the algorithm makes a random choice? Now the problem/puzzle generated will be a deterministic function of the seed: the same seed always yields the same puzzle. Does that achieve what you're looking for or does it fall short in some way? –  D.W. Mar 21 at 16:25
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.