### Tight Verifiable Delay Functions

Nico Döttling, Sanjam Garg, Giulio Malavolta, and Prashant Nalini Vasudevan

##### Abstract

A Verifiable Delay Function (VDF) is a function that takes at least $T$ sequential steps to evaluate and produces a unique output that can be verified efficiently, in time essentially independent of $T$. In this work we study tight VDFs, where the function can be evaluated in time not much more than the sequentiality bound $T$. On the negative side, we show the impossibility of a black-box construction from random oracles of a VDF that can be evaluated in time $T + O(T^\delta)$ for any constant $\delta < 1$. On the positive side, we show that any VDF with an inefficient prover (running in time $cT$ for some constant $c$) that has a natural self-composability property can be generically transformed into a VDF with a tight prover efficiency of $T+O(1)$. Our compiler introduces only a logarithmic factor overhead in the proof size and in the number of parallel threads needed by the prover. As a corollary, we obtain a simple construction of a tight VDF from any succinct non-interactive argument combined with repeated hashing. This is in contrast with prior generic constructions (Boneh et al, CRYPTO 2018) that required the existence of incremental verifiable computation, which entails stronger assumptions and complex machinery.

Available format(s)
Category
Foundations
Publication info
Published elsewhere. SCN 2020
Keywords
Verifiable Delay Functions
Contact author(s)
giulio malavolta @ hotmail it
nico doettling @ gmail com
sanjamg @ berkeley edu
prashantv91 @ gmail com
History
2020-06-30: revised
See all versions
Short URL
https://ia.cr/2019/659

CC BY

BibTeX

@misc{cryptoeprint:2019/659,
author = {Nico Döttling and Sanjam Garg and Giulio Malavolta and Prashant Nalini Vasudevan},
title = {Tight Verifiable Delay Functions},
howpublished = {Cryptology ePrint Archive, Paper 2019/659},
year = {2019},
note = {\url{https://eprint.iacr.org/2019/659}},
url = {https://eprint.iacr.org/2019/659}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.