The automorphism groups of random linear codes
2026-07-27 • Information Theory
Information Theory
AI summaryⓘ
The authors study the symmetries of random linear codes, which are important for understanding some cryptographic security assumptions. They show that for large enough codes, these random codes almost always have no nontrivial symmetries (automorphisms). This result confirms a commonly used assumption in analyzing certain cryptographic schemes, where such symmetries are presumed to be absent. Their proof applies when the dimension of the code or its complement grows at a certain rate relative to the code length.
linear codesautomorphism grouprandom codescoding theorycryptographyLinear Code Equivalence (LCE) problemmatching codewords frameworkcode dimensionfinite fields
Authors
Xiaoru Li, Qi Wang, Yue Zhou
Abstract
The study of automorphism groups of linear codes is a fundamental topic in coding theory. The matching codewords framework is currently a standard tool for analyzing the security of cryptographic schemes based on the hardness of the Linear Code Equivalence (LCE) problem, such as the LESS signature scheme. This framework often relies on the assumption that $q$-ary random codes have trivial automorphism groups. However, this assumption has not been formally proved in the literature. In this paper, we prove that with high probability, $k$-dimensional random codes $\mathcal{C} \subseteq \mathbb{F}_q^n$ have a trivial automorphism group as $n$ goes to infinity as long as $\min\{k, n-k\} \geq (2+\varepsilon)\log_q n$, for any $\varepsilon >0$.