Paper 2019/663
Can Verifiable Delay Functions be Based on Random Oracles?
Mohammad Mahmoody, Caleb Smith, and David J. Wu
Abstract
Boneh, Bonneau, Bünz, and Fisch (CRYPTO 2018) recently introduced the notion of a verifiable delay function (VDF). VDFs are functions that take a long sequential time $T$ to compute, but whose outputs $y = \mathsf{Eval}(x)$ can be efficiently verified (possibly given a proof $\pi$) in time $t \ll T$ (e.g., $t=\mathrm{poly}(\lambda, \log T)$ where $\lambda$ is the security parameter). The first security requirement on a VDF, called uniqueness, is that no polynomialtime algorithm can find a convincing proof $\pi'$ that verifies for an input $x$ and a different output $y' \neq y$. The second security requirement, called sequentiality, is that no polynomialtime algorithm running in time $\sigma<T$ for some parameter $\sigma$ (e.g., $\sigma=T^{1/10}$) can compute $y$, even with $\mathrm{poly} (T,\lambda)$ many parallel processors. Starting from the work of Boneh et al., there are now multiple constructions of VDFs from various algebraic assumptions. In this work, we study whether VDFs can be constructed from ideal hash functions in a blackbox way, as modeled in the random oracle model (ROM). In the ROM, we measure the running time by the number of oracle queries and the sequentiality by the number of rounds of oracle queries. We rule out two classes of constructions of VDFs in the ROM: (1) We show that VDFs satisfying perfect uniqueness (i.e., no different convincing solution $y' \neq y$ exists) cannot be constructed in the ROM. More formally, we give an attacker that finds the solution $y$ in $\approx t$ rounds of queries, asking only $\mathrm{poly}(T)$ queries in total. (2) We also rule out tight VDFs in the ROM. Tight VDFs were recently studied by Döttling, Garg, Malavolta, and Vasudevan (ePrint Report 2019) and require sequentiality $\sigma \approx TT^\rho$ for some constant $0 < \rho <1$. More generally, our lower bound also applies to proofs of sequential work (i.e., VDFs without the uniqueness property), even in the private verification setting, and sequentiality $\sigma > T\frac{T}{2t}$ for a concrete verification time $t$.
Note: This is the full version of a paper published in ICALP 2020. This version subsumes an earlier version of the work titled "A Note on the (Im)possibility of Verifiable Delay Functions in the Random Oracle Model"
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Published elsewhere. Minor revision. International Colloquium on Automata, Languages and Programming (ICALP) 2020
 Keywords
 Verifiable Delay FunctionsProofs of Sequential WorkRandom Oracle Model
 Contact author(s)

mohammad @ virginia edu
caleb @ virginia edu
dwu4 @ virginia edu  History
 20200510: last of 3 revisions
 20190605: received
 See all versions
 Short URL
 https://ia.cr/2019/663
 License

CC BY
BibTeX
@misc{cryptoeprint:2019/663, author = {Mohammad Mahmoody and Caleb Smith and David J. Wu}, title = {Can Verifiable Delay Functions be Based on Random Oracles?}, howpublished = {Cryptology {ePrint} Archive, Paper 2019/663}, year = {2019}, url = {https://eprint.iacr.org/2019/663} }