Welcome to the resource topic for 2019/659
Title:
Tight Verifiable Delay Functions
Authors: Nico Döttling, Sanjam Garg, Giulio Malavolta, 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.
ePrint: https://eprint.iacr.org/2019/659
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .