We present an IOP that simultaneously achieves the properties of zero knowledge, linear-time proving, and polylogarithmic-time verification. 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 $\polylog(N)$ field operations (with proof length $O(N)$ and query complexity $\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).
Our result implies progress on a basic goal in the area of efficient zero knowledge. Via a known transformation, we obtain a zero knowledge argument system where the prover runs in linear time and the verifier runs in polylogarithmic time; the construction is plausibly post-quantum and only makes a black-box use of lightweight cryptography (collision-resistant hash functions).
Category / Keywords: foundations / interactive oracle proofs; zero knowledge; succinct arguments Date: received 4 Dec 2020, last revised 14 Oct 2021 Contact author: jbt at zurich ibm com, alexch at berkeley edu, sliu18 at berkeley edu Available format(s): PDF | BibTeX Citation Version: 20211014:074945 (All versions of this report) Short URL: ia.cr/2020/1527