Name
Abstract | ||
|---|---|---|
Time-lock puzzles are a mechanism for sending messages "to the future". A sender can quickly generate a puzzle with a solution s that remains hidden until a moderately large amount of time t has elapsed. The solution s should be hidden from any adversary that runs in time significantly less than t, including resourceful parallel adversaries with polynomially many processors.While the notion of time-lock puzzles has been around for 22 years, there has only been a single candidate proposed. Fifteen years ago, Rivest, Shamir and Wagner suggested a beautiful candidate time-lock puzzle based on the assumption that exponentiation modulo an RSA integer is an "inherently sequential" computation.We show that various flavors of randomized encodings give rise to time-lock puzzles of varying strengths, whose security can be shown assuming the mere existence of non-parallelizing languages, which are languages that require circuits of depth at least t to decide, in the worst-case. The existence of such languages is necessary for the existence of time-lock puzzles. We instantiate the construction with different randomized encodings from the literature, where increasingly better efficiency is obtained based on increasingly stronger cryptographic assumptions, ranging from one-way functions to indistinguishability obfuscation. We also observe that time-lock puzzles imply one-way functions, and thus the reliance on some cryptographic assumption is necessary.Finally, generalizing the above, we construct other types of puzzles such as proofs of work from randomized encodings and a suitable worst-case hardness assumption (that is necessary for such puzzles to exist). |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1145/2840728.2840745 | ITCS'16: PROCEEDINGS OF THE 2016 ACM CONFERENCE ON INNOVATIONS IN THEORETICAL COMPUTER SCIENCE |
Field | DocType | Volume |
Integer,Discrete mathematics,Mathematical puzzle,Cryptography,Modulo,God's algorithm,Theoretical computer science,Mathematical proof,Obfuscation,Exponentiation,Mathematics | Conference | 2015 |
Citations | PageRank | References |
24 | 0.86 | 43 |
Authors | ||
6 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Nir Bitansky | 1 | 833 | 31.00 |
| Shafi Goldwasser | 2 | 9935 | 2069.05 |
| Abhishek Jain 0002 | 3 | 73 | 3.14 |
| Omer Paneth | 4 | 535 | 22.42 |
| Vinod Vaikuntanathan | 5 | 5353 | 200.79 |
| Brent Waters | 6 | 14792 | 541.54 |