CryptoDB
Linear-Size Constant-Query IOPs for Delegating Computation
NOTE: imports for ToSC and TCHES are no longer functioning.
Authors: | |
---|---|
Download: | |
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 }