Carmit Hazay
Bar-Ilan University

David Heath
University of Illinois Urbana-Champaign

Vladimir Kolesnikov
Georgia Institute of Technology

Muthuramakrishnan Venkitasubramaniam
Ligero Inc.

Yibin Yang
Georgia Institute of Technology

Keywords: Zero-Knowledge, Disjunctions, and VOLE-Based ZK.

Abstract

In the Zero-Knowledge Proof (ZKP) of a disjunctive statement, P and V agree on B fan-in 2 circuits C₀, ..., C_B-1 over a field F; each circuit has n_in inputs, n_x multiplications, and one output. P’s goal is to demonstrate the knowledge of a witness (id ∈ [B], w ∈ F^n_in), s.t. C_id(w) = 0 where neither w nor id is revealed. Disjunctive statements are effective, for example, in implementing ZKP based on sequential execution of CPU steps.

This paper studies ZKP (of knowledge) protocols over disjunctive statements based on Vector OLE. Denoting by λ the statistical security parameter and let ρ = max{log |F|, λ}, the previous state-of-the-art protocol Robin (Yang et al. CCS' 23) required (n_in + 3n_x)log |F| + O(ρB) bits of communication with O(1) rounds, and Mac'n'Cheese (Baum et al. CRYPTO' 21) required (n_in + n_x)log |F| + 2n_xρ + O(ρ log B) bits of communication with O(log B) rounds, both in the VOLE-hybrid model.

Our novel protocol LogRobin++ achieves the same functionality at the cost of (n_in + n_x)log |F| + O(ρ log B) bits of communication with O(1) rounds in the VOLE-hybrid model. Crucially, LogRobin++ takes advantage of two new techniques — (1) an O(log B)-overhead approach to prove in ZK that an IT-MAC commitment vector contains a zero; and (2) the realization of VOLE-based ZK over a disjunctive statement, where P commits only to w and multiplication outputs of C_id(w) (as opposed to prior work where P commits to w and all three wires that are associated with each multiplication gate).

We implemented LogRobin++ over Boolean (i.e., F₂) and arithmetic (i.e., F_2⁶¹-1) fields. In our experiments, including the cost of generating VOLE correlations, LogRobin++ achieved up to 170× optimization over Robin in communication, resulting in up to 7× (resp. 3×) wall-clock time improvements in a WAN-like (resp. LAN-like) setting.