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
- 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
- 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?)
- Information set decoding in the Lee metric with applications to cryptography
- Information-set decoding for linear codes over 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 asymptotic behaviour of Lee-codes
- On the Hardness of the Decoding and the Minimum Distance Problems for Rank 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
(11)- On the (in)security of optimized Stern-like signature schemes
- Improved information set decoding algorithms over Galois ring in the Lee metric
- \textsf{FuLeeca}: a Lee-based signature scheme
- Generic error SDP and generic error CVE
- MODRED: a code-based non-interactive key exchange protocol
- On Gaussian sampling for q-ary lattices and linear codes with Lee weight
- Information set decoding for ring-linear codes
- Solving systems of algebraic equations over finite commutative rings and applications
- On the generalizations of the rank metric over finite chain rings
- A zero-knowledge proof for the syndrome decoding problem in the Lee metric
- Better bounds on the minimum Lee distance
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)
