Abstract
A serious concern with quantum key distribution (QKD) schemes is that, when under attack, the quantum devices in a real-life implementation may behave differently than modeled in the security proof. This can lead to real-life attacks against provably secure QKD schemes.
In this work, we show that the standard BB84 QKD scheme is one-sided device-independent. This means that security holds even if Bob’s quantum device is arbitrarily malicious, as long as Alice’s device behaves as it should. Thus, we can completely remove the trust into Bob’s quantum device for free, without the need for changing the scheme, and without the need for hard-to-implement loophole-free violations of Bell inequality, as is required for fully (meaning two-sided) device-independent QKD.
For our analysis, we introduce a new quantum game, called a monogamy-of-entanglement game, and we show a strong parallel repetition theorem for this game. This new notion is likely to be of independent interest and to find additional applications. Indeed, besides the application to QKD, we also show a direct application to position-based quantum cryptography: we give the first security proof for a one-round position-verification scheme that requires only single-qubit operations.
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
Acín, A., Brunner, N., Gisin, N., Massar, S., Pironio, S., Scarani, V.: Device-Independent Security of Quantum Cryptography against Collective Attacks. Phys. Rev. Lett. 98(23) (2007)
Barrett, J., Hardy, L., Kent, A.: No Signaling and Quantum Key Distribution. Phys. Rev. Lett. 95(1) (June 2005)
Beigi, S., König, R.: Simplified Instantaneous Non-Local Quantum Computation with Applications to Position-Based Cryptography. New J. Phys. 13(9), 093036 (2011)
Bennett, C.H., Brassard, G., Mermin, N.: Quantum Cryptography Without Bell’s Theorem. Phys. Rev. Lett. 68(5), 557–559 (1992)
Bennett, C.H., Brassard, G.: Quantum Cryptography: Public Key Distribution and Coin Tossing. In: Proc. IEEE Int. Conf. on Comp., Sys. and Signal Process., Bangalore, pp. 175–179. IEEE (1984)
Branciard, C., Cavalcanti, E.G., Walborn, S.P., Scarani, V., Wiseman, H.M.: One-sided device-independent quantum key distribution: Security, feasibility, and the connection with steering. Phys. Rev. A 85(1), 010301 (2012)
Braunstein, S., Pirandola, S.: Side-Channel-Free Quantum Key Distribution. Phys. Rev. Lett. 108(13), 130502 (2012)
Buhrman, H., Chandran, N., Fehr, S., Gelles, R., Goyal, V., Ostrovsky, R., Schaffner, C.: Position-Based Quantum Cryptography: Impossibility and Constructions. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 429–446. Springer, Heidelberg (2011)
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)
Einstein, A., Podolsky, B., Rosen, N.: Can Quantum-Mechanical Description of Physical Reality Be Considered Complete? Phys. Rev. 47(10), 777–780 (1935)
Ekert, A.K.: Quantum cryptography based on Bell’s theorem. Phys. Rev. Lett. 67(6), 661–663 (1991)
Gisin, N., Pironio, S., Sangouard, N.: Proposal for Implementing Device-Independent Quantum Key Distribution Based on a Heralded Qubit Amplifier. Phys. Rev. Lett. 105(7) (August 2010)
Hänggi, E., Renner, R.: Device-Independent Quantum Key Distribution with Commuting Measurements (September 2010), http://arxiv.org/abs/1009.1833
Hastings, M.: A Counterexample to Additivity of Minimum Output Entropy. Nature Physics 5, 255 (2009)
Heisenberg, W.: Über den anschaulichen Inhalt der quantentheoretischen Kinematik und Mechanik. Z. Phys. 43(3-4), 172–198 (1927)
Kempe, J., Vidick, T.: Parallel Repetition of Entangled Games. In: 43rd STOC, pp. 353–362. ACM (2011)
Kent, A., Munro, W.J., Spiller, T.P.: Quantum Tagging: Authenticating Location via Quantum Information and Relativistic Signalling Constraints (August 2010), http://arxiv.org/abs/1008.2147
Kittaneh, F.: Norm Inequalities for Certain Operator Sums. Journal of Functional Analysis 143(2), 337–348 (1997)
Klauck, H.: A Strong Direct Product Theorem for Disjointness. In: 42nd STOC, pp. 77–86. ACM (2010)
König, R., Renner, R., Schaffner, C.: The Operational Meaning of Min- and Max-Entropy. IEEE Trans. on Inf. Theory 55(9), 4337–4347 (2009)
Krishna, M., Parthasarathy, K.R.: An Entropic Uncertainty Principle for Quantum Measurements. Indian J. Stat. 64(3), 842–851 (2002)
Lau, H.-K., Lo, H.-K.: Insecurity of Position-based Quantum-Cryptography Protocols Against Entanglement Attacks. Phys. Rev. A 83(1), 1–12 (2011)
Lim, C.C.W., Portmann, C., Tomamichel, M., Renner, R., Gisin, N.: Device-Independent Quantum Key Distribution with Local Bell Test (July 2012), http://arxiv.org/abs/1208.0023
Lo, H.-K., Curty, M., Qi, B.: Measurement-Device-Independent Quantum Key Distribution. Phys. Rev. Lett. 108(13), 130503 (2012)
Lydersen, L., Wiechers, C., Wittmann, C., Elser, D., Skaar, J., Makarov, V.: Hacking Commercial Quantum Cryptography Systems by Tailored Bright Illumination. Nat. Photon. 4(10), 686–689 (2010)
Masanes, L., Pironio, S., Acín, A.: Secure Device-independent Quantum Key Distribution With Causally Independent Measurement Devices. Nat. Commun. 2, 238 (2011)
Mayers, D.: Quantum Key Distribution and String Oblivious Transfer in Noisy Channels. In: Koblitz, N. (ed.) CRYPTO 1996. LNCS, vol. 1109, pp. 343–357. Springer, Heidelberg (1996)
Mayers, D., Yao, A.: Quantum Cryptography with Imperfect Apparatus. In: 39th FOCS, pp. 503–509. IEEE Computer Society (1998)
Raz, R.: A Parallel Repetition Theorem. SIAM Journal on Computing 27, 763–803 (1998)
Reichardt, B.W., Unger, F., Vazirani, U.: Classical Command of Quantum Systems via Rigidity of CHSH Games (September 2012), http://arxiv.org/abs/1209.0449
Renner, R.: Security of Quantum Key Distribution. PhD thesis, ETH Zurich (December 2005), http://arxiv.org/abs/quant-ph/0512258
Schaffner, C.: Cryptography in the Bounded-Quantum-Storage Model. PhD thesis, University of Aarhus (September 2007), http://arxiv.org/abs/0709.0289
Shor, P., Preskill, J.: Simple Proof of Security of the BB84 Quantum Key Distribution Protocol. Phys. Rev. Lett. 85(2), 441–444 (2000)
Terhal, B.: Is Entanglement Monogamous? IBM J. Reasearch and Development 48(1), 71–78 (2004)
Tomamichel, M.: A Framework for Non-Asymptotic Quantum Information Theory. PhD thesis, ETH Zurich (March 2012), http://arxiv.org/abs/1203.2142
Tomamichel, M., Fehr, S., Kaniewski, J., Wehner, S.: Strong Parallel Repetition for a Monogamy-of-Entanglement Game (October 2012), http://arxiv.org/abs/1210.4359
Tomamichel, M., Hayashi, M.: A Hierarchy of Information Quantities for Finite Block Length Analysis of Quantum Tasks (August 2012), http://arxiv.org/abs/1208.1478
Tomamichel, M., Renner, R.: Uncertainty Relation for Smooth Entropies. Phys. Rev. Lett. 106(11) (March 2011)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 International Association for Cryptologic Research
About this paper
Cite this paper
Tomamichel, M., Fehr, S., Kaniewski, J., Wehner, S. (2013). One-Sided Device-Independent QKD and Position-Based Cryptography from Monogamy Games. In: Johansson, T., Nguyen, P.Q. (eds) Advances in Cryptology – EUROCRYPT 2013. EUROCRYPT 2013. Lecture Notes in Computer Science, vol 7881. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-38348-9_36
Download citation
DOI: https://doi.org/10.1007/978-3-642-38348-9_36
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-38347-2
Online ISBN: 978-3-642-38348-9
eBook Packages: Computer ScienceComputer Science (R0)