BooLigero: Improved Sublinear Zero Knowledge Proofs for Boolean Circuits

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 \vert \mathbb {F} \vert )^{1/4})\) and \(O((\log \vert \mathbb {F} \vert )^{1/2})\) compared to Ligero, where \(\mathbb {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 \(\text {GF} (2^w) \), bit masking, testing for zero bits, bit rearrangement within and across words, and bitwise outer product. Most of these techniques batch very efficiently, with only a constant overhead regardless of how many constraints of the same type are tested. Like Ligero, our 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.