Paper 2022/1056

Linear-Time Probabilistic Proofs with Sublinear Verification for Algebraic Automata Over Every Field

Jonathan Bootle, IBM Research - Zurich
Alessandro Chiesa, École Polytechnique Fédérale de Lausanne
Ziyi Guan, École Polytechnique Fédérale de Lausanne
Siqi Liu, University of California, Berkeley

Interactive oracle proofs (IOPs) are a generalization of probabilistically checkable proofs that can be used to construct succinct arguments. Improvements in the efficiency of IOPs lead to improvements in the efficiency of succinct arguments. Key efficiency goals include achieving provers that run in linear time and verifiers that run in sublinear time, where the time complexity is with respect to the arithmetic complexity of proved computations over a finite field $\mathbb{F}$. We consider the problem of constructing IOPs for any given finite field $\mathbb{F}$ with a linear-time prover and polylogarithmic query complexity. Several previous works have achieved these efficiency requirements with $O(1)$ soundness error for NP-complete languages. However, constrained by the soundness error of the sumcheck protocol underlying these constructions, the IOPs achieve linear prover time only for instances in fields of size $\Omega(\log n)$. Recent work (Ron-Zewi and Rothblum, STOC 2022) overcomes this problem, but with linear verification time. We construct IOPs for the algebraic automata problem over any finite field $\mathbb{F}$ with a linear-time prover, polylogarithmic query complexity, and sublinear verification complexity. We additionally prove a similar result to Ron-Zewi and Rothblum for the NP-complete language R1CS using different techniques. The IOPs imply succinct arguments for (nondeterministic) arithmetic computations over any finite field with linear-time proving (given black-box access to a linear-time collision-resistant hash function). Inspired by recent constructions of reverse-multiplication-friendly embeddings, our IOP constructions embed problem instances over small fields into larger fields and adapt previous IOP constructions to the new instances. The IOP provers are modelled as random access machines and use precomputation techniques to achieve linear prover time. In this way, we avoid having to replace the sumcheck protocol.

Available format(s)
Publication info
interactive oracle proofs succinct arguments linear-time prover sublinear verification
Contact author(s)
jbt @ zurich ibm com
alessandro chiesa @ epfl ch
ziyi guan @ epfl ch
sliu18 @ berkeley edu
2022-09-26: last of 3 revisions
2022-08-15: received
See all versions
Short URL
Creative Commons Attribution


      author = {Jonathan Bootle and Alessandro Chiesa and Ziyi Guan and Siqi Liu},
      title = {Linear-Time Probabilistic Proofs with Sublinear Verification for Algebraic Automata Over Every Field},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1056},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.