EUVIMEDEUVIMED entdecken
Crossref

Using the Schur Product to Solve the Code Equivalence Problem

Michele Battagliola, Rocco Mora, Paolo Santini

IEEE Transactions on Information Theory · 2026-07 · 72 (7) · 4675-4694

DOI: 10.1109/tit.2026.3694630 ↗

Kurz gefasst

Fachartikel in der Zeitschrift IEEE Transactions on Information Theory, 2026-07. Verfasst von Michele Battagliola und 2 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref). Gefördert von: Ministero dell?Istruzione, dell?Universit? e della Ricerca.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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 \lt \sqrt {2n}$ or $h \lt \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 \gt \sqrt {2n}$ should be employed.

Förderung

  • Ministero dell?Istruzione, dell?Universit? e della Ricerca

Zitieren

APA

Battagliola, M., Mora, R., & Santini, P. (2026). Using the Schur Product to Solve the Code Equivalence Problem. IEEE Transactions on Information Theory, 72(7), 4675-4694. https://doi.org/10.1109/tit.2026.3694630

Vancouver

Battagliola M, Mora R, Santini P. Using the Schur Product to Solve the Code Equivalence Problem. IEEE Transactions on Information Theory. 2026;72(7):4675-4694. doi:10.1109/tit.2026.3694630

BibTeX
@article{Battagliola2026,
  author = {Battagliola, Michele and Mora, Rocco and Santini, Paolo},
  title = {Using the Schur Product to Solve the Code Equivalence Problem},
  journal = {IEEE Transactions on Information Theory},
  year = {2026},
  volume = {72},
  number = {7},
  pages = {4675--4694},
  doi = {10.1109/tit.2026.3694630}
}
Kostenlos starten →