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.

Cited by

[1] 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).

[2] 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).

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

[5] 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).

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

[8] 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", arXiv:1610.06499, Quantum Science and Technology 3 1, 014002 (2018).

[9] 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).

[10] 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).

[11] 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).

[12] 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).

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

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

[15] 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 (2017).

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

[17] 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).

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

[19] 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).

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

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

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

[23] 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).

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

The above citations are from Crossref's cited-by service (last updated 2019-06-18 12:16:54) and SAO/NASA ADS (last updated 2019-06-18 12:16:55). The list may be incomplete as not all publishers provide suitable and complete citation data.