Stacked Garbling for Disjunctive Zero-Knowledge Proofs
Stacked Garbling for Disjunctive Zero-Knowledge Proofs
复制标题
DOI：
10.1007/978-3-030-45727-3_19
复制
发表时间：
2020-05
期刊：
影响因子：
--
通讯作者：
David Heath;V. Kolesnikov
中科院分区：
文献类型：
--
作者：
David Heath;V. Kolesnikov
零知识（ZK）证明（ZKP）受到了广泛关注，侧重于非交互性、短证明大小和快速验证时间。我们专注于最快的总证明时间，特别是对于大型布尔电路。在此指标下，基于乱码电路 (GC) 的 ZKP（Jawurek 等人，[JKO]，CCS 2013）由于计算乱码的低恒定线性缩放而仍然是最先进的技术。我们改进了带有条件子句的证明语句的 GC-ZKP。我们的通信与最长的分支而不是整个证明语句成正比。当分支数量很大时，这非常有用，从而比 JKO 得到高达因子的改进。在我们的概念验证说明性应用程序中，证明演示了对由任意数量的实际 C 代码片段组成的代码库中的错误的了解。我们的计算成本与代码库的大小成线性关系，并且通信在片段数量方面是恒定的。也就是说，我们只需要单个最大片段的足够通信！我们的概念贡献是ZK的堆叠乱码，这是一种无隐私的电路乱码方案，可以与JKO GC-ZKP协议一起使用来构建更高效的ZKP。给定布尔电路和计算安全参数，我们的乱码是位长，其中L是最长执行路径的长度。所有先前的具体有效的乱码方案都会产生大小的乱码。我们的方案的计算成本并没有比之前最先进的技术有所增加。我们实现了 GC-ZKP，并证明具有分支因子的函数的 ZK 性能显着提高（相对于 JKO）。与最近的 ZKP（STARK、Libra、KKW、Ligero、Aurora、Bulletproofs）相比，我们的方案为较大电路（35 或更多，取决于电路大小和比较方案）提供了更好的证明时间。对于我们的说明性应用程序，我们考虑四个 C 代码片段，每个代码片段大约有 30-50 个 LOC；一个片段允许无效的内存取消引用。整个证明需要 0.15 秒，通信大小为 1.5 MB。
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 numberof branches is large, resulting in up to factorimprovement over JKO.In our proof-of-conceptillustrative application, proverdemonstrates knowledge of a bug in a codebase consisting ofany numberof snippets ofactual C code. Our computation cost is linear in the size of the codebase and communication isconstant in the number of snippets. That is, we require only enough communication for a single largest snippet!Ourconceptual contributionisstacked 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 circuitand computational security parameter, our garbling isbits long, whereLis the length of the longest execution path in. All prior concretely efficient garbling schemes produce garblings of size. The computational cost of our scheme is not increased over prior state-of-the-art.We implement our GC-ZKP and demonstrate significantly improved (over JKO) ZK performance for functions with branching factor. Compared with recent ZKP (STARK, Libra, KKW, Ligero, Aurora, Bulletproofs), our scheme offers much better proof times for larger circuits (35-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 s and communication is 1.5 MB.