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

Jonathan Bootle; Alessandro Chiesa; Ziyi Guan; Siqi Liu

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

Abstract

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 . We consider the problem of constructing IOPs for any given finite field with a linear-time prover and polylogarithmic query complexity. Several previous works have achieved these efficiency requirements with 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 . 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 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.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Preprint.
Keywords: 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
History: 2022-09-26: last of 3 revisions; 2022-08-15: received; See all versions
Short URL: https://ia.cr/2022/1056
License: CC BY

BibTeX

@misc{cryptoeprint:2022/1056,
      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},
      url = {https://eprint.iacr.org/2022/1056}
}