Paper 2025/227

Two Is All It Takes: Asymptotic and Concrete Improvements for Solving Code Equivalence

Abstract

The Linear Code Equivalence ($\mathsf{LCE}$) problem asks, for two given linear codes $\mathcal{C}, \mathcal{C}'$, to find a monomial $\mathbf{Q}$ mapping $\mathcal{C}$ into $\mathcal{C}'$. Algorithms solving $\mathsf{LCE}$ crucially rely on a (heuristic) subroutine, which recovers the secret monomial from $\Omega(\log n)$ pairs of codewords $(\mathbf{v}_i, \mathbf{w}_i)\in \mathcal{C} \times \mathcal{C}'$ satisfying $\mathbf{w}_i = \mathbf{v}_i\mathbf{Q}$. We greatly improve on this known bound by giving a constructive algorithm that provably recovers the secret monomial from any \emph{two} pairs of such codewords for fields of sufficiently large prime order $q$. Furthermore, we demonstrate that in practice this algorithm remains effective even for small prime fields. We then show that this reduction in the number of required pairs enables the design of a more efficient algorithm for solving the $\mathsf{LCE}$ problem. Our asymptotic analysis shows that this algorithm outperforms previous approaches for a wide range of parameters. Our concrete analysis reveals significant improvements as well. Most notably, in the context of the LESS signature scheme, a second-round contender in the ongoing NIST standardization effort, we achieve bit security reductions of up to 24 bits.