**Stacked Garbling for Disjunctive Zero-Knowledge Proofs**

*David Heath and Vladimir Kolesnikov*

**Abstract: **Zero-knowledge (ZK) proofs (ZKP) have received wide attention, focusing on non-interactivity, short proof size, and fast verification time. We focus on the fastest total proof time, in particular for large Boolean circuits. Under this metric, Garbled Circuit (GC)-based ZKP (Jawurek et al., [JKO], CCS 2013) remained the state-of-the-art technique due to the low-constant linear scaling of computing the garbling.
We improve GC-ZKP for proof statements with conditional clauses. Our communication is proportional to the longest branch rather than to the entire proof statement. This is most useful when the number m of branches is large, resulting in up to factor $m\times$ improvement over JKO.
In our proof-of-concept illustrative application, prover P demonstrates knowledge of a bug in a codebase consisting of any number of snippets of actual C code. Our computation cost is linear in the size of the codebase and communication is constant in the number of snippets. That is, we require only enough communication for a single largest snippet!
Our conceptual contribution is stacked garbling for ZK, a privacy-free circuit garbling scheme that can be used with the JKO GC-ZKP protocol to construct more efficient ZKP. Given a Boolean circuit C and computational security parameter $\kappa$, our garbling is $L \cdot \kappa$ bits long, where $L$ is the length of the longest execution path in C. All prior concretely efficient garbling schemes produce garblings of size $|C| \cdot \kappa$. The computational cost of our scheme is not increased over prior state-of-the-art.
We implement our GC-ZKP and demonstrate significantly improved ($m\times$ over JKO) ZK performance for functions with branching factor $m$. Compared with recent ZKP (STARK, Libra, KKW, Ligero, Aurora, Bulletproofs), our scheme offers much better proof times for larger circuits ($35-1000\times$ or more, depending on circuit size and compared scheme). For our illustrative application, we consider four C code snippets, each of about 30-50 LOC; one snippet allows an invalid memory dereference. The entire proof takes 0.15 seconds and communication is 1.5 MB.

**Category / Keywords: **cryptographic protocols / Garbled circuits, inactive branch elimination, ZK, proof of C bugs

**Date: **received 7 Feb 2020, last revised 20 Feb 2020

**Contact author: **heath davidanthony at gatech edu,kolesnikov@gatech edu

**Available format(s): **PDF | BibTeX Citation

**Note: **Minor revision:
Adds discussion of Garbled RAM as related work.
Adds acknowledgement of support from NSF.

**Version: **20200220:213111 (All versions of this report)

**Short URL: **ia.cr/2020/136

[ Cryptology ePrint archive ]