Paper 2020/925

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.