Welcome to the resource topic for 2024/229
Title:
Strong Batching for Non-Interactive Statistical Zero-Knowledge
Authors: Changrui Mu, Shafik Nassar, Ron D. Rothblum, Prashant Nalini Vasudevan
Abstract:A zero-knowledge proof enables a prover to convince a verifier that x \in S, without revealing anything beyond this fact. By running a zero-knowledge proof k times, it is possible to prove (still in zero-knowledge) that k separate instances x_1,\dots,x_k are all in S. However, this increases the communication by a factor of k. Can one do better? In other words, is (non-trivial) zero-knowledge batch verification for S 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. Their results had two major limitations: (1) to batch verify k inputs of size n each, the communication in their batch protocol is roughly \textrm{poly}(n,\log{k})+O(k), which is better than the naive cost of k \cdot \textrm{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 \textrm{poly}(n,\log{k}).
ePrint: https://eprint.iacr.org/2024/229
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .