Paper 2026/631

Rethinking r-PKP: a New Formulation for the Relaxed Permuted Kernel Problem

Andrea Gangemi, Polytechnic University of Turin

Lorenzo Romano, Polytechnic University of Turin

Giuliano Romeo, University of Trento

Abstract

Among the schemes in the second round of NIST's additional call for Post-Quantum signatures, PERK builds its security on the intractability of the Permuted Kernel Problem (PKP). In its original formulation, this problem asks, on input three matrices $\mathbf H,\mathbf X,\mathbf Y$, to find a permutation matrix $\mathbf P$ such that $\mathbf H \mathbf P \mathbf X = \mathbf Y$. To achieve better performance and smaller signatures, in its first proposal, the PERK signature modified the security assumption in the following way: given a PKP instance, the matrix $\mathbf P$ does not have to verify the exact previous equation but a relaxed one, taking care of a non-null vector $\mathbf v$ such that $(\mathbf H \mathbf P \mathbf X)\mathbf v = \mathbf Y \mathbf v$. In this work, we rephrase the relaxed problem so that it no longer depends on the PKP instance nor the vector $\mathbf v$. We show that it suffices to find $\mathbf P$ such that $\mathbf H\mathbf P \mathbf X - \mathbf Y$ has rank deficiency. This generalized formulation is easier to model and allows us to design an algebraic attack inspired by those of MinRank and Rank Syndrome Decoding, writing a polynomial system in the entries of $\mathbf P$. Moreover, we can consider it as linear in the minors of $\mathbf P$ and provide some results on them, which may be of independent interest.

@misc{cryptoeprint:2026/631,
      author = {Giuseppe D'Alconzo and Andrea Gangemi and Lorenzo Romano and Giuliano Romeo},
      title = {Rethinking r-{PKP}: a New Formulation for the Relaxed Permuted Kernel Problem},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/631},
      year = {2026},
      url = {https://eprint.iacr.org/2026/631}
}