Cryptology ePrint Archive: Report 2020/1527

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.

Our result is a direct consequence of a new interactive oracle proof (IOP) that simultaneously achieves linear-time proving and zero knowledge. We construct an 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

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

Available format(s): PDF | BibTeX Citation

Version: 20201208:124657 (All versions of this report)

Short URL: ia.cr/2020/1527