The Power of Power Codes: New Classes of Easy Instances for the Linear Equivalence Problem
This work addresses security foundations for post-quantum cryptographic schemes like LESS by identifying algebraic weaknesses in LEP, though it appears incremental as it builds on prior methods for PEP.
The paper tackles the Linear Equivalence Problem (LEP) by extending a Schur product method from the Permutation Equivalence Problem to identify new easy-to-solve instances, using power codes, Frobenius automorphisms, and Hermitian hulls to generalize the approach.
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.