In this paper, we study the hardness of decoding a random code endowed with the cover metric. As the cover metric lies in between the Hamming and rank metric, it presents itself as a promising candidate for code-based cryptography. We give a polynomial-time reduction from the classical Hamming-metric decoding problem, which proves the NP-hardness of the decoding problem in the cover metric. We then provide a generic decoder, following the information set decoding idea from Prange's algorithm in the Hamming metric. A study of its cost then shows that the complexity is exponential in the number of rows and columns, which is in contrast to the behaviour in the Hamming metric, where the complexity grows exponentially in the number of code symbols.
翻译:在本文中,我们研究了解码一个配有覆盖度的随机代码的难度。 封面度量值存在于Hamming和等级度值之间, 它自称是一个有希望的基于代码的加密选择对象。 我们从古典的Hamming测量解码问题中减少了多数值时间, 这证明了封面度量值解码问题的NP- 硬性。 然后我们提供了一个通用解码器, 遵循普朗奇在Hamming 度量值中的算法解码概念。 一项成本研究表明, 其复杂性在行数和列数上是指数指数性的, 这与Hamming 度量值中的行为形成对比, 其复杂性在Hamming 度数中成倍增长。