Paper 2022/1010

Orion: Zero Knowledge Proof with Linear Prover Time

Tiancheng Xie, University of California, Berkeley
Yupeng Zhang, Texas A&M University
Dawn Song, University of California, Berkeley
Abstract

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 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 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.

Note: Full version

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A minor revision of an IACR publication in CRYPTO 2022
Keywords
zero-knowledge proofs expander
Contact author(s)
niconiconi @ berkeley edu
zhangyp @ tamu edu
dawnsong @ gmail com
History
2022-09-28: last of 2 revisions
2022-08-05: received
See all versions
Short URL
https://ia.cr/2022/1010
License
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.