The rank decoding problem has been the subject of much attention in this last decade. This problem, which is at the base of the security of public-key cryptosystems based on rank metric codes, is traditionally studied over finite fields. But the recent generalizations of certain classes of rank-metric codes from finite fields to finite rings have naturally created the interest to tackle the rank decoding problem in the case of finite rings. In this paper, we show that some combinatorial type algorithms for solving the rank decoding problem over finite fields can be generalized to solve the same problem over finite principal ideal rings. We study and provide the average complexity of these algorithms. We also observe that some recent algebraic attacks are not directly applicable when the finite ring is not a field due to zero divisors. These results could be used to justify the use of codes defined over finite rings in rank metric code-based cryptography.
翻译:在过去十年中,等级解码问题一直是人们十分关注的主题。这个问题是公用钥匙加密系统基于标准码的安全基础,传统上是针对有限领域的研究。但最近对从有限字段到有限环的某些等级分解编码类别进行了一般化,自然产生了解决有限环中等级解码问题的兴趣。在本文中,我们显示,解决有限域中等级解码问题的一些组合型算法可以被普遍化,以解决有限主要理想环的同一问题。我们研究并提供这些算法的平均复杂性。我们还注意到,最近一些代数攻击在有限环不是因零分辨器而形成的领域时,不能直接适用。这些结果可以用来证明使用标准代码加密法中定得超过限定圈的编码是合理的。