Article Contents
Article Contents
Early Access

Early Access articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Early Access publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Early Access articles via the “Early Access” tab for the selected journal.

# On the hardness of the Lee syndrome decoding problem

• * Corresponding author: Violetta Weger
• In this paper we study the hardness of the syndrome decoding problem over finite rings endowed with the Lee metric. We first prove that the decisional version of the problem is NP-complete, by a reduction from the $3$-dimensional matching problem. Then, we study the complexity of solving the problem, by translating the best known solvers in the Hamming metric over finite fields to the Lee metric over finite rings, as well as proposing some novel solutions. For the analyzed algorithms, we assess the computational complexity in the asymptotic regime and compare it to the corresponding algorithms in the Hamming metric.

Mathematics Subject Classification: 11T71, 94B35.

 Citation:

• Figure 1.  Illustration of the error vectors at each level of the representation technique algorithm for two levels. At each level, the striped region represents the overlapping part

Figure 2.  Comparing asymptotic complexity of different algorithms for different values of $\lambda$. The values are calculated for $q = 7^2$

Table 1.  Comparison of the asymptotic complexity of all the algorithms at rate $R^* = {\rm{argmax}} _{0 \leq R \leq 1} \left( e(R,q) \right)$. The values are calculated for $q = 7^2$

 $\lambda = 1$ $\lambda = 0.75$ $\lambda = 0.5$ $R^*$ $e(R^*,q)$ $R^*$ $e(R^*,q)$ $R^*$ $e(R^*,q)$ Two-Blocks 0.3886 0.0913 0.4473 0.0978 0.4694 0.1211 $s$-Blocks 0.3969 0.1030 0.3441 0.0745 0.3441 0.07453 Wagner $a=1$ 0.3925 0.0897 0.4473 0.0978 0.4694 0.1211 Wagner $a=2$ 0.3925 0.0897 0.4473 0.0978 0.4694 0.1211 Rep. tech. $a=1$ 0.3896 0.0998 0.4288 0.1155 0.4648 0.1457 Rep. tech. $a=2$ 0.3922 0.1012 0.4275 0.1221 0.4757 0.1557 BJMM level 2 0.4414 0.07440 0.4587 0.0954 0.4801 0.1178 BJMM level 3 0.3921 0.1012 0.4282 0.1220 0.4754 0.1554

Table 2.  Comparison with Hamming metric for $q = 4$ and $\lambda = 1$. The values for Hamming metric ISD algorithms BJMM-MO and Stern are from [20,Table 3] and [21,Table 1], respectively

 $e(R^*,q)$ Lee Metric Prange 0.0575 $s$-Blocks 0.0575 Two-Blocks 0.0556 Wagner $a=1$ 0.0556 Rep. tech. $a=1$ 0.0569 Rep. tech. $a=2$ 0.0571 BJMM level 2 0.05265 BJMM level 3 0.0557 Hamming Metric BJMM-MO 0.04294 Stern 0.04987 Prange 0.05095
•  [1] M. Abramson, Restricted combinations and compositions, Fibonacci Quart., 14 (1976), 439-452. [2] H. Astola and I. Tabus, Bounds on the size of Lee-codes, 2013 8th International Symposium on Image and Signal Processing and Analysis (ISPA), (2013), 471–476. doi: 10.1109/ISPA.2013.6703787. doi: 10.1109/ISPA.2013.6703787. [3] J. Astola, On the asymptotic behaviour of Lee-codes, Discrete Applied Mathematics, 8 (1984), 13-23.  doi: 10.1016/0166-218X(84)90074-X. [4] M. Baldi, A. Barenghi, F. Chiaraluce, G. Pelosi and P. Santini, A finite regime analysis of information set decoding algorithms, Algorithms, 12 (2019), Paper No. 209, 34 pp. doi: 10.3390/a12100209. doi: 10.3390/a12100209. [5] S. Barg, Some new NP-complete coding problems, Problemy Peredachi Informatsii, 30 (1994), 23-28. [6] 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, Advances in Cryptology–EUROCRYPT 2012, Lecture Notes in Comput. Sci., Springer, Heidelberg, 7237 (2012), 520-536.  doi: 10.1007/978-3-642-29011-4_31. [7] E. Berlekamp, Algebraic Coding Theory, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1968. [8] E. R. Berlekamp, R. J. McEliece and H. C. A. van Tilborg, On the inherent intractability of certain coding problems, IEEE Trans. on Inf. Theory, 24 (1978), 384-386.  doi: 10.1109/tit.1978.1055873. [9] D. J. Bernstein, T. Lange and C. Peters, Smaller decoding exponents: Ball-collision decoding, Advances in Cryptology—CRYPTO 2011, Lecture Notes in Comput. Sci., Springer, Heidelberg, 6841 (2011), 743-760.  doi: 10.1007/978-3-642-22792-9_42. [10] E. Byrne, A.-L. Horlemann, K. Khathuria and V. Weger, Density of free modules over finite chain rings, preprint, (2021), arXiv: 2106.09403. [11] A. Canteaut and F. Chabaud, A new algorithm for finding minimum-weight words in a linear code: Application to McEliece's cryptosystem and to narrow-sense BCH codes of length 511, IEEE Trans. on Inf. Theory, 44 (1998), 367-378.  doi: 10.1109/18.651067. [12] A. Canteaut and N. Sendrier, Cryptanalysis of the original McEliece cryptosystem, Advances in Cryptology–ASIACRYPT'98 (Beijing), Lecture Notes in Comput. Sci., Springer, Berlin, 1514 (1998), 187-199.  doi: 10.1007/3-540-49649-1_16. [13] F. Chabaud, Asymptotic analysis of probabilistic algorithms for finding short codewords, Eurocode '92 (Udine, 1992), CISM Courses and Lect., Springer, Vienna, 339 (1993), 175-183. [14] A. Chailloux, T. Debris-Alazard and S. Etinski, Classical and quantum algorithms for generic syndrome decoding problems and applications to the Lee metric, Post-Quantum Cryptography, Lecture Notes in Comput. Sci., Springer, Cham, 12841 (2021), 44–62, arXiv: 2104.12810. doi: 10.1007/978-3-030-81293-5_3. doi: 10.1007/978-3-030-81293-5_3. [15] L. Chen, Y.-K. Liu, S. Jordan, D. Moody, R. Peralta, R. Perlner and D. Smith-Tone, Report on Post-Quantum Cryptography, Technical Report NISTIR 8105, National Institute of Standards and Technology, 2016. doi: 10.6028/NIST.IR.8105. doi: 10.6028/NIST.IR.8105. [16] A. Fiat and A. Shamir, How to prove yourself: Practical solutions to identification and signature problems, Advances in Cryptology—CRYPTO '86 (Santa Barbara, Calif., 1986), Lecture Notes in Comput. Sci., Springer, Berlin, 263 (1987), 186-194.  doi: 10.1007/3-540-47721-7_12. [17] M. Finiasz and N. Sendrier, Security bounds for the design of code-based cryptosystems, International Conference on the Theory and Application of Cryptology and Information Security, (2009), 88-105.  doi: 10.1007/978-3-642-10366-7_6. [18] P. Gaborit and G. Zémor, On the hardness of the decoding and the minimum distance problems for rank codes, IEEE Trans. on Inf. Theory, 62 (2016), 7245-7252.  doi: 10.1109/TIT.2016.2616127. [19] D. Gardy and P. Solé, Saddle point techniques in asymptotic coding theory, Algebraic Coding (Paris, 1991), Lecture Notes in Comput. Sci., Springer, Berlin, 573 (1992), 75-81.  doi: 10.1007/BFb0034343. [20] 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$, Codes, Cryptology and Information Security, Lecture Notes in Comput. Sci., Springer, Cham, 10194 (2017), 96-109.  doi: 10.1007/978-3-319-55589-8. [21] S. Hirose, May-Ozerov algorithm for nearest-neighbor problem over $\mathbb{F}_q$ and its application to information set decoding, International Conference for Information Technology and Communications, (2016), 115-126. [22] A.-L. Horlemann-Trautmann and V. Weger, Information set decoding in the Lee metric with applications to cryptography, Adv. Math. Commun., 15 (2021), 677.  doi: 10.3934/amc.2020089. [23] Wolfram Research, Inc., Mathematica, Version 12.3.1., Champaign, IL, 2021. [24] C. Interlando, K. Khathuria, N. Rohrer, J. Rosenthal and V. Weger, Generalization of the ball-collision algorithm, J. Algebra Comb. Discrete Struct. Appl., 7 (2020), 195-207.  doi: 10.13069/jacodesmath.729477. [25] C. Y. Lee, Some properties of nonbinary error-correcting codes, IRE Trans. Inf. Theory, IT-4 (1958), 77-82.  doi: 10.1109/tit.1958.1057446. [26] P. J. Lee and E. F. Brickell, An observation on the security of McEliece's public-key cryptosystem, Advances in Cryptology—EUROCRYPT '88 (Davos, 1988), Lecture Notes in Comput. Sci., Springer, Berlin, 330 (1988), 275-280.  doi: 10.1007/3-540-45961-8_25. [27] J. S. Leon, A probabilistic algorithm for computing minimum weights of large error-correcting codes, IEEE Trans. on Inf. Theory, 34 (1988), part 2, 1354–1359. doi: 10.1109/18.21270. doi: 10.1109/18.21270. [28] A. May, A. Meurer and E. Thomae, Decoding random linear codes in $\tilde{\mathcal{O}}(2^{0.054 n})$, Advances in Cryptology—ASIACRYPT 2011, Lecture Notes in Comput. Sci., Springer, Heidelberg, 7073 (2011), 107-124.  doi: 10.1007/978-3-642-25385-0_6. [29] R. McEliece, A public-key cryptosystem based on algebraic coding theory, DSN Progress Report, (1978), 114-116. [30] A. Meurer, A Coding-Theoretic Approach to Cryptanalysis, PhD thesis, Ruhr Universität Bochum, 2013. [31] R. Niebuhr, E. Persichetti, P.-L. Cayrel, S. Bulygin and J. Buchmann, On lower bounds for information set decoding over $\mathbb{F}_q$ and on the effect of partial knowledge, Int. J. Inf. Coding Theory, 4 (2017), 47-78.  doi: 10.1504/IJICOT.2017.081458. [32] H. Niederreiter, Knapsack-type cryptosystems and algebraic coding theory, Problems Control Inform. Theory/Problemy Upravlen. Teor. Inform., 15 (1986), 159-166. [33] C. Peters, Information-set decoding for linear codes over $\mathbb{F}_q$, Post-Quantum Cryptography, Lecture Notes in Comput. Sci., Springer, Berlin, 6061 (2010), 81-94.  doi: 10.1007/978-3-642-12929-2_7. [34] E. Prange, The use of information sets in decoding cyclic codes, IRE Trans. Inf. Theory, IT-8 (1962), 5-9.  doi: 10.1109/tit.1962.1057777. [35] S. Puchinger, J. Renner and J. Rosenkilde, Generic decoding in the sum-rank metric, 2020 IEEE International Symposium on Information Theory (ISIT), (2020), 54–59. [36] P. Santini, M. Battaglioni, F. Chiaraluce, M. Baldi and E. Persichetti, Low-Lee-density parity-check codes, ICC 2020 - 2020 IEEE International Conference on Communications (ICC), (2020), 1–6. [37] J. Stern, A method for finding codewords of small weight, Coding theory and applications (Toulon, 1988), Lecture Notes in Comput. Sci., Springer, New York, 388 (1989), 106-113.  doi: 10.1007/BFb0019850. [38] J. Stern, A new identification scheme based on syndrome decoding, Advances in Cryptology–CRYPTO' 93, (1994), 13–21. doi: 10.1007/3-540-48329-2_2. doi: 10.1007/3-540-48329-2_2. [39] The Sage Developers, SageMath, the Sage Mathematics Software System (Version 8.4), 2018, https://www.sagemath.org. [40] W. Ulrich, Non-binary error correction codes, The Bell System Technical Journal, 36 (1957), 1341-1388. [41] D. Wagner, A generalized birthday problem, Advances in Cryptology—CRYPTO 2002, Lecture Notes in Comput. Sci., Springer, Berlin, 2442 (2002), 288-303.  doi: 10.1007/3-540-45708-9_19.

Figures(2)

Tables(2)