LogRobin++: Optimizing Proofs of Disjunctive Statements in VOLE-Based ZK
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
Abstract
In the Zero-Knowledge Proof (ZKP) of a disjunctive statement, and agree on fan-in circuits over a field ; each circuit has inputs, multiplications, and one output. 's goal is to demonstrate the knowledge of a witness , , s.t. where neither nor 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 , the previous state-of-the-art protocol (Yang et al. CCS'23) required bits of communication with rounds, and (Baum et al. CRYPTO'21) required bits of communication with rounds, both in the VOLE-hybrid model.
Our novel protocol achieves the same functionality at the cost of bits of communication with rounds in the VOLE-hybrid model. Crucially, takes advantage of two new techniques -- (1) an -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 commits only to and multiplication outputs of (as opposed to prior work where commits to and all three wires that are associated with each multiplication gate).
We implemented over Boolean (i.e., ) and arithmetic (i.e., ) fields. In our experiments, including the cost of generating VOLE correlations, achieved up to optimization over in communication, resulting in up to (resp. ) wall-clock time improvements in a WAN-like (resp. LAN-like) setting.
@misc{cryptoeprint:2024/1427,
author = {Carmit Hazay and David Heath and Vladimir Kolesnikov and Muthuramakrishnan Venkitasubramaniam and Yibin Yang},
title = {{LogRobin}++: Optimizing Proofs of Disjunctive Statements in {VOLE}-Based {ZK}},
howpublished = {Cryptology {ePrint} Archive, Paper 2024/1427},
year = {2024},
url = {https://eprint.iacr.org/2024/1427}
}
Note: In order to protect the privacy of readers, eprint.iacr.org
does not use cookies or embedded third party content.