Tal Moran@BIU on: Time-lock puzzles and Proofs-of-Work in the Random Oracle Model

Primary tabs

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 time-lock 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), 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. In particular, this rules out black-box constructions of such time-lock puzzles from one-way permutations and collision-resistant hash-functions.

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.

Date and Time: 
Wednesday, May 23, 2012 - 11:30 to Thursday, May 24, 2012 - 12:45
Speaker: 
Tal Moran
Location: 
Bar-Ilan, Seminar Room Building 408