The position of a device or agent is an important security credential in today’s society, both online and in the real world. Unless in direct proximity, however, the secure verification of a position is impossible without further assumptions. This is true classically1, but also in any future quantum-equipped communications infrastructure2. We show in this work that minimal quantum resources, in the form of a single qubit, combined with classical communication are sufficient to thwart quantum adversaries that pretend to be at a specific position and have the ability to coordinate their action with entanglement. More precisely, we show that adversaries using an increasing amount of entanglement can be combatted solely by increasing the number of classical bits used in the protocol. The presented protocols are noise-robust and within reach of current quantum technology.
Your institute does not have access to this article
Subscription info for Chinese customers
We have a dedicated website for our Chinese customers. Please go to naturechina.com to subscribe to this journal.
Get time limited or full article access on ReadCube.
All prices are NET prices.
Data sharing is not applicable to this Article as no datasets were generated or analysed during the current study.
Chandran, N., Goyal, V., Moriarty, R. & Ostrovsky, R. Position based cryptography. In Proc. Advances in Cryptology—CRYPTO 2009, Lecture Notes in Computer Science (ed. Halevi, S.) Vol. 5677, 391–407 (Springer, 2009).
Buhrman, H. et al. Position-based quantum cryptography: impossibility and constructions. SIAM J. Comput. 43, 150–178 (2014).
Kent, A., Munro, W. J. & Spiller, T. P. Quantum tagging: authenticating location via quantum information and relativistic signaling constraints. Phys. Rev. A 84, 012326 (2011).
Malaney, R. A. Location-dependent communications using quantum entanglement. Phys. Rev. A 81, 042319 (2010).
Vaidman, L. Instantaneous measurement of nonlocal variables. Phys. Rev. Lett. 90, 010402 (2003).
Beigi, S. & König, R. Simplified instantaneous non-local quantum computation with applications to position-based cryptography. N. J. Phys. 13, 093036 (2011).
Tomamichel, M., Fehr, S., Kaniewski, J. & Wehner, S. A monogamy-of-entanglement game with applications to device-independent quantum cryptography. N. J. Phys. 15, 103002 (2013).
Ribeiro, J. & Grosshans, F. A tight lower bound for the BB84-states quantum-position-verification protocol. Preprint at https://arxiv.org/abs/1504.07171 (2015).
Lau, H.-K. & Lo, H.-K. Insecurity of position-based quantum-cryptography protocols against entanglement attacks. Phys. Rev. A 83, 012322 (2011).
Chakraborty, K. & Leverrier, A. Practical position-based quantum cryptography. Phys. Rev. A 92, 052304 (2015).
Malaney, R. The quantum car. IEEE Wirel. Commun. Lett. 5, 624–627 (2016).
Das, S. & Siopsis, G. Practically secure quantum position verification. N. J. Phys. 23, 063069 (2021).
Gonzales, A. & Chitambar, E. Bounds on instantaneous nonlocal quantum computation. IEEE Trans. Inf. Theory 66, 2951–2963 (2019).
Buhrman, H., Fehr, S., Schaffner, C. & Speelman, F. The garden-hose model. In Proc. 4th Conference on Innovations in Theoretical Computer Science ITCS ’13 145–158 (ACM, 2013).
Speelman, F. Instantaneous non-local computation of low T-depth quantum circuits. In Proc. 11th Conference on the Theory of Quantum Computation, Communication and Cryptography TQC 2016, Leibniz International Proceedings in Informatics (LIPIcs) (ed. Broadbent, A.) Vol. 61, 9:1–9:24 (Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2016).
Olivo, A., Chabaud, U., Chailloux, A. & Grosshans, F. Breaking simple quantum position verification protocols with little entanglement. Preprint at https://arxiv.org/abs/2007.15808 (2020).
Kent, A. Quantum tagging for tags containing secret classical data. Phys. Rev. A 84, 022335 (2011).
Gao, F., Liu, B. & Wen, Q.-Y. Enhanced no-go theorem for quantum position verification. Preprint at https://arxiv.org/abs/1305.4254 (2013).
Unruh, D. Quantum position verification in the random oracle model. In Proc. Advances in Cryptology—CRYPTO 2014, Lecture Notes in Computer Science (eds. Garay J.A., Gennaro R.) Vol. 8617, 1–18 (Springer, 2014).
Qi, B. & Siopsis, G. Loss-tolerant position-based quantum cryptography. Phys. Rev. A 91, 042337 (2015).
Lim, C. C. W. et al. Loss-tolerant quantum secure positioning with weak laser sources. Phys. Rev. A 94, 032315 (2016).
Allerstorfer, R., Buhrman, H., Speelman, F. & Verduyn Lunel, P. New protocols and ideas for practical quantum position verification. Preprint at https://arxiv.org/abs/2106.12911 (2021).
Junge, M., Kubicki, A. M., Palazuelos, C. & Pérez-García, D. Geometry of Banach spaces: a new route towards position based cryptography. Preprint at https://arxiv.org/abs/2103.16357 (2021).
Renes, J. M. & Boileau, J.-C. Conjectured strong complementary information tradeoff. Phys. Rev. Lett. 103, 020402 (2009).
Berta, M., Christandl, M., Colbeck, R., Renes, J. M. & Renner, R. The uncertainty principle in the presence of quantum memory. Nat. Phys. 6, 659–662 (2010).
We thank A. Kent for organizing a workshop on relativistic quantum information theory in February 2020, during which part of this work was presented. A.B. and M.C. acknowledge financial support from the European Research Council (grant agreement no. 81876), VILLUM FONDEN via the QMATH Centre of Excellence (grant no.10059) and the QuantERA ERA-NET Cofund in Quantum Technologies implemented within the European Union’s Horizon 2020 Programme (QuantAlgo project) via the Innovation Fund Denmark.
The authors declare no competing interests.
Peer review information
Nature Physics thanks Carl Miller, Yusuf Alnawakhtha and the other, anonymous, reviewer(s) for their contribution to the peer review of this work.
Publisher’s note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
About this article
Cite this article
Bluhm, A., Christandl, M. & Speelman, F. A single-qubit position verification protocol that is secure against multi-qubit attacks. Nat. Phys. 18, 623–626 (2022). https://doi.org/10.1038/s41567-022-01577-0
Nature Physics (2022)