ECCC-Report TR24-024https://eccc.weizmann.ac.il/report/2024/024Comments and Revisions published for TR24-024en-usWed, 14 Feb 2024 14:09:04 +0200
Paper TR24-024
| Strong Batching for Non-Interactive Statistical Zero-Knowledge |
Ron Rothblum,
Changrui Mu,
Shafik Nassar,
Prashant Nalini Vasudevan
https://eccc.weizmann.ac.il/report/2024/024A 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})$.Wed, 14 Feb 2024 14:09:04 +0200https://eccc.weizmann.ac.il/report/2024/024