Abstract
The aim of position-based cryptography is to use the geographical position of a party as its only credential. In this work, we study position-based cryptography in the quantum setting.
We show that if collaborating adversaries are allowed to pre-share an arbitrarily large entangled quantum state, then position-verification, and as a consequence position-based cryptography in general, is impossible (also) in the quantum setting.
To this end, we prove that with the help of sufficient pre-shared entanglement, any non-local quantum computation, i.e., any computation that involves quantum inputs from two parties at different locations, can be performed instantaneously and without any communication, up to local corrections that need to be applied to the outputs. The latter can be understood in that the parties obtain their respective outputs “encrypted”, where each corresponding encryption key is known by the opposite party. This result generalizes to any number of parties, and it implies that any non-local quantum computation can be performed using a single round of mutual communication (in which the parties exchange the encryption keys), and that any position-verification scheme can be broken, assuming sufficient pre-shared entanglement among the adversaries.
On the positive side, we show that for adversaries that are restricted to not share any entangled quantum states, 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.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Chandran, N., Goyal, V., Moriarty, R., Ostrovsky, R.: Position based cryptography. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 391–407. Springer, Heidelberg (2009)
Brands, S., Chaum, D.: Distance-bounding protocols. In: Helleseth, T. (ed.) EUROCRYPT 1993. LNCS, vol. 765, pp. 344–359. Springer, Heidelberg (1994)
Sastry, N., Shankar, U., Wagner, D.: Secure verification of location claims. In: WiSe 2003, pp. 1–10 (2003)
Vora, A., Nesterenko, M.: Secure location verification using radio broadcast. In: Higashino, T. (ed.) OPODIS 2004. LNCS, vol. 3544, pp. 369–383. Springer, Heidelberg (2005)
Bussard, L.: Trust Establishment Protocols for Communicating Devices. PhD thesis, Eurecom-ENST (2004)
Capkun, S., Hubaux, J.P.: Secure positioning of wireless devices with application to sensor networks. In: IEEE INFOCOM, 1917–1928 (2005)
Singelee, D., Preneel, B.: Location verification using secure distance bounding protocols. In: IEEE MASS’10 (2005)
Zhang, Y., Liu, W., Fang, Y., Wu, D.: Secure localization and authentication in ultra-wideband sensor networks. IEEE Journal on Selected Areas in Communications 24, 829–835 (2006)
Capkun, S., Cagalj, M., Srivastava, M.: Secure localization with hidden and mobile base stations. In: IEEE INFOCOM (2006)
Bennett, C.H., Brassard, G., Crépeau, C., Jozsa, R., Peres, A., Wootters, W.K.: Teleporting an unknown quantum state via dual classical and einstein-podolsky-rosen channels. Phys. Rev. Lett. 70(13), 1895–1899 (1993)
Vaidman, L.: Instantaneous measurement of nonlocal variables. Phys. Rev. Lett. 90(1), 010402 (2003)
Kent, A., Munro, W., Spiller, T., Beausoleil, R.: Tagging systems, US patent nr 2006/0022832 (2006)
Kent, A., Munro, B., Spiller, T.: Quantum tagging: Authenticating location via quantum information and relativistic signalling constraints, arXiv/quant-ph:1008.2147 (2010)
Malaney, R.A.: Location-dependent communications using quantum entanglement. Phys. Rev. A 81(4), 042319 (2010)
Malaney, R.A.: Quantum location verification in noisy channels, arXiv/quant-ph:1004.2689 (2010)
Chandran, N., Fehr, S., Gelles, R., Goyal, V., Ostrovsky, R.: Position-based quantum cryptography, arXiv/quant-ph:1005.1750 (2010)
Lau, H.K., Lo, H.K.: Insecurity of position-based quantum-cryptography protocols against entanglement attacks. Phys. Rev. A 83(1), 012322 (2011)
Kent, A.: Quantum tagging with cryptographically secure tags, arXiv/quant-ph:1008.5380 (2010)
Clark, S.R., Connor, A.J., Jaksch, D., Popescu, S.: Entanglement consumption of instantaneous nonlocal quantum measurements. New Journal of Physics 12(8), 083034 (2010)
Beigi, S., Koenig, R.: Simplified instantaneous non-local quantum computation with applications to position-based cryptography, arXiv/quant-ph:1101.1065 (2011)
Ishizaka, S., Hiroshima, T.: Asymptotic teleportation scheme as a universal programmable quantum processor. Phys. Rev. Lett. 101(24), 240501 (2008)
Ishizaka, S., Hiroshima, T.: Quantum teleportation scheme by selecting one of multiple output ports. Phys. Rev. A 79(4), 042306 (2009)
Giovannetti, V., Lloyd, S., Maccone, L.: Quantum cryptographic ranging. Journal of Optics B 4(4), 042319 (2002)
Renes, J., Boileau, J.: Conjectured strong complementary information tradeoff. Phys. Rev. Let. 103(2), 020402 (2009)
Buhrman, H., Chandran, N., Fehr, S., Gelles, R., Goyal, V., Ostrovsky, R., Schaffner, C.: Position-Based Quantum Cryptography: Impossibility and Constructions. Full version of this paper (2010), http://arxiv.org/abs/1009.2490
Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information. Cambridge University Press, Cambridge (2000)
Berta, M., Christandl, M., Colbeck, R., Renes, J.M., Renner, R.: The uncertainty principle in the presence of quantum memory. Nature Physics (2010)
Damgård, I., Fehr, S., Salvail, L., Schaffner, C.: Cryptography in the bounded quantum-storage model. In: 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 449–458. IEEE, Los Alamitos (2005)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 International Association for Cryptologic Research
About this paper
Cite this paper
Buhrman, H. et al. (2011). Position-Based Quantum Cryptography: Impossibility and Constructions. In: Rogaway, P. (eds) Advances in Cryptology – CRYPTO 2011. CRYPTO 2011. Lecture Notes in Computer Science, vol 6841. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-22792-9_24
Download citation
DOI: https://doi.org/10.1007/978-3-642-22792-9_24
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-22791-2
Online ISBN: 978-3-642-22792-9
eBook Packages: Computer ScienceComputer Science (R0)