Cryptology ePrint Archive: Report 2019/659

Tight Verifiable Delay Functions

Nico Döttling and Sanjam Garg and 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.

Category / Keywords: foundations / Verifiable Delay Functions

Original Publication (in the same form): SCN 2020

Date: received 4 Jun 2019, last revised 30 Jun 2020

Contact author: giulio malavolta at hotmail it, nico doettling at gmail com, sanjamg at berkeley edu, prashantv91 at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20200630:183603 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]