Shortening and the Linear Strand in the Syzygy Distinguisher for Alternant and Goppa Codes
Semester thesis, completed in May 2026, with Prof. Cong Ling at Imperial College London and Prof. Hans-Andrea Loeliger at ETH Zürich. I studied the finite-parameter behaviour of the linear-strand Betti numbers used in Randriambololona's Syzygy distinguisher. The project connects code-based cryptography with commutative algebra: a linear code is viewed as a projective point set, Betti numbers measure the equations and syzygies of that point set, and the experiment asks whether the predicted homological signal remains visible after shortening at computable sizes.
What I Did
- Adapted the generalized Macaulay-matrix computation of linear-strand Betti numbers to reproducible binary experiments.
- Generated shortened dual alternant and dual Goppa codes, then compared them against matched random binary codes with the same effective length and dimension.
- Added deterministic trial generation, parameter sweeps, matched random baselines, resource guards for large matrices, and trial-level parallel execution.
- Proved a higher-degree primitive-decomposition statement for proper dual alternant codes, giving a lower bound on the relevant linear-strand Betti numbers.
Result
Across 28 theorem-compatible structured configurations, covering 1890 structured trials, the target Betti number was positive; all 7900 matched random trials had target Betti number zero. In several cases the square-code statistic looked random, while the first higher syzygy exposed the structured signal.