CryptoDB
Public-Coin Statistical Zero-Knowledge Batch Verification against Malicious Verifiers
| Authors: |
|
|---|---|
| Download: |
|
| Conference: | EUROCRYPT 2021 |
| 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,\dots,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 $(k+poly(m)) \cdot polylog(k,m)$. |
Video from EUROCRYPT 2021
BibTeX
@inproceedings{eurocrypt-2021-30832,
title={Public-Coin Statistical Zero-Knowledge Batch Verification against Malicious Verifiers},
publisher={Springer-Verlag},
doi={10.1007/978-3-030-77883-5_8},
author={Inbar Kaslasi and Ron D. Rothblum and Prashant Nalini Vasudevan},
year=2021
}