• Previous Article
    Optimal data placements for triple replication in distributed storage systems
  • AMC Home
  • This Issue
  • Next Article
    On the linear complexity and autocorrelation of generalized cyclotomic binary sequences with period $ 4p^n $
doi: 10.3934/amc.2022029
Online First

Online First 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). Online First publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Online First articles via the “Online First” tab for the selected journal.

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

Received  September 2021 Revised  February 2022 Early access April 2022

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.

Citation: Violetta Weger, Karan Khathuria, Anna-Lena Horlemann, Massimo Battaglioni, Paolo Santini, Edoardo Persichetti. On the hardness of the Lee syndrome decoding problem. Advances in Mathematics of Communications, doi: 10.3934/amc.2022029
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. BeckerA. JouxA. 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. BerlekampR. 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. BernsteinT. 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. GueyeJ. 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. InterlandoK. KhathuriaN. RohrerJ. 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. MayA. 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. NiebuhrE. PersichettiP.-L. CayrelS. 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.

show all references

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. BeckerA. JouxA. 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. BerlekampR. 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. BernsteinT. 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. GueyeJ. 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. InterlandoK. KhathuriaN. RohrerJ. 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. MayA. 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. NiebuhrE. PersichettiP.-L. CayrelS. 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.

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
$ \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
$ 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]

Anna-Lena Horlemann-Trautmann, Violetta Weger. Information set decoding in the Lee metric with applications to cryptography. Advances in Mathematics of Communications, 2021, 15 (4) : 677-699. doi: 10.3934/amc.2020089

[2]

Irene I. Bouw, Sabine Kampf. Syndrome decoding for Hermite codes with a Sugiyama-type algorithm. Advances in Mathematics of Communications, 2012, 6 (4) : 419-442. doi: 10.3934/amc.2012.6.419

[3]

Kwankyu Lee. Decoding of differential AG codes. Advances in Mathematics of Communications, 2016, 10 (2) : 307-319. doi: 10.3934/amc.2016007

[4]

Jonas Eriksson. A weight-based characterization of the set of correctable error patterns under list-of-2 decoding. Advances in Mathematics of Communications, 2007, 1 (3) : 331-356. doi: 10.3934/amc.2007.1.331

[5]

Elisa Gorla, Felice Manganiello, Joachim Rosenthal. An algebraic approach for decoding spread codes. Advances in Mathematics of Communications, 2012, 6 (4) : 443-466. doi: 10.3934/amc.2012.6.443

[6]

Washiela Fish, Jennifer D. Key, Eric Mwambene. Partial permutation decoding for simplex codes. Advances in Mathematics of Communications, 2012, 6 (4) : 505-516. doi: 10.3934/amc.2012.6.505

[7]

Alexander Barg, Arya Mazumdar, Gilles Zémor. Weight distribution and decoding of codes on hypergraphs. Advances in Mathematics of Communications, 2008, 2 (4) : 433-450. doi: 10.3934/amc.2008.2.433

[8]

Terasan Niyomsataya, Ali Miri, Monica Nevins. Decoding affine reflection group codes with trellises. Advances in Mathematics of Communications, 2012, 6 (4) : 385-400. doi: 10.3934/amc.2012.6.385

[9]

Heide Gluesing-Luerssen, Uwe Helmke, José Ignacio Iglesias Curto. Algebraic decoding for doubly cyclic convolutional codes. Advances in Mathematics of Communications, 2010, 4 (1) : 83-99. doi: 10.3934/amc.2010.4.83

[10]

Robert F. Bailey, John N. Bray. Decoding the Mathieu group M12. Advances in Mathematics of Communications, 2007, 1 (4) : 477-487. doi: 10.3934/amc.2007.1.477

[11]

Hannes Bartz, Antonia Wachter-Zeh. Efficient decoding of interleaved subspace and Gabidulin codes beyond their unique decoding radius using Gröbner bases. Advances in Mathematics of Communications, 2018, 12 (4) : 773-804. doi: 10.3934/amc.2018046

[12]

Joan-Josep Climent, Diego Napp, Raquel Pinto, Rita Simões. Decoding of $2$D convolutional codes over an erasure channel. Advances in Mathematics of Communications, 2016, 10 (1) : 179-193. doi: 10.3934/amc.2016.10.179

[13]

Johan Rosenkilde. Power decoding Reed-Solomon codes up to the Johnson radius. Advances in Mathematics of Communications, 2018, 12 (1) : 81-106. doi: 10.3934/amc.2018005

[14]

Ahmed S. Mansour, Holger Boche, Rafael F. Schaefer. The secrecy capacity of the arbitrarily varying wiretap channel under list decoding. Advances in Mathematics of Communications, 2019, 13 (1) : 11-39. doi: 10.3934/amc.2019002

[15]

Anas Chaaban, Vladimir Sidorenko, Christian Senger. On multi-trial Forney-Kovalev decoding of concatenated codes. Advances in Mathematics of Communications, 2014, 8 (1) : 1-20. doi: 10.3934/amc.2014.8.1

[16]

Vladimir Sidorenko, Christian Senger, Martin Bossert, Victor Zyablov. Single-trial decoding of concatenated codes using fixed or adaptive erasing. Advances in Mathematics of Communications, 2010, 4 (1) : 49-60. doi: 10.3934/amc.2010.4.49

[17]

Peter Beelen, Kristian Brander. Efficient list decoding of a class of algebraic-geometry codes. Advances in Mathematics of Communications, 2010, 4 (4) : 485-518. doi: 10.3934/amc.2010.4.485

[18]

Alexey Frolov, Victor Zyablov. On the multiple threshold decoding of LDPC codes over GF(q). Advances in Mathematics of Communications, 2017, 11 (1) : 123-137. doi: 10.3934/amc.2017007

[19]

Henry Cohn, Nadia Heninger. Ideal forms of Coppersmith's theorem and Guruswami-Sudan list decoding. Advances in Mathematics of Communications, 2015, 9 (3) : 311-339. doi: 10.3934/amc.2015.9.311

[20]

Julia Lieb, Raquel Pinto. A decoding algorithm for 2D convolutional codes over the erasure channel. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021031

[Back to Top]