Necessity of large primes and delay commitment in efficient verifiable delay function
A verifiable delay function (VDF) is a function that takes a specified sequential time T to be evaluated, but can be verified in O(log T)-time. The efficient verifiable delay function (Wesolowski, EUROCRYPT 2019) is considered to be one of the finest constructions in this domain. For the security parameter λ, the verifier in Wesolowski's VDF challenges the prover with a prime sampled from the set of first 22λ primes ℙ2λ. The sequential complexity of the verifier could be halved without harming its soundness if the primes were sampled from ℙλ. We show that it is necessary to avoid the primes in ℙλ. Otherwise, we construct an efficient adversary that breaks the soundness of this VDF with probability > 1/2λ. We also show that it is necessary to commit the delay T before sampling the prime. Otherwise, we give another adversary to refute its soundness for the applications with flexible delay.
Authors
- Souvik Sur (ORCID: https://orcid.org/0000-0003-1109-8595)
Institutions
- Indian Institute of Technology Kharagpur (IN)
Publication Details
- Journal
- International Journal of Applied Cryptography
- Published
- 2025-01-01
- DOI
- https://doi.org/10.1504/ijact.2025.147919
- Primary Topic
- Coding theory and cryptography
- Type
- article
- Field-Weighted Citation Impact
- 0.00