Paper 2021/233

Public-Coin Statistical Zero-Knowledge Batch Verification against Malicious Verifiers

Inbar Kaslasi, Ron D. Rothblum, and Prashant Nalini Vasudevan

Abstract

Suppose that a problem $\Pi$ has a statistical zero-knowledge (SZK) proof with communication complexity $m$. The question of batch verification for SZK asks whether one can prove that $k$ instances $x_1,\ldots,x_k$ all belong to $\Pi$ with a statistical zero-knowledge proof whose communication complexity is better than $k \cdot m$ (which is the complexity of the trivial solution of executing the original protocol independently on each input). In a recent work, Kaslasi et al. (TCC, 2020) constructed such a batch verification protocol for any problem having a non-interactive SZK (NISZK) proof-system. Two drawbacks of their result are that their protocol is private-coin and is only zero-knowledge with respect to the honest verifier. In this work, we eliminate these two drawbacks by constructing a public-coin malicious-verifier SZK protocol for batch verification of NISZK. Similarly to the aforementioned prior work, the communication complexity of our protocol is $\big(k+poly(m) \big) \cdot polylog(k,m)$.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A major revision of an IACR publication in Eurocrypt 2021
Keywords
Statistical Zero-KnowledgeBatch Verification
Contact author(s)
kaslasi inbar @ gmail com
rothblum @ gmail com
prashantv91 @ gmail com
History
2021-03-02: received
Short URL
https://ia.cr/2021/233
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/233,
      author = {Inbar Kaslasi and Ron D.  Rothblum and Prashant Nalini Vasudevan},
      title = {Public-Coin Statistical Zero-Knowledge Batch Verification against Malicious Verifiers},
      howpublished = {Cryptology ePrint Archive, Paper 2021/233},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/233}},
      url = {https://eprint.iacr.org/2021/233}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.