The automorphism groups of random linear codes

2026/07/27 by Xiaoru Li, Qi Wang, Yue Zhou
#cs.IT #math.CO #math.IT

paper · pdf

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 C ⊆ \mathbbF_qⁿ have a trivial automorphism group as n goes to infinity as long as min\k, n-k\ ≥ (2+ε)log_q n, for any ε >0.

Citations

• The asymptotic number of equivalence classes of linear codes with given dimension
• On automorphism groups of polar codes
• On the Automorphism Group of Polar Codes
• Automorphism Ensemble Decoding of Reed-Muller Codes
• Automorphism groups of cyclic codes

Related

• On automorphism groups of polar codes
• Generalized Automorphisms of Channel Codes: Properties, Code Design, and a Decoder
• On the automorphism groups of binary linear codes
• The automorphism group of the doubly-even [72,36,16] code can only be of order 1, 3 or 5
• On Linear Codes with Random Multiplier Vectors and the Maximum Trace Dimension Property