**Zero-Knowledge Succinct Arguments with a Linear-Time Prover**

*Jonathan Bootle and Alessandro Chiesa and Siqi Liu*

**Abstract: **We construct a zero knowledge argument system with polylogarithmic communication complexity where the prover runs in linear time and the verifier runs in polylogarithmic time. This achieves a central goal in the area of efficient zero knowledge. Additionally, our construction is plausibly post-quantum and only makes a black-box use of lightweight cryptography (collision-resistant hash functions).

Our result is a direct consequence of fundamental progress in probabilistic proofs: a new interactive oracle proof (IOP) that simultaneously achieves zero knowledge, linear-time proving, and polylogarithmic verification. Specifically, we construct a zero-knowledge IOP where, for the satisfiability of an $N$-gate arithmetic circuit over any field of size $\Omega(N)$, the prover uses $O(N)$ field operations and the verifier uses $\mathrm{polylog}(N)$ field operations (with proof length $O(N)$ and query complexity $\mathrm{polylog}(N)$). Polylogarithmic verification is achieved in the holographic setting for every circuit (the verifier has oracle access to a linear-time-computable encoding of the circuit whose satisfiability is being proved).

**Category / Keywords: **foundations / succinct arguments; zero knowledge; interactive oracle proofs

**Date: **received 4 Dec 2020, last revised 24 Feb 2021

**Contact author: **jbt at zurich ibm com, alexch at berkeley edu, sliu18 at berkeley edu

**Available format(s): **PDF | BibTeX Citation

**Version: **20210224:211730 (All versions of this report)

**Short URL: **ia.cr/2020/1527

[ Cryptology ePrint archive ]