Paper 2024/781

Doubly-Efficient Batch Verification in Statistical Zero-Knowledge

Or Keret, Technion – Israel Institute of Technology
Ron D. Rothblum, Technion – Israel Institute of Technology
Prashant Nalini Vasudevan, National University of Singapore

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 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.

Available format(s)
Cryptographic protocols
Publication info
SZKBatch Verification
Contact author(s)
or keret @ campus technion ac il
rothblum @ cs technion ac il
prashvas @ nus edu sg
2024-05-24: approved
2024-05-21: received
See all versions
Short URL
Creative Commons Attribution


      author = {Or Keret and Ron D. Rothblum and Prashant Nalini Vasudevan},
      title = {Doubly-Efficient Batch Verification in Statistical Zero-Knowledge},
      howpublished = {Cryptology ePrint Archive, Paper 2024/781},
      year = {2024},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.