On the hardness of the Lee syndrome decoding problem
From MaRDI portal
Publication:6089464
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 -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.
Recommendations
- Information set decoding for Lee-metric codes using restricted balls
- Classical and quantum algorithms for generic syndrome decoding problems and applications to the Lee metric
- Improved information set decoding algorithms over Galois ring in the Lee metric
- Information set decoding in the Lee metric with applications to cryptography
- \(\mathcal{NP}\)-completeness of the Goppa parameterised random binary quasi-dyadic syndrome decoding problem
Cites work
- scientific article; zbMATH DE number 3989251 (Why is no real title available?)
- scientific article; zbMATH DE number 4070796 (Why is no real title available?)
- scientific article; zbMATH DE number 4112524 (Why is no real title available?)
- scientific article; zbMATH DE number 3557797 (Why is no real title available?)
- scientific article; zbMATH DE number 1302794 (Why is no real title available?)
- scientific article; zbMATH DE number 493091 (Why is no real title available?)
- scientific article; zbMATH DE number 1942427 (Why is no real title available?)
- scientific article; zbMATH DE number 910958 (Why is no real title available?)
- scientific article; zbMATH DE number 3225714 (Why is no real title available?)
- 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
- A new identification scheme based on syndrome decoding
- A probabilistic algorithm for computing minimum weights of large error-correcting codes
- Algebraic coding theory
- Classical and quantum algorithms for generic syndrome decoding problems and applications to the Lee metric
- Codes, cryptology and information security. Second international conference, C2SI 2017, Rabat, Morocco, April 10--12, 2017. Proceedings -- in honor of Claude Carlet
- Decoding Random Binary Linear Codes in 2 n/20: How 1 + 1 = 0 Improves Information Set Decoding
- Decoding random linear codes in \(\tilde{\mathcal{O}}(2^{0.054n})\)
- Density of free modules over finite chain rings
- Generalization of the ball-collision algorithm
- Generic Decoding in the Sum-Rank Metric
- How To Prove Yourself: Practical Solutions to Identification and Signature Problems
- Information set decoding in the Lee metric with applications to cryptography
- Information-set decoding for linear codes over \(\mathbb F_q\)
- LEDAkem: a post-quantum key encapsulation mechanism based on QC-LDPC codes
- On lower bounds for information set decoding over \(\mathbb F_q\) and on the effect of partial knowledge
- On the Hardness of the Decoding and the Minimum Distance Problems for Rank Codes
- On the asymptotic behaviour of Lee-codes
- On the inherent intractability of certain coding problems (Corresp.)
- Security bounds for the design of code-based cryptosystems
- Smaller decoding exponents: ball-collision decoding
- Some new NP-complete coding problems
Cited in
(5)
This page was built for publication: On the hardness of the Lee syndrome decoding problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6089464)
