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

Institutions

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
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
article

Necessity of large primes and delay commitment in efficient verifiable delay function

Souvik Sur
International Journal of Applied Cryptography
Coding theory and cryptography
article

Necessity of large primes and delay commitment in efficient verifiable delay function

Souvik Sur
article en

Abstract

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.

International Journal of Applied CryptographyVol. 5(2)
Indian Institute of Technology Kharagpur (IN)
Openalex Percentile: Top 89%
Coding theory and cryptography
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.