Error Reconciliation based on Integer Linear Programming in Quantum Key Distribution
Subject Areas : Communication Systems & Deviceszahra eskandari 1 , mohammad rezaee 2
1 - Department of computer engineering, Quchan University of Technology,iran
2 - Department of computer engineering, Quchan University of Technology,iran
Keywords: Key reconciliation algorithm, error correction, LDPC codes, Belief Propagation, Integer Linear Programming,
Abstract :
Quantum telecommunication has received a lot of attention today by providing unconditional security because of the inherent nature of quantum channels based on the no-cloning theorem. In this mode of communication, first, the key is sent through a quantum channel that is resistant to eavesdropping, and then secure communication is established using the exchanged key. Due to the inevitability of noise, the received key needs to be distilled. One of the vital steps in key distillation is named key reconciliation which corrects the occurred errors in the key. Different solutions have been presented for this issue, with different efficiency and success rate. One of the most notable works is LDPC decoding which has higher efficiency compared to the others, but unfortunately, this method does not work well in the codes with a high rate. In this paper, we present an approach to correct the errors in the high rate LDPC code-based reconciliation algorithm. The proposed algorithm utilizes Integer Linear Programming to model the error correction problem to an optimization problem and solve it. Testing the proposed approach through simulation, we show it has high efficiency in high rate LDPC codes as well as a higher success rate compared with the LDPC decoding method - belief propagation – in a reasonable time.
[1] N. Gisin, G. Ribordy, W. Tittel, and H. Zbinden, “Quantum cryptography,” Rev. Mod. Phys. 74(1), 145–195 (2002).
[2] V. Scarani, H. Bechmann-Pasquinucci, N. J. Cerf, M. Dušek, N. Lütkenhaus, and M. Peev, “The security of practical quantum key distribution,” Rev. Mod. Phys. 81(3), 1301–1350 (2009).
[3] H. Weier, H. Krauss, M. Rau, M. Fuerst, S. Nauerth, and H. Weinfurter, “Quantum eavesdropping without interception: an attack exploiting the dead time of single photon detectors,” New J. Phys. 13(7), 073024 (2011).
[4] N. Jain, C. Wittmann, L. Lydersen, C. Wiechers, D. Elser, C. Marquardt, V. Makarov, and G. Leuchs, “Device calibration impacts security of quantum key distribution,” Phys. Rev. Lett. 107(11), 110501 (2011).
[5] C. H. Bennet and G. Brassard, “Quantum cryptography: public key distribution and coin tossing,” in Proceedings of the IEEE International Conference on Computers Systems and Signal Processing (IEEE, 1984), pp. 175–179.
[6] X.B. Wang, “Beating the photon-number-splitting attack in practical quantum cryptography,” Phys. Rev. Lett. 94(23), 230503 (2005).
[7] P. Treeviriyanupab, T. Phromsaard, C.M. Zhang, M. Li, P. Sangwongngam, T. S. N. Ayutaya, N. Songneam, R. Rattanatamma, C. Ingkavet, W. Sanor, W. Chen, Z.F. Han, and K. Sripimanwat, “Rate-adaptive reconciliation and its estimator for quantum bit error rate,” in Proceedings of International Symposium on Communications and Information Technologies (IEEE, 2014), pp. 351–355.
[8] C. Gao, J. Dong, G. Yu, L. Chen, Multi-matrix error estimation and reconciliation for quantum key distribution. Optics Express. (2019). 27. 14545. 10.1364/OE.27.014545.
[9] C. Gao, Y. Guo, D. Jiang, L. Chen, Multi-matrix rate-compatible reconciliation for quantum key distribution. ArXiv(2020)., abs/2001.01074.
[10] Wootters, W.K., Zurek, W.H.: A single quantum cannot be cloned. Nature 299, 802–803 (1982).
[11] Bennett, C.H., Bessette, F., Brassard, G., Salvail, L., Smolin, J.: Experimental quantum cryptography. J. Cryptol. 5, 3–28 (1992).
[12] Brassard, G., Salvail, L.: Secret-Key Reconciliation by Public Discussion, pp. 410–423. Springer, Berlin (1994).
[13] Furukawa, E., Yamazaki, K.: Application of existing perfect code to secret key reconciliation. In: Proceedings of International Symposium on Communication and Information Technologies, pp. 397– 400 (2001).
[14] Buttler, W.T., Lamoreaux, S.K., Torgerson, J.R., Nickel, G.H., Donahue, C.H., Peterson, C.G.: Fast, efficient error reconciliation for quantum cryptography. Phys. Rev. A 67, 052303 (2003).
[15] E. Kiktenko, A. Malyshev, A. Bozhedarov, N. Pozhar, M. Anufriev, and A. Fedorov, “Error estimation at the information reconciliation stage of quantum key distribution,” J. Russ. Laser Res. 39(6), 558–567 (2018).
[16] C. H. Bennett, G. Brassard, and J.M. Robert, “Privacy amplification by public discussion,” SIAM J. Comput. 17(2), 210–229 (1988).
[17] C. H. Bennett, G. Brassard, C. Crepeau, and U. M. Maurer, “Generalized privacy amplification,” IEEE Trans. Inf. Theory 41(6), 1915–1923 (1995).
[18] R. G. Gallager, Low Density Parity-Check Codes. MIT Press, Cambridge, MA, 1963.
[19] S. Chung, T. J. Richardson, and R. L. Urbanke, “Analysis of sum-product decoding of low-density parity-check codes using a Gaussian approximation,” IEEE Trans. Inf. Theory 47(2), 657–670 (2001).
[20] Mehic M., Niemiec M., Siljak H., Voznak M. (2020) Error Reconciliation in Quantum Key Distribution Protocols. In: Ulidowski I., Lanese I., Schultz U., Ferreira C. (eds) Reversible Computation: Extending Horizons of Computing. RC 2020. Lecture Notes in Computer Science, vol 12070. Springer, Cham.
[21] Niemiec, M. Error correction in quantum cryptography based on artificial neural networks. Quantum Inf Process 18, 174 (2019). https://doi.org/10.1007/s11128-019-2296-4.
[22] J. Feldman, "Decoding Error-Correcting Codes via Linear Programming". PhD thesis, M.I.T., Cambridge, MA, 2003.
[23] K. Yang, X. Wang, and J. Feldman, “A new linear programming approach to decoding linear block codes,” IEEE Trans. Inf. Theory, vol. 54, no. 3, pp. 1061–1072, Mar. 2008.
[24] H. Wei and A. H. Banihashemi, “An iterative check polytope projec tion algorithm for ADMM-based LP decoding of LDPC codes,” IEEE Commun. Lett., vol. 22, no. 1, pp. 29–32, Jan. 2018.
[25] J. Bai, Y. C, Wang, and F. C. M. Lau, “Minimum-polytope-based linear programming decoder for LDPC Codes via ADMM approach”, IEEE Wireless Commun. Lett., vol. 8, no. 4, pp. 1032-1035, Aug. 2019.
[26] D. J. C. MacKay and R. M. Neal, “Good codes based on very sparse matrices,” in Cryptography and Coding, ser. Lecture Notes in Computer Science, C. Boyd, Ed. Heidelberg/Berlin: Springer, 1995, vol. 1025, pp. 100-111.
[27] D. J. C. MacKay and R. M. Neal, “Near Shannon-limit performance of low density parity check codes,” Electron. Lett., vol. 33, no. 6, pp. 457- 458, Mar. 1997.
[28] F. R. Kschischang, B. J. Frey, and H. A. Loeliger, “Factor graphs and the sum-product algorithm,” IEEE Trans. Inf. Theory, vol. 47, no. 2, pp. 498-519, Feb. 2001. 16.
[29] W. Ryan and S. Lin, Channel Codes: Classical and Modern. Cambridge University Press, 2009.
[30] T. Richardson and R. Urbanke, Modern Coding Theory. Cambridge University Press, 2008.
[31] R. M. Tanner, “A recursive approach to low complexity codes,” IEEE Trans. Inf. Theory 27(5), 533–547 (1981).
[32] L. A. Wolsey and G. L. Nemhauser: Integer and Combinatorial Optimization Wiley-Interscience, November 1999.
[33] Clovis C. Gonzaga, On the Complexity of Linear Programming, Resenhas IME-USP 1995, Vol. 2, No. 2, 197-207.
[34] EgonBalas, Sebastián Ceria, Gérard Cornuéjols: A lift-and-project cutting plane algorithm for mixed 0–1 programs, Mathematical Programming, Volume 58, January 1993, pp 295-324.
[35] H. Land , A. G. Doig, An Automatic Method of Solving Discrete Linear Programming Problems, July 1960, Econometrica 28(3):497-520.
[36] Ralph Gomory, Outline of an Algorithm for Integer Solutions to Linear Programs, September 1958, Bulletin of the American Mathematical Society 64(5):275-278.
[37] Pritchard, D., Chakrabarty, D. Approximability of Sparse Integer Programs. Algorithmica 61, 75–93 (2011). https://doi.org/10.1007/s00453-010-9431-z.
[38]Andres Iroume, SPARSITY IN INTEGER PROGRAMMING. PhD thesis, Georgia Institute of Technology, 2017.
[39] Koutecký, Martin; Levin, Asaf; Onn, Shmuel (2018). A Parameterized Strongly Polynomial Algorithm for Block Structured Integer Programs. Michael Wagner: 14 pages. arXiv:1802.05859. doi:10.4230/LIPICS.ICALP.2018.85. S2CID 3336201.
[40]www.ibm.com/software/commerce/optimization/cplex-optimizer/.
[41] www.gurobi.com/,
[42] J. Borghoff, Mixed-integer Linear Programming in the Analysis of Trivium and Ktantan, IACR Cryptol. ePrint Arch. 2012.
[43] EEE Standard for Information Technology—Local and Metropoli tan Area Networks—Specific Requirements—Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Spec ifications Amendment 5: Enhancements for Higher Throughput, IEEE Standard 802.11n-2009, Oct. 2009.
[44] Elkouss, D., Martinez-Mateo, J. & Martin, V. Untainted Puncturing for Irregular Low-Density Parity-Check Codes. IEEE Wireless Communications Letters 1, 585–588 (2012).
[45] Guo, D., He, C., Guo, T. et al. Comprehensive high-speed reconciliation for continuous-variable quantum key distribution. Quantum Inf Process 19, 320 (2020).
[46] E. O. Kiktenko, A. O. Malyshev and A. K. Fedorov, "Blind Information Reconciliation With Polar Codes for Quantum Key Distribution," in IEEE Communications Letters, vol. 25, no. 1, pp. 79-83, Jan. 2021.
[47] Liu, Z., Wu, Z. & Huang, A. Blind information reconciliation with variable step sizes for quantum key distribution. Sci Rep 10, 171 (2020). https://doi.org/10.1038/s41598-019-56637-y.
[48] K. Zhang, X. -Q. Jiang, Y. Feng, R. Qiu and E. Bai, "High Efficiency Continuous-Variable Quantum Key Distribution Based on Quasi-Cyclic LDPC Codes," 2020 5th International Conference on Communication, Image and Signal Processing (CCISP), 2020, pp. 38-42, doi: 10.1109/CCISP51026.2020.9273490.
[49] B. Bilash, B. K. Park, C. Hoon Park and S. -W. Han, "Error-Correction Method Based on LDPC for Quantum Key Distribution Systems," 2020 International Conference on Information and Communication Technology Convergence (ICTC), 2020, pp. 151-153, doi: 10.1109/ICTC49870.2020.9289451.
[50] Georgios Papachristoudis, John W. Fisher, Adaptive Belief Propagation, 32th International Conference on Machine Learning, Lille, France, 2015. JMLR: W&CP volume 37.
[51] Daniel Lokshtanov, New Methods in Parameterized Algorithms and Complexity, Dissertation for the degree of Philosophiae Doctor (PhD) University of Bergen Norway April 2009.
