Paper 2019/1230

Linear-Size Constant-Query IOPs for Delegating Computation

Eli Ben-Sasson, Alessandro Chiesa, Lior Goldberg, Tom Gur, 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

BibTeX

@misc{cryptoeprint:2019/1230,
      author = {Eli Ben-Sasson and Alessandro Chiesa and Lior Goldberg and Tom Gur and Michael Riabzev and Nicholas Spooner},
      title = {Linear-Size Constant-Query IOPs for Delegating Computation},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1230},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/1230}},
      url = {https://eprint.iacr.org/2019/1230}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.