You are looking at a specific version 20191024:043418 of this paper. See the latest version.

Paper 2019/1230

Linear-Size Constant-Query IOPs for Delegating Computation

Eli Ben-Sasson and Alessandro Chiesa and Lior Goldberg and Tom Gur and Michael Riabzev and Nicholas Spooner

Abstract

We study the problem of delegating computations via interactive proofs that can be probabilistically checked. Known as *interactive oracle proofs* (IOPs), these proofs extend probabilistically checkable proofs (PCPs) to multi-round protocols, and have received much attention due to their application to constructing cryptographic proofs (such as succinct non-interactive arguments). We prove that a rich class of NEXP-complete problems, which includes machine computations over large fields and succinctly-described arithmetic circuits, has constant-query IOPs with O(T)-size proofs and polylog(T)-time verification for T-size computations. This is the first construction that simultaneously achieves linear-size proofs and fast verification, regardless of query complexity. An important metric when using IOPs to delegate computations is the cost of producing the proof. The highly-optimized proof length in our construction enables a very efficient prover, with arithmetic complexity O(T log T). Hence this construction is also the first to simultaneously achieve prover complexity O(T log T) and verifier complexity polylog(T).

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A major revision of an IACR publication in TCC 2019
Keywords
interactive oracle proofsprobabilistically checkable proofsdelegation of computation
Contact author(s)
alexch @ berkeley edu
History
2019-10-24: revised
2019-10-21: received
See all versions
Short URL
https://ia.cr/2019/1230
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.