Doubly Efficient Interactive Proofs for General Arithmetic Circuits with Linear Prover Time
Doubly Efficient Interactive Proofs for General Arithmetic Circuits with Linear Prover Time
复制标题
DOI：
10.1145/3460120.3484767
复制
发表时间：
2021-11
期刊：
影响因子：
--
通讯作者：
Jiaheng Zhang;Weijie Wang;Yinuo Zhang;Yupeng Zhang
中科院分区：
文献类型：
--
作者：
Jiaheng Zhang;Weijie Wang;Yinuo Zhang;Yupeng Zhang
我们针对一般算术电路提出了一种新的双高效交互式证明协议。该协议将Goldwasser、Kalai和Rothblum提出的分层电路交互式证明推广到任意电路，同时保持了与电路规模严格成线性关系的最优证明者复杂度。对于低深度电路，证明规模仍然简洁，对于结构化电路，验证者时间为次线性。然后，我们利用新的交互式证明协议以及多项式承诺，为一般算术电路构建了一种新的零知识论证方案。我们的关键技术是一个新的和检验方程，它将关于一层输出的断言仅简化为关于其输入的断言，而不是关于其上方所有层的断言，因为后者不可避免地会产生与电路深度成比例的开销。我们为证明者开发了高效算法来运行这个和检验协议，并在电路规模的线性时间内将多个断言合并回一个。我们的新协议不仅在渐近意义上实现了最优证明者复杂度，而且在实践中也很高效。我们的实验表明，为一个具有超过60万个门的电路生成证明仅需0.3秒，这比相应分层电路上的原始交互式证明协议快13倍。证明大小为208千字节，验证者时间为66毫秒。我们的实现可以直接处理一般算术电路，而无需将它们转换为分层电路，从而避免电路规模上的高开销。
We propose a new doubly efficient interactive proof protocol for general arithmetic circuits. The protocol generalizes the interactive proof for layered circuits proposed by Goldwasser, Kalai and Rothblum to arbitrary circuits, while preserving the optimal prover complexity that is strictly linear to the size of the circuits. The proof size remains succinct for low depth circuits and the verifier time is sublinear for structured circuits. We then construct a new zero knowledge argument scheme for general arithmetic circuits using our new interactive proof protocol together with polynomial commitments. Our key technique is a new sumcheck equation that reduces a claim about the output of one layer to claims about its input only, instead of claims about all the layers above which inevitably incurs an overhead proportional to the depth of the circuit. We developed efficient algorithms for the prover to run this sumcheck protocol and to combine multiple claims back into one in linear time in the size of the circuit. Not only does our new protocol achieve optimal prover complexity asymptotically, but it is also efficient in practice. Our experiments show that it only takes 0.3 seconds to generate the proof for a circuit with more than 600,000 gates, which is 13 times faster than the original interactive proof protocol on the corresponding layered circuit. The proof size is 208 kilobytes and the verifier time is 66 milliseconds. Our implementation can take general arithmetic circuits directly, without transforming them to layered circuits with a high overhead on the size of the circuit.