The Power of Power Codes: New Classes of Easy Instances for the Linear Equivalence Problem
Michele Battagliola, Anna-Lena Horlemann, Abhinaba Mazumder, Rocco Mora, Paolo Santini, Michael Schaller, Violetta Weger · 2026
Read The Power of Power Codes: New Classes of Easy Instances for the Linear Equivalence Problem by Michele Battagliola, Anna-Lena Horlemann, Abhinaba Mazumder, Rocco Mora, Paolo Santini, Michael Schaller, Violetta Weger (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-23230.txt.
Introduction
Battagliola and six co-authors study the Linear Equivalence Problem for error-correcting codes. The problem asks whether a linear map can turn one code into another. Its permutation-only cousin drew interest as a base for post-quantum schemes like LESS. A recent method used the Schur product to crack many easy cases of that cousin. The team extends the idea with power codes, Frobenius maps, and Hermitian hulls. They map out classes of easy linear cases. They also give a sharper reduction to the permutation problem.
Catalog record
| CREATOR | Michele Battagliola, Anna-Lena Horlemann, Abhinaba Mazumder, Rocco Mora, Paolo Santini, Michael Schaller, Violetta Weger |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 34577 |
| LICENSE | http://creativecommons.org/licenses/by-sa/4.0/ |
| RIGHTS | CC BY SA |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.23230
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
The Power of Power Codes: New Classes of Easy Instances for the Linear Equivalence Problem Michele Battagliola, Anna-Lena Horlemann, Abhinaba Mazumder, Rocco Mora, Paolo Santini, Michael Schaller, Violetta Weger Abstract Given two linear codes, the Linear Equivalence Problem (LEP) asks to find (if it exists) a linear isometry between them; as a special case, we have the Permutation Equivalence Problem (PEP), in which isometries must be permutations. LEP and PEP have recently gained renewed interest as the security foundations for several post-quantum schemes, including LESS. A recent paper has introduced the use of the Schur product to solve PEP, identifying many new easy-to-solve instances. In this paper, we extend this result to LEP. In particular, we generalize the approach and rely on the more general notion of power codes. Combining it with Frobenius automorphisms and Hermitian hulls, we identify many classes of easy LEP instances. To the best of our knowledge, this is the first work exploiting algebraic weaknesses for LEP. Finally we show an improved reduction to PEP whenever the coefficients of the monomial matrix are in a subgroup of the multiplicative group of the finite field. 1 Introduction The Code Equivalence Problem (CEP) asks whether there exists a Hamming-metric isometry mapping one linear code to another. Whenever the isometry is required to be a permutation, we speak of the Permutation Equivalence Problem (PEP); when instead we consider the more general case of monomials (permutations that can also scale coordinates), then we speak of the Linear Equivalence Problem (LEP). In recent years, PEP and LEP have gained a renewed interest because of their use as security assumptions in post-quantum cryptographic schemes such as [ 8 , 4 , 5 , 11 , 1 , 2 ] . Interestingly, attacks on CEP comprise several mathematical tools and techniques, ranging from the use of low weight codewords [ 7 , 9 ] , weight enumeration of the hull [ 20 ] , graph theory [ 3 ] , canonical forms [ 10 , 14 ] , algebraic solvers [ 16 ] and the Schur product [ 6 ] . These attacks reveal a rather different situation regarding the hardness of PEP and LEP. Indeed, several weak instances for PEP are known: whenever the hull is too small, then PEP can be solved in average polynomial time [ 20 , 3 , 6 ] . Instead, when it comes to LEP, the only currently known weak instances are those defined over q -ary finite fields with q<5 [ 18 ] . For q\geq 5 , no weak instance is known: a random LEP instance with non-trivial parameters is currently deemed hard to solve 1 1 1 As we discuss later on, up to polynomial factors, LEP can be solved in worst case time O(q^{k}) , with k being the code dimension. When k is too small, e.g., it is a constant or O\big(\log(n)\big) , we have efficient solvers. . Our contribution In this paper, we identify several previously unknown weak instances. At the basis of our techniques lies the use of power codes , exploiting the property that the powers of equivalent codes remain equivalent. This approach, combined with the concepts of the Frobenius automorphism and the (Hermitian) hull, allows us to derive new easy LEP instances based on the length and dimension of the code. Remarkably, prior to this paper, power codes in the context of CEP have only been used to attack PEP [ 6 ] . Here, we show how power codes can be used to attack (certain instances of) LEP. Looking ahead, the classes of weak instances we identify, differ significantly from the ones that were already known, which required only q\leq 4 . Indeed, our attacks have a strong algebraic flavor and show that, for any finite field, weak instances with non-trivial parameters (i.e., with dimension that grows as a power of n ) do exist. For instance, the first class we identify requires k<\sqrt[r]{r!\cdot n}\cdot\big(1+o(1)\big) , for r an integer such that q=2r+1 . We further improve the attack for non-prime fields. Furthermore, for a subgroup U\subseteq\mathbb{F}_{q}^{\star} , we introduce an intermediate problem LEP( U ) between LEP and PEP and the concept of the partial-closure , which gives a reduction from this novel problem to PEP. Together with power codes this can be used to improve the complexity of the reduction from LEP to PEP compared to the classical reduction. 2 Preliminaries In this section we introduce some preliminary facts. 2.1 Notation For q a prime power, we denote by \mathbb{F}_{q} a finite field with q elements and by \mathbb{F}_{q}^{\star} its multiplicative group. We denote matrices/vectors by bold upper/lower case letters. The identity matrix of size k is denoted by \mathbf{I}_{k} . By \GL_{n}(\mathbb{F}_{q}) we denote the group of n\times n invertible matrices over \mathbb{F}_{q} . In addition, we denote by S_{n} the symmetric group on n elements, and by \mathrm{diag}(\mathbf{d}) the diagonal matrix whose diagonal is \mathbf{d} . We denote by \langle\mathbf{x},\mathbf{y}\rangle the standard inner product, i.e., \langle\mathbf{x},\mathbf{y}\rangle\stackrel{{\scriptstyle\text{def}}}{{=}}\sum_{i=1}^{n}x_{i}y_{i}, and by \mathbf{x}*\mathbf{y}\stackrel{{\scriptstyle\text{def}}}{{=}}(x_{1}y_{1},\dots,x_{n}y_{n}) the component-wise product or Schur product of \mathbf{x} and \mathbf{y} . Finally, we denote by \otimes the Kronecker product. 2.2 Coding Theory Basics We now provide some basics on coding theory, see also [ 12 ] . An [n,k]_{q} linear code \mathcal{A} is a k -dimensional linear subspace of \mathbb{F}_{q}^{n} . We call \mathbf{A}\in\mathbb{F}_{q}^{k\times n} a generator matrix of \mathcal{A} if its rows form a basis of \mathcal{A} . The dual code of \mathcal{A} is an [n,n-k]_{q} linear code defined as \mathcal{A}^{\perp}\stackrel{{\scriptstyle\text{def}}}{{=}}\{\mathbf{x}\in\mathbb{F}_{q}^{n}:\langle\mathbf{x},\mathbf{y}\rangle=0\text{ for all }\mathbf{y}\in\mathcal{A}\} . A generator matrix \mathbf{H}\in\mathbb{F}_{q}^{(n-k)\times n} of \mathcal{A}^{\perp} is called parity-check matrix of \mathcal{A} . In particular, we have that \mathbf{A}\mathbf{H}^{\top}=0 . Definition 1 (Hull) . The hull of a linear code \mathcal{A} is defined as \mathcal{H}(\mathcal{A})\stackrel{{\scriptstyle\text{def}}}{{=}}\mathcal{A}\cap\mathcal{A}^{\perp} . The dimension of the hull of a random code has been studied in [ 19 ] . In particular, a random code has a trivial hull with probability \geq 1-1/q-1/q^{2}, see [ 1 , Lemma 1] . Definition 2 (Power Code) . Let \mathcal{A} be a [n,k]_{q} linear code and \ell be a positive integer. The \ell -th power code of \mathcal{A} is defined as \mathcal{A}^{(\ell)}\stackrel{{\scriptstyle\text{def}}}{{=}}\langle\{\mathbf{x}_{1}*\cdots*\mathbf{x}_{\ell}\mid\mathbf{x}_{1},\ldots,\mathbf{x}_{\ell}\in\mathcal{A}\}\rangle. When \ell=2 we call \mathcal{A}^{(2)} the square code . If \mathcal{A} is a random [n,k]_{q} linear code, then the dimension of \mathcal{A}^{(\ell)} has been shown in [ 13 ] to be with high probability \dim(\mathcal{A}^{(\ell)})=\min\left\{\binom{k+\ell-1}{\ell},n\right\}, for \ell\in\{1,\ldots,q\} . Definition 3 (Hermitian Inner Product) . Let q=p^{2m} , for some prime p and positive integer m. For \mathbf{x},\mathbf{y}\in\mathbb{F}_{q}^{n} let us denote by \langle\mathbf{x},\mathbf{y}\rangle_{H} the Hermitian inner product, i.e., \langle\mathbf{x},\mathbf{y}\rangle_{H}\stackrel{{\scriptstyle\text{def}}}{{=}}\sum_{i=1}^{n}x_{i}y_{i}^{p^{m}}. Analogously to the previous definitions we can also define the Hermitian dual, parity-check matrix and hull ( \mathcal{H}_{H}(\mathcal{A}) ), by replacing the standard with the Hermitian inner product. Definition 4 (Closure) . Let \mathcal{A} be an [n,k]_{q} linear code with generator matrix \mathbf{A}\in\mathbb{F}_{q}^{k\times n} , let \alpha\in\mathbb{F}_{q} be a primitive element, and denote \boldsymbol{\alpha}=(1,\alpha,\ldots,\alpha^{q-2})\in\mathbb{F}_{q}^{q-1} . The closure \boldsymbol{\alpha}\otimes\mathcal{A} of \mathcal{A} is defined as the code with generator matrix \boldsymbol{\alpha}\otimes\mathbf{A} . The closure is an [n(q-1),k]_{q} code. 2.3 The Code Equivalence Problem Definition 5 (Linear Equivalence Problem (LEP)) . Given as input two generator matrices \mathbf{A},\mathbf{B}\in\mathbb{F}_{q}^{k\times n} of two linear codes \mathcal{A},\mathcal{B}\subseteq\mathbb{F}_{q}^{n} , the Linear Equivalence Problem