You are looking at a specific version 20201115:074602 of this paper. See the latest version.

Paper 2020/1426

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).

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A major revision of an IACR publication in TCC 2020
Keywords
interactive oracle proofstensor codessuccinct arguments
Contact author(s)
jbt @ zurich ibm com,alexch @ berkeley edu
History
2020-12-28: revised
2020-11-15: received
See all versions
Short URL
https://ia.cr/2020/1426
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.