Information set decoding for Lee-metric codes using restricted balls
From MaRDI portal
Abstract: The Lee metric syndrome decoding problem is an NP-hard problem and several generic decoders have been proposed. The observation that such decoders come with a larger cost than their Hamming metric counterparts make the Lee metric a promising alternative for classical code-based cryptography. Unlike in the Hamming metric, an error vector that is chosen uniform at random of a given Lee weight is expected to have only few entries with large Lee weight. Using this expected distribution of entries, we are able to drastically decrease the cost of generic decoders in the Lee metric, by reducing the original problem to a smaller instance, whose solution lives in restricted balls.
Recommendations
- Classical and quantum algorithms for generic syndrome decoding problems and applications to the Lee metric
- Information set decoding in the Lee metric with applications to cryptography
- On the design and security of Lee metric McEliece cryptosystems
- Decoding a class of Lee metric codes over a Galois ring
- Decoding a class of alternant codes for the Lee metric
Cites work
- Classical and quantum algorithms for generic syndrome decoding problems and applications to the Lee metric
- 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
- scientific article; zbMATH DE number 1942427 (Why is no real title available?)
- scientific article; zbMATH DE number 910958 (Why is no real title available?)
- Information set decoding in the Lee metric with applications to cryptography
- Lattice problems and norm embeddings
- New generic algorithms for hard knapsacks
- On the asymptotic behaviour of Lee-codes
- On the inherent intractability of certain coding problems (Corresp.)
- Some new NP-complete coding problems
- Ternary Syndrome Decoding with large weight
Cited in
(7)- Generalized information-set decoding of \((L,g)\)-codes
- Classical and quantum algorithms for generic syndrome decoding problems and applications to the Lee metric
- On the hardness of the Lee syndrome decoding problem
- Improved information set decoding algorithms over Galois ring in the Lee metric
- \textsf{FuLeeca}: a Lee-based signature scheme
- Information set decoding for ring-linear codes
- Information set decoding in the Lee metric with applications to cryptography
This page was built for publication: Information set decoding for Lee-metric codes using restricted balls
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6174647)
