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
Abstract

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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
SZKBatch Verification
Contact author(s)
or keret @ campus technion ac il
rothblum @ cs technion ac il
prashvas @ nus edu sg
History
2024-05-24: approved
2024-05-21: received
See all versions
Short URL
https://ia.cr/2024/781
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/781,
      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{https://eprint.iacr.org/2024/781}},
      url = {https://eprint.iacr.org/2024/781}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.