## Time-Lock Puzzles in the Random Oracle Model

**Mohammad Mahmoody, Tal Moran, and Salil Vadhan**

*Cornell University, Harvard University, and Harvard University*
**
Abstract.** A time-lock puzzle is a mechanism for sending messages
“to the future”.
The sender publishes a puzzle whose solution is the message to be sent,
thus hiding it until enough time has elapsed for the puzzle to be solved. For timelock
puzzles to be useful, generating a puzzle should take less time than solving it.
Since adversaries may have access to many more computers than honest solvers,
massively parallel solvers should not be able to produce a solution much faster
than serial ones.

To date, we know of only one mechanism that is believed to satisfy these properties:
the one proposed by Rivest, Shamir and Wagner (1996), who originally
introduced the notion of time-lock puzzles. Their puzzle is based on the serial nature
of exponentiation and the hardness of factoring, and is therefore vulnerable
to advances in factoring techniques (as well as to quantum attacks).

In this work, we study the possibility of constructing time-lock puzzles in the
random-oracle model. Our main result is negative, ruling out time-lock puzzles
that require more parallel time to solve than the total work required to generate
a puzzle. In particular, this should rule out black-box constructions of such timelock
puzzles from one-way permutations and collision-resistant hash-functions.
On the positive side, we construct a time-lock puzzle with a linear gap in parallel
time: a new puzzle can be generated with one round of *n* parallel queries to the
random oracle, but *n* rounds of *serial* queries are required to solve it (even for
massively parallel adversaries).