Paper 2022/1749

Computational Hardness of the Permuted Kernel and Subcode Equivalence Problems

Paolo Santini, Marche Polytechnic University
Marco Baldi, Marche Polytechnic University
Franco Chiaraluce, Marche Polytechnic University

The Permuted Kernel Problem (PKP) asks to find a permutation which makes an input matrix an element of the kernel of some given vector space. The literature exhibits several works studying its hardness in the case of the input matrix being mono-dimensional (i.e., a vector), while the multi-dimensional case has received much less attention and, de facto, only the case of a binary ambient finite field has been studied. The Subcode Equivalence Problem (SEP), instead, asks to find a permutation so that a given linear code becomes a subcode of another given code. At the best of our knowledge, no algorithm to solve the SEP has ever been proposed. In this paper we study the computational hardness of solving these problems. We first show that, despite going by different names, PKP and SEP are exactly the same problem. Then we consider the state-of-the-art solver for the mono-dimensional PKP (namely, the KMP algorithm), generalize it to the multi-dimensional case and analyze both the finite and the asymptotic regimes. We further propose a new algorithm, which can be thought of as a refinement of KMP. In the asymptotic regime our algorithm becomes slower than existing solutions but, in the finite regime (and for parameters of practical interest), it achieves competitive performances. As an evidence, we show that it is the fastest algorithm to attack several recommended instances of cryptosystems based on PKP. As a side-effect, given the mentioned equivalence between PKP and SEP, all the algorithms we analyze in this paper can be used to solve instances of the latter problem.

Note: With respect to the previous version, some typos have been fixed

Available format(s)
Attacks and cryptanalysis
Publication info
Permuted Kernel ProblemSubcode Equivalence ProblemCode-based cryptography
Contact author(s)
p santini @ univpm it
m baldi @ univpm it
f chiaraluce @ univpm it
2023-01-10: revised
2022-12-20: received
See all versions
Short URL
Creative Commons Attribution


      author = {Paolo Santini and Marco Baldi and Franco Chiaraluce},
      title = {Computational Hardness of the Permuted Kernel and Subcode Equivalence Problems},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1749},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.