Cryptology ePrint Archive: Report 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).

Category / Keywords: foundations / interactive oracle proofs; probabilistically checkable proofs; delegation of computation

Original Publication (with major differences): IACR-TCC-2019

Date: received 19 Oct 2019, last revised 23 Oct 2019

Contact author: alexch at berkeley edu

Available format(s): PDF | BibTeX Citation

Version: 20191024:043418 (All versions of this report)

Short URL: ia.cr/2019/1230


[ Cryptology ePrint archive ]