Paper 2026/550

Solving the Linear Code Equivalence Problem from Single Codeword Matching

Abstract

In the Linear Code Equivalence (LCE) problem, one seeks the isometry of the Hamming space $\mathbb{F}_q^n$ relating two given linear codes. This problem is considered computationally hard for any alphabet size $q \ge 5$. The matching codewords framework currently serves as the benchmark for evaluating the security of cryptographic schemes whose security relies on the hardness of LCE, such as the LESS signature scheme. The framework operates by sampling multiple low-weight codewords in both target codes until matching codewords are discovered, thereby revealing the underlying isometry. Recent advancements improved this framework by introducing a new matching algorithm to decide whether two pairs of codewords match. While this technique offers better scalability than previous approaches and has led to enhanced attacks on LESS, it remains computationally intensive for certain parameter ranges. In this work, we propose a novel method to determine if a single pair of codewords matches. Our approach is based on the Schur product by an inverse vector, $\mathbf{v}^{-1} \star \mathcal{C}$, defined component-wisely. We demonstrate that if the codes $\mathcal{C}_1$ and $\mathcal{C}_2$ are linearly equivalent and the codewords $\mathbf{v}_1$ and $\mathbf{v}_2$ match, then the resulting products $\mathbf{v}_1^{-1} \star \mathcal{C}_1$ and $\mathbf{v}_2^{-1} \star \mathcal{C}_2$ are permutation equivalent. Since the permutation equivalence problem is efficiently solvable, this provides a highly effective match-testing algorithm. By leveraging this idea, we propose several algorithms that improve the asymptotic exponent of LCE solvers for all parameters. Notably, our method reaches the optimal asymptotic exponent of the framework for a wide range of parameters. When applied to LESS, our technique substantially reduces the best-known bit complexity; for instance, reducing the security of LESS-1 from 127 to 120 bits.