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

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.


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 Press.

[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.

Cited by

[1] S. Pirandola, U. L. Andersen, L. Banchi, M. Berta, D. Bunandar, R. Colbeck, D. Englund, T. Gehring, C. Lupo, C. Ottaviani, J. L. Pereira, M. Razavi, J. Shamsul Shaari, M. Tomamichel, V. C. Usenko, G. Vallone, P. Villoresi, and P. Wallden, "Advances in quantum cryptography", Advances in Optics and Photonics 12 4, 1012 (2020).

[2] Mario Mastriani and Sundaraja Sitharama Iyengar, "Satellite quantum repeaters for a quantum Internet", Quantum Engineering 2 4(2020).

[3] Akihiro Mizutani, Go Kato, Koji Azuma, Marcos Curty, Rikizo Ikuta, Takashi Yamamoto, Nobuyuki Imoto, Hoi-Kwong Lo, and Kiyoshi Tamaki, "Quantum key distribution with setting-choice-independently correlated light sources", npj Quantum Information 5 1, 8 (2019).

[4] Ernest Y.-Z. Tan, Charles C.-W. Lim, and Renato Renner, "Advantage Distillation for Device-Independent Quantum Key Distribution", Physical Review Letters 124 2, 020502 (2020).

[5] A S Trushechkin, E O Kiktenko, D A Kronberg, and A K Fedorov, "Security of the decoy state method for quantum key distribution", Physics-Uspekhi 64 1, 88 (2021).

[6] A Pirker, M Zwerger, V Dunjko, H J Briegel, and W Dür, "Simple proof of confidentiality for private quantum channels in noisy environments", Quantum Science and Technology 4 2, 025009 (2019).

[7] Fabio Banfi, Ueli Maurer, Christopher Portmann, and Jiamin Zhu, Lecture Notes in Computer Science 11891, 282 (2019) ISBN:978-3-030-36029-0.

[8] Akihiro Mizutani, "Quantum key distribution with any two independent and identically distributed states", Physical Review A 102 2, 022613 (2020).

[9] Ya-Dong Wu, Ge Bai, Giulio Chiribella, and Nana Liu, "Efficient Verification of Continuous-Variable Quantum States and Devices without Assuming Identical and Independent Operations", Physical Review Letters 126 24, 240503 (2021).

[10] Kiyoshi Tamaki, Hoi-Kwong Lo, Akihiro Mizutani, Go Kato, Charles Ci Wen Lim, Koji Azuma, and Marcos Curty, "Security of quantum key distribution with iterative sifting", Quantum Science and Technology 3 1, 014002 (2018).

[11] M. K. Bochkov and A. S. Trushechkin, "Security of quantum key distribution with detection-efficiency mismatch in the single-photon case: Tight bounds", Physical Review A 99 3, 032308 (2019).

[12] Gláucia Murta, Federico Grasselli, Hermann Kampermann, and Dagmar Bruß, "Quantum Conference Key Agreement: A Review", Advanced Quantum Technologies 3 11, 2000025 (2020).

[13] Evgeniy O. Kiktenko, Aleksei O. Malyshev, Maxim A. Gavreev, Anton A. Bozhedarov, Nikolay O. Pozhar, Maxim N. Anufriev, and Aleksey K. Fedorov, "Lightweight Authentication for Quantum Key Distribution", IEEE Transactions on Information Theory 66 10, 6354 (2020).

[14] Alireza Poostindouz and Reihaneh Safavi-Naini, 2021 IEEE International Symposium on Information Theory (ISIT) 1254 (2021) ISBN:978-1-5386-8209-8.

[15] Shouvik Ghorai, Philippe Grangier, Eleni Diamanti, and Anthony Leverrier, "Asymptotic Security of Continuous-Variable Quantum Key Distribution with a Discrete Modulation", Physical Review X 9 2, 021059 (2019).

[16] Anurag Anshu, Mario Berta, Rahul Jain, and Marco Tomamichel, "A minimax approach to one-shot entropy inequalities", Journal of Mathematical Physics 60 12, 122201 (2019).

[17] Akihiro Mizutani, Toshihiko Sasaki, Yuki Takeuchi, Kiyoshi Tamaki, and Masato Koashi, "Quantum key distribution with simply characterized light sources", npj Quantum Information 5 1, 87 (2019).

[18] A. S. Trushechkin, E. O. Kiktenko, and A. K. Fedorov, "Practical issues in decoy-state quantum key distribution based on the central limit theorem", Physical Review A 96 2, 022316 (2017).

[19] V. E. Rodimin, E. O. Kiktenko, V. V. Usova, M. Y. Ponomarev, T. V. Kazieva, A. V. Miller, A. S. Sokolov, A. A. Kanapin, A. V. Losev, A. S. Trushechkin, M. N. Anufriev, N. O. Pozhar, V. L. Kurochkin, Y. V. Kurochkin, and A. K. Fedorov, "Modular Quantum Key Distribution Setup for Research and Development Applications", Journal of Russian Laser Research 40 3, 221 (2019).

[20] Yuki Takeuchi, Atul Mantri, Tomoyuki Morimae, Akihiro Mizutani, and Joseph F. Fitzsimons, "Resource-efficient verification of quantum computing using Serfling’s bound", npj Quantum Information 5 1, 27 (2019).

[21] Anne Broadbent and Rabib Islam, Lecture Notes in Computer Science 12552, 92 (2020) ISBN:978-3-030-64380-5.

[22] Yuki Takeuchi, Yuichiro Matsuzaki, Koichiro Miyanishi, Takanori Sugiyama, and William J. Munro, "Quantum remote sensing with asymmetric information gain", Physical Review A 99 2, 022325 (2019).

[23] Charles Ci-Wen Lim, Feihu Xu, Jian-Wei Pan, and Artur Ekert, "Security Analysis of Quantum Key Distribution with Small Block Length and Its Application to Quantum Space Communications", Physical Review Letters 126 10, 100501 (2021).

[24] G Murta, S B van Dam, J Ribeiro, R Hanson, and S Wehner, "Towards a realization of device-independent quantum key distribution", Quantum Science and Technology 4 3, 035011 (2019).

[25] Michael Epping, Hermann Kampermann, Chiara macchiavello, and Dagmar Bruß, "Multi-partite entanglement can speed up quantum key distribution in networks", New Journal of Physics 19 9, 093012 (2017).

[26] Jérémy Ribeiro, Gláucia Murta, and Stephanie Wehner, "Fully device-independent conference key agreement", Physical Review A 97 2, 022307 (2018).

[27] H. F. Chau, "Security of finite-key-length measurement-device-independent quantum key distribution using an arbitrary number of decoys", Physical Review A 102 1, 012611 (2020).

[28] Anton S. Trushechkin, Evgeniy O. Kiktenko, Dmitry A. Kronberg, and Aleksey K. Fedorov, "Security of the decoy state method for quantum key distribution", Uspekhi Fizicheskih Nauk 191 01, 93 (2021).

[29] Ryan Amiri, Petros Wallden, Adrian Kent, and Erika Andersson, "Secure quantum signatures using insecure quantum channels", Physical Review A 93 3, 032325 (2016).

[30] Mario Berta, Stephanie Wehner, and Mark M. Wilde, "Entropic uncertainty and measurement reversibility", New Journal of Physics 18 7, 073004 (2016).

[31] Ittoop Vergheese Puthoor, Ryan Amiri, Petros Wallden, Marcos Curty, and Erika Andersson, "Measurement-device-independent quantum digital signatures", Physical Review A 94 2, 022328 (2016).

[32] Carl A. Miller and Yaoyun Shi, "Robust protocols for securely expanding randomness and distributing keys using untrusted quantum devices", arXiv:1402.0489.

[33] Akihiro Mizutani, Nobuyuki Imoto, and Kiyoshi Tamaki, "Robustness of the round-robin differential-phase-shift quantum-key-distribution protocol against source flaws", Physical Review A 92 6, 060303 (2015).

[34] Kamil Brádler, Mohammad Mirhosseini, Robert Fickler, Anne Broadbent, and Robert Boyd, "Finite-key security analysis for multilevel quantum key distribution", New Journal of Physics 18 7, 073030 (2016).

[35] Corsin Pfister, Norbert Lütkenhaus, Stephanie Wehner, and Patrick J. Coles, "Sifting attacks in finite-size quantum key distribution", arXiv:1506.07502, New Journal of Physics 18 5, 053001 (2016).

[36] Christopher Portmann and Renato Renner, "Security in Quantum Cryptography", arXiv:2102.00021.

[37] Evgeny Kiktenko, Anton Trushechkin, Yury Kurochkin, and Aleksey Fedorov, "Post-processing procedure for industrial quantum key distribution systems", Journal of Physics Conference Series 741 1, 012081 (2016).

[38] Thomas Vidick, "Parallel DIQKD from parallel repetition", arXiv:1703.08508.

[39] Marco Tomamichel, Jesus Martinez-Mateo, Christoph Pacher, and David Elkouss, "Fundamental Finite Key Limits for One-Way Information Reconciliation in Quantum Key Distribution", arXiv:1401.5194, Quantum Information Processing 16 11, 280 (2014).

[40] Anne Broadbent and Christian Schaffner, "Quantum Cryptography Beyond Quantum Key Distribution", arXiv:1510.06120.

[41] S. N. Molotkov, "Quantum Key Distribution As a Scheme with Bernoulli Tests", Soviet Journal of Experimental and Theoretical Physics 126 6, 741 (2018).

[42] Christopher Portmann, "(Quantum) Min-Entropy Resources", arXiv:1705.10595.

[43] Sumeet Khatri, Eneet Kaur, Saikat Guha, and Mark M. Wilde, "Second-order coding rates for key distillation in quantum key distribution", arXiv:1910.03883.

[44] Fabio Banfi, Ueli Maurer, Christopher Portmann, and Jiamin Zhu, "Composable and Finite Computational Security of Quantum Message Transmission", arXiv:1908.03436.

[45] Vladimir L. Kurochkin, Yuriy V. Kurochkin, Alexander V. Miller, Alexander S. Sokolov, and Alan A. Kanapin, "Effect of crosstalk on QBER in QKD in urban telecommunication fiber lines", Society of Photo-Optical Instrumentation Engineers (SPIE) Conference Series 10224, 102242U (2016).

[46] Yixin Zhang, "Blockchain of Signature Material Combining Cryptographic Hash Function and DNA Steganography", arXiv:1909.07914.

[47] Ramona Wolf, "Quantum Key Distribution in the Non-Asymptotic Regime", arXiv:1511.06519.

[48] Arash Atashpendar, "From Information Theory Puzzles in Deletion Channels to Deniability in Quantum Cryptography", arXiv:2003.11663.

[49] Janusz Czub, Ryszard Veynar, Wiesław Laskowski, and Marcin Pawłowski, "Optimal pumping strength for BBM92 key distribution protocol", International Journal of Quantum Information 14 8, 1650049-179 (2016).

The above citations are from Crossref's cited-by service (last updated successfully 2021-10-26 23:14:18) and SAO/NASA ADS (last updated successfully 2021-10-27 15:30:07). The list may be incomplete as not all publishers provide suitable and complete citation data.

Could not fetch Crossref cited-by data during last attempt 2021-10-27 15:29:59: cURL error 28: Operation timed out after 6000 milliseconds with 0 bytes received