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

Chenkai Weng, Kang Yang, 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 (i.e., high memory usage) or relatively high communication complexity (at least &#954; 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 an efficient prover with asymptotically optimal memory usage and significantly lower communication compared to protocols with similar memory efficiency. 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 hundreds of 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.

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
See all versions
Short URL
https://ia.cr/2020/925

CC BY

BibTeX

@misc{cryptoeprint:2020/925,
author = {Chenkai Weng and Kang Yang and Jonathan Katz and Xiao Wang},
title = {Wolverine: Fast, Scalable, and Communication-Efficient Zero-Knowledge Proofs for Boolean and Arithmetic Circuits},
howpublished = {Cryptology ePrint Archive, Paper 2020/925},
year = {2020},
note = {\url{https://eprint.iacr.org/2020/925}},
url = {https://eprint.iacr.org/2020/925}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.