International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Continuous Verifiable Delay Functions

Authors:
Naomi Ephraim , Cornell Tech
Cody Freitag , Cornell Tech
Ilan Komargodski , NTT Research
Rafael Pass , Cornell Tech
Download:
DOI: 10.1007/978-3-030-45727-3_5 (login may be required)
Search ePrint
Search Google
Conference: EUROCRYPT 2020
Abstract: We introduce the notion of a 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 public randomness beacons that only require an initial random seed (and no further unpredictable sources of randomness), (b) enable 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 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 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).
Video from EUROCRYPT 2020
BibTeX
@inproceedings{eurocrypt-2020-30225,
  title={Continuous Verifiable Delay Functions},
  booktitle={39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, May 10–14, 2020, Proceedings},
  series={Lecture Notes in Computer Science},
  publisher={Springer},
  keywords={verifiable delay function;iteratively sequential function;PPAD hardness},
  volume={12105},
  doi={10.1007/978-3-030-45727-3_5},
  author={Naomi Ephraim and Cody Freitag and Ilan Komargodski and Rafael Pass},
  year=2020
}