Welcome to the resource topic for 2011/553
Title:
Publicly Verifiable Proofs of Sequential Work
Authors: Mohammad Mahmoody, Tal Moran, Salil Vadhan
Abstract:We construct a publicly verifiable protocol for proving computational work based on collision-resistant hash functions and a new plausible complexity assumption regarding the existence of “inherently sequential” hash functions. Our protocol is based on a novel construction of time-lock puzzles. Given a sampled “puzzle” P \gets D_n, where n is the security parameter and D_n is the distribution of the puzzles, a corresponding “solution” can be generated using N evaluations of the sequential hash function, where N>n is another parameter, while any feasible adversarial strategy for generating valid solutions must take at least as much time as \Omega(N) sequential evaluations of the hash function after receiving P. Thus, valid solutions constitute a “proof” that \Omega(N) parallel time elapsed since P was received. Solutions can be publicly and efficiently verified in time \poly(n) \cdot \polylog(N). Applications of these “time-lock puzzles” include noninteractive timestamping of documents (when the distribution over the possible documents corresponds to the puzzle distribution D_n) and universally verifiable CPU benchmarks. 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.
ePrint: https://eprint.iacr.org/2011/553
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .