Welcome to the resource topic for 2020/1426
Title:
Linear-Time Arguments with Sublinear Verification from Tensor Codes
Authors: Jonathan Bootle, Alessandro Chiesa, 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).
ePrint: https://eprint.iacr.org/2020/1426
Talk: https://www.youtube.com/watch?v=X4XI2t-XSVs
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .