International Association for Cryptologic Research

International Association
for Cryptologic Research


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

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
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). 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.
  title={Linear-Size Constant-Query IOPs for Delegating Computation},
  booktitle={Theory of Cryptography},
  series={Lecture Notes in Computer Science},
  author={Eli Ben-Sasson and Alessandro Chiesa and Lior Goldberg and Tom Gur and Michael Riabzev and Nicholas Spooner},