Document Open Access Logo

Interactive Oracle Proofs with Constant Rate and Query Complexity

Authors Eli Ben-Sasson, Alessandro Chiesa, Ariel Gabizon, Michael Riabzev, Nicholas Spooner

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2017.40.pdf
  • Filesize: 0.56 MB
  • 15 pages

Document Identifiers

Author Details

Eli Ben-Sasson
Alessandro Chiesa
Ariel Gabizon
Michael Riabzev
Nicholas Spooner

Cite As Get BibTex

Eli Ben-Sasson, Alessandro Chiesa, Ariel Gabizon, Michael Riabzev, and Nicholas Spooner. Interactive Oracle Proofs with Constant Rate and Query Complexity. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 40:1-40:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ICALP.2017.40

Abstract

We study interactive oracle proofs (IOPs) [BCS16,RRR16], which combine aspects of probabilistically checkable proofs (PCPs) and interactive proofs (IPs). We present IOP constructions and techniques that enable us to obtain tradeoffs in proof length versus query complexity that are not known to be achievable via PCPs or IPs alone. Our main results are:
1. Circuit satisfiability has 3-round IOPs with linear proof length (counted in bits) and constant query complexity.
2. Reed-Solomon codes have 2-round IOPs of proximity with linear proof length and constant query complexity.
3. Tensor product codes have 1-round IOPs of proximity with sublinear proof length and constant query complexity.

For all the above, known PCP constructions give quasilinear proof length and constant query complexity [BS08,Din07]. Also, for circuit satisfiability, [BKKMS13] obtain PCPs with linear proof length but sublinear (and super-constant) query complexity. As in [BKKMS13], we rely on algebraic-geometry codes to obtain our first result; but, unlike that work, our use of such codes is much "lighter" because we do not rely on any automorphisms of the code.

We obtain our results by proving and combining "IOP-analogues" of tools underlying numerous IPs and PCPs:
* Interactive proof composition.  Proof composition [AS98] is used to reduce the query complexity of PCP verifiers, at the cost of increasing proof length by an additive factor that is exponential in the verifier's randomness complexity. We prove a composition theorem for IOPs where this additive factor is linear.
* Sublinear sumcheck.  The sumcheck protocol [LFKN92] is an IP that enables the verifier to check the sum of values of a low-degree multi-variate polynomial on an exponentially-large hypercube, but the verifier's running time depends linearly on the bound on individual degrees. We prove a sumcheck protocol for IOPs where this dependence is sublinear (e.g., polylogarithmic).

Our work demonstrates that even constant-round IOPs are more efficient than known PCPs and IPs.

Subject Classification

Keywords
  • probabilistically checkable proofs
  • interactive proofs
  • proof composition
  • sumcheck

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Noga Alon, Oded Goldreich, Johan Håstad, and René Peralta. Simple construction of almost k-wise independent random variables. Random Structures and Algorithms, 3(3):289-304, 1992. Google Scholar
  2. Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof verification and the hardness of approximation problems. Journal of the ACM, 45(3):501-555, 1998. Preliminary version in FOCS'92. Google Scholar
  3. Sanjeev Arora and Shmuel Safra. Probabilistic checking of proofs: a new characterization of NP. Journal of the ACM, 45(1):70-122, 1998. Preliminary version in FOCS'92. Google Scholar
  4. László Babai. Trading group theory for randomness. In Proceedings of the 17th Annual ACM Symposium on Theory of Computing, STOC'85, pages 421-429, 1985. Google Scholar
  5. László Babai, Lance Fortnow, Leonid A. Levin, and Mario Szegedy. Checking computations in polylogarithmic time. In Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, STOC'91, pages 21-32, 1991. Google Scholar
  6. Eli Ben-Sasson, Alessandro Chiesa, Ariel Gabizon, and Madars Virza. Quasilinear-size zero knowledge from linear-algebraic PCPs. In Proceedings of the 13th Theory of Cryptography Conference, TCC'16-A, pages 33-64, 2016. Google Scholar
  7. Eli Ben-Sasson, Alessandro Chiesa, and Nicholas Spooner. Interactive oracle proofs. In Proceedings of the 14th Theory of Cryptography Conference, TCC'16-B, pages 31-60, 2016. Google Scholar
  8. Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, and Salil Vadhan. Short PCPs verifiable in polylogarithmic time. In Proceedings of the 20th Annual IEEE Conference on Computational Complexity, CCC'05, pages 120-134, 2005. Google Scholar
  9. Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, and Salil P. Vadhan. Robust PCPs of proximity, shorter PCPs, and applications to coding. SIAM Journal on Computing, 36(4):889-974, 2006. Google Scholar
  10. Eli Ben-Sasson, Yohay Kaplan, Swastik Kopparty, Or Meir, and Henning Stichtenoth. Constant rate PCPs for Circuit-SAT with sublinear query complexity. In Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS'13, pages 320-329, 2013. Google Scholar
  11. Eli Ben-Sasson and Madhu Sudan. Robust locally testable codes and products of codes. Random Structures and Algorithms, 28(4):387-402, 2006. Google Scholar
  12. Eli Ben-Sasson and Madhu Sudan. Short PCPs with polylog query complexity. SIAM Journal on Computing, 38(2):551-607, 2008. Preliminary version appeared in STOC'05. Google Scholar
  13. Eli Ben-Sasson, Madhu Sudan, Salil Vadhan, and Avi Wigderson. Randomness-efficient low degree tests and short PCPs via epsilon-biased sets. In Proceedings of the 35th Annual ACM Symposium on Theory of Computing, STOC'03, pages 612-621, 2003. Google Scholar
  14. D. V. Chudnovsky and G. V. Chudnovsky. Algebraic complexities and algebraic curves over finite fields. Journal of Complexity, 4(4):285-316, 1988. Google Scholar
  15. Richard A. DeMillo and Richard J. Lipton. A probabilistic remark on algebraic program testing. Information Processing Letters, 7(4):193-195, 1978. Google Scholar
  16. Irit Dinur. The PCP theorem by gap amplification. Journal of the ACM, 54(3):12, 2007. Google Scholar
  17. Irit Dinur and Omer Reingold. Assignment testers: Towards a combinatorial proof of the PCP theorem. In Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, FOCS'04, pages 155-164, 2004. Google Scholar
  18. Irit Dinur, Madhu Sudan, and Avi Wigderson. Robust local testability of tensor products of LDPC codes. In Proceedings of the 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, and of the 10th International Workshop on Randomization and Computation, APPROX-RANDOM'06, pages 304-315, 2006. Google Scholar
  19. Klim Efremenko. 3-query locally decodable codes of subexponential length. SIAM Journal on Computing, 41(6):1694-1703, 2012. Preliminary version appeared in STOC'09. Google Scholar
  20. Uriel Feige, Shafi Goldwasser, László Lovász, Shmuel Safra, and Mario Szegedy. Approximating clique is almost NP-complete (preliminary version). In Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, SFCS'91, pages 2-12, 1991. Google Scholar
  21. Amos Fiat and Adi Shamir. How to prove yourself: practical solutions to identification and signature problems. In Proceedings of the 6th Annual International Cryptology Conference, CRYPTO'86, pages 186-194, 1986. Google Scholar
  22. Lance Fortnow, John Rompel, and Michael Sipser. On the power of multi-prover interactive protocols. In Theoretical Computer Science, pages 156-161, 1988. Google Scholar
  23. Arnaldo Garcia and Henning Stichtenoth. On the asymptotic behaviour of some towers of function fields over finite fields. Journal of Number Theory, 61(2):248-273, 1996. Google Scholar
  24. Oded Goldreich and Madhu Sudan. Locally testable codes and PCPs of almost-linear length. Journal of the ACM, 53:558-655, July 2006. Preliminary version in STOC'02. Google Scholar
  25. Shafi Goldwasser, Yael Tauman Kalai, and Guy N. Rothblum. Delegating computation: Interactive proofs for Muggles. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing, STOC'08, pages 113-122, 2008. Google Scholar
  26. Shafi Goldwasser, Silvio Micali, and Charles Rackoff. The knowledge complexity of interactive proof systems. SIAM Journal on Computing, 18(1):186-208, 1989. Preliminary version appeared in STOC'85. Google Scholar
  27. Parikshit Gopalan, Venkatesan Guruswami, and Prasad Raghavendra. List decoding tensor products and interleaved codes. SIAM Journal on Computing, 40(5):1432-1462, 2011. Preliminary version appeared in STOC'09. Google Scholar
  28. Vipul Goyal, Yuval Ishai, Mohammad Mahmoody, and Amit Sahai. Interactive locking, zero-knowledge PCPs, and unconditional cryptography. In Proceedings of the 30th Annual Conference on Advances in Cryptology, CRYPTO'10, pages 173-190, 2010. Google Scholar
  29. Venkatesan Guruswami and Piotr Indyk. Linear-time encodable/decodable codes with near-optimal rate. IEEE Transactions on Information Theory, 51(10):3393-3400, 2005. Preliminary version appeared in STOC'03. Google Scholar
  30. Prahladh Harsha and Madhu Sudan. Small PCPs with low query complexity. Computational Complexity, 9(3-4):157-201, Dec 2000. Preliminary version in STACS'01. Google Scholar
  31. Yael Kalai and Ran Raz. Interactive PCP. In Proceedings of the 35th International Colloquium on Automata, Languages and Programming, ICALP'08, pages 536-547, 2008. Google Scholar
  32. Swastik Kopparty, Or Meir, Noga Ron-Zewi, and Shubhangi Saraf. High-rate locally-correctable and locally-testable codes with sub-polynomial query complexity. In Proceedings of the 48th ACM Symposium on the Theory of Computing, STOC'16, pages 202-215, 2016. Google Scholar
  33. Swastik Kopparty, Shubhangi Saraf, and Sergey Yekhanin. High-rate codes with sublinear-time decoding. Journal of the ACM, 61(5):28:1-28:20, 2014. Preliminary version appeared in STOC'11. Google Scholar
  34. Carsten Lund, Lance Fortnow, Howard J. Karloff, and Noam Nisan. Algebraic methods for interactive proof systems. Journal of the ACM, 39(4):859-868, 1992. Google Scholar
  35. Or Meir. Combinatorial PCPs with short proofs. In Proceedings of the 26th Annual IEEE Conference on Computational Complexity, CCC'12, 2012. Google Scholar
  36. Or Meir. IP = PSPACE using error-correcting codes. SIAM Journal on Computing, 42(1):380-403, 2013. Google Scholar
  37. Silvio Micali. Computationally sound proofs. SIAM Journal on Computing, 30(4):1253-1298, 2000. Preliminary version appeared in FOCS'94. Google Scholar
  38. Thilo Mie. Short PCPPs verifiable in polylogarithmic time with o(1) queries. Annals of Mathematics and Artificial Intelligence, 56:313-338, 2009. Google Scholar
  39. Joseph Naor and Moni Naor. Small-bias probability spaces: efficient constructions and applications. In Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, STOC'90, pages 213-223, 1990. Google Scholar
  40. Nicholas Pippenger and Michael J. Fischer. Relations among complexity measures. Journal of the ACM, 26(2):361-381, 1979. Google Scholar
  41. David Pointcheval and Jacques Stern. Security proofs for signature schemes. In Proceedings of the 14th Annual International Conference on Theory and Application of Cryptographic Techniques, EUROCRYPT'96, pages 387-398, 1996. Google Scholar
  42. Alexander Polishchuk and Daniel A. Spielman. Nearly-linear size holographic proofs. In Proceedings of the 26th Annual ACM Symposium on Theory of Computing, STOC'94, pages 194-203, 1994. Google Scholar
  43. Omer Reingold, Ron Rothblum, and Guy Rothblum. Constant-round interactive proofs for delegating computation. In Proceedings of the 48th ACM Symposium on the Theory of Computing, STOC'16, pages 49-62, 2016. Google Scholar
  44. Ron M. Roth and Vitaly Skachek. Improved nearly-MDS expander codes. IEEE Transactions on Information Theory, 52(8):3650-3661, 2006. Google Scholar
  45. Jacob T. Schwartz. Fast probabilistic algorithms for verification of polynomial identities. Journal of the ACM, 27(4):701-717, 1980. Google Scholar
  46. Adi Shamir. IP = PSPACE. Journal of the ACM, 39(4):869-877, 1992. Google Scholar
  47. Kenneth W. Shum, Ilia Aleshnikov, P. Vijay Kumar, Henning Stichtenoth, and Vinay Deolalikar. A low-complexity algorithm for the construction of algebraic-geometric codes better than the Gilbert-Varshamov bound. IEEE Transactions on Information Theory, 47(6):2225-2241, 2001. Google Scholar
  48. Daniel A. Spielman. Linear-time encodable and decodable error-correcting codes. IEEE Transactions on Information Theory, 42(6):1723-1731, 1996. Preliminary version appeared in STOC'95. Google Scholar
  49. Paul Valiant. Incrementally verifiable computation or proofs of knowledge imply time/space efficiency. In Proceedings of the 5th Theory of Cryptography Conference, TCC'08, pages 1-18, 2008. Google Scholar
  50. Michael Viderman. A note on high-rate locally testable codes with sublinear query complexity, 2010. ECCC TR10-171. Google Scholar
  51. Michael Viderman. A combination of testability and decodability by tensor products. Random Structures and Algorithms, 46(3):572-598, 2015. Preliminary version appeared in APPROX-RANDOM'12. Google Scholar
  52. Sergey Yekhanin. Towards 3-query locally decodable codes of subexponential length. Journal of the ACM, 55(1), 2008. Preliminary version appeared in STOC'07. Google Scholar
  53. Richard Zippel. Probabilistic algorithms for sparse polynomials. In Proceedings of the 1979 International Symposium on Symbolic and Algebraic Computation, EUROSAM'79, pages 216-226, 1979. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact