Paper 2024/229
Strong Batching for NonInteractive Statistical ZeroKnowledge
Abstract
A zeroknowledge proof enables a prover to convince a verifier that $x \in S$, without revealing anything beyond this fact. By running a zeroknowledge proof $k$ times, it is possible to prove (still in zeroknowledge) 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 (nontrivial) zeroknowledge batch verification for $S$ possible? Recent works by Kaslasi et al. (TCC 2020, Eurocrypt 2021) show that any problem possessing a noninteractive statistical zeroknowledge proof (NISZK) has a nontrivial statistical zeroknowledge 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 noninteractive statistical zeroknowledge batch verification protocol with communication $\textrm{poly}(n,\log{k})$.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 A minor revision of an IACR publication in EUROCRYPT 2024
 Keywords
 Batch VerificationZeroknowlege ProofsSZK
 Contact author(s)

changrui mu @ u nus edu
shafik @ cs utexas edu
rothblum @ cs technion ac il
prashant @ comp nus edu sg  History
 20240216: approved
 20240214: received
 See all versions
 Short URL
 https://ia.cr/2024/229
 License

CC BY
BibTeX
@misc{cryptoeprint:2024/229, author = {Changrui Mu and Shafik Nassar and Ron D. Rothblum and Prashant Nalini Vasudevan}, title = {Strong Batching for NonInteractive Statistical ZeroKnowledge}, howpublished = {Cryptology ePrint Archive, Paper 2024/229}, year = {2024}, note = {\url{https://eprint.iacr.org/2024/229}}, url = {https://eprint.iacr.org/2024/229} }