{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,29]],"date-time":"2026-05-29T15:39:41Z","timestamp":1780069181854,"version":"3.54.0"},"reference-count":89,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2015,9,11]],"date-time":"2015-09-11T00:00:00Z","timestamp":1441929600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100004732","name":"Symantec Corporation","doi-asserted-by":"publisher","award":["Graduate Fellowship"],"award-info":[{"award-number":["Graduate Fellowship"]}],"id":[{"id":"10.13039\/100004732","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006445","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-0514167, CCF-0635297, NSF-0729011, CNS-0430336"],"award-info":[{"award-number":["CCF-0514167, CCF-0635297, NSF-0729011, CNS-0430336"]}],"id":[{"id":"10.13039\/100006445","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001735","name":"Weizmann Institute of Science","doi-asserted-by":"publisher","award":["Chais Fellows"],"award-info":[{"award-number":["Chais Fellows"]}],"id":[{"id":"10.13039\/501100001735","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2015,9,11]]},"abstract":"<jats:p>In this work we study interactive proofs for tractable languages. The (honest) prover should be efficient and run in polynomial time or, in other words, a \u201cmuggle\u201d.1 The verifier should be super-efficient and run in nearly linear time. These proof systems can be used for delegating computation: a server can run a computation for a client and interactively prove the correctness of the result. The client can verify the result\u2019s correctness in nearly linear time (instead of running the entire computation itself).<\/jats:p>\n          <jats:p>Previously, related questions were considered in the holographic proof setting by Babai et al. [1991b] in the argument setting under computational assumptions by Kilian, and in the random oracle model by Micali [1994]. Our focus, however, is on the original interactive proof model where no assumptions are made on the computational power or adaptiveness of dishonest provers.<\/jats:p>\n          <jats:p>\n            Our main technical theorem gives a public coin interactive proof for any language computable by a log-space uniform boolean circuit with depth\n            <jats:italic>d<\/jats:italic>\n            and input length\n            <jats:italic>n<\/jats:italic>\n            . The verifier runs in time n \u00b7 poly(\n            <jats:italic>d<\/jats:italic>\n            , log(\n            <jats:italic>n<\/jats:italic>\n            )) and space\n            <jats:italic>O<\/jats:italic>\n            (log(\n            <jats:italic>n<\/jats:italic>\n            )), the communication complexity is poly(\n            <jats:italic>d<\/jats:italic>\n            , log(\n            <jats:italic>n<\/jats:italic>\n            )), and the prover runs in time poly(\n            <jats:italic>n<\/jats:italic>\n            ). In particular, for languages computable by log-space uniform\n            <jats:italic>NC<\/jats:italic>\n            (circuits of polylog(\n            <jats:italic>n<\/jats:italic>\n            ) depth), the prover is efficient, the verifier runs in time\n            <jats:italic>n<\/jats:italic>\n            \u00b7 polylog(\n            <jats:italic>n<\/jats:italic>\n            ) and space\n            <jats:italic>O<\/jats:italic>\n            (log(\n            <jats:italic>n<\/jats:italic>\n            )), and the communication complexity is polylog(\n            <jats:italic>n<\/jats:italic>\n            ). Using this theorem we make progress on several questions.\n          <\/jats:p>\n          <jats:p>\n            --- We show how to construct 1-round computationally sound arguments with polylog communication for any log-space uniform\n            <jats:italic>NC<\/jats:italic>\n            computation. The verifier runs in quasi-linear time. This result uses a recent transformation of Kalai and Raz from public coin interactive\n            <jats:italic>proofs<\/jats:italic>\n            to 1-round\n            <jats:italic>arguments<\/jats:italic>\n            . The soundness of the argument system is based on the existence of a PIR scheme with polylog communication.\n          <\/jats:p>\n          <jats:p>\n            --- We construct interactive proofs with public coin, log-space, poly-time verifiers for all of\n            <jats:italic>P<\/jats:italic>\n            are given. This settles an open question regarding the expressive power of proof systems with such verifiers.\n          <\/jats:p>\n          <jats:p>\n            --- We construct zero-knowledge interactive proofs are given with communication complexity quasi-linear in the\n            <jats:italic>witness<\/jats:italic>\n            length for any\n            <jats:italic>NP<\/jats:italic>\n            language verifiable in\n            <jats:italic>NC<\/jats:italic>\n            , based on the existence of 1-way functions.\n          <\/jats:p>\n          <jats:p>\n            --- We construct probabilistically checkable arguments (a model due to Kalai and Raz) of size polynomial in the witness length (rather than instance length) for any\n            <jats:italic>NP<\/jats:italic>\n            language verifiable in\n            <jats:italic>NC<\/jats:italic>\n            , under computational assumptions, are provided.\n          <\/jats:p>","DOI":"10.1145\/2699436","type":"journal-article","created":{"date-parts":[[2015,9,15]],"date-time":"2015-09-15T12:09:15Z","timestamp":1442318955000},"page":"1-64","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":191,"title":["Delegating Computation"],"prefix":"10.1145","volume":"62","author":[{"given":"Shafi","family":"Goldwasser","sequence":"first","affiliation":[{"name":"MIT and Weizmann Institute of Science"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yael Tauman","family":"Kalai","sequence":"additional","affiliation":[{"name":"Microsoft Research"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Guy N.","family":"Rothblum","sequence":"additional","affiliation":[{"name":"MIT"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2015,9,11]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2004.160.781"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the Conference on Shared Knowledge and the Web.","author":"Anderson David P.","year":"2003","unstructured":"David P. Anderson. 2003. Public computing: Reconnecting people to science. In Proceedings of the Conference on Shared Knowledge and the Web."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/GRID.2004.14"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/1880918.1880936"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/278298.278306"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/273865.273901"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/22145.22192"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200430"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/103418.103428"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/874063.875552"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/872747.873184"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1991.185343"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/646753.704888"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62223"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705446810"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2090236.2090263"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488623"},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the International Congress of Mathematicians (ICM\u201987)","author":"Blum Manuel","year":"1987","unstructured":"Manuel Blum. 1987. How to prove a theorem so no-one else can claim it. In Proceedings of the International Congress of Mathematicians (ICM\u201987). 1444--1451."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/200836.200880"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.12"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/1756123.1756163"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1008731.1008734"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/293347.293350"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/2033036.2033048"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/1881412.1881446"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/103516.128681"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(88)90038-4"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63519"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2090236.2090245"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258635"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-28914-9_4"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1236457.1236459"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705446962"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/950620.950623"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/146585.146599"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/146585.146601"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509958"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/226643.226652"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258644"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.5555\/36664.36676"},{"key":"e_1_2_1_41_1","volume-title":"Complexity-theoretic aspects of interactive proof systems. Tech. rep. MIT\/LCS\/TR-447","author":"Fortnow Lance","unstructured":"Lance Fortnow. 1989. Complexity-theoretic aspects of interactive proof systems. Tech. rep. MIT\/LCS\/TR-447, Massachusetts Institute of Technology. http:\/\/people.cs.uchicago.edu\/~fortnow\/papers\/thesis.pdf."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(93)90210-K"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.5555\/1881412.1881445"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-38348-9_37"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536440"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993651"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.5555\/552556"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.5555\/519078"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/116825.116852"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250855"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.5555\/946243.946302"},{"key":"e_1_2_1_52_1","unstructured":"Shafi Goldwasser Huijia Lin and Aviad Rubinstein. 2011. Delegation of computation without rejection problem from designated verifier CS-proofs. https:\/\/eprint.iacr.org\/2011\/456.pdf."},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1137\/0218012"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-17373-8_19"},{"key":"e_1_2_1_55_1","doi-asserted-by":"crossref","unstructured":"Tom Gur and Ron Rothblum. 2013. Non-interactive proofs of proximity. http:\/\/eccc.hpi-web.de\/report\/2013\/078\/.","DOI":"10.1145\/2488608.2488709"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793244708"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250794"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.5555\/1760749.1760790"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.74"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70583-3_44"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03356-8_9"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488679"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591809"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1988.21918"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/129712.129782"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.5555\/646760.705867"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.5555\/795663.796363"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1145\/174130.174138"},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1007\/11556992_23"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-28914-9_10"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1145\/146585.146605"},{"key":"e_1_2_1_72_1","unstructured":"Mersenne. 2007. The great Internet Mersenne prime search. http:\/\/www.mersenne.org\/."},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1994.365746"},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1137\/060656838"},{"key":"e_1_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.5555\/646754.705040"},{"key":"e_1_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-45146-4_6"},{"key":"e_1_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-28914-9_24"},{"key":"e_1_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.1145\/195058.195132"},{"key":"e_1_2_1_79_1","first-page":"169","article-title":"On data banks and privacy homomorphisms","volume":"4","author":"Rivest Ron","year":"1978","unstructured":"Ron Rivest, Leonard Adleman, and Michael Dertouzos. 1978. On data banks and privacy homomorphisms. Foundat. Secure Comput. 4, 11, 169--179.","journal-title":"Foundat. Secure Comput."},{"key":"e_1_2_1_80_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2009.40"},{"key":"e_1_2_1_81_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488709"},{"key":"e_1_2_1_82_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793255151"},{"key":"e_1_2_1_83_1","unstructured":"SETI. 1999. ET phone SETI@home!. Science@NASA headlines. http:\/\/science.nasa.gov\/science-news\/science-at-nasa\/1999\/ast23may99_ 1\/."},{"key":"e_1_2_1_84_1","unstructured":"SETI. 2007. SETI@home project website. http:\/\/setiathome.berkeley.edu\/."},{"key":"e_1_2_1_85_1","doi-asserted-by":"publisher","DOI":"10.1145\/146585.146609"},{"key":"e_1_2_1_86_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40084-1_5"},{"key":"e_1_2_1_87_1","unstructured":"Justin Thaler Mike Roberts Michael Mitzenmacher and Hanspeter Pfister. 2012. Verifiable computation with massively parallel interactive proofs. http:\/\/arxiv.org\/abs\/1202.1350."},{"key":"e_1_2_1_88_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2013.48"},{"key":"e_1_2_1_89_1","volume-title":"Blumberg","author":"Walfish Michael","year":"2013","unstructured":"Michael Walfish and Andrew J. Blumberg. 2013. Verifying computations without reexecuting them: From theoretical possibility to near-practicality. http:\/\/eccc.hpi-web.de\/report\/2013\/165\/."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2699436","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2699436","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T06:16:58Z","timestamp":1750227418000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2699436"}},"subtitle":["Interactive Proofs for Muggles"],"short-title":[],"issued":{"date-parts":[[2015,9,11]]},"references-count":89,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2015,9,11]]}},"alternative-id":["10.1145\/2699436"],"URL":"https:\/\/doi.org\/10.1145\/2699436","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,9,11]]},"assertion":[{"value":"2014-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-09-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}