  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.
