Paper 2024/766
Breaking Verifiable Delay Functions in the Random Oracle Model
Abstract
A verifiable delay function (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-10-03: last of 2 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}
}
