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

Duke Privacy and Security Seminar
Speaker Name
Chenkai Weng
Date and Time
-
Location
The talk will be virtual on Zoom.
Notes
The Zoom link will be emailed to CS faculty/grad students, or contact Jennifer Schmidt (jschmidt at cs.duke.edu) to request it.
Abstract

Wolverine: Fast, Scalable, and Communication-Efficient Zero-Knowledge Proofs for Boolean and Arithmetic Circuits (https://eprint.iacr.org/2020/925)
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 κ bits per gate, for computational security parameter κ). 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.

Quicksilver: Efficient and Affordable Zero-Knowledge Proofs for Circuits and Polynomials over Any Field (https://eprint.iacr.org/2021/076)
In this paper, we propose several new ZK protocols in this setting, which improve the concrete efficiency and, at the same time, enable sublinear amortized communication for circuits with some notion of relaxed uniformity.

  1. In the circuit-based model, where the computation is represented as a circuit over a field, our ZK protocol achieves a communication complexity of 1 field element per non-linear gate for any field size while keeping the computation very cheap.
  2. In the setting where part of the computation can be represented as a set of polynomials, we can achieve communication sublinear to the polynomial size: the communication only depends on the input size and the highest degree of all polynomials, independent of the number of polynomials and the number of multiplications in the polynomials.
Short Biography

Chenkai Weng is a PhD student in the Department of Computer Science at Northwestern University. He is advised by Professor Xiao Wang. His research focuses on secure multi-party computation and zero-knowledge proofs. He has published research papers concerning security issues on garbled circuits, efficient correlated oblivious transfer and zero-knowledge proofs for Boolean and arithmetic circuits.

Host
Johes Bater