Cryptology ePrint Archive: Report 2019/619

Continuous Verifiable Delay Functions

Naomi Ephraim and Cody Freitag and 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., EUROCRYPT '19), 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 a $\textit{public randomness beacon}$ that only requires 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 even when viewed as a (plain) VDF, our construction enjoys several advantages over previous ones: it satisfies a stronger soundness property under a weaker FS assumption (earlier constructions require the FS heuristic for either super-logarithmic round protocols, or for arguments (as opposed to proofs)).

Category / Keywords: foundations / Verifiable delay functions, continuous verifiability, randomness beacons, PPAD hardness,

Date: received 31 May 2019, last revised 3 Jun 2019

Contact author: nephraim at cs cornell edu,cfreitag@cs cornell edu,komargodski@cornell edu,rafael@cs cornell edu

Available format(s): PDF | BibTeX Citation

Version: 20190603:201318 (All versions of this report)

Short URL: ia.cr/2019/619


[ Cryptology ePrint archive ]