A Novel Attack to the Permuted Kernel Problem. (arXiv:2206.14547v1 [cs.CR])

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 …

attack kernel problem