论文标题
关于李综合症解码问题的硬度
On the Hardness of the Lee Syndrome Decoding Problem
论文作者
论文摘要
在本文中，我们研究了综合征解码问题的硬度，而不是有限的环。我们首先证明了该问题的决策版本是NP完整的，这是从$ 3 $维的匹配问题中减少的。然后，我们通过将有限场上的锤子指标中最知名的求解器转换为有限环上的Lee指标，并提出一些新颖的解决方案来研究解决问题的复杂性。对于分析的算法，我们评估了渐近状态中的计算复杂性，并将其与锤式指标中的相应算法进行比较。
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.
