On the hardness of the Lee syndrome decoding problem

Violetta Weger; Karan Khathuria; Anna-Lena Horlemann; Massimo Battaglioni; Paolo Santini; Edoardo Persichetti

doi:10.3934/amc.2022029

Article Contents

2024, Volume 18, Issue 1: 233-266. Doi: 10.3934/amc.2022029

This issue Previous Article Reconstructing points of superelliptic curves over a prime finite field Next Article

On the hardness of the Lee syndrome decoding problem

1.
Department of Electrical and Computer Engineering, Technical University of Munich, Theresienstrasse 90, 80333, München, Germany
2.
Institute of Computer Science, University of Tartu, 51009 Tartu, Estonia
3.
School of Computer Science, University of St. Gallen, Dufourstrasse 50, CH-9000 St. Gallen, Switzerland
4.
Department of Information Engineering, Marche Polytechnic University, Via Brecce Bianche 12, 60131 Ancona, Italy
5.
Department of Mathematical Sciences, Florida Atlantic University, 777 Glades Road, Boca Raton, FL 33431, USA

^* Corresponding author: Violetta Weger
^* Corresponding author: Violetta Weger

Received: September 2021

Revised: February 2022

Early access: April 2022

Published: February 2024

Abstract / Introduction Full Text(HTML) Figure(2) / Table(2) Related Papers Cited by

Abstract

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.

Keywords:

Mathematics Subject Classification: 11T71, 94B35.

Citation:

Full Text(HTML)

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

Download: Full-size image PowerPoint slide

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

Download: Full-size image PowerPoint slide

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

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[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.
[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.
[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.
[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.
[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.
[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.
[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.