Paper 2024/229

Strong Batching for Non-Interactive Statistical Zero-Knowledge

Changrui Mu, National University of Singapore
Shafik Nassar, The University of Texas at Austin
Ron D. Rothblum, Technion – Israel Institute of Technology
Prashant Nalini Vasudevan, National University of Singapore

A zero-knowledge proof enables a prover to convince a verifier that $x \in S$, without revealing anything beyond this fact. By running a zero-knowledge proof $k$ times, it is possible to prove (still in zero-knowledge) that $k$ separate instances $x_1,\dots,x_k$ are all in $S$. However, this increases the communication by a factor of $k$. Can one do better? In other words, is (non-trivial) zero-knowledge batch verification for $S$ possible? Recent works by Kaslasi et al. (TCC 2020, Eurocrypt 2021) show that any problem possessing a non-interactive statistical zero-knowledge proof (NISZK) has a non-trivial statistical zero-knowledge batch verification protocol. Their results had two major limitations: (1) to batch verify $k$ inputs of size $n$ each, the communication in their batch protocol is roughly $\textrm{poly}(n,\log{k})+O(k)$, which is better than the naive cost of $k \cdot \textrm{poly}(n)$ but still scales linearly with $k$, and, (2) the batch protocol requires $\Omega(k)$ rounds of interaction. In this work we remove both of these limitations by showing that any problem in $NISZK$ has a non-interactive statistical zero-knowledge batch verification protocol with communication $\textrm{poly}(n,\log{k})$.

Available format(s)
Publication info
A minor revision of an IACR publication in EUROCRYPT 2024
Batch VerificationZero-knowlege ProofsSZK
Contact author(s)
changrui mu @ u nus edu
shafik @ cs utexas edu
rothblum @ cs technion ac il
prashant @ comp nus edu sg
2024-02-16: approved
2024-02-14: received
See all versions
Short URL
Creative Commons Attribution


      author = {Changrui Mu and Shafik Nassar and Ron D. Rothblum and Prashant Nalini Vasudevan},
      title = {Strong Batching for Non-Interactive Statistical Zero-Knowledge},
      howpublished = {Cryptology ePrint Archive, Paper 2024/229},
      year = {2024},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.