A sequence of recent works, concluding with Mu et al. (Eurocrypt, 2024) has shown that every problem \(\varPi \) admitting a non-interactive statistical zero-knowledge proof ( \(\text {NISZK}\) ) has an efficient zero-knowledge batch verification protocol. Namely, an \(\text {NISZK}\) protocol for proving that \(x_1,\dots ,x_k \in \varPi \) 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 \(\text {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 \(\text {NP}\) witnesses.    In this work we show that every problem in \(\text {NISZK}\cap \text {UP}\) has a doubly-efficient interactive statistical zero-knowledge proof with communication \(\textrm{poly}(n,\log (k))\) and \(\textrm{poly}(\log (k),\log (n))\) rounds. The prover runs in time \(\textrm{poly}(n,k)\) given access to the k \(\text {UP}\) witnesses. Here n denotes the length of each individual input, and \(\text {UP}\) is the subclass of \(\text {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.

Doubly-Efficient Batch Verification in Statistical Zero-Knowledge

会议论文
发表日期：

2025年

查看全文

Or Keret,
Ron D. Rothblum,
Prashant Nalini Vasudevan

摘要

A sequence of recent works, concluding with Mu et al. (Eurocrypt, 2024) has shown that every problem \(\varPi \) admitting a non-interactive statistical zero-knowledge proof ( \(\text {NISZK}\) ) has an efficient zero-knowledge batch verification protocol. Namely, an \(\text {NISZK}\) protocol for proving that \(x_1,\dots ,x_k \in \varPi \) 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 \(\text {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 \(\text {NP}\) witnesses. In this work we show that every problem in \(\text {NISZK}\cap \text {UP}\) has a doubly-efficient interactive statistical zero-knowledge proof with communication \(\textrm{poly}(n,\log (k))\) and \(\textrm{poly}(\log (k),\log (n))\) rounds. The prover runs in time \(\textrm{poly}(n,k)\) given access to the k \(\text {UP}\) witnesses. Here n denotes the length of each individual input, and \(\text {UP}\) is the subclass of \(\text {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.