ECCC-Report TR24-101https://eccc.weizmann.ac.il/report/2024/101Comments and Revisions published for TR24-101en-usSun, 09 Jun 2024 08:46:46 +0300
Paper TR24-101
| Doubly-Efficient Batch Verification in Statistical Zero-Knowledge |
Ron Rothblum,
Prashant Nalini Vasudevan,
Or Keret
https://eccc.weizmann.ac.il/report/2024/101A 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 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 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 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.Sun, 09 Jun 2024 08:46:46 +0300https://eccc.weizmann.ac.il/report/2024/101