Paper 2022/1010
Orion: Zero Knowledge Proof with Linear Prover Time
Abstract
Zeroknowledge 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 superlinear 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 zeroknowledge argument system that achieves $O(N)$ prover time of field operations and hash functions and $O(\log^2 N)$ proof size. Orion is concretely efficient and our implementation shows that the prover time is 3.09s and the proof size is 1.5MB for a circuit with $2^{20}$ multiplication 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 small set expansion problem. It allows us to sample lossless expanders with an overwhelming probability. The technique improves the efficiency and/or security of all existing zeroknowledge argument schemes with a linear prover time. (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 zeroknowledge argument is the same as the message in the linear code. The proof composition only introduces a small overhead on the prover time.
Note: We fix three mistakes in the previous version of the paper. (1) There was a mistake in the proof of the expander testing algorithm based on the densets subgraph algorithm. In particular, in Case 2 of Theorem 2 in the original version, the density $\frac{E'+c}{V'+1}>\frac{E'}{V'}$ only holds when $c>\frac{E'}{V'}$, or $V'>E'$, which was not the case for lossless expanders. In this version, we propose a different algorithm based on the small set expansion problem to identify lossles expander graphs with a negligible soundness error in Section 3. (2) While achieving zeroknowledge, we masked the protocol by a random message instead of a random vector of length $n$, which was not zeroknowledge. We provide a new protocol with proof of soundness and zeroknowledge using the techniques in [BCG+17] properly. (3) In the old Protocol 4, we used a SNARK as a building block, which was not sound. It needs to be replaced by a commitandprove SNARK. We thank Quang Dao, Xifan Yu, Weijie Wang, and Charalampos Papamanthou for pointing out the mistake in the densest subgraph algorithm, we thank Jonathan Bootle for pointing out the problem in the zeroknowledge variant, and Binyi Chen and Benedikt Bünz for pointing out the problem and giving a solution using CPSNARK.
Metadata
 Available format(s)
 Category
 Cryptographic protocols
 Publication info
 A major revision of an IACR publication in CRYPTO 2022
 Keywords
 zeroknowledge proofsexpander
 Contact author(s)

niconiconi @ berkeley edu
zhangyp @ illinois edu
dawnsong @ gmail com  History
 20231102: last of 4 revisions
 20220805: received
 See all versions
 Short URL
 https://ia.cr/2022/1010
 License

CC BY
BibTeX
@misc{cryptoeprint:2022/1010, author = {Tiancheng Xie and Yupeng Zhang and Dawn Song}, title = {Orion: Zero Knowledge Proof with Linear Prover Time}, howpublished = {Cryptology ePrint Archive, Paper 2022/1010}, year = {2022}, note = {\url{https://eprint.iacr.org/2022/1010}}, url = {https://eprint.iacr.org/2022/1010} }