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 with \emph{imperfect completeness} and \emph{computational uniqueness} 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 permutations and collision-resistant hash functions. Prior to our work, Mahmoody, Smith and Wu (ICALP 2020) prove that VDFs satisfying both \emph{perfect completeness} and \emph{perfect uniqueness} do not exist in the random oracle model; on the other hand, Ephraim, Freitag, Komargodski, and Pass (Eurocrypt 2020) construct VDFs with \emph{perfect completeness} and \emph{computational uniqueness} 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.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Preprint.
- Keywords
- verifiable delay functionsrandom oracle modelquery complexitydecision trees
- Contact author(s)
-
ziyi guan @ epfl ch
artur riazanov @ epfl ch
weiqiang yuan @ epfl ch - History
- 2024-11-05: last of 4 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}
}
