On the hardness of the Lee syndrome decoding problem
From MaRDI portal
Publication:6089464
DOI10.3934/AMC.2022029zbMATH Open1529.94057arXiv2002.12785OpenAlexW3017785777MaRDI QIDQ6089464FDOQ6089464
Authors: Violetta Weger, Karan Khathuria, Anna-Lena Horlemann, Massimo Battaglioni, P. M. Santini, Edoardo Persichetti 
Publication date: 14 December 2023
Published in: Advances in Mathematics of Communications (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/2002.12785
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
- LEDAkem: a post-quantum key encapsulation mechanism based on QC-LDPC codes
- Algebraic coding theory
- 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})\)
- Information-set decoding for linear codes over \(\mathbb F_q\)
- Security bounds for the design of code-based cryptosystems
- How To Prove Yourself: Practical Solutions to Identification and Signature Problems
- Title not available (Why is that?)
- A probabilistic algorithm for computing minimum weights of large error-correcting codes
- Title not available (Why is that?)
- 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
- Smaller decoding exponents: ball-collision decoding
- Title not available (Why is that?)
- On the inherent intractability of certain coding problems (Corresp.)
- Title not available (Why is that?)
- Title not available (Why is that?)
- A new identification scheme based on syndrome decoding
- Codes, cryptology and information security. Second international conference, C2SI 2017, Rabat, Morocco, April 10--12, 2017. Proceedings -- in honor of Claude Carlet
- On the asymptotic behaviour of Lee-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
- Title not available (Why is that?)
- Generalization of the ball-collision algorithm
- Information set decoding in the Lee metric with applications to cryptography
- Title not available (Why is that?)
- Some new NP-complete coding problems
- Density of free modules over finite chain rings
- Title not available (Why is that?)
- Title not available (Why is that?)
- Classical and quantum algorithms for generic syndrome decoding problems and applications to the Lee metric
- Generic Decoding in the Sum-Rank Metric
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)
