{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,19]],"date-time":"2025-12-19T15:21:34Z","timestamp":1766157694376,"version":"3.41.0"},"reference-count":85,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2013,11,1]],"date-time":"2013-11-01T00:00:00Z","timestamp":1383264000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100021745","name":"Perimeter Institute","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100021745","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100007631","name":"Canadian Institute for Advanced Research","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100007631","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003150","name":"Fonds Qu\u00e9b\u00e9cois de la Recherche sur la Nature et les Technologies","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100003150","id-type":"DOI","asserted-by":"publisher"}]},{"name":"QuantumWorks"},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["N000140811249"],"award-info":[{"award-number":["N000140811249"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004489","name":"Mitacs","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100004489","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001804","name":"Canada Research Chairs","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001804","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2013,11]]},"abstract":"<jats:p>\n            The existence of quantum uncertainty relations is the essential reason that some classically unrealizable cryptographic primitives become realizable when quantum communication is allowed. One operational manifestation of these uncertainty relations is a purely quantum effect referred to as\n            <jats:italic>information locking<\/jats:italic>\n            [DiVincenzo et al. 2004]. A locking scheme can be viewed as a cryptographic protocol in which a uniformly random\n            <jats:italic>n<\/jats:italic>\n            -bit message is encoded in a quantum system using a classical key of size much smaller than\n            <jats:italic>n<\/jats:italic>\n            . Without the key, no measurement of this quantum state can extract more than a negligible amount of information about the message, in which case the message is said to be \u201clocked\u201d. Furthermore, knowing the key, it is possible to recover, that is \u201cunlock\u201d, the message.\n          <\/jats:p>\n          <jats:p>\n            In this article, we make the following contributions by exploiting a connection between uncertainty relations and low-distortion embeddings of Euclidean spaces into slightly larger spaces endowed with the \u2113\n            <jats:sub>1<\/jats:sub>\n            norm. We introduce the notion of a\n            <jats:italic>metric uncertainty relation<\/jats:italic>\n            and connect it to low-distortion embeddings of \u2113\n            <jats:sub>2<\/jats:sub>\n            into \u2113\n            <jats:sub>1<\/jats:sub>\n            . A metric uncertainty relation also implies an entropic uncertainty relation. We prove that random bases satisfy uncertainty relations with a stronger definition and better parameters than previously known. Our proof is also considerably simpler than earlier proofs. We then apply this result to show the existence of locking schemes with key size independent of the message length. Moreover, we give\n            <jats:italic>efficient<\/jats:italic>\n            constructions of bases satisfying metric uncertainty relations. The bases defining these metric uncertainty relations are computable by quantum circuits of almost linear size. This leads to the first explicit construction of a strong information locking scheme. These constructions are obtained by adapting an explicit norm embedding due to Indyk [2007] and an extractor construction of Guruswami et al. [2009]. We apply our metric uncertainty relations to exhibit communication protocols that perform equality testing of\n            <jats:italic>n<\/jats:italic>\n            -qubit states. We prove that this task can be performed by a single message protocol using\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:sup>2<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            ) qubits and\n            <jats:italic>n<\/jats:italic>\n            bits of communication, where the computation of the sender is efficient.\n          <\/jats:p>","DOI":"10.1145\/2518131","type":"journal-article","created":{"date-parts":[[2013,12,4]],"date-time":"2013-12-04T14:04:47Z","timestamp":1386165887000},"page":"1-61","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":30,"title":["From Low-Distortion Norm Embeddings to Explicit Uncertainty Relations and Efficient Information Locking"],"prefix":"10.1145","volume":"60","author":[{"given":"Omar","family":"Fawzi","sequence":"first","affiliation":[{"name":"McGill University"}]},{"given":"Patrick","family":"Hayden","sequence":"additional","affiliation":[{"name":"McGill University"}]},{"given":"Pranab","family":"Sen","sequence":"additional","affiliation":[{"name":"Tata Institute of Fundamental Research"}]}],"member":"320","published-online":{"date-parts":[[2013,11]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.42172"},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","unstructured":"Ambainis A. 2010. Limits on entropic uncertainty relations. Quant. Inf. Comput. 10 9 & 10 848--858.   Ambainis A. 2010. Limits on entropic uncertainty relations. Quant. Inf. Comput. 10 9 & 10 848--858.","DOI":"10.26421\/QIC10.9-10-10"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/795666.796592"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-27821-4_23"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1063\/1.3271044"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00220-010-1172-y"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1088\/1751-8113\/40\/28\/S18"},{"key":"e_1_2_1_8_1","first-page":"1","article-title":"An elementary introduction to modern convex geometry","volume":"31","author":"Ball K.","year":"1997","journal-title":"Flavors Geom."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.75.022319"},{"volume-title":"Proceedings of the IEEE International Conference on Computers, Systems and Signal Processing.","author":"Bennett C. H.","key":"e_1_2_1_10_1"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.54.3824"},{"volume":"7417","volume-title":"Proceedings of CRYPTO. Lecture Notes in Computer Science","author":"Berta M.","key":"e_1_2_1_12_1"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01608825"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.87.167902"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.97.250501"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.78.022316"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24676-3_6"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.30"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/11535218_30"},{"volume":"4622","volume-title":"Proceedings of CRYPTO. Lecture Notes in Computer Science","author":"Damg\u00e5rd I.","key":"e_1_2_1_20_1"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.80.012304"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11128-009-0111-3"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2010.2048488"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.50.631"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.92.067902"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30576-7_30"},{"volume-title":"Expos\u00e9 de la th\u00e9orie des cha\u0131nes simples constantes de markov \u00e1 un nombre fini d\u00e9tats. Math\u00e9. de l","author":"Doeblin W.","key":"e_1_2_1_27_1"},{"key":"e_1_2_1_29_1","unstructured":"Dupuis F. Florjanczyk J. Hayden P. and Leung D. 2010. Locking classical information. arXiv:1011.1612v1 {quant-ph}.  Dupuis F. Florjanczyk J. Hayden P. and Leung D. 2010. Locking classical information. arXiv:1011.1612v1 {quant-ph}."},{"volume-title":"Proceedings of ICASSP. IEEE, 3586--3589","author":"Dvijotham K.","key":"e_1_2_1_30_1"},{"volume-title":"Proceedings of the International Symposium on Linear Spaces. Jerusalem Academic Press, 123--160","year":"1961","author":"Dvoretzky A.","key":"e_1_2_1_31_1"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01646490"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02392234"},{"key":"e_1_2_1_34_1","unstructured":"Gavinsky D. and Ito T. 2010. Quantum fingerprints that keep secrets. arXiv:1010.5342v1 {quant-ph}.  Gavinsky D. and Ito T. 2010. Quantum fingerprints that keep secrets. arXiv:1010.5342v1 {quant-ph}."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804106"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199712)11:4%3C315::AID-RSA3%3E3.0.CO;2-1"},{"volume-title":"Proceedings of ACM-SIAM SODA. SIAM, 353--362","author":"Guruswami V.","key":"e_1_2_1_37_1"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1538902.1538904"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1857914.1857918"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.92.187901"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1038\/nphys1224"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00220-008-0624-0"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2012.2191695"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00220-004-1087-6"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00220-006-1535-6"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.864469"},{"key":"e_1_2_1_47_1","first-page":"172","article-title":"\u00dcber den anschaulichen Inhalt der quantentheoretischen Kinematik und Mechanik","volume":"43","author":"Heisenberg W.","year":"1927","journal-title":"Zeitschrift f\u00fcr Physik A Hadrons and Nuclei"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.94.200501"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/73007.73009"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/1147954.1147955"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250881"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.5555\/1886521.1886570"},{"key":"e_1_2_1_53_1","first-page":"334","article-title":"Sections of some finite dimensional sets and classes of smooth functions","volume":"41","author":"Kashin B.","year":"1977","journal-title":"Izv. Acad. Nauk SSSR"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.69.022309"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.98.140502"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2011.2177772"},{"key":"e_1_2_1_57_1","doi-asserted-by":"crossref","unstructured":"Kushilevitz E. and Nisan N. 1997. Communication Complexity. Cambridge University Press.   Kushilevitz E. and Nisan N. 1997. Communication Complexity . Cambridge University Press.","DOI":"10.1017\/CBO9780511574948"},{"volume-title":"The Concentration of Measure Phenomenon","author":"Ledoux M.","key":"e_1_2_1_58_1","doi-asserted-by":"crossref","DOI":"10.1090\/surv\/089"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1088\/1742-6596\/143\/1\/012008"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.78.3410"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02126799"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.60.1103"},{"volume-title":"Lectures on Discrete Geometry","author":"Matou\u0161ek J.","key":"e_1_2_1_63_1","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4613-0039-7"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.78.3414"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01086740"},{"volume":"1200","volume-title":"Asymptotic Theory of Finite Dimensional Normed Spaces. Lecture Notes in Mathematics","author":"Milman V. D.","key":"e_1_2_1_66_1"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.72.042309"},{"key":"e_1_2_1_68_1","doi-asserted-by":"crossref","unstructured":"Pisier G. 1989. The Volume of Convex Bodies and Banach Space Geometry. Cambridge University Press.  Pisier G. 1989. The Volume of Convex Bodies and Banach Space Geometry . Cambridge University Press.","DOI":"10.1017\/CBO9780511662454"},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-008-9231-x"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1145\/301250.301292"},{"volume-title":"Proceedings of IEEE FOCS. 3--13","author":"Reingold O.","key":"e_1_2_1_71_1"},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRev.34.163"},{"volume":"2332","volume-title":"Proceedings of EUROCRYPT. Lecture Notes in Computer Science","author":"Russell A.","key":"e_1_2_1_73_1"},{"key":"e_1_2_1_74_1","first-page":"67","article-title":"Recent developments in explicit constructions of extractors","volume":"77","author":"Shaltiel R.","year":"2002","journal-title":"Bull. EATCS"},{"key":"e_1_2_1_75_1","doi-asserted-by":"crossref","unstructured":"Shoup V. 1990. New algorithms for finding irreducible polynomials over finite fields. Math. Comp. 54 189 435--447.  Shoup V. 1990. New algorithms for finding irreducible polynomials over finite fields. Math. Comp. 54 189 435--447.","DOI":"10.1090\/S0025-5718-1990-0993933-0"},{"key":"e_1_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1992-1106981-9"},{"key":"e_1_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.65.012310"},{"key":"e_1_2_1_78_1","volume-title":"Proceedings of the International Congress of Mathematicians.","volume":"2","author":"Szarek S.","year":"2006"},{"key":"e_1_2_1_79_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.106.110506"},{"key":"e_1_2_1_80_1","doi-asserted-by":"publisher","DOI":"10.1038\/ncomms1631"},{"key":"e_1_2_1_82_1","doi-asserted-by":"publisher","DOI":"10.1145\/1324215.1324225"},{"key":"e_1_2_1_83_1","unstructured":"von zur Gathen J. and Gerhard J. 1999. Modern Computer Algebra. Cambridge University Press.   von zur Gathen J. and Gerhard J. 1999. Modern Computer Algebra . Cambridge University Press."},{"key":"e_1_2_1_84_1","doi-asserted-by":"publisher","DOI":"10.1088\/1367-2630\/12\/2\/025009"},{"key":"e_1_2_1_85_1","doi-asserted-by":"crossref","unstructured":"Winter A. 2004. Quantum and classical message identification via quantum channels. Quantum Inf. Comput. 4 6&7 563--578.   Winter A. 2004. Quantum and classical message identification via quantum channels. Quantum Inf. Comput. 4 6&7 563--578.","DOI":"10.26421\/QIC4.6-7-14"},{"key":"e_1_2_1_86_1","doi-asserted-by":"publisher","DOI":"10.1016\/0003-4916(89)90322-9"},{"key":"e_1_2_1_87_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199712)11:4%3C345::AID-RSA4%3E3.0.CO;2-Z"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2518131","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2518131","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:14:13Z","timestamp":1750277653000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2518131"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,11]]},"references-count":85,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2013,11]]}},"alternative-id":["10.1145\/2518131"],"URL":"https:\/\/doi.org\/10.1145\/2518131","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2013,11]]},"assertion":[{"value":"2012-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-11-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}