Paper 2021/233
PublicCoin Statistical ZeroKnowledge Batch Verification against Malicious Verifiers
Inbar Kaslasi, Ron D. Rothblum, and Prashant Nalini Vasudevan
Abstract
Suppose that a problem $\Pi$ has a statistical zeroknowledge (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 zeroknowledge 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 noninteractive SZK (NISZK) proofsystem. Two drawbacks of their result are that their protocol is privatecoin and is only zeroknowledge with respect to the honest verifier. In this work, we eliminate these two drawbacks by constructing a publiccoin maliciousverifier 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)$.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 A major revision of an IACR publication in EUROCRYPT 2021
 Keywords
 Statistical ZeroKnowledgeBatch Verification
 Contact author(s)

kaslasi inbar @ gmail com
rothblum @ gmail com
prashantv91 @ gmail com  History
 20210302: received
 Short URL
 https://ia.cr/2021/233
 License

CC BY
BibTeX
@misc{cryptoeprint:2021/233, author = {Inbar Kaslasi and Ron D. Rothblum and Prashant Nalini Vasudevan}, title = {PublicCoin Statistical ZeroKnowledge Batch Verification against Malicious Verifiers}, howpublished = {Cryptology ePrint Archive, Paper 2021/233}, year = {2021}, note = {\url{https://eprint.iacr.org/2021/233}}, url = {https://eprint.iacr.org/2021/233} }