Paper 2020/1426

Linear-Time Arguments with Sublinear Verification from Tensor Codes

Jonathan Bootle, 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).

Note: Added full version.

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

BibTeX

@misc{cryptoeprint:2020/1426,
      author = {Jonathan Bootle and Alessandro Chiesa and Jens Groth},
      title = {Linear-Time Arguments with Sublinear Verification from Tensor Codes},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1426},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/1426}},
      url = {https://eprint.iacr.org/2020/1426}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.