Paper 2019/663
A Note on the (Im)possibility of Verifiable Delay Functions in the Random Oracle Model
Mohammad Mahmoody and 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 \get \mathrm{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 is that no polynomial-time algorithm can find a convincing proof $\pi'$ that verifies for an input $x$ and a different output $y' \neq y$. The second security requirement is that that no polynomial-time algorithm running in sequential time $T'<T$ (e.g., $T'=T^{1/10}$) can compute $y$. 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 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 show that VDFs satisfying perfect uniqueness (i.e., VDFs where no algorithm can find a convincing different solution $y' \neq y$) cannot be constructed in the ROM. More formally, we give an attacker that finds the solution $y$ in $\approx t$ rounds of queries and asking only $\mathrm{poly}(T)$ queries in total. In addition, we show that a simple adaptation of our techniques can be used to rule out tight proofs of sequential work (proofs of sequential work are essentially VDFs without the uniqueness property).
Metadata
- Available format(s)
- Category
- Foundations
- Publication info
- Preprint. MINOR revision.
- Keywords
- Verifiable Delay FunctionsProofs of Sequential WorkRandom Oracle Model
- Contact author(s)
- mohammad @ virginia edu,caleb @ virginia edu,dwu4 @ virginia edu
- History
- 2020-05-10: last of 3 revisions
- 2019-06-05: received
- See all versions
- Short URL
- https://ia.cr/2019/663
- License
-
CC BY