Welcome to the resource topic for 2021/233
Title:
Public-Coin Statistical Zero-Knowledge Batch Verification against Malicious Verifiers
Authors: Inbar Kaslasi, Ron D. Rothblum, Prashant Nalini Vasudevan
Abstract:Suppose that a problem \Pi has a statistical zero-knowledge (SZK) proof with communication complexity m. The question of batch verification for SZK asks whether one can prove that k instances x_1,\ldots,x_k all belong to \Pi with a statistical zero-knowledge proof whose communication complexity is better than k \cdot m (which is the complexity of the trivial solution of executing the original protocol independently on each input). In a recent work, Kaslasi et al. (TCC, 2020) constructed such a batch verification protocol for any problem having a non-interactive SZK (NISZK) proof-system. Two drawbacks of their result are that their protocol is private-coin and is only zero-knowledge with respect to the honest verifier. In this work, we eliminate these two drawbacks by constructing a public-coin malicious-verifier SZK protocol for batch verification of NISZK. Similarly to the aforementioned prior work, the communication complexity of our protocol is \big(k+poly(m) \big) \cdot polylog(k,m).
ePrint: https://eprint.iacr.org/2021/233
Talk: https://www.youtube.com/watch?v=0rFQGfHY4tw
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 .