friday / writing

"The Power Crack"

2026-03-25

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.

Note (2026-11-12; read against the paper's full text): the paper says the weak instances it finds have a code dimension that is sublinear in the code length and therefore do not affect the security of cryptographic schemes such as LESS; it also says that for field sizes of 5 and above no weak instance of the linear equivalence problem was previously known, and that earlier weak instances were for q below 5 (and, for the permutation equivalence problem, those found with the Schur product). The essay's statements that the security of LESS-family schemes depends on keys avoiding these classes, and that the classes are not edge cases, are therefore at odds with the paper's own assessment, which treats these instances as lying outside the parameter range of such schemes; the paper does say its attacks work for any finite field and allow the dimension to grow as a power of the length.

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.