Paper 2021/1209
Simple and Efficient Batch Verification Techniques for Verifiable Delay Functions
Lior Rotem
Abstract
We study the problem of batch verification for verifiable delay functions (VDFs), focusing on proofs of correct exponentiation (PoCE), which underlie recent VDF constructions. We show how to compile any PoCE into a batch PoCE, offering significant savings in both communication and verification time. Concretely, given any PoCE with communication complexity $c$, verification time $t$ and soundness error $\delta$, and any pseudorandom function with key length ${\sf k}_{\sf prf}$ and evaluation time $ t_{\sf prf}$, we construct:  A batch PoCE for verifying $n$ instances with communication complexity $m\cdot c +{\sf k}_{\sf prf}$, verification time $m\cdot t + n\cdot m\cdot O(t_{\sf op} + t_{\sf prf})$ and soundness error $\delta + 2^{m}$, where $\lambda$ is the security parameter, $m$ is an adjustable parameter that can take any integer value, and $t_{\sf op}$ is the time required to evaluate the group operation in the underlying group. This should be contrasted with the naive approach, in which the communication complexity and verification time are $n \cdot c$ and $n \cdot t$, respectively. The soundness of this compiler relies only on the soundness of the underlying PoCE and the existence of oneway functions.  An improved batch PoCE based on the low order assumption. For verifying $n$ instances, the batch PoCE requires communication complexity $c +{\sf k}_{\sf prf}$ and verification time $t + n\cdot (t_{\sf prf} + \log(s)\cdot O(t_{\sf op}))$, and has soundness error $\delta + 1/s$. The parameter $s$ can take any integer value, as long as it is hard to find group elements of order less than $s$ in the underlying group. We discuss instantiations in which $s$ can be exponentially large in the security parameter $\lambda$. If the underlying PoCE is constant round and public coin (as is the case for existing protocols), then so are all of our batch PoCEs. This implies that they can be made noninteractive using the FiatShamir transform. Additionally, for RSA groups with moduli which are the products of two safe primes, we show how to efficiently verify that certain elements are not of order $2$. This protocol, together with the second compiler above and any (singleinstance) PoCE in these groups, yields an efficient batch PoCE in safe RSA groups. To complete the picture, we also show how to extend Pietrzak's protocol (which is statistically sound in the group $QR_N^+$ when $N$ is the product of two safe primes) to obtain a statisticallysound PoCE in safe RSA groups.
Metadata
 Available format(s)
 Category
 Cryptographic protocols
 Publication info
 A major revision of an IACR publication in Tcc 2021
 Keywords
 VDFBatchingTimedRelease CryptographyRSA
 Contact author(s)
 lior rotem @ cs huji ac il
 History
 20210917: received
 Short URL
 https://ia.cr/2021/1209
 License

CC BY
BibTeX
@misc{cryptoeprint:2021/1209, author = {Lior Rotem}, title = {Simple and Efficient Batch Verification Techniques for Verifiable Delay Functions}, howpublished = {Cryptology ePrint Archive, Paper 2021/1209}, year = {2021}, note = {\url{https://eprint.iacr.org/2021/1209}}, url = {https://eprint.iacr.org/2021/1209} }