Paper 2024/781

Doubly-Efficient Batch Verification in Statistical Zero-Knowledge

Abstract

A sequence of recent works, concluding with Mu et al. (Eurocrypt, 2024) has shown that every problem $\mathrm{\Pi }$ admitting a non-interactive statistical zero-knowledge proof (NISZK) has an efficient zero-knowledge batch verification protocol. Namely, an NISZK protocol for proving that $x_1,\dots ,x_k\in \mathrm{\Pi }$ with communication that only scales poly-logarithmically with $$. 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 doubly-efficient proof - that is, a prover that runs in polynomial-time given the $$ NP witnesses. In this work we show that every problem in $$ has a doubly-efficient interactive statistical zero-knowledge proof with communication $$ and $$ rounds. The prover runs in time $$ given access to the $$ UP witnesses. Here $$ 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.