Worst-Case Analysis of the Soundness of Efficient Verifiable Delay Function

A Verifiable Delay Function (VDF) is a function that takes a specified sequential time <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$T$</tex> to be evaluated, but can be verified in <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathcal{O} (\log T)$</tex>-time. VDFs have several applications, like blockchains in crypto-currencies. that demand public verifiability of proofs. The efficient verifiable delay function (Wesolowski, EUROCRYPT 2019) is considered to be one of the finest constructions in this domain of research. In order to achieve computational soundness with respect to the security parameter λ, the verifier in Wesolowski's VDF challenges the prover with a prime <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\ell$</tex> sampled from the set of first <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$2^{2\lambda}$</tex> primes, uniformly at random. So, on average, it samples <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\Omega(\lambda \log \lambda)$</tex>-bit primes, but in the worst-case the sampled primes may be smaller than <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$2^{\lambda}$</tex>. In this work, we show that this VDF has a vulnerability in the worst-case sampling of primes, so it is necessary to avoid the primes smaller than <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$2^{\lambda}$</tex>. Otherwise, we construct an efficient adversary that breaks the computational soundness of this VDF with probability <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$1/\ell$</tex>.