Paper 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 2–4 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.
Metadata
- Available format(s)
- Category
- Cryptographic protocols
- Publication info
- Preprint. MINOR revision.
- Keywords
- zero-knowledge proofs
- Contact author(s)
- wangxiao @ cs northwestern edu
- History
- 2021-01-13: last of 5 revisions
- 2020-07-26: received
- See all versions
- Short URL
- https://ia.cr/2020/925
- License
-
CC BY