Cryptology ePrint Archive: Report 2021/121

BooLigero: Improved Sublinear Zero Knowledge Proofs for Boolean Circuits

Yaron Gvili and 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.

Category / Keywords: cryptographic protocols / zero knowledge

Date: received 2 Feb 2021, last revised 5 Feb 2021

Contact author: sscheff at bu edu, varia@bu edu, yaron gvili@cs tau ac il

Available format(s): PDF | BibTeX Citation

Version: 20210205:190538 (All versions of this report)

Short URL: ia.cr/2021/121


[ Cryptology ePrint archive ]