Minimum Distances of Binary Goppa Codes and Constructions with Prescribed Alternating Automorphism Groups

Source: arXiv:2608.02436 · Published 2026-08-03 · By Tianni He, Kangquan Li, Longjiang Qu

TL;DR

This paper addresses two central challenges in the theory of binary Goppa codes: precisely determining their minimum distances and constructing Goppa codes with prescribed automorphism groups, particularly the alternating groups A4 and A5. The authors develop two new algebraic criteria that guarantee the minimum distance of certain classes of binary separable Goppa codes attains their designed distance. These classes are defined by power-composite Goppa polynomials g(X) = f(X^t) and composite polynomials g(X) = A(X)h(φ(X)). Utilizing these criteria, they derive multiple infinite families of binary Goppa codes with explicitly determined minimum distances, including families built from polynomials like X^{2t} + X^t + 1, X^{3t} + X^t + 1, and X^4 + cX.

Beyond parameter analysis, the paper constructs quasi-cyclic binary Goppa codes and their variants with automorphism groups isomorphic to A4 or A5 by leveraging subgroup actions of PGL(2, 2^m). This yields new explicit orbit-based families of quasi-cyclic codes exhibiting these symmetries. Applying the minimum-distance criteria established, the authors determine exact parameters of an A4-invariant binary Goppa code family. The results combine deep algebraic tools with character sum techniques to provide both theoretical insight and explicit constructions, enriching the toolkit for code-based cryptography and algebraic coding theory.

Key findings

• Theorem 3.2: For g(X) = f(X^t) with separable f and t|(2^m -1), the minimum distance d = 2r t + 1 is attained if a polynomial P(X) of degree 2r satisfies specified divisibility and gcd conditions.
• Proposition 3.3: For g(X) = X^{2t} + X^t + 1, if 5|ℓ or 7|ℓ where 2^m -1 = tℓ, then d = 4t + 1, with explicit examples matching computed distances (e.g. [14,6,5], [254,238,5]).
• Proposition 3.4: For g(X) = X^{3t} + X^t +1, when 15|ℓ, 21|ℓ, or 31|ℓ, d = 6t +1 holds under analogous polynomial conditions.
• Theorem 3.5: For composite Goppa polynomials g(X) = A(X) h(φ(X)) with A dividing φ' and δ|2r+1, a constructed codeword of weight 2r+1 exists, proving minimum distance equals designed distance.
• Theorem 3.8: For g(X) = X^4 + cX with m even ≥6, the minimum distance is d = 9. Parameters are exactly determined for related A4-invariant codes (e.g. [63,39,9]).
• Section 4: Binary Goppa codes and extended/expurgated variants with automorphism groups isomorphic to A4 and A5 are constructed through orbit decomposition of subgroups of PGL(2, 2^m).
• Lemma 4.1: PGL(2, 2^m) contains A4 and A5 subgroups if and only if m is even, a key structural fact enabling the constructions.
• Table I, II, III, and IV provide explicit infinite families and concrete parameters of Goppa codes with determined minimum distances matching theoretical predictions.

Methodology — deep read

The paper's methodology can be summarized as follows:

1. Threat Model & Assumptions: While primarily theoretical in coding theory, the authors implicitly assume a classical linear code adversary seeking to exploit minimum distance bounds and code structure. They focus on binary separable Goppa codes over finite fields F_{2^m} with specific polynomial supports and polynomial Goppa polynomials.

2. Data & Setup: The authors define Goppa codes through supports L ⊆ F_{2^m} (or projective line) where the Goppa polynomial g(α) ≠ 0 for α ∈ L. They consider several infinite families parameterized by m, t, and polynomial forms (e.g. g(X) = f(X^t), or composite forms). The supports often are formed from orbits under group actions or multiplicative cosets.

3. Architecture/Algorithm:

• For minimum distance, they transform the problem into constructing explicit codewords of weight equal to the designed distance 2r+1 (for degree r polynomials). They introduce conditions on an auxiliary polynomial P(X), such that P divides X^{ℓ}-1 (with ℓ from the factorization of 2^m -1), and satisfies relations with f(X) (or h(ϕ(X)) in composite case). This enables algebraic construction of low-weight codewords.
• In the composite polynomial case, they use complete fiber decomposition of polynomial maps ϕ(X) and carefully analyze the derivatives to guarantee constructed codewords.
• For automorphism constructions, they identify subgroups isomorphic to A4 and A5 inside PGL(2, 2^m) when m is even, then decompose F_{2^m} into orbits under these groups. They define Goppa polynomials g(X) whose roots are unions of orbits, ensuring that the code is invariant under the group action.

4. Training / Computation:

• No training in ML sense; rather, the authors verify their constructions via symbolic computations and explicit verification using Magma for example parameters.
• They perform explicit exponential sum calculations and Gauss sum evaluations to prove existence of necessary field elements satisfying divisibility and root conditions.

5. Evaluation Protocol:

• They verify minimum distance bounds by constructing explicit codewords, matching designed distances.
• They compute code parameters [n,k,d] for several example fields and polynomials using Magma, confirming theoretical bounds.
• Several theorems give sufficient algebraic criteria which when met guarantee exact minimum distances.

6. Reproducibility:

• The paper does not mention public code releases or frozen weights (non-ML research).
• Full polynomial and algebraic constructions are described in detail to enable reproduction by a skilled researcher.

Example end-to-end: For g(X) = X^{2t} + X^t + 1, under conditions on factorization of 2^m -1, the authors find a polynomial P(X) dividing X^{ℓ}-1 with gcd conditions. Using P(X), they explicitly construct a subset S in the support L of size 2rt+1. The associated codeword of weight 2rt+1 proves d = 2rt+1. Magma computations on small m,t verify the parameters match theoretical predictions.

Technical innovations

• Development of two algebraic criteria (Theorems 3.2 and 3.5) linking separable Goppa polynomials with auxiliary polynomials P(X) or fiber decompositions that guarantee minimum distances attain designed values.
• Construction of infinite explicit families of binary Goppa codes with determined minimum distances for polynomials of the form g(X) = f(X^t) (power-composite) and g(X) = A(X)h(ϕ(X)) (composite).
• Use of projective linear group PGL(2, 2^m) subgroup orbit decompositions to construct binary Goppa codes and related codes with alternating group automorphism groups A4 and A5.
• Combining exponential sum and Gauss sum analyses to prove existence of necessary field elements for polynomial divisibility and root conditions, enabling minimum-distance proofs for complex polynomial forms.

Baselines vs proposed

• Proposition 3.3 family (g(X)=X^{2t}+X^{t}+1): computed minimum distances match theoretical d=4t+1, e.g., for m=4,t=1, n=14, [14,6,5].
• Proposition 3.4 family (g(X)=X^{3t}+X^{t}+1): computed minimum distances match theoretical d=6t+1, e.g., m=6,t=3, n=55, [55,5,19].
• Theorem 3.8 family (g(X)=X^4 + cX): computed minimum distance d=9 for m≥6 (even), example [63,39,9] matches theoretical.
• The constructed A4-invariant Goppa codes exhibit parameters exactly matching designed-distance criteria combined with dimension bounds from Section 4.

Limitations

• The two minimum distance criteria provide sufficient but not necessary conditions; not all binary Goppa codes with minimum distance equal to the designed distance are captured by these constructions.
• Automorphism-group based constructions rely on m being even (to embed A4 or A5 in PGL(2, 2^m)) limiting applicability.
• The paper primarily focuses on binary separable Goppa codes; extensions to non-binary or inseparable cases remain open.
• No extensive adversarial or cryptanalysis evaluation of the constructed codes' security or resistance to known attacks is included.
• Some conditions (e.g., divisibility of auxiliary polynomials) need explicit verification or exhaustive search, complicating practical parameter selection.
• No publicly available code or datasets released, potentially hindering independent reproduction.

Open questions / follow-ons

• Can analogous minimum-distance criteria be extended to non-binary or non-separable Goppa codes?
• How do the constructed codes with A4 or A5 automorphisms impact the trade-offs in code-based cryptosystems between key size, decoding efficiency, and security?
• Are there broader classes of automorphism groups beyond alternating groups that can be exploited to systematically construct quasi-cyclic Goppa codes?
• What are the resilience properties of these new code families against emerging quantum or classical structural attacks on code-based cryptography?

Why it matters for bot defense

For practitioners focused on bot-defense or CAPTCHA design, this paper offers advanced algebraic constructions of binary Goppa codes with guaranteed minimum distances and structured symmetries. Since structured codes with large automorphisms can enable more compact key representations and efficient encoding/decoding, insights here may inform designing cryptographic primitives with better performance profiles. Although the work is not directly related to CAPTCHA challenges, understanding how code automorphisms and minimum-distance guarantees are established can inspire new error-correcting code techniques to detect and mitigate automated attack attempts reliably. Moreover, the quasi-cyclic structures emerging from these alternating group actions could be leveraged to generate hard-to-decipher puzzles or proof-of-work schemes grounded in coding theory. However, practical applicability requires bridging the gap between pure algebraic theory and system-level bot-defense implementations.

Cite

@article{arxiv2608_02436,
  title={ Minimum Distances of Binary Goppa Codes and Constructions with Prescribed Alternating Automorphism Groups },
  author={ Tianni He and Kangquan Li and Longjiang Qu },
  journal={arXiv preprint arXiv:2608.02436},
  year={ 2026 },
  url={https://arxiv.org/abs/2608.02436}
}

Read the full paper

• arXiv:2608.02436 (abstract)
• arXiv:2608.02436 (PDF)