Cryptology ePrint Archive: Report 2020/925

Wolverine: Fast, Scalable, and Communication-Efficient Zero-Knowledge Proofs for Boolean and Arithmetic Circuits

Chenkai Weng and Kang Yang and Jonathan Katz and Xiao Wang

Abstract: Efficient zero-knowledge (ZK) proofs for arbitrary boolean or arithmetic circuits have recently attracted much attention. Existing solutions suffer from either significant prover overhead (superlinear running time and/or high memory usage) or relatively high communication complexity (at least $\kappa$ bits per gate, for computational security parameter $\kappa$). In this paper, we propose a new protocol for constant-round interactive ZK proofs that simultaneously allows for a highly efficient prover and low communication. Specifically:

- The prover in our ZK protocol has linear running time and, perhaps more importantly, memory usage linear in the memory needed to evaluate the circuit non-cryptographically. This allows our proof system to scale easily to very large circuits. - For statistical security parameter $\rho= 40$, our ZK protocol communicates roughly 9 bits/gate for boolean circuits and 24 field elements/gate for arithmetic circuits over large fields. Using 5 threads, 400 MB of memory, and a 200 Mbps network to evaluate a circuit with billions of gates, our implementation ($\rho = 40, \kappa = 128$) runs at a rate of 0.45 $\mu$s/gate in the boolean case, and 1.6 $\mu$s/gate for an arithmetic circuit over a 61-bit field.

We also present an improved subfield Vector Oblivious Linear Evaluation (sVOLE) protocol with malicious security that is of independent interest.

Category / Keywords: cryptographic protocols / zero-knowledge proofs

Date: received 24 Jul 2020, last revised 6 Oct 2020

Contact author: wangxiao at cs northwestern edu

Available format(s): PDF | BibTeX Citation

Version: 20201006:210909 (All versions of this report)

Short URL: ia.cr/2020/925


[ Cryptology ePrint archive ]