{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,21]],"date-time":"2026-05-21T01:14:30Z","timestamp":1779326070385,"version":"3.51.4"},"reference-count":66,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2021,11,29]],"date-time":"2021-11-29T00:00:00Z","timestamp":1638144000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"crossref"}]},{"name":"I-CORE Program of the Planning and Budgeting Committee and the Israel Science Foundation"},{"name":"Simons Collaboration on Algorithms and Geometry"},{"name":"Simons Investigator Award"},{"name":"NSF","award":["CCF-0832797, DMS-0835373, CCF-1714779"],"award-info":[{"award-number":["CCF-0832797, DMS-0835373, CCF-1714779"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2022,2,28]]},"abstract":"<jats:p>\n            We construct a 1-round delegation scheme (i.e., argument-system) for every language computable in time\n            <jats:italic>t<\/jats:italic>\n            =\n            <jats:italic>t<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            ), where the running time of the prover is\n            <jats:monospace>poly<\/jats:monospace>\n            (\n            <jats:italic>t<\/jats:italic>\n            ) and the running time of the verifier is n \u00b7\n            <jats:monospace>polylog<\/jats:monospace>\n            (\n            <jats:italic>t<\/jats:italic>\n            ). In particular, for every language in\n            <jats:monospace>P<\/jats:monospace>\n            we obtain a delegation scheme with almost linear time verification. Our construction relies on the existence of a computational sub-exponentially secure private information retrieval (\n            <jats:monospace>PIR<\/jats:monospace>\n            ) scheme.\n          <\/jats:p>\n          <jats:p>\n            The proof exploits a curious connection between the problem of\n            <jats:italic>computation delegation<\/jats:italic>\n            and the model of\n            <jats:italic>multi-prover interactive proofs that are sound against no-signaling (cheating) strategies<\/jats:italic>\n            , a model that was studied in the context of multi-prover interactive proofs with provers that share quantum entanglement, and is motivated by the physical principle that information cannot travel faster than light.\n          <\/jats:p>\n          <jats:p>\n            For any language computable in time\n            <jats:italic>t<\/jats:italic>\n            =\n            <jats:italic>t<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            ), we construct a multi-prover interactive proof (\n            <jats:monospace>MIP<\/jats:monospace>\n            ), that is, sound against no-signaling strategies, where the running time of the provers is\n            <jats:monospace>poly<\/jats:monospace>\n            (\n            <jats:italic>t<\/jats:italic>\n            ), the number of provers is\n            <jats:monospace>polylog<\/jats:monospace>\n            (\n            <jats:italic>t<\/jats:italic>\n            ), and the running time of the verifier is\n            <jats:italic>n<\/jats:italic>\n            \u00b7\n            <jats:monospace>polylog<\/jats:monospace>\n            (\n            <jats:italic>t<\/jats:italic>\n            ).\n          <\/jats:p>\n          <jats:p>\n            In particular, this shows that the class of languages that have polynomial-time\n            <jats:monospace>MIP<\/jats:monospace>\n            s that are sound against no-signaling strategies, is exactly\n            <jats:monospace>EXP<\/jats:monospace>\n            . Previously, this class was only known to contain\n            <jats:monospace>PSPACE<\/jats:monospace>\n            .\n          <\/jats:p>\n          <jats:p>\n            To convert our\n            <jats:monospace>MIP<\/jats:monospace>\n            into a 1-round delegation scheme, we use the method suggested by Aiello et al. (ICALP, 2000), which makes use of a\n            <jats:monospace>PIR<\/jats:monospace>\n            scheme. This method lacked a proof of security. We prove that this method is secure assuming the underlying\n            <jats:monospace>MIP<\/jats:monospace>\n            is secure against no-signaling provers.\n          <\/jats:p>","DOI":"10.1145\/3456867","type":"journal-article","created":{"date-parts":[[2021,11,30]],"date-time":"2021-11-30T01:58:53Z","timestamp":1638237533000},"page":"1-82","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["How to Delegate Computations: The Power of No-Signaling Proofs"],"prefix":"10.1145","volume":"69","author":[{"given":"Yael Tauman","family":"Kalai","sequence":"first","affiliation":[{"name":"Microsoft Research and MIT"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ran","family":"Raz","sequence":"additional","affiliation":[{"name":"Princeton University and the Weizmann Institute of Science, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5481-7276","authenticated-orcid":false,"given":"Ron D.","family":"Rothblum","sequence":"additional","affiliation":[{"name":"Technion - Israel Institute of Technology"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,11,29]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45022-X_39"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-14165-2_14"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/278298.278306"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1088\/0305-4470\/39\/36\/010"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200056"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188924"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.71.022101"},{"key":"e_1_3_2_9_2","first-page":"183","volume-title":"Proceedings of the 2nd International Workshop on Mobile Agents","author":"Biehl Ingrid","year":"1999","unstructured":"Ingrid Biehl, Bernd Meyer, and Susanne Wetzel. 1999. Ensuring the integrity of agent-based computations by short proofs. In Proceedings of the 2nd International Workshop on Mobile Agents. Springer-Verlag, 183\u2013194. Retrieved from http:\/\/dl.acm.org\/citation.cfm?id=647628.732433."},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/2090236.2090263"},{"key":"e_1_3_2_11_2","doi-asserted-by":"crossref","unstructured":"Nir Bitansky Ran Canetti Alessandro Chiesa and Eran Tromer. 2013. Recursive composition and bootstrapping for SNARKs and proof-carrying data. In Proceedings of the Symposium on Theory of Computing Conference Palo Alto CA USA June 1-4 (STOC\u201913) Dan Boneh Tim Roughgarden and Joan Feigenbaum (Eds.). ACM 111\u2013120. DOI:10.1145\/2488608.2488623","DOI":"10.1145\/2488608.2488623"},{"key":"e_1_3_2_12_2","doi-asserted-by":"crossref","unstructured":"Zvika Brakerski Justin Holmgren and Yael Tauman Kalai. 2017. Non-interactive RAM and batch NP delegation from any PIR. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC\u201917) Hamed Hatami Pierre McKenzie and Valerie King (Eds.). ACM 474\u2013482. DOI:10.1145\/3055399.3055497","DOI":"10.1145\/3055399.3055497"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.12"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-48910-X_28"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316380"},{"key":"e_1_3_2_16_2","first-page":"25:1\u201325:17","volume-title":"Proceedings of the 10th Innovations in Theoretical Computer Science Conference","volume":"124","author":"Chiesa Alessandro","year":"2019","unstructured":"Alessandro Chiesa, Peter Manohar, and Igor Shinkar. 2019. Probabilistic checking against non-signaling strategies from linearity testing. In Proceedings of the 10th Innovations in Theoretical Computer Science Conference, Avrim Blum (Ed.), Vol. 124. 25:1\u201325:17. DOI: https:\/\/doi.org\/10.4230\/LIPIcs.ITCS.2019.25"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-22792-9_9"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-14623-7_26"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-28914-9_4"},{"key":"e_1_3_2_20_2","doi-asserted-by":"crossref","unstructured":"Yevgeniy Dodis Shai Halevi Ron D. Rothblum and Daniel Wichs. 2016. Spooky encryption and its applications. In Proceedings of the Advances in Cryptology 36th Annual International Cryptology Conference Matthew Robshaw and Jonathan Katz (Eds.). Lecture Notes in Computer Science Vol. 9816. Springer 93\u2013122. DOI:10.1007\/978-3-662-53015-3_4","DOI":"10.1007\/978-3-662-53015-3_4"},{"key":"e_1_3_2_21_2","unstructured":"Cynthia Dwork Michael Langberg Moni Naor Kobbi Nissim and Omer Reingold. 2004. Succinct Proofs for NP and Spooky Interactions. (2004). Unpublished manuscript Retrieved 15 September 2021 from https:\/\/www.wisdom.weizmann.ac.il\/naor\/PAPERS\/spooky.pdf."},{"key":"e_1_3_2_22_2","first-page":"186","volume-title":"Proceedings of the CRYPTO","author":"Fiat Amos","year":"1986","unstructured":"Amos Fiat and Adi Shamir. 1986. How to prove yourself: Practical solutions to identification and signature problems. In Proceedings of the CRYPTO. 186\u2013194."},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-14623-7_25"},{"key":"e_1_3_2_24_2","doi-asserted-by":"crossref","unstructured":"Rosario Gennaro Craig Gentry Bryan Parno and Mariana Raykova. 2012. Quadratic span programs and succinct NIZKs without PCPs. In Proceedings of the 32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques Thomas Johansson and Phong Q. Nguyen (Eds.). Lecture Notes in Computer Science Vol. 7881. Springer 626\u2013645. DOI:10.1007\/978-3-642-38348-9_37","DOI":"10.1007\/978-3-642-38348-9_37"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536440"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993651"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.5555\/552556"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804106"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374396"},{"key":"e_1_3_2_30_2","doi-asserted-by":"crossref","unstructured":"Shafi Goldwasser Huijia Lin and Aviad Rubinstein. 2017. Delegation of computation without rejection problem from designated verifier CS-Proofs. J. Cryptol. 30 4 (2017) 989\u20131066. DOI:10.1007\/s00145-016-9241-9","DOI":"10.1007\/s00145-016-9241-9"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-17373-8_19"},{"key":"e_1_3_2_32_2","doi-asserted-by":"crossref","first-page":"1024","DOI":"10.1145\/3357713.3384246","volume-title":"Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing","author":"Holden Dhiraj","year":"2020","unstructured":"Dhiraj Holden and Yael Tauman Kalai. 2020. Non-signaling proofs with o( log n) provers are in PSPACE. In Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of ComputingKonstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy (Eds.). ACM, 1024\u20131037. DOI: https:\/\/doi.org\/10.1145\/3357713.3384246"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2009.v005a008"},{"key":"e_1_3_2_34_2","first-page":"35","article-title":"No-Signaling MIPs and faster-than-light communication, revisited","volume":"27","author":"Holmgren Justin","year":"2020","unstructured":"Justin Holmgren. 2020. No-Signaling MIPs and faster-than-light communication, revisited. Electron. Colloquium Comput. Complex. 27 (2020), 35. Retrieved from https:\/\/eccc.weizmann.ac.il\/report\/2020\/035.","journal-title":"Electron. Colloquium Comput. Complex."},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00021"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316367"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-14165-2_13"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2009.22"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.11"},{"key":"e_1_3_2_40_2","first-page":"144","article-title":"Toward probabilistic checking against non-signaling strategies with constant locality","volume":"27","author":"Jahanara Mohammad Mahdi","year":"2020","unstructured":"Mohammad Mahdi Jahanara, Sajin Koroth, and Igor Shinkar. 2020. Toward probabilistic checking against non-signaling strategies with constant locality. Electron. Colloquium Comput. Complex. 27 (2020), 144. Retrieved from https:\/\/eccc.weizmann.ac.il\/report\/2020\/144.","journal-title":"Electron. Colloquium Comput. Complex."},{"key":"e_1_3_2_41_2","doi-asserted-by":"crossref","unstructured":"Ruta Jawale Yael Tauman Kalai Dakshita Khurana and Rachel Zhang. 2021. SNARGs for bounded depth computations and PPAD hardness from sub-exponential LWE. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing Samir Khuller and Virginia Vassilevska Williams (Eds.). ACM 708\u2013721. DOI:10.1145\/3406325.3451055","DOI":"10.1145\/3406325.3451055"},{"key":"e_1_3_2_42_2","unstructured":"Zhengfeng Ji Anand Natarajan Thomas Vidick John Wright and Henry Yuen. 2020. MIP* = RE. CoRR abs\/2001.04383 . https:\/\/arxiv.org\/abs\/2001.04383."},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53644-5_4"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316411"},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03356-8_9"},{"key":"e_1_3_2_46_2","doi-asserted-by":"publisher","DOI":"10.1145\/2840728.2840750"},{"key":"e_1_3_2_47_2","first-page":"565","volume-title":"Proceedings of the STOC","author":"Kalai Yael Tauman","year":"2013","unstructured":"Yael Tauman Kalai, Ran Raz, and Ron D. Rothblum. 2013. Delegation for bounded space. In Proceedings of the STOC. 565\u2013574."},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591809"},{"key":"e_1_3_2_49_2","first-page":"422","volume-title":"Proceedings of the Advances in Cryptology 35th Annual Cryptology Conference","volume":"9216","author":"Kalai Yael Tauman","year":"2015","unstructured":"Yael Tauman Kalai and Ron D. Rothblum. 2015. Arguments of proximity - [Extended Abstract]. In Proceedings of the Advances in Cryptology 35th Annual Cryptology Conference. Rosario Gennaro and Matthew Robshaw (Eds.), Lecture Notes in Computer Science, Vol. 9216. Springer, 422\u2013442. DOI: https:\/\/doi.org\/10.1007\/978-3-662-48000-7_21"},{"key":"e_1_3_2_50_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.8"},{"key":"e_1_3_2_51_2","first-page":"441","volume-title":"Proceedings of the Symposium on the Foundations of Modern Physics","author":"Khalfin Leonid A.","year":"1985","unstructured":"Leonid A. Khalfin and Boris S. Tsirelson. 1985. Quantum and quasi-classical analogs of Bell inequalities. In Proceedings of the Symposium on the Foundations of Modern Physics. 441\u2013460."},{"key":"e_1_3_2_52_2","doi-asserted-by":"publisher","DOI":"10.1145\/129712.129782"},{"key":"e_1_3_2_53_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-03807-6_3"},{"key":"e_1_3_2_54_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1997.646125"},{"key":"e_1_3_2_55_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-28914-9_10"},{"key":"e_1_3_2_56_2","doi-asserted-by":"publisher","DOI":"10.1145\/146585.146605"},{"key":"e_1_3_2_57_2","first-page":"436","volume-title":"Proceedings of the FOCS","author":"Micali Silvio","year":"1994","unstructured":"Silvio Micali. 1994. CS proofs (Extended Abstracts). In Proceedings of the FOCS. 436\u2013453."},{"key":"e_1_3_2_58_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-45146-4_6"},{"key":"e_1_3_2_59_2","doi-asserted-by":"crossref","unstructured":"Omer Paneth and Guy N. Rothblum. 2017. Publicly verifiable non-interactive arguments for delegating computation. In Proceedings of the Theory of Cryptography - 15th International Conference {TCC} 2017 Baltimore MD USA November 12-15 Yael Kalai and Leonid Reyzin. Lecture Notes in Computer Science Vol. 10678. Springer 283\u2013315. DOI:10.1007\/978-3-319-70503-3_9","DOI":"10.1007\/978-3-319-70503-3_9"},{"key":"e_1_3_2_60_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-28914-9_24"},{"key":"e_1_3_2_61_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02058098"},{"key":"e_1_3_2_62_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF00739036"},{"key":"e_1_3_2_63_2","first-page":"169","article-title":"On data banks and privacy homomorphisms","author":"Rivest R. L.","year":"1978","unstructured":"R. L. Rivest, L. Adleman, and M. L. Dertouzos. 1978. On data banks and privacy homomorphisms. Foundations of Secure Computation, Academia Press (1978), 169\u2013179.","journal-title":"Foundations of Secure Computation, Academia Press"},{"key":"e_1_3_2_64_2","volume-title":"Delegating computation reliably: Paradigms and constructions","author":"Rothblum Guy N.","year":"2009","unstructured":"Guy N. Rothblum. 2009. Delegating computation reliably: Paradigms and constructions. Ph.D. Dissertation. Massachusetts Institute of Technology."},{"key":"e_1_3_2_65_2","doi-asserted-by":"publisher","DOI":"10.1145\/146585.146609"},{"key":"e_1_3_2_66_2","unstructured":"Madhu Sudan. 2000. Probabilistically Checkable Proofs - Lecture Notes. (2000). Retrieved on 15 August 2021 from http:\/\/people.csail.mit.edu\/madhu\/pcp\/pcp.ps."},{"key":"e_1_3_2_67_2","doi-asserted-by":"publisher","DOI":"10.1098\/rspa.2008.0149"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3456867","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3456867","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3456867","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:31:26Z","timestamp":1750195886000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3456867"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,11,29]]},"references-count":66,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,2,28]]}},"alternative-id":["10.1145\/3456867"],"URL":"https:\/\/doi.org\/10.1145\/3456867","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,11,29]]},"assertion":[{"value":"2020-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-11-29","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}