International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Linear-Size Constant-Query IOPs for Delegating Computation

Authors:
Eli Ben-Sasson
Alessandro Chiesa
Lior Goldberg
Tom Gur
Michael Riabzev
Nicholas Spooner
Download:
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.
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
}