Paper 2024/229

Strong Batching for Non-Interactive Statistical Zero-Knowledge

Abstract

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 $$ separate instances $$ are all in $$. However, this increases the communication by a factor of $$. Can one do better? In other words, is (non-trivial) zero-knowledge batch verification for $$ 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 $$ inputs of size $$ each, the communication in their batch protocol is roughly $$, which is better than the naive cost of $$ but still scales linearly with $$, and, (2) the batch protocol requires $$ rounds of interaction. In this work we remove both of these limitations by showing that any problem in $$ has a non-interactive statistical zero-knowledge batch verification protocol with communication $$.