## CryptoDB

### Paper: Linear-Size Constant-Query IOPs for Delegating Computation

Authors: Eli Ben-Sasson Alessandro Chiesa Lior Goldberg Tom Gur Michael Riabzev Nicholas Spooner DOI: 10.1007/978-3-030-36033-7_19 Search ePrint Search Google 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). The relevant complexity measures for IOPs in this context are prover and verifier time, and query complexity.We construct highly efficient IOPs for a rich class of nondeterministic algebraic computations, which includes succinct versions of arithmetic circuit satisfiability and rank-one constraint system (R1CS) satisfiability. For a time-T computation, we obtain prover arithmetic complexity $O(T \log T)$ and verifier complexity polylog(T). These IOPs are the first to simultaneously achieve the state of the art in prover complexity, due to [14], and in verifier complexity, due to [7]. We also improve upon the query complexity of both schemes.The efficiency of our prover is a result of our highly optimized proof length; in particular, ours is the first construction that simultaneously achieves linear-size proofs and polylogarithmic-time verification, regardless of query complexity.
##### BibTeX
@article{tcc-2019-30005,
title={Linear-Size Constant-Query IOPs for Delegating Computation},
booktitle={Theory of Cryptography},
series={Lecture Notes in Computer Science},
publisher={Springer},
volume={11892},
pages={494-521},
doi={10.1007/978-3-030-36033-7_19},
author={Eli Ben-Sasson and Alessandro Chiesa and Lior Goldberg and Tom Gur and Michael Riabzev and Nicholas Spooner},
year=2019
}