License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2020.83
URN: urn:nbn:de:0030-drops-124907
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12490/
Mahmoody, Mohammad ;
Smith, Caleb ;
Wu, David J.
Can Verifiable Delay Functions Be Based on Random Oracles?
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 := Eval(x) can be efficiently verified (possibly given a proof π) in time t ≪ T (e.g., t = poly(λ, log T) where λ is the security parameter). The first security requirement on a VDF, called uniqueness, is that no polynomial-time algorithm can find a convincing proof π' that verifies for an input x and a different output y' ≠ y. The second security requirement, called sequentiality, is that no polynomial-time algorithm running in time σ < T for some parameter σ (e.g., σ = T^{1/10}) can compute y, even with poly(T,λ) 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 black-box 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:
- We show that VDFs satisfying perfect uniqueness (i.e., VDFs where no different convincing solution y' ≠ y exists) cannot be constructed in the ROM. More formally, we give an attacker that finds the solution y in ≈ t rounds of queries, asking only poly(T) queries in total.
- We also rule out tight verifiable delay functions in the ROM. Tight verifiable delay functions, recently studied by Döttling, Garg, Malavolta, and Vasudevan (ePrint Report 2019), require sequentiality for σ ≈ T-T^ρ for some constant 0 < ρ < 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 σ > T-(T)/(2t) for a concrete verification time t.
BibTeX - Entry
@InProceedings{mahmoody_et_al:LIPIcs:2020:12490,
author = {Mohammad Mahmoody and Caleb Smith and David J. Wu},
title = {{Can Verifiable Delay Functions Be Based on Random Oracles?}},
booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
pages = {83:1--83:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-138-2},
ISSN = {1868-8969},
year = {2020},
volume = {168},
editor = {Artur Czumaj and Anuj Dawar and Emanuela Merelli},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12490},
URN = {urn:nbn:de:0030-drops-124907},
doi = {10.4230/LIPIcs.ICALP.2020.83},
annote = {Keywords: verifiable delay function, lower bound, random oracle model}
}
|
Keywords: |
|
verifiable delay function, lower bound, random oracle model |
|
Collection: |
|
47th International Colloquium on Automata, Languages, and Programming (ICALP 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
29.06.2020 |
