Paper 2020/1167
Batch Verification for Statistical Zero Knowledge Proofs
Inbar Kaslasi, Guy N. Rothblum, Ron D. Rothblum, Adam Sealfon, and Prashant Nalini Vasudevan
Abstract
A statistical zeroknowledge proof (SZK) for a problem $\Pi$ enables a computationally unbounded prover to convince a polynomialtime verifier that $x \in \Pi$ without revealing any additional information about $x$ to the verifier, in a strong informationtheoretic sense. Suppose, however, that the prover wishes to convince the verifier that $k$ separate inputs $x_1,\dots,x_k$ all belong to $\Pi$ (without revealing anything else). A naive way of doing so is to simply run the SZK protocol separately for each input. In this work we ask whether one can do better  that is, is efficient batch verification possible for SZK? We give a partial positive answer to this question by constructing a batch verification protocol for a natural and important subclass of SZK  all problems $\Pi$ that have a noninteractive SZK protocol (in the common random string model). More specifically, we show that, for every such problem $\Pi$, there exists an honestverifier SZK protocol for batch verification of $k$ instances, with communication complexity $poly(n) + k \cdot poly(\log{n},\log{k})$, where $poly$ refers to a fixed polynomial that depends only on $\Pi$ (and not on $k$). This result should be contrasted with the naive solution, which has communication complexity $k \cdot poly(n)$. Our proof leverages a new NISZKcomplete problem, called Approximate Injectivity, that we find to be of independent interest. The goal in this problem is to distinguish circuits that are nearly injective, from those that are noninjective on almost all inputs.
Metadata
 Available format(s)
 Category
 Cryptographic protocols
 Publication info
 A minor revision of an IACR publication in TCC 2020
 Keywords
 Zeroknowledge proofsSZKbatch verification
 Contact author(s)

kaslasi inbar @ gmail com
inbar kaslasi @ gmail com  History
 20200925: received
 Short URL
 https://ia.cr/2020/1167
 License

CC BY
BibTeX
@misc{cryptoeprint:2020/1167, author = {Inbar Kaslasi and Guy N. Rothblum and Ron D. Rothblum and Adam Sealfon and Prashant Nalini Vasudevan}, title = {Batch Verification for Statistical Zero Knowledge Proofs}, howpublished = {Cryptology ePrint Archive, Paper 2020/1167}, year = {2020}, note = {\url{https://eprint.iacr.org/2020/1167}}, url = {https://eprint.iacr.org/2020/1167} }