{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,21]],"date-time":"2025-12-21T01:02:42Z","timestamp":1766278962412,"version":"3.48.0"},"publisher-location":"Cham","reference-count":39,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031223174"},{"type":"electronic","value":"9783031223181"}],"license":[{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022]]},"DOI":"10.1007\/978-3-031-22318-1_16","type":"book-chapter","created":{"date-parts":[[2022,12,21]],"date-time":"2022-12-21T03:04:30Z","timestamp":1671591870000},"page":"447-466","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["A Toolbox for\u00a0Barriers on\u00a0Interactive Oracle Proofs"],"prefix":"10.1007","author":[{"given":"Gal","family":"Arnon","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Amey","family":"Bhangale","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alessandro","family":"Chiesa","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eylon","family":"Yogev","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,12,21]]},"reference":[{"key":"16_CR1","unstructured":"Applebaum, B., Golombek, E.: On the randomness complexity of interactive proofs and statistical zero-knowledge proofs. In: Proceedings of the 2nd Conference on Information-Theoretic Cryptography, ITC 2021, pp. 4:1\u20134:23 (2021)"},{"key":"16_CR2","unstructured":"Arnon, G., Chiesa, A., Yogev, E.: Hardness of approximation for stochastic problems via interactive oracle proofs. In: Proceedings of the 37th Annual IEEE Conference on Computational Complexity, CCC 2022, pp. 24:1\u201324:16 (2022)"},{"key":"16_CR3","doi-asserted-by":"crossref","unstructured":"Arnon, G., Chiesa, A., Yogev, E.: A PCP theorem for interactive proofs. In: Proceedings of the 41st Annual International Conference on Theory and Application of Cryptographic Techniques, EUROCRYPT 2022, pp. 64\u201394 (2022)","DOI":"10.1007\/978-3-031-07085-3_3"},{"key":"16_CR4","doi-asserted-by":"crossref","unstructured":"Arora, S., Lund, C., Motwani, R., Sudan, M., Szegedy, M.: Proof verification and the hardness of approximation problems. J. ACM 45(3), 501\u2013555 (1998). Preliminary version in FOCS \u201992","DOI":"10.1145\/278298.278306"},{"key":"16_CR5","doi-asserted-by":"crossref","unstructured":"Arora, S., Safra, S.: Probabilistic checking of proofs: a new characterization of NP. J. ACM 45(1), 70\u2013122 (1998). Preliminary version in FOCS \u201992","DOI":"10.1145\/273865.273901"},{"key":"16_CR6","doi-asserted-by":"crossref","unstructured":"Babai, L., Fortnow, L., Levin, L.A., Szegedy, M.: Checking computations in polylogarithmic time. In: Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, STOC 1991, pp. 21\u201332 (1991)","DOI":"10.1145\/103418.103428"},{"key":"16_CR7","doi-asserted-by":"crossref","unstructured":"Bellare, M., Goldwasser, S., Lund, C., Russell, A.: Efficient probabilistically checkable proofs and applications to approximations. In: Proceedings of the 25th Annual ACM Symposium on Theory of Computing, STOC 1993, pp. 294\u2013304 (1993)","DOI":"10.1145\/167088.167174"},{"key":"16_CR8","doi-asserted-by":"crossref","unstructured":"Ben-Sasson, E., et al.: Computational integrity with a public random string from quasi-linear PCPs. In: Proceedings of the 36th Annual International Conference on Theory and Application of Cryptographic Techniques, EUROCRYPT 2017, pp. 551\u2013579 (2017)","DOI":"10.1007\/978-3-319-56617-7_19"},{"key":"16_CR9","unstructured":"Ben-Sasson, E., Bentov, I., Horesh, Y., Riabzev, M.: Fast Reed-Solomon interactive oracle proofs of proximity. In: Proceedings of the 45th International Colloquium on Automata, Languages and Programming, ICALP 2018, pp. 14:1\u201314:17 (2018)"},{"key":"16_CR10","unstructured":"Ben-Sasson, E., Chiesa, A., Gabizon, A., Riabzev, M., Spooner, N.: Interactive oracle proofs with constant rate and query complexity. In: Proceedings of the 44th International Colloquium on Automata, Languages and Programming, ICALP 2017, pp. 40:1\u201340:15 (2017)"},{"key":"16_CR11","doi-asserted-by":"crossref","unstructured":"Ben-Sasson, E., Chiesa, A., Gabizon, A., Virza, M.: Quasilinear-size zero knowledge from linear-algebraic PCPs. In: Proceedings of the 13th Theory of Cryptography Conference, TCC 2016-A, pp. 33\u201364 (2016)","DOI":"10.1007\/978-3-662-49099-0_2"},{"key":"16_CR12","doi-asserted-by":"crossref","unstructured":"Ben-Sasson, E., Chiesa, A., Spooner, N.: Interactive oracle proofs. In: Proceedings of the 14th Theory of Cryptography Conference, TCC 2016-B, pp. 31\u201360 (2016)","DOI":"10.1007\/978-3-662-53644-5_2"},{"key":"16_CR13","doi-asserted-by":"crossref","unstructured":"Ben-Sasson, E., Sudan, M.: Short PCPs with polylog query complexity. SIAM J. Comput. 38(2), 551\u2013607 (2008). Preliminary version appeared in STOC \u201905","DOI":"10.1137\/050646445"},{"key":"16_CR14","doi-asserted-by":"crossref","unstructured":"Bootle, J., Cerulli, A., Ghadafi, E., Groth, J., Hajiabadi, M., Jakobsen, S.K.: Linear-time zero-knowledge proofs for arithmetic circuit satisfiability. In: Proceedings of the 23rd International Conference on the Theory and Applications of Cryptology and Information Security, ASIACRYPT 2017, pp. 336\u2013365 (2017)","DOI":"10.1007\/978-3-319-70700-6_12"},{"key":"16_CR15","doi-asserted-by":"crossref","unstructured":"Bootle, J., Chiesa, A., Groth, J.: Linear-time arguments with sublinear verification from tensor codes. In: Proceedings of the 18th Theory of Cryptography Conference, TCC 2020, pp. 19\u201346 (2020)","DOI":"10.1007\/978-3-030-64378-2_2"},{"key":"16_CR16","doi-asserted-by":"crossref","unstructured":"Bootle, J., Chiesa, A., Liu, S.: Zero-knowledge IOPs with linear-time prover and polylogarithmic-time verifier. In: Proceedings of the 41st Annual International Conference on Theory and Application of Cryptographic Techniques, EUROCRYPT 2022, pp. 275\u2013304 (2022)","DOI":"10.1007\/978-3-031-07085-3_10"},{"key":"16_CR17","unstructured":"Bordage, S., Nardi, J.: Interactive oracle proofs of proximity to algebraic geometry codes. In: Proceedings of the 37th Annual IEEE Conference on Computational Complexity, CCC 2022, pp. 30:1\u201330:45 (2022)"},{"key":"16_CR18","doi-asserted-by":"crossref","unstructured":"Chiesa, A., Yogev, E.: Barriers for succinct arguments in the random oracle model. In: Proceedings of the 18th Theory of Cryptography Conference, TCC 2020, pp. 47\u201376 (2020)","DOI":"10.1007\/978-3-030-64378-2_3"},{"issue":"2","key":"16_CR19","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1137\/S0097539793260738","volume":"26","author":"A Condon","year":"1997","unstructured":"Condon, A., Feigenbaum, J., Lund, C., Shor, P.W.: Random debaters and the hardness of approximating stochastic functions. SIAM J. Comput. 26(2), 369\u2013400 (1997)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"16_CR20","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1145\/1236457.1236459","volume":"54","author":"I Dinur","year":"2007","unstructured":"Dinur, I.: The PCP theorem by gap amplification. J. ACM 54(3), 12 (2007)","journal-title":"J. ACM"},{"key":"16_CR21","doi-asserted-by":"crossref","unstructured":"Dinur, I., Harsha, P., Kindler, G.: Polynomially low error PCPs with polyloglog n queries via modular composition. In: Proceedings of the 47th Annual ACM Symposium on Theory of Computing, STOC 2015, pp. 267\u2013276 (2015)","DOI":"10.1145\/2746539.2746630"},{"key":"16_CR22","doi-asserted-by":"crossref","unstructured":"Drucker, A.: A PCP characterization of AM. In: Proceedings of the 38th International Colloquium on Automata, Languages and Programming, ICALP 2011, pp. 581\u2013592 (2011)","DOI":"10.1007\/978-3-642-22006-7_49"},{"key":"16_CR23","doi-asserted-by":"crossref","unstructured":"Feige, U., Goldwasser, S., Lov\u00e1sz, L., Safra, S., Szegedy, M.: Approximating clique is almost NP-complete (preliminary version). In: Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, SFCS 1991, pp. 2\u201312 (1991)","DOI":"10.1109\/SFCS.1991.185341"},{"key":"16_CR24","doi-asserted-by":"crossref","unstructured":"Feige, U., Goldwasser, S., Lov\u00e1sz, L., Safra, S., Szegedy, M.: Interactive proofs and the hardness of approximating cliques. J. ACM 43(2), 268\u2013292 (1996). Preliminary version in FOCS \u201991","DOI":"10.1145\/226643.226652"},{"key":"16_CR25","first-page":"429","volume":"5","author":"M F\u00fcrer","year":"1989","unstructured":"F\u00fcrer, M., Goldreich, O., Mansour, Y., Sipser, M., Zachos, S.: On completeness and soundness in interactive proof systems. Adv. Comput. Res. 5, 429\u2013442 (1989)","journal-title":"Adv. Comput. Res."},{"issue":"4","key":"16_CR26","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/S0020-0190(98)00116-1","volume":"67","author":"O Goldreich","year":"1998","unstructured":"Goldreich, O., H\u00e5stad, J.: On the complexity of interactive proofs with bounded communication. Inf. Process. Lett. 67(4), 205\u2013214 (1998)","journal-title":"Inf. Process. Lett."},{"issue":"1\/2","key":"16_CR27","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00037-002-0169-0","volume":"11","author":"O Goldreich","year":"2002","unstructured":"Goldreich, O., Vadhan, S., Wigderson, A.: On interactive proofs with a laconic prover. Comput. Complex. 11(1\/2), 1\u201353 (2002)","journal-title":"Comput. Complex."},{"key":"16_CR28","unstructured":"Golovnev, A., Lee, J., V., S.S.T., Thaler, J., Wahby, R.S.: Brakedown: linear-time and post-quantum snarks for R1CS. Cryptology ePrint Archive, Report 2021\/1043 (2021)"},{"key":"16_CR29","doi-asserted-by":"crossref","unstructured":"Hast, G.: Beating a random assignment: approximating constraint satisfaction problems. Ph.D. thesis, KTH (2005)","DOI":"10.1007\/11538462_12"},{"issue":"1","key":"16_CR30","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1137\/120882718","volume":"43","author":"J H\u00e5stad","year":"2014","unstructured":"H\u00e5stad, J.: On the NP-hardness of max-not-2. SIAM J. Comput. 43(1), 179\u2013193 (2014)","journal-title":"SIAM J. Comput."},{"key":"16_CR31","unstructured":"Lee, J., Setty, S.T.V., Thaler, J., Wahby, R.S.: Linear-time zero-knowledge snarks for R1CS. Cryptology ePrint Archive, Report 2021\/30 (2021)"},{"issue":"3","key":"16_CR32","doi-asserted-by":"publisher","first-page":"1","DOI":"10.4086\/toc.2022.v018a003","volume":"18","author":"P Manurangsi","year":"2022","unstructured":"Manurangsi, P., Nakkiran, P., Trevisan, L.: Near-optimal NP-hardness of approximating MAX k-CSPR. Theory Comput. 18(3), 1\u201329 (2022)","journal-title":"Theory Comput."},{"key":"16_CR33","doi-asserted-by":"crossref","unstructured":"Nassar, S., Rothblum, R.D.: Succinct interactive oracle proofs: applications and limitations. In: Proceedings of the 42nd Annual International Cryptology Conference, CRYPTO 2022 (2022)","DOI":"10.1007\/978-3-031-15802-5_18"},{"key":"16_CR34","doi-asserted-by":"crossref","unstructured":"Reingold, O., Rothblum, R., Rothblum, G.: Constant-round interactive proofs for delegating computation. In: Proceedings of the 48th ACM Symposium on the Theory of Computing, STOC 2016, pp. 49\u201362 (2016)","DOI":"10.1145\/2897518.2897652"},{"key":"16_CR35","doi-asserted-by":"crossref","unstructured":"Ron-Zewi, N., Rothblum, R.: Local proofs approaching the witness length. In: Proceedings of the 61st Annual IEEE Symposium on Foundations of Computer Science, FOCS 2020, pp. 846\u2013857 (2020)","DOI":"10.1109\/FOCS46700.2020.00083"},{"key":"16_CR36","doi-asserted-by":"crossref","unstructured":"Ron-Zewi, N., Rothblum, R.D.: Proving as fast as computing: succinct arguments with constant prover overhead. In: Proceedings of the 54th ACM Symposium on the Theory of Computing, STOC 2022, pp. 1353\u20131363 (2022)","DOI":"10.1145\/3519935.3519956"},{"key":"16_CR37","doi-asserted-by":"crossref","unstructured":"Schaefer, T.J.: The complexity of satisfiability problems. In: Proceedings of the 10th Annual ACM Symposium on Theory of Computing, STOC 1978, pp. 216\u2013226 (1978)","DOI":"10.1145\/800133.804350"},{"key":"16_CR38","doi-asserted-by":"crossref","unstructured":"Xie, T., Zhang, J., Zhang, Y., Papamanthou, C., Song, D.: Libra: succinct zero-knowledge proofs with optimal prover computation. In: Proceedings of the 39th Annual International Cryptology Conference, CRYPTO 1919, pp. 733\u2013764 (2019)","DOI":"10.1007\/978-3-030-26954-8_24"},{"key":"16_CR39","unstructured":"Zwick, U.: Approximation algorithms for constraint satisfaction problems involving at most three variables per constraint. In: Proceedings of the 9th Annual Symposium on Discrete Algorithms, SODA 1998, pp. 201\u2013210 (1998)"}],"container-title":["Lecture Notes in Computer Science","Theory of Cryptography"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-22318-1_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,21]],"date-time":"2025-12-21T01:01:59Z","timestamp":1766278919000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-22318-1_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9783031223174","9783031223181"],"references-count":39,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-22318-1_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2022]]},"assertion":[{"value":"21 December 2022","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"TCC","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Theory of Cryptography Conference","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Chicago, IL","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"USA","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2022","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"7 November 2022","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"10 November 2022","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"20","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"tcc2022","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/tcc.iacr.org\/2022\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"HotCRP","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"139","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"60","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"43% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3.1","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"9.9","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}