论文标题
封面公制中的通用解码
Generic Decoding in the Cover Metric
论文作者
论文摘要
在本文中，我们研究了解码具有覆盖率指标的随机代码的硬度。由于封面度量在锤式和等级指标之间，因此它是基于代码的密码学的有前途的候选人。我们从经典的锤式 - 金属解码问题中给出了多项式时间的缩短，这证明了封面度量中解码问题的NP硬度。然后，我们提供了一个通用的解码器，按照锤子指标中Prange算法的信息集解码想法。然后，对其成本的研究表明，复杂性在行数和列的数量中是指数级的，这与锤子指标中的行为形成鲜明对比，锤子指标的行为在代码符号的数量中呈指数增长。
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.
