Local Proofs Approaching the Witness Length
Abstract
Interactive oracle proofs (IOPs) are a hybrid between interactive proofs and PCPs. In an IOP, the prover is allowed to interact with a verifier (like in an interactive proof) by sending relatively long messages to the verifier, who in turn is only allowed to query a few of the bits that were sent (like in a PCP). Efficient IOPs are currently at the core of leading practical implementations of highly efficient proof-systems.
In this work we construct, for a large class of NP relations, IOPs in which the communication complexity approaches the witness length. More precisely, for any NP relation for which membership can be decided in polynomial-time with bounded polynomial space (i.e., space nξ for some sufficiently small constant ξ > 0; e.g., SAT, Hamiltonicity, Clique, Vertex-Cover) and for any constant γ > 0, we construct an IOP with communication complexity (1 + γ) ⋅ n, where n is the original witness length. The number of rounds, as well as the number of queries made by the IOP verifier, are constant.
This result improves over prior works on short IOPs/PCPs in two ways. First, the communication complexity in these short IOPs is proportional to the complexity of verifying the NP witness, which can be polynomially larger than the witness size. Second, even ignoring the difference between witness length and non-deterministic verification time, prior works incur (at the very least) a large constant multiplicative overhead to the communication complexity.
In particular, as a special case, we also obtain an IOP for CircuitSAT with communication complexity (1 + γ) ⋅ t, for circuits of size t and any constant γ > 0. This improves upon the prior state-of-the-art work of Ben Sasson et al. (ICALP, 2017) who construct an IOP for CircuitSAT with communication length c ⋅ t for a large (unspecified) constant c ≥ 1.
Our proof leverages the local testability and (relaxed) local correctability of high-rate tensor codes, as well as their support of a sumcheck-like procedure. In particular, we bypass the barrier imposed by the low rate of multiplication codes (e.g., Reed–Solomon, Reed–Muller, or AG codes)—a key building block of all known short PCP/IOP constructions.
References
[1]
Amir Abboud, Aviad Rubinstein, and Ryan Williams. 2017. Distributed PCP theorems for hardness of approximation in P. In Proceedings of the 58th Annual IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society, 25–36. DOI:
[2]
Benny Applebaum. 2017. Exponentially-hard Gap-CSP and local PRG via local hardcore functions. In Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society, 836–847. DOI:
[3]
Gal Arnon, Alessandro Chiesa, and Eylon Yogev. 2022. Hardness of approximation for stochastic problems via interactive oracle proofs. In Proceedings of the 37th Computational Complexity Conference (CCC). LIPIcs, Vol. 234, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 24:1–24:16. DOI:
[4]
Gal Arnon, Alessandro Chiesa, and Eylon Yogev. 2022. A PCP theorem for interactive proofs and applications. In Proceedings of the 41st Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT). Vol. 13276, Springer, 64–94. DOI:
[5]
Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. 1998. Proof verification and intractability of approximation problems. Journal of the ACM 45, 3 (1998), 501–555.
[6]
Sanjeev Arora and Shmuel Safra. 1998. Probabilistic checkable proofs: A new characterization of NP. Journal of the ACM 45, 1 (1998), 70–122.
[7]
László Babai, Lance Fortnow, Leonid Levin, and Mario Szegedy. 1991. Checking computations in polylogarithmic time. In Proceedings of the 23rd Annual ACM Symposium on Theory of Computing (STOC). ACM, 21–31.
[8]
László Babai, Lance Fortnow, and Carsten Lund. 1991. Non-deterministic exponential time has two-prover interactive protocols. Computational Complexity 1 (1991), 3–40.
[9]
Omri Ben-Eliezer, Eldar Fischer, Amit Levi, and Ron D. Rothblum. 2020. Hard properties with (very) short PCPPs and their applications. In Proceedings of the 11th Innovations in Theoretical Computer Science Conference (ITCS). LIPIcs, Vol. 151, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 9:1–9:27. DOI:
[10]
Eli Ben-Sasson, Iddo Bentov, Yinon Horesh, and Michael Riabzev. 2018. Fast Reed-Solomon interactive oracle proofs of proximity. In Proceedings of the 45th International Colloquium on Automata, Languages and Programming (ICALP). Springer, 14:1–14:17. DOI:
[11]
Eli Ben-Sasson, Iddo Bentov, Yinon Horesh, and Michael Riabzev. 2019. Scalable zero knowledge with no trusted setup. In Proceedings of the 39th Annual International Cryptology Conference (Crypto). Lecture Notes in Computer Science, Springer, 701–732. DOI:
[12]
Eli Ben-Sasson, Alessandro Chiesa, Ariel Gabizon, Michael Riabzev, and Nicholas Spooner. 2017. Interactive oracle proofs with constant rate and query complexity. In Proceedings of the 44th International Colloquium on Automata, Languages and Programming (ICALP). Springer, 40:1–40:15. DOI:
[13]
Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin, and Eran Tromer. 2013. On the concrete efficiency of probabilistically-checkable proofs. In Proceedings of the 45th Annual ACM Symposium on Theory of Computing (STOC). ACM, 585–594. DOI:
[14]
Eli Ben-Sasson, Alessandro Chiesa, Michael Riabzev, Nicholas Spooner, Madars Virza, and Nicholas P. Ward. 2019. Aurora: Transparent succinct arguments for R1CS. In Proceedings of the 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT). Lecture Notes in Computer Science, Springer, 103–128. DOI:
[15]
Eli Ben-Sasson, Alessandro Chiesa, and Nicholas Spooner. 2016. Interactive oracle proofs. In Proceedings of the 14th IACR Theory of Cryptography Conference (TCC). Springer, 31–60. DOI:
[16]
Eli Ben-Sasson, Lior Goldberg, Swastik Kopparty, and Shubhangi Saraf. 2020. DEEP-FRI: Sampling outside the box improves soundness. In Proceedings of the 11th Innovations in Theoretical Computer Science Conference (ITCS). LIPIcs, Vol. 151, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 5:1–5:32. DOI:
[17]
Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, and Salil P. Vadhan. 2006. Robust PCPs of proximity, shorter PCPs, and applications to coding. SIAM Journal on Computing 36, 4 (2006), 889–974.
[18]
Eli Ben-Sasson, Yohay Kaplan, Swastik Kopparty, Or Meir, and Henning Stichtenoth. 2016. Constant rate PCPs for circuit-SAT with sublinear query complexity. Journal of the ACM 63, 4 (2016), 32:1–32:57. DOI:
[19]
Eli Ben-Sasson and Madhu Sudan. 2006. Robust locally testable codes and products of codes. Random Structures and Algorithms 28, 4 (2006), 387–402. DOI:
[20]
Eli Ben-Sasson and Madhu Sudan. 2008. Short PCPs with polylog query complexity. SIAM Journal on Computing 38, 2 (2008), 551–607. DOI:
[21]
Eli Ben-Sasson and Michael Viderman. 2015. Composition of semi-LTCs by two-wise tensor products. Computational Complexity 24, 3 (2015), 601–643. DOI:
[22]
Jonathan Bootle, Alessandro Chiesa, and Jens Groth. 2020. Linear-time arguments with sublinear verification from tensor codes. In Proceedings of the 18th International Theory of Cryptography Conference (TCC). Lecture Notes in Computer Science, Vol. 12551, Springer, 19–46. DOI:
[23]
Jonathan Bootle, Alessandro Chiesa, and Siqi Liu. 2022. Zero-knowledge IOPs with linear-time prover and polylogarithmic-time verifier. In Proceedings of the 41st Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT). Lecture Notes in Computer Science, Vol. 13276, Springer, 275–304. DOI:
[24]
Lijie Chen, Shafi Goldwasser, Kaifeng Lyu, Guy Rothblum, and Aviad Rubinstein. 2019. Fine-grained complexity meets IP = PSPACE. In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 1–20.
[25]
Irit Dinur. 2007. The PCP theorem by gap amplification. Journal of the ACM 54, 3 (2007), 12. DOI:
[26]
Irit Dinur. 2016. Mildly exponential reduction from gap 3SAT to polynomial-gap label-cover. Electronic Colloquium on Computational Complexity (ECCC) 23 (2016), 128. Retrieved from http://eccc.hpi-web.de/report/2016/128
[27]
Irit Dinur, Shai Evra, Ron Livne, Alexander Lubotzky, and Shahar Mozes. 2022. Locally testable codes with constant rate, distance, and locality. In Proceedings of the 54th Annual ACM Symposium on Theory of Computing (STOC). ACM, 357–374. DOI:
[28]
Irit Dinur and Omer Reingold. 2006. Assignment testers: Towards a combinatorial proof of the PCP theorem. SIAM Journal on Computing 36, 4 (2006), 975–1024. DOI:
[29]
Irit Dinur, Madhu Sudan, and Avi Wigderson. 2006. Robust local testability of tensor products of LDPC codes. In Proceedings of the 9th International Workshop on Randomization and Computation (RANDOM). Springer, 304–315.
[30]
Funda Ergün, Ravi Kumar, and Ronitt Rubinfeld. 2004. Fast approximate probabilistically checkable proofs. Information and Computation 189, 2 (2004), 135–159. DOI:
[31]
Uriel Feige, Shafi Goldwasser, László Lovász, Shmuel Safra, and Mario Szegedy. 1996. Interactive proofs and the hardness of approximating cliques. Journal of the ACM 43, 2 (1996), 268–292.
[32]
Lance Fortnow and Rahul Santhanam. 2011. Infeasibility of instance compression and succinct PCPs for NP. Journal of Computer and System Sciences 77, 1 (2011), 91–106. DOI:
[33]
Oded Goldreich. 2008. Computational Complexity - A Conceptual Perspective. Cambridge University Press.
[34]
Oded Goldreich. 2018. On doubly-efficient interactive proof systems. Foundations and Trends in Theoretical Computer Science 13, 3 (2018), 158–246. DOI:
[35]
Oded Goldreich and Johan Håstad. 1998. On the complexity of interactive proofs with bounded communication. Information Processing Letters 67, 4 (1998), 205–214. DOI:
[36]
Oded Goldreich and Or Meir. 2012. The tensor product of two good codes is not necessarily locally testable. Information Processing Letters 112, 8–9 (2012), 351–355.
[37]
Oded Goldreich, Salil P. Vadhan, and Avi Wigderson. 2002. On interactive proofs with a laconic prover. Computational Complexity 11, 1–2 (2002), 1–53. DOI:
[38]
Shafi Goldwasser, Yael Tauman Kalai, and Guy N. Rothblum. 2015. Delegating computation: Interactive proofs for muggles. Journal of the ACM 62, 4 (2015), 27:1–27:64. DOI:
[39]
Alexander Golovnev, Jonathan Lee, Srinath Setty, Justin Thaler, and Riad Wahby. 2021. Brakedown: Linear-Time and Post-Quantum SNARKs for R1CS. Cryptology ePrint Archive, Report 2021/1043. Retrieved from https://ia.cr/2021/1043
[40]
Tom Gur, Govind Ramnarayan, and Ron D. Rothblum. 2018. Relaxed locally correctable codes. In Proceedings of the 9th Innovations in Theoretical Computer Science Conference (ITCS). LIPIcs, Vol. 94, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 27:1–27:11. Retrieved from http://www.dagstuhl.de/dagpub/978-3-95977-060-6
[41]
Tom Gur and Ron D. Rothblum. 2018. Non-interactive proofs of proximity. Computational Complexity 27, 1 (2018), 99–207. DOI:
[42]
Johan Håstad. 2001. Some optimal inapproximability results. Journal of the ACM 48, 4 (2001), 798–859. DOI:
[43]
Neil Immerman. 1988. Nondeterministic space is closed under complementation. SIAM Journal on Computing 17, 5 (1988), 935–938. DOI:
[44]
Jørn Justesen. 1972. Class of constructive asymptotically good algebraic codes. IEEE Transactions on Information Theory 18, 5 (1972), 652–656. DOI:
[45]
Yael Tauman Kalai and Ran Raz. 2008. Interactive PCP. In Proceedings of the 35th International Colloquium on Automata, Languages, and Programming (ICALP). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 536–547. DOI:
[46]
Yael Tauman Kalai and Ron D. Rothblum. 2015. Arguments of proximity. In Proceedings of the 35th Annual International Cryptology Conference (Crypto). Lecture Notes in Computer Science, Springer, 422–442. DOI:
[47]
R. M. Karp. 1975. Reducibility among combinatorial problems. In Complexity of Computer Computations, Raymond E. Miller and James W. Thatcher (Eds.). Plenum Press, 85–103.
[48]
Joe Kilian. 1992. A note on efficient zero-knowledge proofs and arguments. In Proceedings of the 24th Annual ACM Symposium on Theory of Computing (STOC). ACM, 723–732. DOI:
[49]
Swastik Kopparty, Or Meir, Noga Ron-Zewi, and Shubhangi Saraf. 2017. High-rate locally correctable and locally testable codes with sub-polynomial query complexity. Journal of the ACM 64, 2 (2017), 11:1–11:42. DOI:
[50]
Swastik Kopparty, Shubhangi Saraf, and Sergey Yekhanin. 2014. High-rate codes with sublinear-time decoding. Journal of the ACM 61, 5 (2014), 28.
[51]
Carsten Lund, Lance Fortnow, Howard J. Karloff, and Noam Nisan. 1992. Algebraic methods for interactive proof systems. Journal of the ACM 39, 4 (1992), 859–868.
[52]
Pasin Manurangsi and Prasad Raghavendra. 2017. A birthday repetition theorem and complexity of approximating dense CSPs. In Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP). LIPIcs, Vol. 80, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 78:1–78:15. Retrieved from http://www.dagstuhl.de/dagpub/978-3-95977-041-5
[53]
Or Meir. 2013. IP = PSPACE using error-correcting codes. SIAM Journal on Computing 42, 1 (2013), 380–403. DOI:
[54]
Or Meir. 2014. Combinatorial PCPs with efficient verifiers. Computational Complexity 23, 3 (2014), 355–478. DOI:
[55]
Silvio Micali. 2000. Computationally sound proofs. SIAM Journal on Computing 30, 4 (2000), 1253–1298. DOI:
[56]
Thilo Mie. 2009. Short PCPPs verifiable in polylogarithmic time with O (1) queries. Annals of Mathematics and Artificial Intelligence 56, 3–4 (2009), 313–338.
[57]
David Muller. 1954. Application of boolean algebra to switching circuit design and to error detection. Transactions of the IRE Professional Group on Electronic Computers 3, 3 (1954), 6–12.
[58]
Shafik Nassar and Ron D. Rothblum. 2022. Succinct interactive oracle proofs: Applications and limitations. Advances in Cryptology - CRYPTO 2022-42nd Annual International Cryptology Conference, CRYPTO 2022, Lecture Notes in Computer Science, Yevgeniy Dodis and Thomas Shrimpton (Eds.). Vol. 13507, Springer, 504–532. DOI:
[59]
Pavel Panteleev and Gleb Kalachev. 2022. Asymptotically good quantum and locally testable classical LDPC codes. In Proceedings of the 54th Annual ACM Symposium on Theory of Computing (STOC). ACM, 375–388. DOI:
[60]
Nicholas Pippenger and Michael J. Fischer. 1979. Relations among complexity measures. Journal of the ACM 26, 2 (1979), 361–381. DOI:
[61]
Hugues Randriambololona. 2013. An upper bound of singleton type for componentwise products of linear codes. IEEE Transactions on Information Theory 59, 12 (2013), 7936–7939. DOI:
[62]
Irving Reed. 1954. A class of multiple-error-correcting codes and the decoding scheme. Transactions of the IRE Professional Group on Information Theory 4 (1954), 38–49.
[63]
Irving S. Reed and Gustave Solomon. 1960. Polynomial codes over certain finite fields. SIAM Journal of the Society for Industrial and Applied Mathematics 8, 2 (1960), 300–304.
[64]
Omer Reingold, Guy N. Rothblum, and Ron D. Rothblum. 2017. Personal Communication.
[65]
Omer Reingold, Guy N. Rothblum, and Ron D. Rothblum. 2021. Constant-round interactive proofs for delegating computation. SIAM Journal on Computing 50, 3 (2021). DOI:
[66]
Noga Ron-Zewi and Ron Rothblum. 2019. Local proofs approaching the witness length. Electronic Colloquium on Computational Complexity (2019), 127. Retrieved from https://eccc.weizmann.ac.il/report/2019/127https://eccc.weizmann.ac.il/report/2019/127/
[67]
Noga Ron-Zewi and Ron Rothblum. 2022. Proving as fast as computing: Succinct arguments with constant prover overhead. In Proceedings of the 54th Annual ACM Symposium on Theory of Computing (STOC). ACM, 1353–1363.
[68]
Guy N. Rothblum and Ron D. Rothblum. 2020. Batch verification and proofs of proximity with polylog overhead. In Proceedings of the 18th IACR Theory of Cryptography Conference (TCC). Lecture Notes in Computer Science, Vol. 12551, Springer, 108–138. DOI:
[69]
Guy N. Rothblum, Salil P. Vadhan, and Avi Wigderson. 2013. Interactive proofs of proximity: Delegating computation in sublinear time. In Proceedings of the 45th Annual Symposium on Theory of Computing (STOC). ACM, 793–802. DOI:
[70]
Aviad Rubinstein. 2018. Hardness of approximate nearest neighbor search. In Proceedings of the 50th Annual Symposium on Theory of Computing (STOC). ACM, 1260–1268. DOI:
[71]
Victor Shoup. 1988. New algorithms for finding irreducible polynomials over finite fields. In Proceedings of the 29th Annual IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society, 283–290. DOI:
[72]
Daniel A. Spielman. 1996. Linear-time encodable and decodable error-correcting codes. IEEE Transactions on Information Theory 42, 6 (1996), 1723–1731.
[73]
Henning Stichtenoth. 2006. Transitive and self-dual codes attaining the Tsfasman-Vladut-Zink bound. IEEE Transactions on Information Theory 52, 5 (2006), 2218–2224.
[74]
Madhu Sudan. 2000. Probabilistically Checkable Proofs - Lecture Notes. Retrieved May 9, 2024 from http://madhu.seas.harvard.edu/MIT/pcp/pcp.ps
[75]
Madhu Sudan. 2001. Algorithmic Introduction to Coding Theory (Lecture Notes).
[76]
Róbert Szelepcsényi. 1987. The method of forcing for nondeterministic automata. Bulletin of the EATCS 33 (1987), 96–99.
[77]
Paul Valiant. 2005. The tensor product of two codes is not necessarily robustly testable. In Proceedings of the 9th International Workshop on Randomization and Computation (RANDOM). Springer, 472–481.
[78]
Michael Viderman. 2015. A combination of testability and decodability by tensor products. Random Structures and Algorithms 46, 3 (2015), 572–598.
[79]
Tiancheng Xie, Yupeng Zhang, and Dawn Song. 2022. Orion: Zero knowledge proof with linear prover time. In Advances in Cryptology - CRYPTO 2022-42nd Annual International Cryptology Conference, CRYPTO 2022, Lecture Notes in Computer Science, Vol. 13510, Yevgeniy Dodis and Thomas Shrimpton (Eds.). Springer, 299–328. DOI:
Index Terms
- Local Proofs Approaching the Witness Length
Recommendations
A PCP Theorem for Interactive Proofs and Applications
Advances in Cryptology – EUROCRYPT 2022AbstractThe celebrated PCP Theorem states that any language in can be decided via a verifier that reads O(1) bits from a polynomially long proof. Interactive oracle proofs (IOP), a generalization of PCPs, allow the verifier to interact with the prover ...
Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
Traditional hardness versus randomness results focus on time-efficient randomized decision procedures. We generalize these trade-offs to a much wider class of randomized processes. We work out various applications, most notably to derandomizing Arthur-...
Computationally Sound Proofs
This paper puts forward a new notion of a proof based on computational complexity and explores its implications for computation at large. Computationally sound proofs provide, in a novel and meaningful framework, answers to old and new questions in ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
June 2024
323 pages
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 11 June 2024
Online AM: 25 April 2024
Accepted: 16 April 2024
Revised: 05 January 2024
Received: 31 October 2022
Published in JACM Volume 71, Issue 3
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
- Israeli Science Foundation
- Technion Hiroshi Fujiwara cyber security research center and Israel cyber directorate
- European Union
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 147Total Downloads
- Downloads (Last 12 months)147
- Downloads (Last 6 weeks)13
Reflects downloads up to 11 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in