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)
- 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
-
CC BY