The Taub Faculty of Computer Science Events and Talks

Time-lock puzzles are a class of computational problems that take longer to solve than they do to generate. They can be used, for example, to send a message ``to the future'': the sender publishes a puzzle whose solution is the message to be sent, thus hiding it for the time it takes to solve the puzzle. 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), based on the serial nature of exponentiation and the hardness of factoring. In this talk, I will discuss the possibility of constructing time-lock puzzles based on more general assumptions.

We give both negative and positive results: On the one hand, we rule out time-lock puzzles in the random oracle model that require more parallel time to solve than the total work required to generate a puzzle (this rules out black-box constructions from one-way functions and collision-resistant hashes). On the other hand, we construct "proofs of work" based on "inherently serial" collision-resistant hash functions (or unconditionally in the random oracle model): proofs-of-work are a variant of time-lock puzzles in which the puzzle generator does not know in advance the solution to the puzzle. This type of puzzle can be used to create non-interactive timestamps.

Based on joint work with Mohammad Mahmoody and Salil Vadhan.