### Mac'n'Cheese: Zero-Knowledge Proofs for Boolean and Arithmetic Circuits with Nested Disjunctions

Carsten Baum, Alex J. Malozemoff, Marc B. Rosen, and Peter Scholl

##### Abstract

Zero knowledge proofs are an important building block in many cryptographic applications. 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 boolean and arithmetic circuits, called Mac'n'Cheese, with a focus on supporting large circuits. 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 online phase of Mac'n'Cheese and achieve a runtime of 144 ns per AND gate and 1.5 $\mu$s per multiplication gate in $\mathbb{F}_{2^{61}-1}$ when run over a network with a 95 ms latency and a bandwidth of 31.5 Mbps. In addition, we show that the disjunction optimization improves communication as expected: when proving a boolean circuit with eight branches and each branch containing roughly 1 billion multiplications, Mac'n'Cheese requires only 75 more bytes to communicate than in the single branch case.

Available format(s)
Category
Cryptographic protocols
Publication info
A minor revision of an IACR publication in CRYPTO 2021
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
See all versions
Short URL
https://ia.cr/2020/1410

CC BY

BibTeX

@misc{cryptoeprint:2020/1410,
author = {Carsten Baum and Alex J.  Malozemoff and Marc B.  Rosen and Peter Scholl},
title = {Mac'n'Cheese: Zero-Knowledge Proofs for Boolean and Arithmetic Circuits with Nested Disjunctions},
howpublished = {Cryptology ePrint Archive, Paper 2020/1410},
year = {2020},
note = {\url{https://eprint.iacr.org/2020/1410}},
url = {https://eprint.iacr.org/2020/1410}
}

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