QKD parameter estimation by two-universal hashing

Dimiter Ostrev

Institute of Communications and Navigation, German Aerospace Center, Oberpfaffenhofen, 82234 Weßling, Germany

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

Abstract

This paper proposes and proves security of a QKD protocol which uses two-universal hashing instead of random sampling to estimate the number of bit flip and phase flip errors. This protocol dramatically outperforms previous QKD protocols for small block sizes. More generally, for the two-universal hashing QKD protocol, the difference between asymptotic and finite key rate decreases with the number $n$ of qubits as $cn^{-1}$, where $c$ depends on the security parameter. For comparison, the same difference decreases no faster than $c'n^{-1/3}$ for an optimized protocol that uses random sampling and has the same asymptotic rate, where $c'$ depends on the security parameter and the error rate.

A quantum key distribution (QKD) protocol allows two users to establish a secret key by communicating over an authenticated classical channel and a completely insecure quantum channel. Important parameters for a QKD protocol are the number of qubits sent over the quantum channel, the resistance to noise on the quantum channel, the size of the output secret key, and the security level.

Existing QKD protocols and security proofs exhibit trade-offs between the parameters: for a given number of qubits, improving noise resistance or security makes the output size smaller. These trade-offs are especially severe when the number of qubits is small, i.e. around 1000-10000. Such a small number of qubits arises in practice when the quantum channel is particularly difficult to implement, for example when a satellite is transmitting entangled photon pairs to two ground stations.

The present work asks: are there QKD protocols and security proofs that exhibit better parameter trade-offs, especially in the case when the number of qubits is small? It presents one such QKD protocol and security proof. This protocol uses two-universal hashing instead of random sampling to estimate the number of bit flip and phase flip errors, leading to a dramatic improvement in parameter trade-offs for small numbers of qubits, but also making the protocol harder to implement.

► BibTeX data

► References

[1] Charles H. Bennett, David P. DiVincenzo, John A. Smolin, and William K. Wootters. Mixed-state entanglement and quantum error correction. Phys. Rev. A, 54:3824–3851, Nov 1996. URL: https:/​/​link.aps.org/​doi/​10.1103/​PhysRevA.54.3824, doi:10.1103/​PhysRevA.54.3824.
https:/​/​doi.org/​10.1103/​PhysRevA.54.3824

[2] Niek J Bouman and Serge Fehr. Sampling in a quantum population, and applications. In Annual Cryptology Conference, pages 724–741. Springer, 2010. doi:10.1007/​978-3-642-14623-7_39.
https:/​/​doi.org/​10.1007/​978-3-642-14623-7_39

[3] Gilles Brassard and Louis Salvail. Secret-key reconciliation by public discussion. In Workshop on the Theory and Application of of Cryptographic Techniques, pages 410–423. Springer, 1993. doi:10.1007/​3-540-48285-7_35.
https:/​/​doi.org/​10.1007/​3-540-48285-7_35

[4] A. R. Calderbank, E. M. Rains, P. W. Shor, and N. J. A. Sloane. Quantum error correction and orthogonal geometry. Phys. Rev. Lett., 78:405–408, Jan 1997. URL: https:/​/​link.aps.org/​doi/​10.1103/​PhysRevLett.78.405, doi:10.1103/​PhysRevLett.78.405.
https:/​/​doi.org/​10.1103/​PhysRevLett.78.405

[5] A. R. Calderbank and Peter W. Shor. Good quantum error-correcting codes exist. Phys. Rev. A, 54:1098–1105, Aug 1996. URL: https:/​/​link.aps.org/​doi/​10.1103/​PhysRevA.54.1098, doi:10.1103/​PhysRevA.54.1098.
https:/​/​doi.org/​10.1103/​PhysRevA.54.1098

[6] J.Lawrence Carter and Mark N. Wegman. Universal classes of hash functions. Journal of Computer and System Sciences, 18(2):143–154, 1979. URL: https:/​/​www.sciencedirect.com/​science/​article/​pii/​0022000079900448, doi:10.1016/​0022-0000(79)90044-8.
https:/​/​doi.org/​10.1016/​0022-0000(79)90044-8
https:/​/​www.sciencedirect.com/​science/​article/​pii/​0022000079900448

[7] Peter Elias. Coding for two noisy channels. In Colin Cherry, editor, Information Theory, 3rd London Symposium, London, England, Sept. 1955. Butterworth's scientific publications, 1956. URL: https:/​/​worldcat.org/​en/​title/​562487502, doi:10.1038/​176773a0.
https:/​/​doi.org/​10.1038/​176773a0
https:/​/​worldcat.org/​en/​title/​562487502

[8] Chi-Hang Fred Fung, Xiongfeng Ma, and H. F. Chau. Practical issues in quantum-key-distribution postprocessing. Physical Review A, 81(1), Jan 2010. URL: http:/​/​dx.doi.org/​10.1103/​PhysRevA.81.012318, doi:10.1103/​physreva.81.012318.
https:/​/​doi.org/​10.1103/​PhysRevA.81.012318

[9] Robert G. Gallager. Low-Density Parity-Check Codes. The MIT Press, 09 1963. doi:10.7551/​mitpress/​4347.001.0001.
https:/​/​doi.org/​10.7551/​mitpress/​4347.001.0001

[10] Daniel Gottesman. Class of quantum error-correcting codes saturating the quantum hamming bound. Phys. Rev. A, 54:1862–1868, Sep 1996. URL: https:/​/​link.aps.org/​doi/​10.1103/​PhysRevA.54.1862, doi:10.1103/​PhysRevA.54.1862.
https:/​/​doi.org/​10.1103/​PhysRevA.54.1862

[11] M Koashi. Simple security proof of quantum key distribution based on complementarity. New Journal of Physics, 11(4):045018, apr 2009. URL: https:/​/​dx.doi.org/​10.1088/​1367-2630/​11/​4/​045018, doi:10.1088/​1367-2630/​11/​4/​045018.
https:/​/​doi.org/​10.1088/​1367-2630/​11/​4/​045018

[12] 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), Mar 2021. URL: http:/​/​dx.doi.org/​10.1103/​PhysRevLett.126.100501, doi:10.1103/​physrevlett.126.100501.
https:/​/​doi.org/​10.1103/​PhysRevLett.126.100501

[13] Hoi-Kwong Lo and H. F. Chau. Unconditional security of quantum key distribution over arbitrarily long distances. Science, 283(5410):2050–2056, mar 1999. URL: https:/​/​doi.org/​10.1126/​science.283.5410.2050, doi:10.1126/​science.283.5410.2050.
https:/​/​doi.org/​10.1126/​science.283.5410.2050

[14] Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, jun 2012.
https:/​/​doi.org/​10.1017/​cbo9780511976667

[15] Dimiter Ostrev. Composable, unconditionally secure message authentication without any secret key. In 2019 IEEE International Symposium on Information Theory (ISIT), pages 622–626, 2019. doi:10.1109/​ISIT.2019.8849510.
https:/​/​doi.org/​10.1109/​ISIT.2019.8849510

[16] 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. Adv. Opt. Photon., 12(4):1012–1236, Dec 2020. URL: http:/​/​opg.optica.org/​aop/​abstract.cfm?URI=aop-12-4-1012, doi:10.1364/​AOP.361502.
https:/​/​doi.org/​10.1364/​AOP.361502
http:/​/​opg.optica.org/​aop/​abstract.cfm?URI=aop-12-4-1012

[17] Christopher Portmann. Key recycling in authentication. IEEE Transactions on Information Theory, 60(7):4383–4396, 2014. doi:10.1109/​TIT.2014.2317312.
https:/​/​doi.org/​10.1109/​TIT.2014.2317312

[18] Christopher Portmann and Renato Renner. Cryptographic security of quantum key distribution, 2014. URL: https:/​/​arxiv.org/​abs/​1409.3525, doi:10.48550/​ARXIV.1409.3525.
https:/​/​doi.org/​10.48550/​ARXIV.1409.3525
arXiv:1409.3525

[19] Renato Renner. Security of Quantum Key Distribution. PhD thesis, ETH Zurich, 2005. URL: https:/​/​arxiv.org/​abs/​quant-ph/​0512258, doi:10.48550/​ARXIV.QUANT-PH/​0512258.
https:/​/​doi.org/​10.48550/​ARXIV.QUANT-PH/​0512258
arXiv:quant-ph/0512258

[20] Peter W. Shor and John Preskill. Simple proof of security of the bb84 quantum key distribution protocol. Phys. Rev. Lett., 85:441–444, Jul 2000. URL: https:/​/​link.aps.org/​doi/​10.1103/​PhysRevLett.85.441, doi:10.1103/​PhysRevLett.85.441.
https:/​/​doi.org/​10.1103/​PhysRevLett.85.441

[21] Andrew Steane. Multiple-particle interference and quantum error correction. Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences, 452(1954):2551–2577, 1996. URL: https:/​/​royalsocietypublishing.org/​doi/​abs/​10.1098/​rspa.1996.0136, doi:10.1098/​rspa.1996.0136.
https:/​/​doi.org/​10.1098/​rspa.1996.0136

[22] W. Forrest Stinespring. Positive functions on c*-algebras. Proceedings of the American Mathematical Society, 6(2):211–216, 1955. URL: http:/​/​www.jstor.org/​stable/​2032342, doi:10.2307/​2032342.
https:/​/​doi.org/​10.2307/​2032342
http:/​/​www.jstor.org/​stable/​2032342

[23] Marco Tomamichel and Anthony Leverrier. A largely self-contained and complete security proof for quantum key distribution. Quantum, 1:14, Jul 2017. URL: http:/​/​dx.doi.org/​10.22331/​q-2017-07-14-14, doi:10.22331/​q-2017-07-14-14.
https:/​/​doi.org/​10.22331/​q-2017-07-14-14

[24] Marco Tomamichel, Charles Ci Wen Lim, Nicolas Gisin, and Renato Renner. Tight finite-key analysis for quantum cryptography. Nature communications, 3(1):1–6, 2012. doi:10.1038/​ncomms1631.
https:/​/​doi.org/​10.1038/​ncomms1631

[25] Mark N. Wegman and J.Lawrence Carter. New hash functions and their use in authentication and set equality. Journal of Computer and System Sciences, 22(3):265–279, 1981. URL: https:/​/​www.sciencedirect.com/​science/​article/​pii/​0022000081900337, doi:10.1016/​0022-0000(81)90033-7.
https:/​/​doi.org/​10.1016/​0022-0000(81)90033-7
https:/​/​www.sciencedirect.com/​science/​article/​pii/​0022000081900337

[26] Juan Yin, Yu-Huai Li, Sheng-Kai Liao, Meng Yang, Yuan Cao, Liang Zhang, Ji-Gang Ren, Wen-Qi Cai, Wei-Yue Liu, Shuang-Lin Li, et al. Entanglement-based secure quantum cryptography over 1,120 kilometres. Nature, 582(7813):501–505, 2020. doi:10.1038/​s41586-020-2401-y.
https:/​/​doi.org/​10.1038/​s41586-020-2401-y

Cited by

[1] Manuel B. Santos, Paulo Mateus, and Chrysoula Vlachou, "Quantum Universally Composable Oblivious Linear Evaluation", arXiv:2204.14171, (2022).

[2] Dimiter Ostrev, Davide Orsucci, Francisco Lázaro, and Balazs Matuz, "Classical product code constructions for quantum Calderbank-Shor-Steane codes", arXiv:2209.13474, (2022).

The above citations are from SAO/NASA ADS (last updated successfully 2023-02-07 12:30:10). The list may be incomplete as not all publishers provide suitable and complete citation data.

On Crossref's cited-by service no data on citing works was found (last attempt 2023-02-07 12:30:08).