Welcome to the resource topic for 2021/1209
Title:
Simple and Efficient Batch Verification Techniques for Verifiable Delay Functions
Authors: 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 one-way 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 non-interactive using the Fiat-Shamir 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 (single-instance) 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 statistically-sound PoCE in safe RSA groups.
ePrint: https://eprint.iacr.org/2021/1209
Talk: https://www.youtube.com/watch?v=g2zLG8p60bg
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .