**Linear-Time Arguments with Sublinear Verification from Tensor Codes**

*Jonathan Bootle and Alessandro Chiesa and Jens Groth*

**Abstract: **Minimizing the computational cost of the prover is a central goal in the area of succinct arguments. In particular, it remains a challenging open problem to construct a succinct argument where the prover runs in linear time and the verifier runs in polylogarithmic time.

We make progress towards this goal by presenting a new linear-time probabilistic proof. For any fixed $\epsilon > 0$, we construct an interactive oracle proof (IOP) that, when used for the satisfiability of an $N$-gate arithmetic circuit, has a prover that uses $O(N)$ field operations and a verifier that uses $O(N^{\epsilon})$ field operations. The sublinear verifier time is achieved in the holographic setting for every circuit (the verifier has oracle access to a linear-size encoding of the circuit that is computable in linear time).

When combined with a linear-time collision-resistant hash function, our IOP immediately leads to an argument system where the prover performs $O(N)$ field operations and hash computations, and the verifier performs $O(N^{\epsilon})$ field operations and hash computations (given a short digest of the $N$-gate circuit).

**Category / Keywords: **foundations / interactive oracle proofs; tensor codes; succinct arguments

**Original Publication**** (with major differences): **IACR-TCC-2020

**Date: **received 14 Nov 2020, last revised 28 Dec 2020

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

**Available format(s): **PDF | BibTeX Citation

**Note: **Added full version.

**Version: **20201228:222449 (All versions of this report)

**Short URL: **ia.cr/2020/1426

[ Cryptology ePrint archive ]