Cryptology ePrint Archive: Report 2018/623

Efficient verifiable delay functions

Benjamin Wesolowski

Abstract: We construct a verifiable delay function (VDF). A VDF is a function whose evaluation requires to run a given number of sequential steps, yet the result can be efficiently verified. They have applications in decentralised systems, such as the generation of trustworthy public randomness in a trustless environment, or resource-efficient blockchains. To construct a VDF, we actually build a trapdoor VDF. A trapdoor VDF is essentially a VDF which can be evaluated efficiently by parties who know a secret (the trapdoor). By setting up this scheme in a way that the trapdoor is unknown (not even by the party running the setup, so that there is no need for a trusted setup environment), we obtain a simple VDF. Our construction is based on groups of unknown order (such as an RSA group, or the class group of an imaginary quadratic field). The output of our construction is very short (the result and the proof of correctness are both a single element of the group), and the verification of correctness is very efficient.

Category / Keywords: cryptographic protocols / time-lock puzzle, proof of sequential work, randomness beacon, RSA, class group of imaginary quadratic field

Date: received 20 Jun 2018, last revised 7 Aug 2018

Contact author: bj wesolowski at orange fr

Available format(s): PDF | BibTeX Citation

Version: 20180807:122807 (All versions of this report)

Short URL: ia.cr/2018/623

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]