Welcome to the resource topic for 2025/1782
Title:
On Verifiable Delay Functions from Time-Lock Puzzles
Authors: Hamza Abusalah, Karen Azari, Dario Fiore, Chethan Kamath, Erkan Tairi
Abstract:A verifiable delay function (VDF) [Boneh et al., CRYPTO 2018] is a function f that is slow-to-compute, but is quickly verifiable given a short proof. This is formalised using two security requirements: i) sequentiality, which requires that a parallel adversary is unable to compute f faster; and ii) soundness, which requires that an adversary is unable to generate a proof that verifies wrong outputs. A time-lock puzzle (TLP), on the other hand, is a puzzle that can be quickly generated, but is slow-to-solve. The security requirement here is sequentiality, which requires that a parallel adversary is unable to solve puzzles faster.
In this paper, we study the relationship between these two timed primitives. Our main result is a construction of one-time'' VDF from TLP using indistinguishability obfuscation (iO) and one-way functions (OWFs), where by one-time’’ we mean that sequentiality of the VDF holds only against parallel adversaries that do not preprocess public parameters. Our VDF satisfies several desirable properties. For instance, we achieve perfectly sound and short proofs of O(\lambda) bits, where \lambda is the security parameter. Moreover, our construction is a trapdoor (one-time) VDF that can be easily extended to achieve interesting extra properties (defined in our paper) such as trapdoor-homomorphic and trapdoor-constrained evaluation.
Finally, when combined with the results of Bitansky et al., [ITCS 2016], this yields one-time VDFs from any worst-case non-parallelizing language, iO and OWF. To the best of our knowledge, this is the first such construction that only relies on polynomial security.
ePrint: https://eprint.iacr.org/2025/1782
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 .