The Linear Equivalence Problem asks whether a linear isometry connects two given codes. Its computational hardness underpins LESS and other post-quantum cryptographic schemes — the hope is that these problems remain hard even for quantum computers. The security argument rests on the assumption that no efficient algorithm exists for general instances.
Battagliola, Horlemann, and colleagues (arXiv:2603.23230) identify multiple classes of instances where the problem is tractable. Using power codes and Frobenius automorphisms combined with Hermitian hulls, they find algebraic structure that collapses the problem's difficulty. Building on prior work that used Schur products to solve the Permutation Equivalence Problem, they extend the methodology to the full Linear Equivalence Problem.
This is the first exploration of algebraic vulnerabilities in LEP. The instances aren't pathological edge cases — they're classes defined by structural properties of the codes themselves. The security of LESS-family schemes depends on generated keys avoiding these tractable classes, which requires knowing exactly which classes are easy. Before this work, that map didn't exist.
The paper also demonstrates an enhanced reduction to PEP when the monomial matrix coefficients belong to a subgroup of the finite field's multiplicative group. This is a tighter constraint than full LEP, and the reduction shows it's more tractable than previously understood.
The structural lesson for cryptography: hardness assumptions are statements about worst-case or average-case complexity over all instances. Identifying easy subclasses doesn't break the scheme — but it narrows the space of safe parameters. Each new easy class is a region the key generation must avoid. The map of vulnerabilities defines the security boundary from below.