### BooLigero: Improved Sublinear Zero Knowledge Proofs for Boolean Circuits

Yaron Gvili, Sarah Scheffler, and Mayank Varia

##### Abstract

We provide a modified version of the Ligero sublinear zero knowledge proof system for arithmetic circuits provided by Ames et. al. (CCS ‘17). Our modification "BooLigero" tailors Ligero for use in Boolean circuits to achieve a significant improvement in proof size. Although the original Ligero system could be used for Boolean circuits, Ligero generally requires allocating an entire field element to represent a single bit on a wire in a Boolean circuit. In contrast, our system performs operations over words of bits, allowing a proof size savings of between O(log(|F|)^1/4) and O(log(|F|)^1/2) compared to Ligero, where F is the field that leads to the optimal proof size in original Ligero. We achieve improvements in proof size of approximately 1.1-1.6x for SHA-2 and 1.7-2.8x for SHA-3. In addition to checking constraints of standard Boolean operations such as AND, XOR, and NOT over words, BooLigero also supports several other constraints such as multiplication in GF(2^w), bit masking, bit rearrangement within and across words, and bitwise outer product. Like Ligero, construction requires no trusted setup and no computational assumptions, which is ideal for blockchain applications. It is plausibly post-quantum secure in the standard model. Furthermore, it is public-coin, perfect honest-verifier zero knowledge, and can be made non-interactive in the random oracle model using the Fiat-Shamir transform.

Available format(s)
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Keywords
zero knowledge
Contact author(s)
sscheff @ bu edu
varia @ bu edu
yaron gvili @ cs tau ac il
History
2021-02-05: revised
See all versions
Short URL
https://ia.cr/2021/121

CC BY

BibTeX

@misc{cryptoeprint:2021/121,
author = {Yaron Gvili and Sarah Scheffler and Mayank Varia},
title = {BooLigero: Improved Sublinear Zero Knowledge Proofs for Boolean Circuits},
howpublished = {Cryptology ePrint Archive, Paper 2021/121},
year = {2021},
note = {\url{https://eprint.iacr.org/2021/121}},
url = {https://eprint.iacr.org/2021/121}
}

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