### Continuous Verifiable Delay Functions

Naomi Ephraim, Cody Freitag, Ilan Komargodski, and 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).

Available format(s)
Category
Foundations
Publication info
A minor revision of an IACR publication in EUROCRYPT 2020
Keywords
Verifiable delay functionscontinuous verifiabilityrandomness beaconsPPAD hardness
Contact author(s)
nephraim @ cs cornell edu
cfreitag @ cs cornell edu
ilan komargodski @ ntt-research ac il
rafael @ cs cornell edu
History
2020-08-18: last of 3 revisions
See all versions
Short URL
https://ia.cr/2019/619

CC BY

BibTeX

@misc{cryptoeprint:2019/619,
author = {Naomi Ephraim and Cody Freitag and Ilan Komargodski and Rafael Pass},
title = {Continuous Verifiable Delay Functions},
howpublished = {Cryptology ePrint Archive, Paper 2019/619},
year = {2019},
note = {\url{https://eprint.iacr.org/2019/619}},
url = {https://eprint.iacr.org/2019/619}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.