Paper 2019/1230 Original: eprint.iacr.org/2019/1230 ↗
Linear-Size Constant-Query IOPs for Delegating Computation
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
- Preprint.
- History
- 2019-10-24: last updated
- 2019-10-21: published
- Short URL
- https://ia.cr/2019/1230
- License
- https://creativecommons.org/licenses/by/4.0/
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},
url = {https://eprint.iacr.org/2019/1230}
}