Paper 2025/1017

Using the Schur Product to Solve the Code Equivalence Problem

Rocco Mora, Helmholtz Center for Information Security, University of Montpellier

Paolo Santini, Università Politecnica delle Marche

Abstract

Given two linear codes, the Code Equivalence Problem asks to find (if it exists) an isometry mapping one code into the other. A special case is the Permutation Equivalence Problem (PEP), where the isometry must be a permutation. The hardness of PEP is crucially dependent on the hull of a code, that is, the intersection between a code and its dual. Indeed, most of the known algorithms have running time that grows exponentially with the hull dimension. Since random codes have very small hull with large probability, PEP is deemed easy for random codes. In this paper we study how the so-called Schur product between linear codes can be employed to solve PEP. The basic idea is to transform a given PEP instance by computing the square of the given codes. While it is well known that the square code operation preserves equivalence between linear codes, we show that, regardless of the hull dimension of the starting codes, their square codes have trivial hull with high probability. Furthermore, we show that as long as the code rate is sufficiently low, no additional permutations mapping the square codes exist with high probability. This effectively generates a new pair of equivalent codes with trivial hulls, where the underlying permutation remains identical to that of the original instance. This observation allows us to leverage existing hull-based attacks to recover the permutation for the square codes, and consequently, for the original codes. Furthermore, we improve this attack by exploiting the structural relationship between hulls: if a permutation maps two codes, the same permutation also maps their respective hulls. We show that by considering the square of the hull as a code in its own right, its hull also becomes trivial with high probability. This allows for the identification of new weak instances of PEP, leading to an attack whose complexity no longer depends on the initial hull dimension, as it is the case of most known algorithm. In particular, we show that our attack achieves average polynomial-time complexity (since the square of the hull, when seen as a code, intersects with its dual in a low dimensional space with large probability) as long as $k < \sqrt{2n}$ or $h < \sqrt{2n}$, where $n$, $k$, and $h$ denote the code length, dimension, and hull dimension, respectively. We corroborate our analysis, which relies on some (plausible) heuristics, with intensive numerical simulations. As a concrete application, we consider the updatable encryption scheme proposed by Albrecht, Benčina, and Lai at Eurocrypt 2025. All the recommended instances fall into the range of weak PEP instances identified in this paper; hence, they are susceptible to our attack. As a demonstration, we successfully recover the secret permutation for two of the instances claiming 128 bits of security in about $10$ minutes on average on a laptop. As a fix, instances with hull dimension $h > \sqrt{2n}$ should be employed.

@misc{cryptoeprint:2025/1017,
      author = {Michele Battagliola and Rocco Mora and Paolo Santini},
      title = {Using the Schur Product to Solve the Code Equivalence Problem},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/1017},
      year = {2025},
      doi = {https://doi.org/10.1109/TIT.2026.3694630},
      url = {https://eprint.iacr.org/2025/1017}
}