Welcome to the resource topic for 2019/619
Title:
Continuous Verifiable Delay Functions
Authors: Naomi Ephraim, Cody Freitag, Ilan Komargodski, Rafael Pass
Abstract:We introduce the notion of a \textit{continuous verifiable delay function} (cVDF): a function g which is (a) iteratively sequential—meaning that evaluating the iteration g^{(t)} of g (on a random input) takes time roughly t times the time to evaluate g, even with many parallel processors, and (b) (iteratively) verifiable—the output of g^{(t)} can be efficiently verified (in time that is essentially independent of t). In other words, the iterated function g^{(t)} is a verifiable delay function (VDF) (Boneh et al., CRYPTO '18), having the property that intermediate steps of the computation (i.e., g^{(t')} for t'<t) are publicly and continuously verifiable. We demonstrate that cVDFs have intriguing applications: (a) they can be used to construct \textit{public randomness beacons} that only require an initial random seed (and no further unpredictable sources of randomness), (b) enable \textit{outsourceable VDFs} where any part of the VDF computation can be verifiably outsourced, and (c) have deep complexity-theoretic consequences: in particular, they imply the existence of \textit{depth-robust moderately-hard} Nash equilibrium problem instances, i.e. instances that can be solved in polynomial time yet require a high sequential running time. Our main result is the construction of a cVDF based on the repeated squaring assumption and the soundness of the Fiat-Shamir (FS) heuristic for \textit{constant-round proofs}. We highlight that when viewed as a (plain) VDF, our construction requires a weaker FS assumption than previous ones (earlier constructions require the FS heuristic for either super-logarithmic round proofs, or for arguments).
ePrint: https://eprint.iacr.org/2019/619
Talk: https://www.youtube.com/watch?v=26qLKF0TJ_4
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 .