CryptoDB
Justvengers: Batched VOLE ZK Disjunctions in O(R+B+C) Communication
| Authors: |
|
|---|---|
| Download: | |
| Conference: | TCC 2025 |
| Abstract: | Recent progress on zero-knowledge proofs (ZKPs) based on vector oblivious linear evaluation (VOLE) offers a promising paradigm for scaling ZKPs over extremely large statements. In particular, VOLE-based ZK is currently the best choice in terms of end-to-end execution time. However, VOLE-based ZK incurs high communication overhead — it usually scales linearly with the circuit size. To mitigate this, existing literature considers VOLE-based ZK over structured statements. In this work, we focus on the batched disjunctive statement — P and V agree on B fan-in 2 circuits C_1, ..., C_B over a field F; each circuit is of size C with n_in inputs. P’s goal is to demonstrate the knowledge of R witnesses (id_j ∈ [B], w_j ∈ F^{n_in}) for each j ∈ [R] s.t. ∀j ∈ [R], C_{id_j}(w_j) = 0 where neither w_j nor id_j is revealed. Batched disjunctive statements are effective, e.g., in emulating the CPU execution inside ZK. Note, the naïve solution results in a circuit of size O(RBC). To prove such a statement using VOLE-based ZK, the prior state-of-the-art protocol Antman (Weng et al., CCS’22) incurred O(BC + R) communication by additionally relying on AHE, whereas Batchman (Yang et al., CCS’23) achieved O(RC + B) communication using only VOLE. In this work, we combine these two protocols non-trivially and present a novel protocol Justvengers — targeting the batched disjunctive statement — that incurs only O(R + B + C) communication and O(BC + (B + C)R log R) computation for prover, using AHE and VOLE. As in Antman, Justvengers requires an AHE scheme that achieves linear targeted malleability, which is a non-falsifiable assumption. |
BibTeX
@inproceedings{tcc-2025-36257,
title={Justvengers: Batched VOLE ZK Disjunctions in O(R+B+C) Communication},
publisher={Springer-Verlag},
author={Yibin Yang},
year=2025
}