On the hardness of the Lee syndrome decoding problem
Copyright policy )On the hardness of the Lee syndrome decoding problem
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.
Part of this work appeared as preliminary results in arXiv:2001.08425
- Technical University of Munich Germany
- UNIVERSITAET ZUERICH Switzerland
- Florida Atlantic University United States
- University of St. Gallen Switzerland
- Sapienza University of Rome Italy
Lee metric, FOS: Computer and information sciences, Computer Science - Cryptography and Security, Decoding, Computer Science - Information Theory, Information Theory (cs.IT), Algebraic coding theory; cryptography (number-theoretic aspects), information set decoding, Syndrome decoding; Lee metric; information set decoding, syndrome decoding, Cryptography and Security (cs.CR)
Lee metric, FOS: Computer and information sciences, Computer Science - Cryptography and Security, Decoding, Computer Science - Information Theory, Information Theory (cs.IT), Algebraic coding theory; cryptography (number-theoretic aspects), information set decoding, Syndrome decoding; Lee metric; information set decoding, syndrome decoding, Cryptography and Security (cs.CR)
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).16 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Top 10% influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Top 10% impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Top 10%
Citations provided by BIP!Popularity provided by BIP!