Paper 2020/136

Stacked Garbling for Disjunctive Zero-Knowledge Proofs

David Heath and 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.

Note: Minor revision: Fixes various typos and small flow issues. Minor revision: Adds discussion of Garbled RAM as related work. Adds acknowledgement of support from NSF.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A minor revision of an IACR publication in EUROCRYPT 2020
DOI
10.1007/978-3-030-45727-3_19
Keywords
Garbled circuitsinactive branch eliminationZKproof of C bugs
Contact author(s)
heath davidanthony @ gatech edu
kolesnikov @ gatech edu
History
2020-06-22: last of 2 revisions
2020-02-10: received
See all versions
Short URL
https://ia.cr/2020/136
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/136,
      author = {David Heath and Vladimir Kolesnikov},
      title = {Stacked Garbling for Disjunctive Zero-Knowledge Proofs},
      howpublished = {Cryptology {ePrint} Archive, Paper 2020/136},
      year = {2020},
      doi = {10.1007/978-3-030-45727-3_19},
      url = {https://eprint.iacr.org/2020/136}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.