You are looking at a specific version 20190603:201318 of this paper. See the latest version.

Paper 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)).

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
Verifiable delay functionscontinuous verifiabilityrandomness beaconsPPAD hardness
Contact author(s)
nephraim @ cs cornell edu,cfreitag @ cs cornell edu,komargodski @ cornell edu,rafael @ cs cornell edu
History
2020-08-18: last of 3 revisions
2019-06-03: received
See all versions
Short URL
https://ia.cr/2019/619
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.