The automorphism groups of random linear codes

Abstract

The matching codewords framework is a key tool in recent algorithms for solving the Linear Code Equivalence (LCE) problem and in security analyses of LCE-based cryptographic schemes such as LESS. These analyses often rely on the assumption that a random $q$-ary linear code has no monomial automorphisms other than scalar multiples of the identity. For binary codes, Lefmann, Phelps, and Rödl established the corresponding rigidity phenomenon in the relevant logarithmic dimension range. For general $q$, Hou established an averaged result over all dimensions, whereas the recent prescribed-dimension result of Di Giusto and Ravagnani applies only in a restricted regime near $n/2$. For every fixed prime power $q$ and every fixed real number $\epsilon >0$, we prove that a uniformly random $k$-dimensional code $\mathcal{C}\subseteq {\mathbb{F}}_q^n$ has a trivial monomial automorphism group with probability tending to $1$ as $n\to \infty$, provided that $m:=\min \{k,n-k\}\ge (2+\epsilon ){\log }_{q}n$. Furthermore, when $m\le 2{\log }_{q}n+C$, where $C$ is a constant independent of $n$, we also show that the probability that the automorphism group of $\mathcal{C}$ is nontrivial is at least $\frac{1}{2}-\epsilon$ for large enough $n$.