{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,2]],"date-time":"2026-07-02T16:18:27Z","timestamp":1783009107496,"version":"3.54.5"},"reference-count":50,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2022,1,31]],"date-time":"2022-01-31T00:00:00Z","timestamp":1643587200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"UKRI Future Leaders Fellowship","award":["MR\/S031545\/1"],"award-info":[{"award-number":["MR\/S031545\/1"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2022,4,30]]},"abstract":"<jats:p>\n            Zero knowledge plays a central role in cryptography and complexity. The seminal work of Ben-Or et\u00a0al. (STOC 1988) shows that zero knowledge can be achieved unconditionally for any language in\n            <jats:bold>NEXP<\/jats:bold>\n            , as long as one is willing to make a suitable\n            <jats:italic>physical assumption<\/jats:italic>\n            : if the provers are spatially isolated, then they can be assumed to be playing independent strategies.\n          <\/jats:p>\n          <jats:p>\n            Quantum mechanics, however, tells us that this assumption is unrealistic, because spatially-isolated provers could share a quantum entangled state and realize a non-local correlated strategy. The MIP\n            <jats:sup>*<\/jats:sup>\n            model captures this setting.\n          <\/jats:p>\n          <jats:p>\n            In this work, we study the following question:\n            <jats:italic>Does spatial isolation still suffice to unconditionally achieve zero knowledge even in the presence of quantum entanglement?<\/jats:italic>\n          <\/jats:p>\n          <jats:p>\n            We answer this question in the affirmative: we prove that every language in\n            <jats:bold>NEXP<\/jats:bold>\n            has a 2-prover\n            <jats:italic>zero knowledge<\/jats:italic>\n            interactive proof that is sound against entangled provers; that is,\n            <jats:bold>\n              NEXP \u2286 ZK-MIP\n              <jats:sup>*<\/jats:sup>\n            <\/jats:bold>\n            .\n          <\/jats:p>\n          <jats:p>\n            Our proof consists of constructing a zero knowledge interactive probabilistically checkable proof with a strong algebraic structure, and then lifting it to the MIP\n            <jats:sup>*<\/jats:sup>\n            model. This lifting relies on a new framework that builds on recent advances in low-degree testing against entangled strategies, and clearly separates classical and quantum tools.\n          <\/jats:p>\n          <jats:p>Our main technical contribution is the development of new algebraic techniques for obtaining unconditional zero knowledge; this includes a zero knowledge variant of the celebrated sumcheck protocol, a key building block in many probabilistic proof systems. A core component of our sumcheck protocol is a new algebraic commitment scheme, whose analysis relies on algebraic complexity theory.<\/jats:p>","DOI":"10.1145\/3511100","type":"journal-article","created":{"date-parts":[[2022,1,31]],"date-time":"2022-01-31T17:52:59Z","timestamp":1643651579000},"page":"1-44","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Spatial Isolation Implies Zero Knowledge Even in a Quantum World"],"prefix":"10.1145","volume":"69","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3029-2353","authenticated-orcid":false,"given":"Alessandro","family":"Chiesa","sequence":"first","affiliation":[{"name":"UC Berkeley and EPFL, USA and Switzerland, Berkeley, CA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2240-7245","authenticated-orcid":false,"given":"Michael A.","family":"Forbes","sequence":"additional","affiliation":[{"name":"University of Illinois at Urbana\u2013Champaign, Champaign, IL, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7864-7013","authenticated-orcid":false,"given":"Tom","family":"Gur","sequence":"additional","affiliation":[{"name":"University of Warwick, Coventry, England, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0085-2137","authenticated-orcid":false,"given":"Nicholas","family":"Spooner","sequence":"additional","affiliation":[{"name":"University of Warwick, Coventry, England, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2022,1,31]]},"reference":[{"key":"e_1_3_4_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/1490270.1490272"},{"key":"e_1_3_4_3_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(91)90006-Q"},{"key":"e_1_3_4_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/103418.103428"},{"key":"e_1_3_4_5_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200056"},{"key":"e_1_3_4_6_2","doi-asserted-by":"crossref","unstructured":"John S. Bell. 1964. On the einstein podolsky rosen paradox. Physics Physique Fizika 1 3 (1964) 195.","DOI":"10.1103\/PhysicsPhysiqueFizika.1.195"},{"key":"e_1_3_4_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62223"},{"key":"e_1_3_4_8_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-70503-3_6"},{"key":"e_1_3_4_9_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-49099-0_2"},{"key":"e_1_3_4_10_2","doi-asserted-by":"publisher","DOI":"10.5555\/1133618.1133623"},{"key":"e_1_3_4_11_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(87)90232-8"},{"key":"e_1_3_4_12_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.13"},{"key":"e_1_3_4_13_2","doi-asserted-by":"publisher","DOI":"10.1006\/ffta.1999.0243"},{"key":"e_1_3_4_14_2","doi-asserted-by":"publisher","DOI":"10.5555\/1009378.1009560"},{"key":"e_1_3_4_15_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-28628-8_16"},{"key":"e_1_3_4_16_2","first-page":"215","volume-title":"Proceedings of the 11th Annual International Cryptology Conference (CRYPTO\u201992)","author":"Dwork Cynthia","year":"1992","unstructured":"Cynthia Dwork, Uriel Feige, Joe Kilian, Moni Naor, and Shmuel Safra. 1992. Low communication 2-prover zero-knowledge proofs for NP. In Proceedings of the 11th Annual International Cryptology Conference (CRYPTO\u201992). 215\u2013227."},{"key":"e_1_3_4_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0055746"},{"key":"e_1_3_4_18_2","doi-asserted-by":"publisher","DOI":"10.5555\/646754.705058"},{"key":"e_1_3_4_19_2","first-page":"204","volume-title":"Proceedings of the 19th Annual ACM Symposium on Theory of Computing (STOC\u201987)","author":"Fortnow Lance","year":"1987","unstructured":"Lance Fortnow. 1987. The complexity of perfect zero-knowledge (extended abstract). In Proceedings of the 19th Annual ACM Symposium on Theory of Computing (STOC\u201987). 204\u2013209."},{"key":"e_1_3_4_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/116825.116852"},{"key":"e_1_3_4_21_2","doi-asserted-by":"publisher","DOI":"10.1007\/bf00195207"},{"key":"e_1_3_4_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/2699436"},{"key":"e_1_3_4_23_2","doi-asserted-by":"publisher","DOI":"10.1137\/0218012"},{"key":"e_1_3_4_24_2","doi-asserted-by":"publisher","DOI":"10.5555\/1881412.1881426"},{"key":"e_1_3_4_25_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00044"},{"key":"e_1_3_4_26_2","unstructured":"ITCS\u201917 Proceedings of the 8th Innovations in Theoretical Computer Science Conference Tom Gur Ron D Rothblum A hierarchy theorem for interactive proofs of proximity 2017"},{"key":"e_1_3_4_27_2","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2009.22"},{"key":"e_1_3_4_28_2","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2008.12"},{"key":"e_1_3_4_29_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.11"},{"key":"e_1_3_4_30_2","article-title":"Quantum soundness of the classical low individual degree test","author":"Ji Zhengfeng","year":"2021","unstructured":"Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen. 2021. Quantum soundness of the classical low individual degree test. In Proceedings of the 2021 Annual IEEE Symposium on Foundations of Computer Science.","journal-title":"Proceedings of the 2021 Annual IEEE Symposium on Foundations of Computer Science"},{"key":"e_1_3_4_31_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-009-0263-7"},{"key":"e_1_3_4_32_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70583-3_44"},{"key":"e_1_3_4_33_2","doi-asserted-by":"publisher","DOI":"10.1137\/090751293"},{"key":"e_1_3_4_34_2","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258643"},{"key":"e_1_3_4_35_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24587-2_20"},{"key":"e_1_3_4_36_2","doi-asserted-by":"publisher","DOI":"10.5555\/1802614.1802624"},{"key":"e_1_3_4_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/146585.146605"},{"key":"e_1_3_4_38_2","doi-asserted-by":"publisher","DOI":"10.1137\/110829660"},{"key":"e_1_3_4_39_2","article-title":"Oracle separations for quantum statistical zero-knowledge","volume":"1801","author":"Menda Sanketh","year":"2018","unstructured":"Sanketh Menda and John Watrous. 2018. Oracle separations for quantum statistical zero-knowledge. CoRR abs\/1801.08967 (2018).","journal-title":"CoRR"},{"key":"e_1_3_4_40_2","first-page":"20:1\u201320:18","volume-title":"Proceedings of the 32nd Annual IEEE Conference on Computational Complexity (CCC\u201918)","author":"Natarajan Anand","year":"2018","unstructured":"Anand Natarajan and Thomas Vidick. 2018. Two-player entangled games are NP-hard. In Proceedings of the 32nd Annual IEEE Conference on Computational Complexity (CCC\u201918). 20:1\u201320:18."},{"key":"e_1_3_4_41_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2007.896874"},{"key":"e_1_3_4_42_2","doi-asserted-by":"publisher","DOI":"10.1109\/ISTCS.1993.253489"},{"key":"e_1_3_4_43_2","doi-asserted-by":"publisher","DOI":"10.5555\/1009378.1009558"},{"key":"e_1_3_4_44_2","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897652"},{"key":"e_1_3_4_45_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793255151"},{"key":"e_1_3_4_46_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-29011-4_10"},{"key":"e_1_3_4_47_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-46803-6_25"},{"key":"e_1_3_4_48_2","volume-title":"The Complexity of Entangled Games","author":"Vidick Thomas","year":"2011","unstructured":"Thomas Vidick. 2011. The Complexity of Entangled Games. Ph. D. Dissertation. University of California, Berkeley."},{"key":"e_1_3_4_49_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2002.1181970"},{"key":"e_1_3_4_50_2","doi-asserted-by":"publisher","DOI":"10.1137\/060670997"},{"key":"e_1_3_4_51_2","doi-asserted-by":"publisher","DOI":"10.1109\/18.796385"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3511100","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3511100","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:11:58Z","timestamp":1750191118000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3511100"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,31]]},"references-count":50,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,4,30]]}},"alternative-id":["10.1145\/3511100"],"URL":"https:\/\/doi.org\/10.1145\/3511100","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,1,31]]},"assertion":[{"value":"2018-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-01-31","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}