Paper 2026/2408
Separating One-Way Functions from Verifiable Delay Functions
Abstract
Timed cryptography captures computations that inherently require a prescribed amount of time, even in the presence of parallelism, and has emerged as a central notion due to its broad applications in both practice and theory. A natural question is how timed cryptographic primitives relate to traditional cryptography, in particular to primitives in Minicrypt. Guan and Montgomery (CRYPTO 2024) show that sequential functions do not imply one-way functions (OWFs) via black-box reductions. Their result, however, leaves open whether adding public verifiability (a substantially stronger requirement) suffices to imply OWFs. We study this question via verifiable delay functions (VDFs), which require substantial sequential time to evaluate, yet produce a unique output that is efficiently and publicly verifiable. We show that VDFs do not imply OWFs via fully black-box, relativizing reductions. Combined with prior results showing that VDFs cannot be constructed in the random oracle model, this establishes that there is no black-box implication in either direction between VDFs and OWFs. Our proof develops a new oracle separation technique that combines the random oracle with a carefully designed complexity-theoretic oracle inspired by Kolmogorov complexity.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Preprint.
- Keywords
- verifiable delay functionsone-way functionsseparations
- Contact author(s)
-
hamzaabusalah @ gmail com
crypto @ nicholasbrandt de
ziyiguan @ mit edu
kristina hostakova @ inf ethz ch - History
- 2026-10-11: approved
- 2026-10-08: received
- See all versions
- Short URL
- https://ia.cr/2026/2408
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2026/2408,
author = {Hamza Abusalah and Nicholas Brandt and Ziyi Guan and Kristina Hostáková},
title = {Separating One-Way Functions from Verifiable Delay Functions},
howpublished = {Cryptology {ePrint} Archive, Paper 2026/2408},
year = {2026},
url = {https://eprint.iacr.org/2026/2408}
}
