Our construction is secure in the standard model under complexity assumptions (collision-resistant hash functions and inherently sequential hash functions), and makes black-box use of the underlying primitives. Consequently, the corresponding construction in the random oracle model is secure unconditionally. Moreover, as it is a public-coin protocol, it can be made non-interactive in the random oracle model using the Fiat-Shamir Heuristic.
Our construction makes a novel use of ``depth-robust'' directed acyclic graphs---ones whose depth remains large even after removing a constant fraction of vertices---which were previously studied for the purpose of complexity lower bounds. The construction bypasses a recent negative result of Mahmoody, Moran, and Vadhan (CRYPTO `11) for time-lock puzzles in the random oracle model, which showed that it is impossible to have time-lock puzzles like ours in the random oracle model if the puzzle generator also computes a solution together with the puzzle.Category / Keywords: cryptographic protocols / Publication Info: combinatorial cryptography, hash functions, random oracles, Date: received 6 Oct 2011, last revised 17 Mar 2013 Contact author: mahmoody at gmail com Available formats: PDF | BibTeX Citation Note: Polished the proofs a bit (with combining the two hash properties). Version: 20130318:035942 (All versions of this report) Discussion forum: Show discussion | Start new discussion