Paper 2020/1527

Zero-Knowledge IOPs with Linear-Time Prover and Polylogarithmic-Time Verifier

Jonathan Bootle
Alessandro Chiesa
Siqi Liu

Interactive oracle proofs (IOPs) are a multi-round generalization of probabilistically checkable proofs that play a fundamental role in the construction of efficient cryptographic proofs. 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).

Available format(s)
Publication info
A major revision of an IACR publication in EUROCRYPT 2022
interactive oracle proofs zero knowledge succinct arguments
Contact author(s)
jbt @ zurich ibm com
alexch @ berkeley edu
sliu18 @ berkeley edu
2022-06-02: last of 3 revisions
2020-12-08: received
See all versions
Short URL
Creative Commons Attribution


      author = {Jonathan Bootle and Alessandro Chiesa and Siqi Liu},
      title = {Zero-Knowledge IOPs with Linear-Time Prover and Polylogarithmic-Time Verifier},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1527},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.