论文标题
对置换内核问题的新颖攻击
A Novel Attack to the Permuted Kernel Problem
论文作者
论文摘要
置换的内核问题（PKP）要求找到属于给定矩阵内核的给定向量的排列。 PKP是在PKP-DSS的基础上，这是Shamir在1989年提出的识别方案得出的量子后签名方案。PKP的最有效求解器是由于Koussa等人的最新论文所致。在本文中，我们提出了这种算法的改进，我们通过考虑将涉及少量坐标的内核方程应用于内核方程中的其他相撞搜索步骤来实现。我们研究了从编码理论的角度研究此类方程的条件，并描述了如何使用从编码理论中借用的方法（例如信息集解码）有效地找到它们。我们评估了所得算法的复杂性，并表明它在某些情况下表现优于以前的方法。我们还表明，考虑到新求解器，PKP-DSS的某些实例的安全级别被略微高估。
The Permuted Kernel Problem (PKP) asks to find a permutation of a given vector belonging to the kernel of a given matrix. The PKP is at the basis of PKP-DSS, a post-quantum signature scheme deriving from the identification scheme proposed by Shamir in 1989. The most efficient solver for PKP is due to a recent paper by Koussa et al. In this paper we propose an improvement of such an algorithm, which we achieve by considering an additional collision search step applied on kernel equations involving a small number of coordinates. We study the conditions for such equations to exist from a coding theory perspective, and we describe how to efficiently find them with methods borrowed from coding theory, such as information set decoding. We assess the complexity of the resulting algorithm and show that it outperforms previous approaches in several cases. We also show that, taking the new solver into account, the security level of some instances of PKP-DSS turns out to be slightly overestimated.
