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
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
-
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}, url = {https://eprint.iacr.org/2020/1410} }