Welcome to the resource topic for 2024/1427
Title:
LogRobin++: Optimizing Proofs of Disjunctive Statements in VOLE-Based ZK
Authors: Carmit Hazay, David Heath, Vladimir Kolesnikov, Muthuramakrishnan Venkitasubramaniam, Yibin Yang
Abstract:In the Zero-Knowledge Proof (ZKP) of a disjunctive statement, \mathcal{P} and \mathcal{V} agree on B fan-in 2 circuits \mathcal{C}_0, \ldots, \mathcal{C}_{B-1} over a field \mathbb{F}; each circuit has n_{\mathit{in}} inputs, n_\times multiplications, and one output. \mathcal{P}'s goal is to demonstrate the knowledge of a witness (\mathit{id} \in [B], \boldsymbol{w} \in \mathbb{F}^{n_{\mathit{in}}}), s.t. \mathcal{C}_{\mathit{id}}(\boldsymbol{w}) = 0 where neither \boldsymbol{w} nor \mathit{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 \lambda the statistical security parameter and let \rho \overset{\Delta}{=} \max\{\log |\mathbb{F}|, \lambda\}, the previous state-of-the-art protocol \mathsf{Robin} (Yang et al. CCS’23) required (n_{\mathit{in}}+3n_\times)\log \left|\mathbb{F}\right| + \mathcal{O}(\rho B) bits of communication with \mathcal{O}(1) rounds, and \mathsf{Mac'n'Cheese} (Baum et al. CRYPTO’21) required (n_{\mathit{in}}+n_\times)\log \left|\mathbb{F}\right| + 2n_\times\rho + \mathcal{O}(\rho \log B) bits of communication with \mathcal{O}(\log B) rounds, both in the VOLE-hybrid model.
Our novel protocol \mathsf{LogRobin}\texttt{++} achieves the same functionality at the cost of (n_{\mathit{in}}+n_\times)\log \left|\mathbb{F}\right| + \mathcal{O}(\rho \log B) bits of communication with \mathcal{O}(1) rounds in the VOLE-hybrid model. Crucially, \mathsf{LogRobin}\texttt{++} takes advantage of two new techniques – (1) an \mathcal{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 \mathcal{P} commits only to \boldsymbol{w} and multiplication outputs of \mathcal{C}_{\mathit{id}}(\boldsymbol{w}) (as opposed to prior work where \mathcal{P} commits to \boldsymbol{w} and all three wires that are associated with each multiplication gate).
We implemented \mathsf{LogRobin}\texttt{++} over Boolean (i.e., \mathbb{F}_2) and arithmetic (i.e., \mathbb{F}_{2^{61}-1}) fields. In our experiments, including the cost of generating VOLE correlations, \mathsf{LogRobin}\texttt{++} achieved up to 170 \times optimization over \mathsf{Robin} in communication, resulting in up to 7\times (resp. 3\times) wall-clock time improvements in a WAN-like (resp. LAN-like) setting.
ePrint: https://eprint.iacr.org/2024/1427
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 .