[Resource Topic] 2020/136: Stacked Garbling for Disjunctive Zero-Knowledge Proofs

Welcome to the resource topic for 2020/136

Title:
Stacked Garbling for Disjunctive Zero-Knowledge Proofs

Authors: David Heath, Vladimir Kolesnikov

Abstract:

Zero-knowledge (ZK) proofs receive wide attention, especially with respect to non-interactivity, small proof size, and fast verification. We instead focus on fast total proof time, in particular for large Boolean circuits. Under this metric, Garbled Circuit (GC)-based ZK, originally proposed by Jawurek et al. ([JKO], CCS 2013), remains state-of-the-art due to the low-constant linear scaling of garbling. We improve GC-ZK for proof statements with conditional clauses. Our communication is proportional to the longest clause rather than to the entire proof statement. This is most useful when the number of branches m is large, resulting in up to m\times communication improvement over JKO. In our proof-of-concept illustrative application, the prover demonstrates knowledge of a bug in a codebase consisting of any number of snippets of 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 the single largest snippet! Our conceptual contribution is stacked garbling for ZK, a privacy-free circuit garbling scheme that, when used with the JKO GC-ZK protocol, constructs efficient ZK proofs. Given a Boolean circuit C and computational security parameter \kappa, our garbling is L\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|\kappa. The computational cost of our scheme is not increased over prior state-of-the-art. We implemented our technique and demonstrate significantly improved performance. For functions with branching factor m, we improve communication by m\times compared to JKO. Compared with recent systems (STARK, Libra, KKW, Ligero, Aurora, Bulletproofs), our scheme offers better proof times for large circuits: 35-1000\times or more, depending on circuit size and on the compared scheme. For our illustrative application, we consider four C code snippets. Each snippet has 30-50 LOC; one snippet allows an invalid memory dereference. The entire proof takes 0.15 seconds and communicates 1.5 MB.

ePrint: https://eprint.iacr.org/2020/136

Talk: https://www.youtube.com/watch?v=O_kWpyIzqY4

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .