Paper 2018/623

Efficient verifiable delay functions

Benjamin Wesolowski
Abstract

We construct a verifiable delay function (VDF). A VDF is a function whose evaluation requires running 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 our 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 each a single element of the group), and the verification of correctness is very efficient.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A minor revision of an IACR publication in EUROCRYPT 2019
Keywords
time-lock puzzle proof of sequential work randomness beacon RSA class group of imaginary quadratic field
Contact author(s)
benjamin wesolowski @ math u-bordeaux fr
History
2022-10-26: last of 5 revisions
2018-06-22: received
See all versions
Short URL
https://ia.cr/2018/623
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/623,
      author = {Benjamin Wesolowski},
      title = {Efficient verifiable delay functions},
      howpublished = {Cryptology ePrint Archive, Paper 2018/623},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/623}},
      url = {https://eprint.iacr.org/2018/623}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.