Cryptology ePrint Archive: Report 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.

Category / Keywords: cryptographic protocols / zero knowledge

Date: received 12 Nov 2020

Contact author: cbaum at cs au dk, amaloz@galois com, marc@galois com, peter scholl@cs au dk

Available format(s): PDF | BibTeX Citation

Version: 20201115:072902 (All versions of this report)

Short URL: ia.cr/2020/1410


[ Cryptology ePrint archive ]