My own interest in this work arises from my general interest in the paradigm of batch verification. The challenge here is to perform batch verification, which is difficult enough per se, while preserving some natural notion of privacy (specifically, honest-verifier SZK).
The solution is based on an idea that seems doomed: Starting from a problem that essentially calls for distinguishing injective functions from highly non-injective ones, and iterating the natural SZK protocol for this problem (i.e., have the verifier send a random image and ask for its preimage). The problem is that, when reducing to this problem, the function's potential range is significantly larger than its domain, and it is unclear how to iterate the protocol (i.e., compose these functions). One may suggest hashing the potential range to the domain, but this evidently creates collisions. Loosely speaking, the solution is having the verifier help the prover distinguish these hashing collisions, but this has to be done without helping a cheating prover distinguish collisions in the original function. Furthermore, in order to obtain low complexity, hashing is performed by a randomness extractor.
A side note: I used to credit the work of Omer, Guy, and Ron doublly-efficient interactive proof for space bounded computations (known as RRR) for initiating the explicit study of batch verification. But it seems that this notion was explored in Or Meir's work Combinatorial PCPs with Short Proofs (see Sec 5.1). Still, these two settings (i.e., IP vs PCP) are different.
A statistical zero-knowledge proof (SZK) for a problem $\Pi$ enables a computationally unbounded prover to convince a polynomial-time verifier that $x \in \Pi$ without revealing any additional information about $x$ to the verifier, in a strong information-theoretic sense.
Suppose, however, that the prover wishes to convince the verifier that $k$ separate inputs $x_1,\dots,x_k$ all belong to $\Pi$ (without revealing anything else). A naive way of doing so is to simply run the SZK protocol separately for each input. In this work we ask whether one can do better -- that is, is efficient batch verification possible for SZK?
We give a partial positive answer to this question by constructing a batch verification protocol for a natural and important subclass of SZK -- all problems $\Pi$ that have a non-interactive SZK protocol (in the common random string model). More specifically, we show that, for every such problem $\Pi$, there exists an honest-verifier SZK protocol for batch verification of $k$ instances, with communication complexity $poly(n) + k \cdot poly(\log{n},\log{k})$, where $poly$ refers to a fixed polynomial that depends only on $\Pi$ (and not on $k$). This result should be contrasted with the naive solution, which has communication complexity $k \cdot poly(n)$.
Our proof leverages a new NISZK-complete problem, called Approximate Injectivity, that we find to be of independent interest. The goal in this problem is to distinguish circuits that are nearly injective, from those that are non-injective on almost all inputs.
Available from ECCC TR20-147.