{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,9]],"date-time":"2026-05-09T01:55:37Z","timestamp":1778291737651,"version":"3.51.4"},"reference-count":66,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T00:00:00Z","timestamp":1743120000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"ISF","award":["735\/20"],"award-info":[{"award-number":["735\/20"]}]},{"name":"ERC, ECCC","award":["101076663"],"award-info":[{"award-number":["101076663"]}]},{"DOI":"10.13039\/501100003977","name":"Israeli Science Foundation","doi-asserted-by":"crossref","award":["1262\/18 and 2137\/19"],"award-info":[{"award-number":["1262\/18 and 2137\/19"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Technion Hiroshi Fujiwara cyber security research center and Israel cyber directorate"},{"name":"ERC, FASTPROOF","award":["101041208"],"award-info":[{"award-number":["101041208"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2025,4,30]]},"abstract":"\n Succinct arguments are proof systems that allow a powerful, but untrusted, prover to convince a weak verifier that an input\n x<\/jats:italic>\n belongs to a language\n \n \\(L \\in \\mathsf {NP}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , with communication that is much shorter than the\n \n \\(\\mathsf {NP}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n witness. Such arguments, which grew out of the theory literature, are now drawing immense interest also in practice, where a key bottleneck that has arisen is the high computational cost of\n proving<\/jats:italic>\n correctness.\n <\/jats:p>\n \n In this work, we address this problem by constructing succinct arguments for general computations, expressed as Boolean circuits (of bounded fan-in), with a\n strictly linear<\/jats:italic>\n size prover. The soundness error of the protocol is an arbitrarily small constant. Prior to this work, succinct arguments were known with a\n quasi-<\/jats:italic>\n linear size prover for general Boolean circuits or with linear-size only for arithmetic circuits, defined over large finite fields.\n <\/jats:p>\n \n In more detail, for every Boolean circuit\n \n \\(C=C(x,w)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , we construct an\n \n \\(O(\\log |C|)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -round argument-system in which the prover can be implemented by a size\n \n \\(O(|C|)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n Boolean circuit (given as input both the instance\n x<\/jats:italic>\n and the witness\n w<\/jats:italic>\n ), with arbitrarily small constant soundness error and using\n \n \\(\\mathrm{poly}(\\lambda ,\\log |C|)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n communication, where\n \n \\(\\lambda\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n denotes the security parameter. The verifier can be implemented by a size\n \n \\(O(|x|) + \\mathrm{poly}(\\lambda , \\log |C|)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n circuit following a size\n \n \\(O(|C|)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n private pre-processing step, or, alternatively, by using a purely public-coin protocol (with no pre-processing) with a size\n \n \\(O(|C|)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n verifier. The protocol can be made zero-knowledge using standard techniques (and with similar parameters). The soundness of our protocol is computational and relies on the existence of collision resistant hash functions that can be computed by linear-size circuits, such as those proposed by Applebaum et\u00a0al. (ITCS, 2017).\n <\/jats:p>\n \n At the heart of our construction is a new information-theoretic\n interactive oracle proof<\/jats:italic>\n (\n \n \\(\\mathsf {IOP}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n ), an interactive analog of a\n \n \\(\\mathsf {PCP}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , for circuit satisfiability, with constant prover overhead. The improved efficiency of our\n \n \\(\\mathsf {IOP}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n is obtained by bypassing a barrier faced by prior\n \n \\(\\mathsf {IOP}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n constructions, which needed to (either explicitly or implicitly) encode the entire computation using a multiplication code.\n <\/jats:p>","DOI":"10.1145\/3721477","type":"journal-article","created":{"date-parts":[[2025,3,4]],"date-time":"2025-03-04T11:20:58Z","timestamp":1741087258000},"page":"1-54","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Proving as Fast as Computing: Succinct Arguments with Constant Prover Overhead"],"prefix":"10.1145","volume":"72","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8416-893X","authenticated-orcid":false,"given":"Noga","family":"Ron-Zewi","sequence":"first","affiliation":[{"name":"Computer Science, University of Haifa, Haifa, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5481-7276","authenticated-orcid":false,"given":"Ron","family":"Rothblum","sequence":"additional","affiliation":[{"name":"Computer Science, Technion Israel Institute of Technology, Haifa, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,3,28]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/3133956.3134104"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2017.7"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00145-016-9232-x"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-68403-6_12"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-07085-3_3"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/273865.273901"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2014.06.013"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-84259-8_4"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1007\/0-387-34799-2_4"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2018.14"},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-26954-8_23"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2017.40"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488681"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-17653-2_4"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53644-5_2"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705446810"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20120"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.1137\/050646445"},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-03810-6_25"},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-70700-6_12"},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-64378-2_2"},{"key":"e_1_3_3_23_2","first-page":"1056","article-title":"Linear-time probabilistic proofs with sublinear verification for algebraic automata over every field","author":"Bootle Jonathan","year":"2022","unstructured":"Jonathan Bootle, Alessandro Chiesa, Ziyi Guan, and Siqi Liu. 2022. Linear-time probabilistic proofs with sublinear verification for algebraic automata over every field. IACR Cryptol. ePrint Arch. (2022), 1056. Retrieved from https:\/\/eprint.iacr.org\/2022\/1056","journal-title":"IACR Cryptol. ePrint Arch."},{"key":"e_1_3_3_24_2","first-page":"1527","article-title":"Zero-knowledge succinct arguments with a linear-time prover","volume":"2020","author":"Bootle Jonathan","year":"2020","unstructured":"Jonathan Bootle, Alessandro Chiesa, and Siqi Liu. 2020. Zero-knowledge succinct arguments with a linear-time prover. IACR Cryptol. ePrint Arch. 2020 (2020), 1527. Retrieved from https:\/\/eprint.iacr.org\/2020\/1527","journal-title":"IACR Cryptol. ePrint Arch."},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-45721-1_24"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316380"},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.1007\/11818175_31"},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-45721-1_26"},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/2090236.2090245"},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45539-6_22"},{"key":"e_1_3_3_31_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13190-5_23"},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705446962"},{"key":"e_1_3_3_33_2","first-page":"304","volume-title":"Proceedings of the 9th International Workshop on Randomization and Computation (RANDOM\u201906)","author":"Dinur Irit","year":"2006","unstructured":"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\u201906). Springer, 304\u2013315."},{"key":"e_1_3_3_34_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITC.2021.5"},{"key":"e_1_3_3_35_2","doi-asserted-by":"publisher","DOI":"10.1145\/2554797.2554815"},{"key":"e_1_3_3_36_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-47721-7_12"},{"key":"e_1_3_3_37_2","doi-asserted-by":"crossref","unstructured":"Nicholas Franzese Jonathan Katz Steve Lu Rafail Ostrovsky Xiao Wang and Chenkai Weng. 2021. Constant-overhead zero-knowledge for RAM programs. In CCS\u201921: 2021 ACM SIGSAC Conference on Computer and Communications Security Virtual Event Republic of Korea November 15-19 2021 ACM 178\u2013191.","DOI":"10.1145\/3460120.3484800"},{"key":"e_1_3_3_38_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-38545-2_7"},{"key":"e_1_3_3_39_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2018.27"},{"key":"e_1_3_3_40_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.CCC.2024.11"},{"key":"e_1_3_3_41_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-15802-5_17"},{"key":"e_1_3_3_42_2","unstructured":"Yuval Ishai. 2020. Zero-Knowledge Proofs from Information-Theoretic Proof Systems. Retrieved March 11 2025 from https:\/\/zkproof.org\/2020\/08\/12\/information-theoretic-proof-systems"},{"key":"e_1_3_3_43_2","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374438"},{"key":"e_1_3_3_44_2","doi-asserted-by":"publisher","DOI":"10.1137\/080725398"},{"key":"e_1_3_3_45_2","doi-asserted-by":"publisher","DOI":"10.1145\/129712.129782"},{"key":"e_1_3_3_46_2","article-title":"Linear-time Zero-knowledge SNARKs for R1CS","author":"Lee Jonathan","year":"2021","unstructured":"Jonathan Lee, Srinath Setty, Justin Thaler, and Riad Wahby. 2021. Linear-time Zero-knowledge SNARKs for R1CS. Cryptology ePrint Archive, Report 2021\/030. Retrieved from https:\/\/eprint.iacr.org\/2021\/030","journal-title":"Cryptology ePrint Archive, Report 2021\/030"},{"key":"e_1_3_3_47_2","doi-asserted-by":"publisher","DOI":"10.1145\/146585.146605"},{"key":"e_1_3_3_48_2","doi-asserted-by":"publisher","DOI":"10.1137\/110829660"},{"key":"e_1_3_3_49_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795284959"},{"key":"e_1_3_3_50_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10472-009-9169-y"},{"key":"e_1_3_3_51_2","doi-asserted-by":"publisher","DOI":"10.1137\/0222053"},{"key":"e_1_3_3_52_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1960.1057584"},{"key":"e_1_3_3_53_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2013.2237944"},{"issue":"2","key":"e_1_3_3_54_2","doi-asserted-by":"crossref","first-page":"300","DOI":"10.1137\/0108018","article-title":"Polynomial codes over certain finite fields","volume":"8","author":"Reed Irving S.","year":"1960","unstructured":"Irving S. Reed and Gustave Solomon. 1960. Polynomial codes over certain finite fields. SIAM J. Soc. Indust. Appl. Math. 8, 2 (1960), 300\u2013304.","journal-title":"SIAM J. Soc. Indust. Appl. Math."},{"key":"e_1_3_3_55_2","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897652"},{"key":"e_1_3_3_56_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00083"},{"key":"e_1_3_3_57_2","volume-title":"Models of Computation - Exploring the Power of Computing","author":"Savage John E.","year":"1998","unstructured":"John E. Savage. 1998. Models of Computation - Exploring the Power of Computing. Addison-Wesley."},{"key":"e_1_3_3_58_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1988.21944"},{"key":"e_1_3_3_59_2","doi-asserted-by":"publisher","DOI":"10.1109\/18.556667"},{"key":"e_1_3_3_60_2","doi-asserted-by":"publisher","DOI":"10.1109\/18.556668"},{"key":"e_1_3_3_61_2","unstructured":"Madhu Sudan. 2001. Algorithmic Introduction to Coding Theory (Lecture Notes)."},{"key":"e_1_3_3_62_2","doi-asserted-by":"publisher","DOI":"10.1561\/3300000030"},{"key":"e_1_3_3_63_2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20498"},{"key":"e_1_3_3_64_2","doi-asserted-by":"publisher","DOI":"10.1109\/SP40001.2021.00056"},{"key":"e_1_3_3_65_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-26954-8_24"},{"key":"e_1_3_3_66_2","doi-asserted-by":"publisher","DOI":"10.1145\/3460120.3484556"},{"key":"e_1_3_3_67_2","doi-asserted-by":"publisher","DOI":"10.1145\/3460120.3484767"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3721477","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3721477","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:09:47Z","timestamp":1750295387000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3721477"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,3,28]]},"references-count":66,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,4,30]]}},"alternative-id":["10.1145\/3721477"],"URL":"https:\/\/doi.org\/10.1145\/3721477","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,3,28]]},"assertion":[{"value":"2024-05-18","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-02-16","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-03-28","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}