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

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

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review


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 μ s per multiplication gate in F261-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.

Original languageEnglish
Title of host publicationAdvances in Cryptology – CRYPTO 2021 - 41st Annual International Cryptology Conference, CRYPTO 2021, Proceedings : Proceedings
Number of pages21
Publication dateAug 2021
ISBN (Print)978-3-030-84258-1
ISBN (Electronic)978-3-030-84259-8
Publication statusPublished - Aug 2021
EventAnnual International Cryptology Conference - Virtual
Duration: 16 Aug 202120 Aug 2021


ConferenceAnnual International Cryptology Conference
Internet address


Dive into the research topics of 'Mac’n’Cheese: Zero-Knowledge Proofs for Boolean and Arithmetic Circuits with Nested Disjunctions'. Together they form a unique fingerprint.

Cite this