A largely self-contained and complete security proof for quantum key distribution

Marco Tomamichel1 and Anthony Leverrier2

1Centre for Quantum Software and Information, University of Technology Sydney, Australia
2Inria Paris, France

In this work we present a security analysis for quantum key distribution, establishing a rigorous tradeoff between various protocol and security parameters for a class of entanglement-based and prepare-and-measure protocols. The goal of this paper is twofold: 1) to review and clarify the stateof-the-art security analysis based on entropic uncertainty relations, and 2) to provide an accessible resource for researchers interested in a security analysis of quantum cryptographic protocols that takes into account finite resource effects. For this purpose we collect and clarify several arguments spread in the literature on the subject with the goal of making this treatment largely self-contained.
More precisely, we focus on a class of prepare-and-measure protocols based on the Bennett-Brassard (BB84) protocol as well as a class of entanglement-based protocols similar to the Bennett-Brassard-Mermin (BBM92) protocol. We carefully formalize the different steps in these protocols, including randomization, measurement, parameter estimation, error correction and privacy amplification, allowing us to be mathematically precise throughout the security analysis. We start from an operational definition of what it means for a quantum key distribution protocol to be secure and derive simple conditions that serve as sufficient condition for secrecy and correctness. We then derive and eventually discuss tradeoff relations between the block length of the classical computation, the noise tolerance, the secret key length and the security parameters for our protocols. Our results significantly improve upon previously reported tradeoffs.


► BibTeX data

► References

[1] C.H. Bennett and G. Brassard. Quantum Cryptography: Public Key Distribution and Coin Tossing. In Proc. IEEE International Conference on Computers, Systems and Signal Processing 1984, volume 1, pages 175-179, Bangalore, 1984.

[2] A.K. Ekert. Quantum Cryptography Based on Bell's Theorem. Physical Review Letters, 67 (6): 661-663, 1991. 10.1103/​PhysRevLett.67.661.

[3] C. Bennett, G. Brassard, and N. Mermin. Quantum Cryptography Without Bell's Theorem. Physical Review Letters, 68 (5): 557-559, 1992. 10.1103/​PhysRevLett.68.557.

[4] H.-K. Lo and H.F. Chau. Unconditional Security of Quantum Key Distribution over Arbitrarily Long Distances. Science, 283 (5410): 2050-2056, 1999. 10.1126/​science.283.5410.2050.

[5] P.W. Shor and J. Preskill. Simple Proof of Security of the BB84 Quantum Key Distribution Protocol. Physical Review Letters, 85 (2): 441-444, 2000. 10.1103/​PhysRevLett.85.441.

[6] D. Mayers. Unconditional Security in Quantum Cryptography. Journal of the ACM, 48 (3): 351-406, 2001. 10.1145/​382780.382781.

[7] M. Koashi. Unconditional Security of Quantum Key Distribution and the Uncertainty Principle. Journal of Physics: Conference Series, 36 (1): 98-102, 2006. 10.1088/​1742-6596/​36/​1/​016.

[8] H. Maassen and J. Uffink. Generalized Entropic Uncertainty Relations. Physical Review Letters, 60 (12): 1103-1106, 1988. 10.1103/​PhysRevLett.60.1103.

[9] W. Heisenberg. Über den Anschaulichen Inhalt der Quantentheoretischen Kinematik und Mechanik. Zeitschrift für Physik, 43 (3-4): 172-198, mar 1927.

[10] R. Renner. Security of Quantum Key Distribution. PhD thesis, ETH Zurich, 2005. URL http:/​/​arxiv.org/​abs/​quant-ph/​0512258.

[11] L.C. Comandar, M. Lucamarini, B. Fröhlich, J.F. Dynes, A.W. Sharpe, S.W.-B. Tam, Z.L. Yuan, R.V. Penty, and A.J. Shields. Quantum key distribution without detector vulnerabilities using optically seeded lasers. Nature Photonics, 10 (5): 312-315, 2016. 10.1038/​nphoton.2016.50.

[12] P. Jouguet, S. Kunz-Jacques, A. Leverrier, P. Grangier, and E. Diamanti. Experimental demonstration of long-distance continuous-variable quantum key distribution. Nature Photonics, 7 (5): 378-381, 2013. 10.1038/​nphoton.2013.63.

[13] M. Tomamichel, C.C.W. Lim, N. Gisin, and R. Renner. Tight Finite-Key Analysis for Quantum Cryptography. Nature Communications, 3: 634, 2012. 10.1038/​ncomms1631.

[14] M. Hayashi and T. Tsurumaru. Concise and Tight Security Analysis of the Bennett-Brassard 1984 Protocol with Finite Key Lengths. New Journal of Physics, 14 (9): 093014, 2012. 10.1088/​1367-2630/​14/​9/​093014.

[15] V. Scarani and R. Renner. Quantum Cryptography with Finite Resources: Unconditional Security Bound for Discrete-Variable Protocols with One-Way Postprocessing. Physical Review Letters, 100 (20), 2008. 10.1103/​PhysRevLett.100.200501.

[16] R. Renner. Symmetry of Large Physical Systems Implies Independence of Subsystems. Nature Physics, 3 (9): 645-649, 2007. 10.1038/​nphys684.

[17] M. Christandl, R. König, and R. Renner. Postselection Technique for Quantum Channels with Applications to Quantum Cryptography. Physical Review Letters, 102 (2), 2009. 10.1103/​PhysRevLett.102.020504.

[18] L. Sheridan, T.P. Le, and V. Scarani. Finite-Key Security Against Coherent Attacks in Quantum Key Distribution. New Journal of Physics, 12: 123019, 2010.

[19] C. Pfister, N. Lütkenhaus, S. Wehner, and P.J. Coles. Sifting Attacks in Finite-Size Quantum Key Distribution. New Journal of Physics, 18 (5): 053001, 2016. 10.1088/​1367-2630/​18/​5/​053001.

[20] M. Tomamichel, S. Fehr, J. Kaniewski, and S. Wehner. A Monogamy-of-Entanglement Game with Applications to Device-Independent Quantum Cryptography. New Journal of Physics, 15 (10): 103002, 2013. 10.1088/​1367-2630/​15/​10/​103002.

[21] M. Tomamichel and R. Renner. Uncertainty Relation for Smooth Entropies. Physical Review Letters, 106 (11): 110506, 2011. 10.1103/​PhysRevLett.106.110506.

[22] M. Tomamichel. Quantum Information Processing with Finite Resources - Mathematical Foundations, volume 5 of SpringerBriefs in Mathematical Physics. Springer International Publishing, 2016. ISBN 978-3-319-21890-8. 10.1007/​978-3-319-21891-5.

[23] C.W. Helstrom. Quantum Detection and Estimation Theory. Academic Press, New York, NY, 1976.

[24] M. Tomamichel, R. Colbeck, and R. Renner. Duality Between Smooth Min- and Max-Entropies. IEEE Transactions on Information Theory, 56 (9): 4674-4681, 2010. 10.1109/​TIT.2010.2054130.

[25] J.L. Carter and M.N. Wegman. Universal Classes of Hash Functions. Journal of Computer and System Sciences, 18 (2): 143-154, 1979. 10.1016/​0022-0000(79)90044-8.

[26] M.N. Wegman and J.L. Carter. New Hash Functions and their Use in Authentication and Set Equality. Journal of Computer and System Sciences, 22 (3): 265-279, 1981. 10.1016/​0022-0000(81)90033-7.

[27] A. Rényi. On Measures of Information and Entropy. In Proc. 4th Berkeley Symposium on Mathematical Statistics and Probability, volume 1, pages 547-561, Berkeley, California, USA, 1961. University of California Pre.

[28] R. König, R. Renner, and C. Schaffner. The Operational Meaning of Min- and Max-Entropy. IEEE Transactions on Information Theory, 55 (9): 4337-4347, 2009. 10.1109/​TIT.2009.2025545.

[29] S. Winkler, M. Tomamichel, S. Hengl, and R. Renner. Impossibility of Growing Quantum Bit Commitments. Physical Review Letters, 107 (9): 090502, 2011. ISSN 0031-9007. 10.1103/​PhysRevLett.107.090502.

[30] H.-K. Lo, H.F. Chau, and M. Ardehali. Efficient Quantum Key Distribution Scheme and a Proof of Its Unconditional Security. Journal of Cryptology, 18(2):133-165, 2004 10.1007/​s00145-004-0142-y.

[31] D. Frauchiger, R. Renner, and M. Troyer. True randomness from realistic quantum devices, 2013. URL http:/​/​arxiv.org/​abs/​1311.4547.

[32] C. Portmann and R. Renner. Cryptographic Security of Quantum Key Distribution, 2014. URL http:/​/​arxiv.org/​abs/​1409.3525.

[33] L. Lydersen, C. Wiechers, C. Wittmann, D. Elser, J. Skaar, and V. Makarov. Hacking Commercial Quantum Cryptography Systems by Tailored Bright Illumination. Nature Photonics, 4 (10): 686-689, 2010. 10.1038/​nphoton.2010.214.

[34] M. Tomamichel and Esther Hänggi. The Link Between Entropic Uncertainty and Nonlocality. Journal of Physics A: Mathematical and Theoretical, 46 (5): 055301, 2013. 10.1088/​1751-8113/​46/​5/​055301.

[35] C.C.W. Lim, C. Portmann, M. Tomamichel, R. Renner, and Nicolas Gisin. Device-Independent Quantum Key Distribution with Local Bell Test. Physical Review X, 3 (3): 031006, 2013. 10.1103/​PhysRevX.3.031006.

[36] I. Devetak and A. Winter. Distillation of Secret Key and Entanglement from Quantum States. Proceedings of the Royal Society A, 461 (2053): 207-235, 2005. 10.1098/​rspa.2004.1372.

[37] D. Elkouss, A. Leverrier, R. Alleaume, and J.J. Boutros. Efficient Reconciliation Protocol for Discrete-Variable Quantum Key Distribution. In Proc. IEEE ISIT 2009, pages 1879-1883, 2009. 10.1109/​ISIT.2009.5205475.

[38] M. Tomamichel, J. Martinez-Mateo, C. Pacher, and D. Elkouss. Fundamental Finite Key Limits for Information Reconciliation in Quantum Key Distribution, 2014. URL http:/​/​arxiv.org/​abs/​1401.5194.

[39] M. Tomamichel. A Framework for Non-Asymptotic Quantum Information Theory. PhD thesis, ETH Zurich, 2012. URL http:/​/​arxiv.org/​abs/​1203.2142.

[40] R.J. Serfling. Probability Inequalities for the Sum in Sampling without Replacement. Annals of Statistics, 2 (1): 39-48, 1974.

[41] J.H. van Lint. Introduction to Coding Theory. Graduate Texts in Mathematics. Springer, third edition, 1999.

[42] H.-K. Lo, X. Ma, and K. Chen. Decoy State Quantum Key Distribution. Physical Review Letters, 94 (23), 2005. 10.1103/​PhysRevLett.94.230504.

[43] J. Hasegawa, M. Hayashi, T. Hiroshima, and A. Tomita. Security analysis of decoy state quantum key distribution incorporating finite statistics, 2007. URL http:/​/​arxiv.org/​abs/​0707.3541.

[44] C.C.W. Lim, M. Curty, N. Walenta, F. Xu, and H. Zbinden. Concise security bounds for practical decoy-state quantum key distribution. Physical Review A, 89 (2): 022307, 2014. 10.1103/​PhysRevA.89.022307.

[45] D. Bruss. Optimal Eavesdropping in Quantum Cryptography with Six States. Physical Review Letters, 81 (14): 3018-3021, 1998. 10.1103/​PhysRevLett.81.3018.

[46] F. Dupuis, O. Fawzi, and R. Renner. Entropy accumulation, 2016. URL http:/​/​arxiv.org/​abs/​1607.01796.

[47] R. Arnon-Friedman, R. Renner, and T. Vidick. Simple and tight device-independent security proofs, 2016. URL http:/​/​arxiv.org/​abs/​1607.01797.

[48] R. Bhatia. Matrix Analysis. Graduate Texts in Mathematics. Springer, 1997. ISBN 0-387-94846-5.