Paper 2024/766
Breaking Verifiable Delay Functions in the Random Oracle Model
Abstract
A verifiable delay function (VDF) is a cryptographic primitive that takes a long time to compute, but produces a unique output that is efficiently and publicly verifiable. Mahmoody, Smith and Wu (ICALP 2020) prove that VDFs satisfying both perfect completeness and adaptive perfect uniqueness do not exist in the random oracle model. Moreover, Ephraim, Freitag, Komargodski, and Pass (EUROCRYPT 2020) construct a VDF with perfect completeness and computational uniqueness, a much weaker guarantee compare to perfect uniqueness, in the random oracle model under the repeated squaring assumption. In this work, we close the gap between existing constructions and known lower bounds by showing that VDFs with imperfect completeness and non-adaptive computational uniqueness cannot be constructed in the pure random oracle model (without additional computational assumptions).
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-05-20: revised
- 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},
note = {\url{https://eprint.iacr.org/2024/766}},
url = {https://eprint.iacr.org/2024/766}
}
