International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Strong Batching for Non-Interactive Statistical Zero-Knowledge

Authors:
Prashant Nalini Vasudevan , National University of Singapore
Ron D. Rothblum , Technion
Shafik Nassar , The University of Texas at Austin
Changrui Mu , National University of Singapore
Download:
DOI: 10.1007/978-3-031-58751-1_9 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: EUROCRYPT 2024
Abstract: In a zero-knowledge proof, a prover needs to convince a verifier that an input x is contained in a language Pi without revealing any additional information. By repeating a zero-knowledge proof k times, it is possible to prove (still in zero-knowledge) that k separate inputs x1,...,xk all belong to Pi. But this increases the communication by a factor of k. Can one do better? In other words, is (non-trivial) zero-knowledge batch verification for Pi possible? Recent works by Kaslasi et al. (TCC 2020, Eurocrypt 2021) show that any problem possessing a non-interactive statistical zero-knowledge proof (NISZK) has a non-trivial statistical zero-knowledge batch verification protocol. Two major limitations of their results are: (1) the communication in the batch protocol is roughly poly(n,log(k))+O(k), which is better than the naive cost of k*poly(n) but still scales linearly with k, and, (2) the batch protocol requires Omega(k) rounds of interaction. In this work we remove both of these limitations by showing that any problem in NISZK has a non-interactive statistical zero-knowledge batch verification protocol with communication poly(n,log(k)).
BibTeX
@inproceedings{eurocrypt-2024-33926,
  title={Strong Batching for Non-Interactive Statistical Zero-Knowledge},
  publisher={Springer-Verlag},
  doi={10.1007/978-3-031-58751-1_9},
  author={Prashant Nalini Vasudevan and Ron D. Rothblum and Shafik Nassar and Changrui Mu},
  year=2024
}