**Public-Coin Statistical Zero-Knowledge Batch Verification against Malicious Verifiers**

*Inbar Kaslasi and Ron D. Rothblum and 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)$.

**Category / Keywords: **foundations / Statistical Zero-Knowledge, Batch Verification

**Original Publication**** (with major differences): **IACR-EUROCRYPT-2021

**Date: **received 1 Mar 2021

**Contact author: **kaslasi inbar at gmail com, rothblum at gmail com, prashantv91 at gmail com

**Available format(s): **PDF | BibTeX Citation

**Version: **20210302:203449 (All versions of this report)

**Short URL: **ia.cr/2021/233

[ Cryptology ePrint archive ]