**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$ and boolean circuits). We show here 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 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 circuits of size C over an arbitrary finite field and a statistical security parameter $\rho$, the communication complexity of our protocol is roughly 3B + 1 elements per gate, where B = 1 for large fields and $B = \rho/\log C$ for small fields.

Using 5 threads and a 50 Mbps network, our ZK protocol $(\rho = 40,\kappa = 128)$ runs at a rate of $0.54 \mus$/gate for a boolean circuit with 10 billion gates, using only 400 MB of memory and communicating 9 bits/gate. This is roughly an order of magnitude faster than prior work.

**Category / Keywords: **cryptographic protocols / zero-knowledge proofs

**Date: **received 24 Jul 2020

**Contact author: **wangxiao at cs northwestern edu

**Available format(s): **PDF | BibTeX Citation

**Version: **20200726:062731 (All versions of this report)

**Short URL: **ia.cr/2020/925

[ Cryptology ePrint archive ]