Stacking Sigmas: A Framework to Compose Σ-Protocols for Disjunctions
Stacking Sigmas: A Framework to Compose Σ-Protocols for Disjunctions
复制标题
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Aarushi Goel;M. Green;Mathias Hall-Andersen;Gabriel Kaptchuk
中科院分区：
文献类型：
--
作者：
Aarushi Goel;M. Green;Mathias Hall-Andersen;Gabriel Kaptchuk
析取命题的零知识证明一直是研究的热点。经典的结果，如Cramer等人。[1994]和Abe等人。[AC'02]设计通用编译器，将某些类别的ZK证明转换为析取语句的ZK证明。然而，在这些结果中，所得到的协议的通信复杂度最终与证明析取中的所有子句的复杂度成比例。最近，Heath等人。[EC'20]利用乱码电路的特殊性质来构造析取的有效ZK证明，其中证明大小仅与析取中最大子句的长度成比例。然而，这些技术似乎并没有推广到乱码电路之外。在这项工作中，我们专注于实现两全其美。我们设计了一个通用的框架，编译一个大类的未修改的协议，每一个单独的语句，到一个新的协议，证明了这些语句的析取。我们的框架可以使用时，每个条款都证明了相同的双协议，当不同的双协议用于不同的条款。由此产生的双协议是具体有效的，并具有通信复杂度成比例的通信所需的最大条款，与添加剂条款，只有对数的条款的数量。我们表明，我们的编译器可以应用于许多著名的TCP协议，包括经典的协议（例如Schnorr [JC'91]和Guillou-Quisquater [JPTO'88]）和现代的MPC在头协议，如最近的工作Katz，Kolesnikov和王[CCS'18]和Ligero协议的艾姆斯等人。[CCS'17]。最后，由于我们类中的所有协议都可以在使用Fiat-Shamir变换的随机预言模型中进行非交互，因此我们的结果产生了第一个通用的非交互式零知识协议，其中通信仅取决于最大子句的大小。
Zero-Knowledge (ZK) Proofs for disjunctive statements have been a focus of a long line of research. Classical results such as Cramer et al. [CRYPTO’94] and Abe et al. [AC’02] design generic compilers that transform certain classes of ZK proofs into ZK proofs for disjunctive statements. However, communication complexity of the resulting protocols in these results ends up being proportional to the complexity of proving all clauses in the disjunction. More recently, Heath et al. [EC’20] exploited special properties of garbled circuits to construct efficient ZK proofs for disjunctions, where the proof size is only proportional to the length of the largest clause in the disjunction. However, these techniques do not appear to generalize beyond garbled circuits. In this work, we focus on achieving the best of both worlds. We design a general framework that compiles a large class of unmodified Σ-protocols, each for an individual statement, into a new Σ-protocol that proves a disjunction of these statements. Our framework can be used both when each clause is proved with the same Σ-protocol and when different Σ-protocols are used for different clauses. The resulting Σ-protocol is concretely efficient and has communication complexity proportional to the communication required by the largest clause, with additive terms that are only logarithmic in the number of clauses. We show that our compiler can be applied to many well-known Σ-protocols, including classical protocols (e.g. Schnorr [JC’91] and Guillou-Quisquater [CRYPTO’88]) and modern MPC-in-the-head protocols such as the recent work of Katz, Kolesnikov and Wang [CCS’18] and the Ligero protocol of Ames et al. [CCS’17]. Finally, since all of the protocols in our class can be made non-interactive in the random oracle model using the Fiat-Shamir transform, our result yields the first generic non-interactive zeroknowledge protocol for disjunctions where the communication only depends on the size of the largest clause.