Computational Hardness of the Permuted Kernel and Subcode Equivalence Problems

Paolo Santini; Marco Baldi; Franco Chiaraluce

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

Abstract

The Permuted Kernel Problem (PKP) asks to find a permutation which maps an input matrix into 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, proposed by Koussa, Macario-Rat and Patarin), 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 does not improve on KMP but, in the finite regime (and for parameters of practical interest), we achieve significant improvements, especially for the multi-dimensional version of PKP. 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: Minor modifications (typos have been fixed, some text portions and figures has been added/revised)

Metadata

Available format(s): PDF
Category: Attacks and cryptanalysis
Publication info: Published elsewhere. Minor revision. IEEE Transactions on Information Theory
DOI: 10.1109/TIT.2023.3323068
Keywords: Permuted Kernel Problem Subcode Equivalence Problem Code-based cryptography
Contact author(s): p santini @ univpm it
m baldi @ univpm it
f chiaraluce @ univpm it
History: 2023-11-07: last of 2 revisions; 2022-12-20: received; See all versions
Short URL: https://ia.cr/2022/1749
License: CC BY

BibTeX

@misc{cryptoeprint:2022/1749,
      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},
      doi = {10.1109/TIT.2023.3323068},
      note = {\url{https://eprint.iacr.org/2022/1749}},
      url = {https://eprint.iacr.org/2022/1749}
}