Paper 2020/1410
Mac'n'Cheese: Zero-Knowledge Proofs for Arithmetic Circuits with Nested Disjunctions
Carsten Baum and Alex J. Malozemoff and Marc Rosen and Peter Scholl
Abstract
A zero-knowledge proof is a cryptographic primitive that is a versatile building block for both cryptographic protocols alongside a wide range of applications from cryptocurrencies to privacy-preserving auditing. Unfortunately, when the proof statements become very large, existing zero-knowledge proof systems easily reach their limits: either the computational overhead, the memory footprint, or the required bandwidth exceed levels that would be tolerable in practice. We present an interactive zero-knowledge proof system for arithmetic circuits, called Mac'n'Cheese, with a focus on supporting large circuits while using low computational resources. Our work follows the commit-and-prove paradigm instantiated using information-theoretic MACs based on vector oblivious linear evaluation to achieve high efficiency. We additionally show how to optimize disjunctions, with a general OR transformation for proving the disjunction of $m$ statements that has communication complexity proportional to the longest statement (plus an additive term logarithmic in $m$). These disjunctions can further be nested, allowing efficient proofs about complex statements with many levels of disjunctions. We also show how to make Mac'n'Cheese non-interactive (after a preprocessing phase) using the Fiat-Shamir transform, and with only a small degradation in soundness. We have implemented the non-interactive variant of the online phase of Mac'n'Cheese and can achieve 2.5 $\mu s$ per multiplication gate while requiring a minimal amount of memory: for proving the knowledge of two 512-by-512 matrices that equal some fixed public matrix we require less than 36~MB of memory for both the prover and verifier. We achieve this through a streaming approach which is compatible with our disjunctions over sub-circuits.
Metadata
- Available format(s)
- Category
- Cryptographic protocols
- Publication info
- Preprint. MINOR revision.
- Keywords
- zero knowledge
- Contact author(s)
-
cbaum @ cs au dk
amaloz @ galois com
marc @ galois com
peter scholl @ cs au dk - History
- 2021-07-26: revised
- 2020-11-15: received
- See all versions
- Short URL
- https://ia.cr/2020/1410
- License
-
CC BY