Orion: Zero Knowledge Proof with Linear Prover Time
Orion: Zero Knowledge Proof with Linear Prover Time
复制标题
DOI：
10.1007/978-3-031-15985-5_11
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Tiancheng Xie;Yupeng Zhang;D. Song
中科院分区：
文献类型：
--
作者：
Tiancheng Xie;Yupeng Zhang;D. Song
零知识证明是一种在真实的世界中有着广泛应用的密码学基础。然而，现有的计划与简洁的证明大小遭受的证明生成时间是超线性的大小表示为算术电路，限制了他们的效率和可扩展性在实践中的高开销。在本文中，我们提出了Orion，一个新的零知识论证系统，该系统具有O（N）的证明时间的字段操作和散列函数和证明大小。Orion是具体有效的，我们的实现表明，对于具有乘法门的电路，证明时间为3.09 s，证明大小为1.5 MB。证明时间是所有现有简洁证明系统中最快的，证明规模比Golovnev等人2021年提出的一个新方案小一个数量级。特别地，我们开发了两种新技术，从而提高了效率。(1)本文基于可扩展子图算法，提出了一种新的判定随机二部图是否为无损扩展图的算法。它允许我们以压倒性的概率对无损扩展器进行采样。该技术提高了效率和/或安全性的所有现有的零知识参数计划与线性证明时间。基于可扩展子图的测试算法对扩展图的其他应用也有独立的意义。(2)我们开发了一个有效的证明组合方案，代码切换，以减少证明的大小从平方根到多对数的计算的大小。该方案建立在线性码的编码电路上，并证明了第二个零知识论证的证明与线性码中的消息相同。证明合成只在证明器时间上引入了很小的开销。
Zero-knowledge proof is a powerful cryptographic primitive that has found various applications in the real world. However, existing schemes with succinct proof size suffer from a high overhead on the proof generation time that is super-linear in the size of the statement represented as an arithmetic circuit, limiting their efficiency and scalability in practice. In this paper, we present Orion, a new zero-knowledge argument system that achievesO(N) prover time of field operations and hash functions andproof size. Orion is concretely efficient and our implementation shows that the prover time is 3.09 s and the proof size is 1.5 MB for a circuit withmultiplication gates. The prover time is the fastest among all existing succinct proof systems, and the proof size is an order of magnitude smaller than a recent scheme proposed in Golovnev et al. 2021.In particular, we develop two new techniques leading to the efficiency improvement. (1) We propose a new algorithm to test whether a random bipartite graph is a lossless expander graph or not based on the densest subgraph algorithm. It allows us to sample lossless expanders with an overwhelming probability. The technique improves the efficiency and/or security of all existing zero-knowledge argument schemes with a linear prover time. The testing algorithm based on densest subgraph may be of independent interest for other applications of expander graphs. (2) We develop an efficient proof composition scheme, code switching, to reduce the proof size from square root to polylogarithmic in the size of the computation. The scheme is built on the encoding circuit of a linear code and shows that the witness of a second zero-knowledge argument is the same as the message in the linear code. The proof composition only introduces a small overhead on the prover time.