Article Contents
Article Contents

# An algorithm for generalized syndrome decoding problem

• *Corresponding author: Huimin Lao

This work was supported by the National Natural Science Foundation of China (No. 62032009), and the Guangdong Major Program of Basic and Applied Basic Research (No. 2019B030302008)

• Syndrome decoding problem has received a lot of attention due to its applications in code-based cryptography. In this paper, we study a generalization of the syndrome decoding problem. This problem was recently introduced in Khathuria, Rosenthal, and Weger's cryptosystem. We present a new algorithm for the generalized syndrome decoding problem, which is adapted from the information set decoding algorithm proposed by Finiasz and Sendrier. Furthermore, our algorithm can be severed as an attack for Khathuria, Rosenthal, and Weger's cryptosystem. New parameters of their cryptosystem are suggested for which our algorithm needs $2^{128}$ and $2^{256}$ bit operations.

Mathematics Subject Classification: Primary: 94A60, 94B35; Secondary: 14G50.

 Citation:

• Figure 1.  The complexity of our algorithm for different choices of parameters $c_t$ and $\lambda$

Table 1.  The worse case complexity for $q$ when $\lambda = 2$ and $c_n = 0.5$

 $q$ $2$ $7$ $27$ $49$ $64$ $81$ $256$ complexity $0.05972$ $0.06108$ $0.06147$ $0.06164$ $0.06172$ $0.06179$ $0.06212$

Table 2.  The security of the KRW cryptosystem against our algorithm

 $(q, n, r, t, \lambda)$ $p$ $s$ Complexity $(7, 1872, 2920,103, 2)$ $4$ $1468$ $2^{251}$ $(13, 1258, 1835,114, 2)$ $4$ $924$ $2^{251}$

Table 3.  New sets of parameters of the KRW cryptosystem that achieve 128-bit security level

 $k/n$ $q$ $m$ $\lambda$ $n$ $k$ Public key Size (Bits) 0.75 7 4 2 829 622 1929367 0.85 7 4 2 825 701 1599451 0.75 7 7 3 1025 769 6454491 0.85 7 7 3 907 771 4727832 0.75 16 4 2 799 599 2553568 0.85 16 4 2 802 682 2158080

Table 4.  New sets of parameters of the KRW cryptosystem that} {achieve 256-bit security level

 $k/n$ $q$ $m$ $\lambda$ $n$ $k$ Public key Size (Bits) 0.75 7 4 2 1764 1323 8735635 0.85 7 4 2 1741 1480 7145482 0.75 7 7 3 2246 1685 30989821 0.85 7 7 3 1979 1682 22482084 0.75 16 4 2 1750 1313 12249984 0.85 16 4 2 1723 1465 9964992
•  [1] N. Aragon, P. Barreto, S. Bettaieb, O. Blazy, P. Gaborit, S. Gueron, C. A. Melchor, R. Misoczki, E. Persichetti and G. Zémor, Bike: Bit flipping key encapsulation, https://bikesuite.org/. [2] A. Becker, A. Joux, A. May and A. Meurer, Decoding random binary linear codes in $2^{n/20}$: How 1+1 = 0 improves information set decoding, in Advances in Cryptology - EUROCRYPT, Springer, 2012,520-536. doi: 10.1007/978-3-642-29011-4_31. [3] E. Berlekamp, R. McEliece and H. van Tilborg, On the inherent intractability of certain coding problems (corresp.), IEEE Transactions on Information Theory, 24 (1978), 384-386.  doi: 10.1109/tit.1978.1055873. [4] D. J. Bernstein, T. Chou, T. Lange, I. von Maurich, R. Misoczki, R. Niederhagen, E. Persichetti, C. Peters, P. Schwabe, N. Sendrier et al., Classic mceliece: Conservative code-based cryptography, NIST Submissions, https://classic.mceliece.org/. [5] D. J. Bernstein, T. Lange and C. Peters, Smaller decoding exponents: Ball-collision decoding, in Advances in Cryptology - CRYPTO 2011, vol. 6841, Springer, Berlin, Heidelberg, 2011,743-760. doi: 10.1007/978-3-642-22792-9_42. [6] L. Both and A. May, Optimizing BJMM with nearest neighbors: Full decoding in $2^{2n/21}$ and McEliece security, in WCC Workshop on Coding and Cryptography, 2017,214. [7] L. Both and A. May, Decoding linear codes with high error rate and its impact for LPN security, in Post-Quantum Cryptography (eds. T. Lange and R. Steinwandt), Lecture Notes in Computer Science, Springer, Cham, 2018, 25-46. doi: 10.1007/978-3-319-79063-3_2. [8] R. Bricout, A. Chailloux, T. Debris-Alazard and M. Lequesne, Ternary syndrome decoding with large weight, in Selected Areas in Cryptography - SAC 2019 (eds. K. G. Paterson and D. Stebila), Lecture Notes in Computer Science, Springer, 2020,437-466. [9] A. Chailloux, T. Debris-Alazard and S. Etinski, Classical and quantum algorithms for generic syndrome decoding problems and applications to the Lee metric, in International Conference on Post-Quantum Cryptography, Springer, 2021, 44-62. doi: 10.1007/978-3-030-81293-5_3. [10] J. T. Coffey and R. M. Goodman, The complexity of information set decoding, IEEE Transactions on Information Theory, 36 (1990), 1031-1037.  doi: 10.1109/18.57202. [11] C. Cooper, On the distribution of rank of a random matrix over a finite field, Random Structures & Algorithms, 17 (2000), 197-212.  doi: 10.1002/1098-2418(200010/12)17:3/4<197::AID-RSA2>3.0.CO;2-K. [12] A. Couvreur and M. Lequesne, On the security of subspace subcodes of reed–solomon codes for public key encryption, IEEE Transactions on Information Theory, 68 (2021), 632-648.  doi: 10.1109/TIT.2021.3120440. [13] A. Couvreur, A. Otmani and J.-P. Tillich, Polynomial time attack on wild mceliece over quadratic extensions, IEEE Transactions on Information Theory, 63 (2017), 404-427.  doi: 10.1109/TIT.2016.2574841. [14] T. Debris-Alazard, N. Sendrier and J.-P. Tillich, Wave: A new family of trapdoor one-way preimage sampleable functions based on codes, in Advances in Cryptology - ASIACRYPT, Springer, 2019, 21-51. doi: 10.1007/978-3-030-34578-5_2. [15] I. Dumer, On minimum distance decoding of linear codes, in Proc. 5th Joint Soviet-Swedish Int. Workshop Inform. Theory, 1991, 50-52. [16] J.-C. Faugère, L. Perret and F. de Portzamparc, Algebraic attack against variants of mceliece with goppa polynomial of a special form, in International Conference on the Theory and Application of Cryptology and Information Security, Springer, 2014, 21-41. doi: 10.1007/978-3-662-45611-8_2. [17] M. Finiasz and N. Sendrier, Security bounds for the design of code-based cryptosystems, in Advances in Cryptology - ASIACRYPT 2009 (ed. M. Matsui), Lecture Notes in Computer Science, Springer, Berlin, Heidelberg, 2009, 88-105. doi: 10.1007/978-3-642-10366-7_6. [18] C. T. Gueye, J. B. Klamti and S. Hirose, Generalization of BJMM-ISD using May-Ozerov nearest neighbor algorithm over an arbitrary finite field $\mathbb{F}_{q}$, in International Conference on Codes, Cryptology, and Information Security, Springer, 2017, 96-109. doi: 10.1007/978-3-319-55589-8. [19] S. Hirose, May-ozerov algorithm for nearest-neighbor problem over $\mathbb{F}_{q}$ and its application to information set decoding, in Innovative Security Solutions for Information Technology and Communications (eds. I. Bica and R. Reyhanitabar), Lecture Notes in Computer Science, Springer, 2016. [20] C. Interlando, K. Khathuria, N. Rohrer, J. Rosenthal and V. Weger, Generalization of the ball-collision algorithm, Journal of Algebra Combinatorics Discrete Structures and Applications, 7 (2020), 195-207.  doi: 10.13069/jacodesmath.729477. [21] K. Khathuria, J. Rosenthal and V. Weger, Encryption scheme based on expanded Reed-Solomon codes, Advances in Mathematics of Communications, 15 (2021), 207-218.  doi: 10.3934/amc.2020053. [22] P. J. Lee and E. F. Brickell, An observation on the security of McEliece's public-key cryptosystem, in Advances in Cryptology - EUROCRYPT 1988, Springer, 1988,275-280. doi: 10.1007/3-540-45961-8_25. [23] J. S. Leon, A probabilistic algorithm for computing minimum weights of large error-correcting codes, IEEE Transactions on Information Theory, 34 (1988), 1354-1359.  doi: 10.1109/18.21270. [24] A. May, A. Meurer and E. Thomae, Decoding random linear codes in $\widetilde{O}(2^{0.054n})$, in Advances in Cryptology - ASIACRYPT, Springer, 2011,107-124. doi: 10.1007/978-3-642-25385-0_6. [25] A. May and I. Ozerov, On computing nearest neighbors with applications to decoding of binary linear codes, in Advances in Cryptology - EUROCRYPT 2015 (eds. E. Oswald and M. Fischlin), vol. 9056, Springer, 2015,203-228. doi: 10.1007/978-3-662-46800-5_9. [26] R. McEliece, A public-key cryptosystem based on algebraic coding theory, IEEE Transactions on Information Theory, 114-116. [27] C. A. Melchor, N. Aragon, S. Bettaieb, L. Bidoux, O. Blazy, J.-C. Deneuville, P. Gaborit, E. Persichetti, G. Zémor and I. Bourges, Hamming quasi-cyclic (hqc), NIST Submission for Post-Quantum Cryptography, http://pqc-hqc.org/. [28] H. Niederreiter, Knapsack-type cryptosystems and algebraic coding theory, Problems Control Information Theory, 15 (1986), 157-166. [29] R. Overbeck and N. Sendrier, Code-based cryptography, in Post-quantum Cryptography, Springer, 2009, 95-145. doi: 10.1007/978-3-540-88702-7_4. [30] C. Peters, Information set decoding for linear codes over $\mathbb{F}_{q}$, in International Workshop on Post-Quantum Cryptography, Springer, 2010, 81-94. doi: 10.1007/978-3-642-12929-2_7. [31] E. Prange, The use of information sets in decoding cyclic codes, IRE Transactions on Information Theory, 8 (1962), 5-9.  doi: 10.1109/tit.1962.1057777. [32] P. W. Shor, Algorithms for quantum computation: Discrete logarithms and factoring, in Proceedings 35th Annual Symposium on Foundations of Computer Science, IEEE, 1994,124-134. doi: 10.1109/SFCS.1994.365700. [33] J. Stern, A method for finding codewords of small weight, in International Colloquium on Coding Theory and Applications, Springer, 1988,106-113. doi: 10.1007/BFb0019850. [34] J. Stern, A new identification scheme based on syndrome decoding, in Advances in Cryptology - CRYPTO 1993, Springer, 1993, 13-21. doi: 10.1007/3-540-48329-2_2. [35] R. C. Torres, Asymptotic analysis of ISD algorithms for the q-ary case, in Proceedings of the Tenth International Workshop on Coding and Cryptography WCC 2017, 2017,224.

Figures(1)

Tables(4)