Paper 2020/1410

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.

Metadata
Available format(s)
PDF
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
2020-11-15: received
See all versions
Short URL
https://ia.cr/2020/1410
License
Creative Commons Attribution
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.