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.
Error Reconciliation based on Integer Linear Programming in Quantum Key Distribution
|
Department of Computer Engineering, Quchan University of Technology, Quchan, Iran z.eskandari@qiet.ac.ir Mohammad Rezaee Department of Computer Engineering, Quchan University of Technology, Quchan, Iran rezaee@qiet.ac.ir
Received: 14/Sep/2021 Revised: 24/Nov/2021 Accepted: 12/Dec/2021 |
|
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.
Keywords: Key reconciliation algorithm; error correction; LDPC codes; Belief Propagation; Integer Linear Programming.
1- Introduction
Quantum key distribution protocols [1,2] share a secure key between two remote parties and then establish secure communication between them using two channels; quantum channel and public channel. Quantum channel is used to carry qubits which include secret key information and after the key agreement between the two parties, Alice (A) and Bob (B), they use the secret key to establish secure communication in the public channel. It is unfortunate that the key establishment process always takes along with errors because of channel noise, device imperfection [3, 4], or the presence of eavesdropper (Eve) [5]. Thus, after transmitting the key via the quantum channel, A and B use the public channel to estimate the amount of Quantum Bit Error Rate (QBER) and correct errors in the key to establish symmetric key on both sides of the connection.
To do this, A send a key, and then at the side B, 1- the key bits are sifted, then 2- B estimates errors in sifted key bits, QBER, using the error estimation approaches [6-9]. Comparing the estimated QBER with a determined threshold, B decides that the channel is affected by channel or device noises or the presence of Eve. If QBER is higher than the determined threshold, because of the no-cloning theorem [10], it shows that Eve spoofs the connection and the key is not safe anymore. Otherwise, the next step is begun, 3- B uses a reconciliation algorithm [11-15,45-47] to correct the errors and then uses some privacy amplification methods [16,17] to remove the disclosed information along the reconciliation step.
Key reconciliation is important because using an efficient approach with minimum information leakage, in addition to increase secure key generation rate, it impacts on the security of the communication between two sides. The first error reconciliation was the BBBSS protocol [11] which uses some passes to exchange raw key subsets and check the parity of the blocks to determine and correct the errors in the subset. This approach was then improved by [12] as the Cascade algorithm. Other common approaches based on the BBBSS algorithm are Furukawa–Yamazaki [13] and Winnow protocol [14] which uses a Hamming code to reduce the number of errors.
Currently, LDPC (low-density parity check) [18] method has been widely used in this subject [15, 48, 49] as the Belief propagation algorithm (BP) [19], also known as sum-product algorithm, was used to correct the errors. This approach has attracted a lot of attention because it works more efficiently rather than others [20]. It should be mentioned in comparison to Cascade and Winnow, LDPC provides lower communication overhead and also it can reconcile errors at a higher rate than those.
Using artificial neural networks for error correction was introduced in [21]. The work uses the mutual synchronization of artificial neural networks to correct errors in the sifted key after the transmission in the quantum channel. Two sides create the neural networks based on the keys that they have. After the mutual learning process, they correct all errors and can use the key. But, this approach suffers from high processing time and source consumption so it has not been investigated in higher code length.
In this paper, we propose an efficient approach to reconcile errors in quantum keys distribution. As mentioned earlier, by comparing reconciliation efficiency of the three most common reconciliation algorithms, LDPC, Cascade and Winnow, it shows that the efficiency of the LDPC based reconciliation algorithm is superior to the two other in most of the QBERs. So, by considering this fact, we focus on LDPC codes approach. But as discussed later, the reconciliation based on the decoding of these codes suffers from lack of efficiency in codes with high code rate.
Indeed, the code rate has a direct influence on the amount of disclosed information in the reconciliation process. In higher rates that benefit from less leakage, LDPC approach or more specifically, BP decoding approach does not work with enough success. Focusing mentioned problem, in this paper, we decided to propose an approach to correct the errors in high rate codes. To do this we utilize Integer Linear Programming (ILP) approach.
It is noteworthy that the (Mixed) (Integer) Linear programming approaches have already been used to decoding the LDPC codes [22-25], but as it known, it is the first time that an Integer Linear Programming (ILP) model is utilized to reconcile the key in Quantum key distribution and more specifically key reconciliation algorithms. Furthermore, compared to mentioned works, the way we model the problem here is completely different in the number of variables and constraints which has a direct impact on the complexity of solving the ILP problem.
The rest of the paper proceeds as follows: in section 2 we review briefly the required preliminaries, LDPC coding concepts and ILP basics. In section 3, a detailed description of the proposed approach based on ILP is presented. The experimental results are evaluated, discussed and compared in section 4. Finally, section 5 concludes the work.
2- Preliminaries
In this section, we describe the basic concepts of this study. First, a brief overview of the LDPC codes is given, and then the concepts of (Mixed) (Integer) Linear Programming are discussed.
2-1- LDPC Codes
Low-density parity check (LDPC) codes were first introduced by Gallager in 1962 [18] as a method of transmitting a message over a noisy channel with error correction capability. Later, significant attentions were drawn to LDPC code due to its near-Shannon performance [26, 27]. The decoders for LDPC codes are based on Belief propagation (BP) algorithm and its variants [28-30]. However, BP decoding usually suffers from decreasing the success rate in presence of high error rates.
LDPC codes 
can be considered as a 
-dimensional subspace of 
which represented by a generator matrix 
whose rows span code 
and a parity check matrix 
whose rows span 
- i.e., 
if and only if 
, where 
. In LDPC codes, 
and 
are defined as the code and codeword length, correspondingly. The parameter 
is as code rate in range 
which defines the correcting power and efficiency.
When the sender wants to send vector 
through noisy channel, instead of sending raw data, to have correction chance, considering as generator matrix, she calculates codeword 
as
| (1) |
| (2) |
| (3)
|
| (4) |
| (5) |
| (6) |
| (7) |
| (8) |
| (9) |
| (10) |
| (11) | |||||||||||||||||||||||
|
|
| (12) |
| (13) |
| (14) |
| (15) |
|
| (16) |
|
(17) |
Parameter | Value |
Code length | 1944 |
Code rates | 0.5, 0.6777, 0.75, 0.8333 |
QBER range | [1,1.7] |
Number of random keys | 100 |
It should be mentioned that the ILP, BP and MBP approaches were implemented in Python programming language and all the experiments were done on Intel (R) core (TM) i7-9750H CPU @ 2.60 GHz with 16 GB memory.
4-1- Efficiency of LDPC-based Approach
As the most important factor in reconciliation algorithms, we can name reconciliation efficiency 
which shows the relation of the amount of information B obtains to the minimum amount of information he needs for correcting all errors that theoretically calculated. Therefore, to ensure that he can correct all errors, must be greater than or equal to 1, i.e. 
. In theory, 
happens when LDPC code tends to be infinite in length and no cycles in structure, which can reach the Shannon Limit [9]. So in practice, 
. The reconciliation efficiency which implies the efficiency and security of a reconciliation strategy, is calculated as:
| (17) |
| (18) |
