International Association
for Cryptologic Research

A sequence of recent works, concluding with Mu et al. (Eurocrypt, 2024) has shown that every problem $\Pi$ admitting a non-interactive statistical zero-knowledge proof (NISZK) has an efficient zero-knowledge \emph{batch verification} protocol. Namely, an NISZK protocol for proving that $x_1, \dots, x_k \in \Pi$ with communication that only scales poly-logarithmically with $k$. A caveat of this line of work is that the prover runs in exponential-time, whereas for NP problems it is natural to hope to obtain a \emph{doubly-efficient proof} -- that is, a prover that runs in polynomial-time given the $k$ NP witnesses. In this work we show that every problem in NISZK $\cap$ UP has a \emph{doubly-efficient} interactive statistical zero-knowledge proof with communication $\poly(n, \log(k))$ and $\poly(\log(k), \log(n))$ rounds. The prover runs in time $\poly(n, k)$ given access to the $k$ UP witnesses. Here $n$ denotes the length of each individual input, and UP is the subclass of NP relations in which YES instances have unique witnesses. This result yields doubly-efficient statistical zero-knowledge batch verification protocols for a variety of concrete and central cryptographic problems from the literature.