Paper 2024/766
Breaking Verifiable Delay Functions in the Random Oracle Model
Abstract
This work resolves the open problem of whether verifiable delay functions (VDFs) can be constructed in the random oracle model. A VDF is a cryptographic primitive that requires a long time to compute (even with parallelization), but produces a unique output that is efficiently and publicly verifiable. We prove that VDFs do not exist in the random oracle model. This also rules out black-box constructions of VDFs from other cryptographic primitives, such as one-way functions, one-way permutations and collision-resistant hash functions. Prior to our work, Mahmoody, Smith and Wu (ICALP 2020) prove that \emph{perfectly unique} VDFs (a much stronger form of VDFs) do not exist in the random oracle model; on the other hand, Ephraim, Freitag, Komargodski, and Pass (Eurocrypt 2020) construct VDFs in the random oracle model assuming the hardness of repeated squaring. Our result is optimal -- we bridge the current gap between previously known impossibility results and existing constructions. We initiate the study of \emph{proof of work functions}, a new cryptographic primitive that shares similarities with both VDFs and proof of works. We show that a stronger form of it does not exist in the random oracle model, leaving open the fascinating possibility of a random-oracle-based construction.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Preprint.
- Keywords
- verifiable delay functionsproof of work functionsrandom oracle modelquery complexity
- Contact author(s)
-
ziyi guan @ epfl ch
artur riazanov @ epfl ch
weiqiang yuan @ epfl ch - History
- 2025-02-17: last of 5 revisions
- 2024-05-19: received
- See all versions
- Short URL
- https://ia.cr/2024/766
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/766, author = {Ziyi Guan and Artur Riazanov and Weiqiang Yuan}, title = {Breaking Verifiable Delay Functions in the Random Oracle Model}, howpublished = {Cryptology {ePrint} Archive, Paper 2024/766}, year = {2024}, url = {https://eprint.iacr.org/2024/766} }