Paper 2025/531

Understanding the new distinguisher of alternant codes at degree 2

Abstract

Distinguishing Goppa codes or alternant codes from generic linear codes [FGO+11] has been shown to be a first step before being able to attack McEliece cryptosystem based on those codes [BMT24]. Whereas the distinguisher of [FGO+11] is only able to distinguish Goppa codes or alternant codes of rate very close to 1, in [CMT23a] a much more powerful (and more general) distinguisher was proposed. It is based on computing the Hilbert series $$ of a Pfaffian modeling. The distinguisher of [FGO+11] can be interpreted as computing $$. Computing $$ still gives a polynomial time distinguisher for alternant or Goppa codes and is apparently able to distinguish Goppa or alternant codes in a much broader regime of rates as the one of [FGO+11]. However, the scope of this distinguisher was unclear. We give here a formula for $$ corresponding to generic alternant codes when the field size $$ satisfies $$, where r is the degree of the alternant code. We also show that this expression for$$ provides a lower bound in general. The value of $$ corresponding to random linear codes is known and this yields a precise description of the new regime of rates that can be distinguished by this new method. This shows that the new distinguisher improves significantly upon the one given in [FGO+11].