No reduction from ROM to TLP
Statement
No reduction of any kind from the random oracle model to time-lock puzzles exists. Measuring work by oracle queries and parallel time by rounds of oracle queries, MMV11 rule out random-oracle time-lock puzzles that require more parallel time to solve than the total work required to generate a puzzle: a puzzle whose generator makes queries is solved in rounds of polynomially many parallel queries each. The generator of a time-lock puzzle with gap in the sense of BGJ+16 makes queries, so MMV11’s solver uses fewer than rounds for every large enough polynomial , and no time-lock puzzle exists in the model; the solver is bounded in oracle queries and rounds, not in computation.
Notes
- A linear gap is possible: MMV11 construct a random-oracle puzzle generated with one round of parallel queries that requires rounds of serial queries to solve, even for massively parallel adversaries — MMV11.
- The result is expected to rule out black-box constructions of such time-lock puzzles from one-way permutations and collision-resistant hash functions — MMV11.