{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,30]],"date-time":"2026-09-30T19:37:12Z","timestamp":1790797032850,"version":"4.1.0"},"reference-count":49,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2014,1]]},"abstract":"<jats:p>In this work, we study position-based cryptography in the quantum setting. The aim is to use the geographical position of a party as its only credential. On the negative side, we show that if adversaries are allowed to share an arbitrarily large entangled quantum state, the task of secure position-verification is impossible. To this end, we prove the following very general result. Assume that Alice and Bob hold respectively subsystems $A$ and $B$ of a (possibly) unknown quantum state $|\\psi\\rangle \\in {\\cal H}_A \\otimes {\\cal H}_B$. Their goal is to calculate and share a new state $|\\varphi\\rangle = U|\\psi\\rangle$, where $U$ is a fixed unitary operation. The question that we ask is how many rounds of mutual communication are needed. It is easy to achieve such a task using two rounds of classical communication, whereas, in general, it is impossible with no communication at all. Surprisingly, in case Alice and Bob share enough entanglement to start with and we allow an arbitrarily small failure probability, we show that the same task can be done using a single round of classical communication in which Alice and Bob exchange two classical messages. Actually, we prove that a relaxed version of the task can be done with no communication at all, where the task is to compute instead a state $|\\varphi'\\rangle$ that coincides with $|\\varphi\\rangle = U|\\psi\\rangle$ up to local operations on $A$ and on $B$, which are determined by classical information held by Alice and Bob. The one-round scheme for the original task then follows as a simple corollary. We also show that these results generalize to more players. As a consequence, we show a generic attack that breaks any position-verification scheme. On the positive side, we show that if adversaries do not share any entangled quantum state but can compute arbitrary quantum operations, secure position-verification is achievable. Jointly, these results suggest the interesting question whether secure position-verification is possible in case of a bounded amount of entanglement. Our positive result can be interpreted as resolving this question in the simplest case, where the bound is set to zero. In models where secure position-verification is achievable, it has a number of interesting applications. For example, it enables secure communication over an insecure channel without having any preshared key, with the guarantee that only a party at a specific location can learn the content of the conversation. More generally, we show that in settings where secure position-verification is achievable, other position-based cryptographic schemes are possible as well, such as secure position-based authentication and position-based key agreement.<\/jats:p>","DOI":"10.1137\/130913687","type":"journal-article","created":{"date-parts":[[2014,2,4]],"date-time":"2014-02-04T11:14:04Z","timestamp":1391512444000},"page":"150-178","source":"Crossref","is-referenced-by-count":90,"title":["Position-Based Quantum Cryptography: Impossibility and Constructions"],"prefix":"10.1137","volume":"43","author":[{"given":"Harry","family":"Buhrman","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nishanth","family":"Chandran","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Serge","family":"Fehr","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ran","family":"Gelles","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Vipul","family":"Goyal","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rafail","family":"Ostrovsky","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Christian","family":"Schaffner","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2014,2,4]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevD.21.3316"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevD.24.359"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1088\/1367-2630\/13\/9\/093036"},{"key":"atypb4","first-page":"386","author":"Ben-Or M.","year":"2005","journal-title":"Berlin"},{"key":"atypb5","unstructured":"C. Bennett and G. Brassard,\n                      Quantum cryptography: Public key distribution and coin tossing\n                      , in Proceedings of the IEEE International Conference on Computers, Systems and Signal Processing, Vol. 175, IEEE, Washington, DC, 1984, pp. 175-179."},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.70.1895"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1038\/nphys1734"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1007\/s00145-005-0011-3"},{"key":"atypb9","first-page":"344","author":"Brands S.","year":"1994","journal-title":"Berlin"},{"key":"atypb10","first-page":"429","author":"Buhrman H.","year":"2011","journal-title":"Berlin"},{"key":"atypb11","first-page":"145","author":"Buhrman H.","year":"2013","journal-title":"New York"},{"key":"atypb12","unstructured":"L. Bussard,\n                      Trust Establishment Protocols for Communicating Devices\n                      , Ph.D. thesis, Eurecom-ENST, 2004."},{"key":"atypb13","first-page":"1","author":"\u010capkun S.","year":"2006","journal-title":"Washington, DC"},{"key":"atypb14","doi-asserted-by":"crossref","unstructured":"S. \u010capkun and J.P. Hubaux,\n                      Secure positioning of wireless devices with application to sensor networks\n                      , in Proceedings of the IEEE 24th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM '05), Vol. 3, IEEE, Washington, DC, 2005, pp. 1917-1928.","DOI":"10.1109\/INFCOM.2005.1498470"},{"key":"atypb15","unstructured":"N. Chandran, S. Fehr, R. Gelles, V. Goyal, and R. Ostrovsky,\n                      Position-based Quantum Cryptography\n                      , arXiv\/quant-ph:1005.1750, 2010."},{"key":"atypb16","first-page":"391","author":"Chandran N.","year":"2009","journal-title":"Heidelberg"},{"key":"atypb17","first-page":"785","author":"Chandran N.","year":"2010","journal-title":"New York"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177729330"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1088\/1367-2630\/12\/8\/083034"},{"key":"atypb20","unstructured":"T. M. Cover and J. A. Thomas,\n                      Elements of Information Theory\n                      , Wiley, New York, 1991."},{"key":"atypb21","first-page":"449","author":"I.","year":"2005","journal-title":"Washington, DC"},{"key":"atypb22","doi-asserted-by":"crossref","unstructured":"R. Fano,\n                      Transmission of Information: A Statistical Theory of Communications\n                      , MIT Press, Cambridge, MA, 1961.","DOI":"10.1119\/1.1937609"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1088\/1464-4266\/4\/4\/330"},{"key":"atypb24","first-page":"31","volume":"9","author":"Holevo A. S.","year":"1973","journal-title":"Problemy Pereda\u010di Informacii"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.101.240501"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.79.042306"},{"key":"atypb27","first-page":"206","author":"Kanukurthi B.","year":"2009","journal-title":"Berlin"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.84.022335"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1088\/0264-9381\/29\/22\/224013"},{"key":"atypb30","doi-asserted-by":"crossref","unstructured":"A. Kent, W. J. Munro, and T. P. Spiller,\n                      Quantum Tagging: Authenticating Location via Quantum Information and Relativistic Signalling Constraints\n                      , arXiv\/quant-ph:1008.2147, 2010.","DOI":"10.1103\/PhysRevA.84.012326"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.84.012326"},{"key":"atypb32","unstructured":"A. Kent, W. J. Munro, T. P. Spiller, and R. Beausoleil,\n                      Tagging systems\n                      , U.S. Patent 2006\/0022832, 2006."},{"key":"atypb33","unstructured":"H.K. Lau and H.K. Lo,\n                      Insecurity of Position-Based Quantum Cryptography Protocols against Entanglement Attacks\n                      , arXiv\/quant-ph:1009.2256v3 [quant-ph], 2010."},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.83.012322"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1126\/science.283.5410.2050"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.81.042319"},{"key":"atypb37","first-page":"1","author":"Malaney R. A.","year":"2010","journal-title":"Washington, DC"},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1145\/382780.382781"},{"key":"atypb39","unstructured":"M. A. Nielsen and I. L. Chuang,\n                      Quantum Computation and Quantum Information\n                      , Cambridge University Press, Cambridge, UK, 2000."},{"key":"atypb40","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.103.020402"},{"key":"atypb41","unstructured":"R. Renner,\n                      Security of Quantum Key Distribution\n                      , Ph.D. thesis, ETH Z\u00fcrich, Z\u00fcrich, Switzerland, 2005; available online from http:\/\/arxiv.org\/abs\/quant-ph\/0512258."},{"key":"atypb42","first-page":"78","author":"Renner R.","year":"2003","journal-title":"Berlin"},{"key":"atypb43","first-page":"1","author":"Sastry N.","year":"2003","journal-title":"New York"},{"key":"atypb44","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.85.441"},{"key":"atypb45","first-page":"834","author":"Singelee D.","year":"2005","journal-title":"Proceedings of the IEEE International Conference on Mobile Ad Hoc and Sensor Systems Conference, IEEE, Washington, DC"},{"key":"atypb46","first-page":"609","author":"Tomamichel M.","year":"2013","journal-title":"Berlin"},{"key":"atypb47","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.90.010402"},{"key":"atypb48","doi-asserted-by":"publisher","DOI":"10.1109\/TDSC.2006.57"},{"key":"atypb49","doi-asserted-by":"publisher","DOI":"10.1109\/JSAC.2005.863855"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/130913687","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:59:52Z","timestamp":1787338792000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/130913687"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,1]]},"references-count":49,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2014,1]]}},"alternative-id":["10.1137\/130913687"],"URL":"https:\/\/doi.org\/10.1137\/130913687","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,1]]}}}