# Understanding the new distinguisher of alternant codes at degree 2

Axel Lemoine, Rocco Mora, Jean-Pierre Tillich

► To cite this version:

Axel Lemoine, Rocco Mora, Jean-Pierre Tillich. Understanding the new distinguisher of alternant codes at degree 2. WCC 2024: Thirteenth International Workshop on Coding and Cryptography, Jun 2024, Perugia, Italy. hal-04953992

HAL Id: hal-04953992

https://inria.hal.science/hal-04953992v1

Submitted on 18 Feb 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Understanding the new distinguisher of alternant
codes at degree 2

Axel Lemoine¹, Rocco Mora², and Jean-Pierre Tillich¹

¹ Inria Paris, France

`{axel.lemoine,jean-pierre.tillich}@inria.fr`

² CISPA, Germany

rocco.mora@cispa.de

**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 the McEliece type cryptosystem based on those codes [BMT23]. 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 is proposed. It is based on computing the Hilbert series ${HF(d), d \in \mathbb{N}}$ of a Pfaffian modeling. The distinguisher of [FGO$^{+11}$] can be interpreted as computing $HF(1)$. Computing $HF(2)$ 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 $HF(2)$ corresponding to generic alternant codes when the field size $q$ satisfies $q \ge r$ where $r$ is the degree of the alternant code. We also show that this expression for $HF(2)$ is a lower bound in general on it. The $HF(2)$ 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 which shows that the new distinguisher improves significantly upon the one given in [FGO$^{+11}$].

# 1 Introduction

The McEliece cryptosystem [McE78] is the oldest code-based scheme and it is based on binary Goppa codes, a subfamily of alternant codes. It is believed to be quantum-resistant and its IND-CCA secure variation [ABC$^{+22}$] is currently a fourth round finalist of the NIST post-quantum competition. For a long time, it was believed that structural attacks aiming at recovering the underlying Goppa structure from an arbitrary generator matrix of the code were much more expen- sive than message recovery attacks. The latter ignore completely the algebraic structure and aim just at decoding a generic linear code.

In [FGO$^{+11}$] another approach was tried. Instead of trying to recover directly the algebraic structure from a generator matrix of a Goppa code, a potentially easier problem is solved first, namely that of *distinguishing* a Goppa code from a generic linear code just by the knowledge of a generator matrix of the code. This
is a promise problem where either we are given a generator matrix of a Goppa
code or one of a random linear code and one must decide in which case we are. It
turned out that there is a way to solve this problem in polynomial time for Goppa
codes and more generally for the slightly more general family of alternant codes,
at least for very high rate codes [FGO+11]. It took a while to transform this
distinguisher into an algorithm recovering the algebraic structure of the Goppa
or the alternant code, but this has recently been achieved in [BMT23, CMT23b]
(but binary Goppa codes could not be handled by these papers).

Interestingly enough, [CMT23b] also puts forward a new algebraic object, namely the matrix code of quadratic relations. The point is that this matrix code can be associated to any linear code. However, the matrix code associated to Goppa or alternant codes contains matrices of unusually low rank, namely rank 3 in characteristic $\neq$ 2 and rank 2 in characteristic 2, which are consequences of structured quadratic relations. Finding such low rank matrices can in principle be achieved by solving the corresponding MinRank problem. Moreover, in characteristic 2, the matrix code is a subspace of skew-symmetric matrices and the MinRank problem can be modeled with a system where the Pfaffians of principal submatrices of order 4 are equated to 0. The polynomials corresponding to these equations define what we call the Pfaffian ideal. The existence of low-rank matrices has been exploited to mount a distinguisher attack and its complexity has been partially analyzed [CMT23b] as we recall below.

This work focuses on characteristic 2 and aims to advance the knowledge of a
fundamental object associated with the above-mentioned Pfaffian ideal (and with
polynomial ideals in general): its Hilbert function (or series). This Hilbert series
{HF(d), d ∈ N} turns out to be a very good way to distinguish alternant or Goppa
codes from generic linear codes. Whereas HF(d) never vanishes in the first case, it
turns out to be equal to 0 for a large enough degree in the second case. This gives
a new distinguisher for Goppa or alternant codes. The Hilbert function associated
to a generic linear code can be easily derived by making some assumptions
that have been verified experimentally [CMT23b, Conjecture 1] and the smallest
degree for which the Hilbert series vanishes can be computed. Interestingly, when
the co-dimension $n-k$ of the code is of the form $n-k = O(n^\alpha)$ when $\alpha < 1$ and
$n$ is the codelength, the degree $d$ at which this happens is low enough so that the
actual computation of the Hilbert series can be done with a complexity which is
smaller than the aforementioned message recovery attacks. Potentially, this also
paves the way to key attacks on the McEliece cryptosystem based on such codes
of very large rate which are less complex than message recovery attacks.

Unfortunately, whereas the Hilbert series {HF<sub>R</sub>(d), d ∈ N} of a generic linear
code is well understood in [CMT23b], the Hilbert series {HF<sub>A</sub>(d), d ∈ N} that
corresponds to an alternant code is much less understood. This is a pity, since
this would allow to understand precisely the scope of the distinguisher based on
the computation of the Hilbert series. The only case, which was understood right
now is the Hilbert series at degree 1, HF(1). It turns out that knowing HF(1)
is equivalent to knowing the dimension of the square of the dual code and the
distinguisher of alternant or Goppa codes based on the fact that their HF(1) differs is actually equivalent to the distinguisher of [FGO$^{+}$11].

The aim of this work is to understand the value of HF<sub>A</sub>(2). We will provide here a formula for it together with a proof using a natural conjecture that has been verified experimentally. We also prove that this formula is actually a rigorous lower bound on HF<sub>A</sub>(2) in general. It turns out that the distinguisher based on HF<sub>A</sub>(2) ≠ HF<sub>R</sub>(2) works for a much broader set of parameters than the distinguisher HF<sub>A</sub>(1) ≠ HF<sub>R</sub>(1) (which is equivalent to the one of [FGO$^{+}$11]). This could open the way to key attacks in the regime of parameters for which HF<sub>A</sub>(2) ≠ HF<sub>R</sub>(2), much in the same way that [FGO$^{+}$11, MT23] were a first step before the attacks of [BMT23, CMT23b]. On top of that, knowing the Hilbert series precisely is crucial when it comes to solve the Pfaffian system and our work can be viewed as a significant step in this direction.

**Note:** The proofs of all results announced in this extended abstract can be found in the full version of this paper which can be found on eprint.

# 2 Preliminaries

## 2.1 Reed-Solomon and alternant codes

We work in characteristic 2 throughout the paper. We denote by $\mathbb{F}_q$ the finite field of size $q$ which is therefore assumed here to be a power of 2.

**Definition 1 (Generalized Reed-Solomon code).** Let $n \le q$ be an integer, $\mathbf{x} = (x_1, \dots, x_n)$ be a vector of pairwise-distinct elements of $\mathbb{F}_q$, and $\mathbf{y} \in (\mathbb{F}_q^\times)^n$. The generalized Reed-Solomon code of dimension $r$, support $\mathbf{x}$ and multiplier $\mathbf{y}$ is

$$ \mathbf{GRS}_r(\mathbf{x}, \mathbf{y}) \stackrel{\text{def}}{=} \{(y_1 f(x_1), \dots, y_n f(x_n) \mid f \in \mathbb{F}_q[X]_{<r})\}. $$

A (generalized) Reed-Solomon code of degree $r$ is an MDS code of dimension $r$. It is well-known that the dual of a GRS code is also a GRS code [MS77].

**Definition 2 (Alternant code).** Let $r, m$ be two integers, $\mathbf{x} \in \mathbb{F}_{q^m}^n$ be a support, and $\mathbf{y} \in (\mathbb{F}_{q^m}^\times)^n$ be a multiplier. The alternant code of support $\mathbf{x}$ and multiplier $\mathbf{y}$ is

$$ \mathcal{A}_r(\mathbf{x}, \mathbf{y}) \stackrel{\text{def}}{=} (\mathbf{GRS}_r(\mathbf{x}, \mathbf{y})^{\perp})|_{\mathbb{F}_q}. $$

We know that [MS77] $\dim_{\mathbb{F}_q} \mathcal{A}_r(\mathbf{x}, \mathbf{y}) \ge n-rm$ and this bound is generally tight.

## 2.2 Quadratic relations over a basis of a code

We first recall the concept of code of quadratic relations with respect to a basis of a linear code.

**Definition 3.** Let $\mathcal{C}$ be an $[n, k]$-linear code over $\mathbb{F}_q$, and let $\mathcal{V} \stackrel{\text{def}}{=} (v_1, \dots, v_k)$ be a basis of $\mathcal{C}$. The code of quadratic relations of $\mathcal{C}$ with respect to $\mathcal{V}$ is defined as

$$ \mathcal{C}_{rel}(\mathcal{V}) \stackrel{\text{def}}{=} \left\{ \mathbf{c} = (c_{i,j})_{1 \le i \le j \le n} \in \mathbb{F}_q^{\binom{k+1}{2}} \mid \sum_{i \le j} c_{i,j} v_i \star v_j = 0 \right\}, $$
where $\mathbf{a} \star \mathbf{b} \stackrel{\text{def}}{=} (a_1 b_1, \dots, a_n b_n)$ for $\mathbf{a}, \mathbf{b} \in \mathbb{F}_q^n$.

As usual, a codeword $\mathbf{c} \in \mathcal{C}_{\text{rel}}(\mathcal{V})$ may be seen as a quadratic form whose matrix $M_{\mathbf{c}} = (m_{i,j})_{1 \le i,j \le k}$ is defined by $m_{i,j} = c_{i,j}$ if $i < j$, $m_{i,j} = c_{j,i}$ if $i > j$ and $m_{i,i} = 2c_{i,i}$. In characteristic 2, the diagonal of these matrices is thus always zero. We define the code of matrices

$$ \mathcal{C}_{\text{mat}}(\mathcal{V}) \stackrel{\text{def}}{=} \{M_{\mathbf{c}} | \mathbf{c} \in \mathcal{C}_{\text{rel}}(\mathcal{V})\}. $$

We recall that a lot of interesting features of the code of relations remain invariant under a change of basis.

**Lemma 1 ([CMT23b], Proposition 4).**

$$ \dim \mathcal{C}_{\text{mat}}(\mathcal{V}) = \dim \mathcal{C}_{\text{rel}}(\mathcal{V}). $$

$\dim \mathcal{C}_{\text{rel}}(\mathcal{V})$ and the rank distribution of $\mathcal{C}_{\text{mat}}(\mathcal{V})$ is invariant under a change of basis.

As a consequence, we sometimes write $\mathcal{C}_{\text{rel}}$ or $\mathcal{C}_{\text{mat}}$ without specifying the basis when we refer to invariants.

# 3 Codes of relations of a generalized Reed-Solomon code

The key for understanding $\text{HF}_A(2)$ will be to treat the case $m = 1$ first, i.e. when the alternant code is actually a generalized Reed-Solomon code.

## 3.1 Fundamental relations in the canonical basis

**Definition 4 (Canonical basis).** $\mathcal{A} \stackrel{\text{def}}{=} (\mathbf{a}_0, \dots, \mathbf{a}_{r-1})$, where $\mathbf{a}_i = \mathbf{x}^i \star \mathbf{y}$ forms a basis of $\text{GRS}_r(\mathbf{x}, \mathbf{y})$, which we call a canonical basis$^3$.

**Definition 5 (Fundamental relations).** *Quadratic relations of the form*

$$ \mathbf{a}_i \star \mathbf{a}_j = \mathbf{a}_k \star \mathbf{a}_l $$

when $i + j = k + l$ will be called **fundamental relations**.

It is well known that there are $\binom{r-1}{2}$ linearly independent fundamental relations in $\mathcal{C}_{\text{rel}}(\mathcal{A})$, and in some cases these relations generate the code of relations.

**Proposition 1.** If $2r - 1 \le n$, then the fundamental relations form a basis of $\mathcal{C}_{\text{rel}}(\mathcal{A})$.

<footnote>$^3$ Since different vectors $\mathbf{x}$ and $\mathbf{y}$ may generate the same **GRS** code, we talk about a canonical basis rather than the canonical basis.</footnote>
When the above proposition holds, not only $\mathscr{C}_{\text{mat}}(\mathcal{A})$ does not depend on the choice of $\boldsymbol{x}$ and $\boldsymbol{y}$, but every GRS code of dimension $r$ has the same code of relations with respect to any canonical basis. We can even describe a simple algorithm that builds a basis of $\mathscr{C}_{\text{mat}}(\mathcal{A})$. The idea is to list the relations in the following order :

$$ \boldsymbol{a}_0 \star \boldsymbol{a}_2 = \boldsymbol{a}_1 \star \boldsymbol{a}_1, \boldsymbol{a}_0 \star \boldsymbol{a}_3 = \boldsymbol{a}_1 \star \boldsymbol{a}_2, \boldsymbol{a}_0 \star \boldsymbol{a}_4 = \boldsymbol{a}_2 \star \boldsymbol{a}_2, \boldsymbol{a}_1 \star \boldsymbol{a}_3 = \boldsymbol{a}_2 \star \boldsymbol{a}_2, \dots $$

Before describing the algorithm, let us introduce a few notations.

**Definition 6 (Sparse notation).** Let $I = \{(i_1, j_1), \dots, (i_t, j_t)\} \subseteq \llbracket 1, r \rrbracket^2$ be a list of distinct tuples such that $i_s < j_s$ for all $s$. We define $[(i_1, j_1), \dots, (i_t, j_t)]$ as the matrix $(m_{k,l})_{1 \le k,l \le r}$ such that $m_{k,l} = 1$ if $(k, l) \in I$ or $(l, k) \in I$ and $0$ otherwise.

Finally, if $M \in \mathbb{F}_q^{r \times r}$, $\tilde{M}$ denotes the transpose of $M$ with respect to the anti-diagonal $(i+j=r+1)$, i.e $\tilde{m}_{i,j} = m_{r-j+1,r-i+1}$. Using this notation, Algorithm 1 returns a basis of $\mathscr{C}_{\text{mat}}(\mathcal{A})$. One can check that the algorithm produces exactly

**Algorithm 1** Generation of a basis $\mathcal{B} = (M_1, \dots, M_N)$ of $\mathscr{C}_{\text{mat}}(\mathcal{A})$
**Algorithm 2** Generation of a basis $\mathcal{B} = (M_1, \dots, M_N)$ of $\mathscr{C}_{\text{mat}}(\mathcal{A})$
$\mathcal{B} \leftarrow \emptyset$
$s \leftarrow 4$
while $s \le r+1$ do
(i, j) $\leftarrow (1, s-1)$ & $\triangleright$ (i, j) will run along the sub-anti-diagonal $i+j=s$.
if $s$ is even then
while $i < j$ do
$M \leftarrow [(i, j)]$
$\mathcal{B} \leftarrow \mathcal{B} \cup \{M, \tilde{M}\}$
(i, j) $\leftarrow (i+1, j-1)$
else
$k \leftarrow \frac{s-1}{2}$
while $i+1 < j-1$ do
$M \leftarrow [(i, j), (k-1, k)]$
$\mathcal{B} \leftarrow \mathcal{B} \cup \{M, \tilde{M}\}$
(i, j) $\leftarrow (i+1, j-1)$
$s \leftarrow s+1$
return $\mathcal{B}$

$N = \binom{r-1}{2}$ matrices (note that when $s = r + 1$, the set $\{M, \tilde{M}\}$ contains only one matrix). Furthermore, for each matrix $M \in \mathcal{B}$ returned by the algorithm, its nonzero coefficients that are not right above/under the diagonal do not appear in any other matrix in $\mathcal{B}$, which clearly implies that the elements of $\mathcal{B}$ are linearly independent over $\mathbb{F}_q$. Applying Proposition 1, we get

**Corollary 1.** When $2r - 1 \le n$, Algorithm 1 returns a basis of $\mathscr{C}_{\text{mat}}(\mathcal{A})$. This basis is referred to as **the canonical basis**$^4$ of $\mathscr{C}_{\text{mat}}$.

<footnote>$^4$ This basis does not depend on the choice $\boldsymbol{x}$ and $\boldsymbol{y}$, but depends on $r$.</footnote>
## 3.2 Rank 2 matrices in $\mathscr{C}_{mat}$

Among the fundamental relations, the ones of the form

$$a_i \star a_j = a_k^{\star 2}$$

(when $i + j = 2k$) give a matrix of rank 2 when $\mathbb{F}$ is of characteristic 2. This suggests that there are many matrices of rank 2 in $\mathscr{C}_{mat}$.

**Implicit modeling of [CMT23b].** To find rank 2 matrices in $\mathscr{C}_{mat}$, we may adopt the inverse point of view, i.e finding matrices belonging to $\mathscr{C}_{mat}$ inside the variety of skew-symmetric matrices of rank $\le 2$. Writing the generic skew-symmetric matrix

$$M = \begin{pmatrix} 0 & X_{1,2} & \dots & X_{1,r} \\ X_{1,2} & 0 & \dots & X_{2,r} \\ \vdots & \vdots & \ddots & \vdots \\ X_{1,r} & X_{2,r} & \dots & 0 \end{pmatrix},$$

we know that the variety of rank $\le 2$ skew-symmetric matrices in characteristic 2 may be described by the following equations [Wim12]:

$$X_{i,j}X_{k,l} + X_{i,k}X_{j,l} + X_{i,l}X_{j,k} = 0, \quad 1 \le i < j < k < l \le r \quad (1)$$

We call the left-hand side of (1) a *Pfaffian* of $M$, as it is the *Pfaffian* of some $4 \times 4$ principal submatrix of $M$. More generally, if $N$ is any skew-symmetric matrix whose coefficients lie in some polynomial ring, we denote by $\mathrm{Pf}(N, 2)$ the set of all Pfaffians of size 4 of $N$. Adding linear equations expressing the fact that $M$ belongs to $\mathscr{C}_{mat}$, we obtain the first algebraic modeling of rank $\le 2$ matrices in $\mathscr{C}_{mat}$:

**Modeling 1 (Implicit modeling)** *The implicit modeling of rank $\le 2$ matrices in $\mathscr{C}_{mat}$ consists of the ideal I generated by the $\binom{r}{4}$ Pfaffians of the generic skew-symmetric $r \times r$ matrix $M$ and parity-check equations expressing the fact that $M$ belongs to $\mathscr{C}_{mat}$.*

**Explicit modeling.** Another strategy is to compute a basis $(M_1, \dots, M_N)$ of $\mathscr{C}_{mat}$ and solve the MinRank problem with matrix

$$M \stackrel{\mathrm{def}}{=} \sum_{i=1}^{N} X_i M_i \quad (2)$$

$M$ looks like this in the canonical basis when $r = 5$ or $r = 6$

$$M_{(r=5)} = \begin{pmatrix} 0 & 0 & X_1 & X_2 & X_4 \\ 0 & 0 & X_1 & X_2 & X_5 \\ X_1 & X_2 & 0 & X_5 & X_6 \\ X_2 & X_3 & X_5 & 0 & 0 \\ X_4 & X_5 & X_6 & 0 & 0 \end{pmatrix}, \quad M_{(r=6)} = \begin{pmatrix} 0 & 0 & X_1 & X_2 & X_4 & X_6 \\ 0 & 0 & X_1 & X_2 & X_3 & X_5 \\ X_1 & X_2 & 0 & X_5 + X_6 & X_7 & X_9 \\ X_2 & X_3 & X_5 + X_6 & 0 & X_9 & X_{10} \\ X_4 & X_5 & X_7 & X_9 & 0 & 0 \\ X_6 & X_8 & X_9 & X_{10} & 0 & 0 \end{pmatrix}$$
The matrix $\mathbf{M}$ is the generic matrix in $\mathcal{C}_{\mathrm{mat}}$. Since it is skew-symmetric, one may consider its Pfaffians of degree 2, i.e the Pfaffians of all $4 \times 4$ submatrices of $\mathbf{M}$, which leads to the following algebraic modeling.

**Modeling 2 (Explicit Pfaffian modeling)** The explicit modeling consists of $\binom{r}{4}$ equations $f=0$ for $f \in \mathbf{Pf}(\mathbf{M}, 2)$. More explicitly, writing $\mathbf{M} = (\mathbf{m}_{i,j})_{1 \le i,j \le r}$, the equations are

$$ \mathbf{m}_{i,j} \mathbf{m}_{k,l} + \mathbf{m}_{i,k} \mathbf{m}_{j,l} + \mathbf{m}_{i,l} \mathbf{m}_{j,k} = 0. $$

where each coefficient $\mathbf{m}_{i,j}$ is a polynomial of degree 1.

We are interested in computing the Hilbert function at degree 2 of the ideal generated by $\mathbf{Pf}(\mathbf{M}, 2)$. We recall the concept of Hilbert function.

**Definition 7 (Hilbert function).** Let $I$ be a homogeneous ideal of a polynomial ring $\mathbb{F}[\mathbf{X}]$. Writing $\mathbb{F}[\mathbf{X}]_d$ the (finite dimensional) $\mathbb{F}$-vector space spanned by monomials of degree $d$ and $I_d = I \cap \mathbb{F}[\mathbf{X}]_d$, the Hilbert function of $I$ is defined as

$$ \mathrm{HF}_{\mathbb{F}[\mathbf{X}]/I}(d) \stackrel{\mathrm{def}}{=} \dim_{\mathbb{F}} \mathbb{F}[\mathbf{X}]_d/I_d, \ d \in \mathbb{N}. $$

Experimentally, we always find that the elements of $\mathbf{Pf}(\mathbf{M}, 2)$ are linearly independent, which leads us to state the following as a conjecture.

**Conjecture 1.** $\mathrm{HF}(2) = \binom{r-1}{2} + 1 - \binom{r}{4} = \frac{1}{12}(r-1)(r-2)(r^2 - 3r + 6)$.

Note that it might be useful to consider the implicit Pfaffian modeling. However, since the Hilbert function strongly depends on how the equations are written, one must be careful when changing the modeling. In our case, we can safely do so thanks to the following theorem.

**Theorem 1.** Let $I$ (resp. $J$) be the ideal of the polynomial ring $\mathbf{A}$ (resp. $\mathbf{B}$) produced by the implicit (resp. explicit) modeling. $\mathbf{A}/I$ and $\mathbf{B}/J$ both have a structure of graded $\mathbb{F}$-algebra. There exists a map

$$ \Phi : \mathbf{A}/I \to \mathbf{B}/J $$

that defines an isomorphism of graded $\mathbb{F}$-algebras.

In the following, we sometimes talk about the *Pfaffian modeling associated to a code* without specifying whether it is implicit or explicit, since we only deal with Hilbert functions.

# 4 Hilbert function of a Pfaffian ideal associated with a generic alternant code

## 4.1 The block-diagonal code of relations

In the case of alternant codes, the crux for having rank 2 matrices in $\mathcal{C}_{\mathrm{mat}}$ is to consider [CMT23b] the extension to $\mathbb{F}_{q^m}$ of the dual code. Let us then recall the following fact.
**Proposition 2 ([BMT23], Proposition 14).** For any code $\mathcal{C} \subseteq \mathbb{F}_q^n \subseteq \mathbb{F}_{q^m}^n$, we denote by $\mathcal{C}_{\mathbb{F}_{q^m}}$ the $\mathbb{F}_{q^m}$-vector space spanned by $\mathcal{C}$. Let $\mathcal{C} = \mathcal{A}_r(\mathbf{x}, \mathbf{y})$ be an alternant code of extension degree $m$. Then

$$ (\mathcal{A}_r(\mathbf{x}, \mathbf{y})^{\perp})_{\mathbb{F}_{q^m}} = \sum_{j=0}^{m-1} \mathbf{GRS}_r(\mathbf{x}^{q^j}, \mathbf{y}^{q^j}) $$

With the usual assumption that $\dim_{\mathbb{F}_q} \mathcal{A}_r(\mathbf{x}, \mathbf{y}) = n-rm$, the above sum becomes a direct sum and the sequence $\mathcal{A} = (\mathbf{a}_0, \dots, \mathbf{a}_{r-1}, \mathbf{a}_0^q, \dots, \mathbf{a}_{r-1}^q, \dots, \mathbf{a}_{r-1}^{q^{m-1}})$ is a basis of $(\mathcal{A}_r(\mathbf{x}, \mathbf{y})^{\perp})_{\mathbb{F}_{q^m}}$, called the **canonical basis**.

When $r < q+1$, it follows from the analysis of [FGO+11] that $\mathcal{C}_{rel}(\mathcal{A})$ is spanned by relations like

$$ \mathbf{a}_a^{q^l} \star \mathbf{a}_b^{q^l} = \mathbf{a}_c^{q^l} \star \mathbf{a}_d^{q^l} $$

for $0 \le l < m$ and $0 \le a, b, c, d < r$ such that $a+b=c+d$. This implies that any matrix $A \in \mathcal{C}_{mat}(\mathcal{A})$ has a block-diagonal structure, i.e.

$$ \mathbf{A} = \begin{pmatrix} \mathbf{A}_0 & \dots & \mathbf{0}_r \\ \vdots & \ddots & \vdots \\ \mathbf{0}_r & \dots & \mathbf{A}_{m-1} \end{pmatrix} $$

where $\mathbf{A}_j \in \mathcal{C}_{mat}(\mathbf{a}_0^{q^i}, \dots, \mathbf{a}_{r-1}^{q^j})$ is the matrix associated with some element of the code of quadratic relations of $\mathbf{GRS}_r(\mathbf{x}, \mathbf{y})^{q^j} = \mathbf{GRS}_r(\mathbf{x}^{q^j}, \mathbf{y}^{q^j})$ with respect to its canonical basis.

## 4.2 The Hilbert function at degree 2

The authors of [CMT23b] noticed that the Hilbert function of the Pfaffian modeling at degree 1 can be used as a distinguisher that boils down to the one presented in [FGO+11]. We recall that a generic alternant code is square-distinguishable if it is 1-distinguishable in the sense of [CMT23b]. The Hilbert function at degree 2 can also be used as a distinguisher which seems to work on a larger range of parameters. Our goal here is to find a formula for HF(2) when the code is 2-distinguishable, assuming $r < q+1$.

Let $(B_1, \dots, B_N)$ be the matrices returned by Algorithm 1. As a reminder, $N = \binom{r-1}{2}$. One can find $\text{rank} \le 2$ matrices in $\mathcal{C}_{mat}(\mathcal{A})$ by solving the linear MinRank problem associated with the matrix

$$ \mathbf{M} = \begin{pmatrix} \mathbf{M}_0 & \dots & \mathbf{0}_r \\ \vdots & \ddots & \vdots \\ \mathbf{0}_r & \dots & \mathbf{M}_{m-1} \end{pmatrix} \in \mathbb{F}_{q^m} [X_i \mid 1 \le i \le mN]^{rm \times rm} \quad (3) $$

where $\mathbf{M}_j = \sum_{i=1}^N X_{Nj+i} B_i \in \mathbb{F}_{q^m} [X_i \mid Nj+1 \le i \le (N+1)j]^{r \times r}$ is essentially the matrix associated with a generalized Reed-Solomon code as described in the previous section. The main result of this work is the following theorem.
**Theorem 2.** Assume Conjecture 1 is true. Let $\mathcal{A}_r(\mathbf{x}, \mathbf{y})$ be a generic square-distinguishable alternant code with $r < q + 1$. Then the Hilbert function $HF_A$ at degree 2 of the Pfaffian modeling associated with $\mathcal{A}_r(\mathbf{x}, \mathbf{y})$ is given by

$$HF_A(2) = \frac{m}{12}(r-1)(r-2)(r^2 - 3r + 6).$$

Theorem 2 requires Conjecture 1 to hold, and is also limited to the case $r < q + 1$. Indeed, equality cannot be claimed in general, because there might exist alternant codes for which additional relations occur. Analogously to previous results on the Hilbert function at degree 1 [MT23], the value provided by Theorem 2 for degree 2 still represents a lower bound.

**Corollary 2.** The Hilbert function of the Pfaffian modeling associated with an alternant code of order $r$ and extension degree $m$ satisfies

$$HF_A(2) \geq \frac{m}{12}(r-1)(r-2)(r^2 - 3r + 6).$$

Corollary 2 allows us to state when a generic alternant code is 2-distinguishable. We use here the following definition of $d$-distinguishability

**Definition 8.** An alternant code is $d$-distinguishable if the associated Hilbert function $HF_A$ satisfies

$$HF_A(d) > HF_R(d)$$

where $HF_R$ is the Hilbert series of a random linear code of the same length and dimension as the alternant code.

**Corollary 3.** If $HF_R(2) < \frac{m}{12}(r-1)(r-2)(r^2 - 3r + 6)$, then an alternant code $\mathcal{A}_r$ is 2-distinguishable.

In the case $r < q + 1$, we experimentally found that the Hilbert function at degree 2 for a generic 2-distinguishable alternant code was always equal to $\frac{m}{12}(r-1)(r-2)(r^2 - 3r + 6)$.

# 5 The new distinguisher regime

From [CMT23a], it can be readily deduced that $HF_R(2)$ corresponding to a random linear code of the same dimension $k = n - rm$ as a generic alternant code of length $n$, degree $r$ and extension degree $m$ is given by

$$HF_R(2) = \max \left\{ 0, \frac{1}{2} \left( k^2 - k(s^2 - s + 1) + \frac{s^4 - s^2}{6} \right) \right\}, \quad (4)$$

where $s \stackrel{\text{def}}{=} rm$. Combined with Corollary 3, this implies
**Proposition 3.** For a given degree $r$ and extension degree $m$ and assuming that the field size $q$ satisfies $q \ge r$, a generic alternant code whose dimension satisfies $k > k_0$ where

$$k_0 \stackrel{\text{def}}{=} \frac{s^2 - s + 1 - \sqrt{\frac{s^4}{3} + \frac{2H}{3} - 2s^3 + \frac{11}{3}s^2 - 2s + 1}}{2}$$

with $s \stackrel{\text{def}}{=} rm$, $H \stackrel{\text{def}}{=} m(r-1)(r-2)(r^2 - 3r + 6)$ is 2-distinguishable.

A natural asymptotic choice of parameters is to let $r$ go to infinity and assume that $m = O(\log r)$. This is in general the range which is chosen for $m$, since in order to maximize the decoding capacity one chooses the smallest possible $m$ such that $q^m \ge n$. In such a case, it is straightforward to check that

$$k_0 \stackrel{\sim}{\rightarrow}_{r \rightarrow \infty} \frac{1 - \sqrt{\frac{1 + \frac{2}{m^3}}{3}}}{2} m^2 r^2.$$

When $m$ also goes to infinity with $r$, we have

$$k_0 \sim \frac{1 - \sqrt{\frac{1}{3}}}{2} m^2 r^2 \approx 0.21 m^2 r^2.$$

This is much better than the distinguisher of [FGO+11]. In the regime where $q \ge r$, it is able to distinguish a generic alternant code from a generic linear code when $n > \binom{mr+1}{2} - \frac{m(r-1)(r-2)}{2}$, that is when $k > \binom{mr+1}{2} - rm - \frac{m(r-1)(r-2)}{2}$. This corresponds to $k > k_1 \stackrel{\text{def}}{=} \binom{mr}{2} - \frac{m(r-1)(r-2)}{2}$ with $k_1 = \frac{1-\frac{1}{m}}{2}m^2r^2 + o(m^2r^2)$) as $r \to \infty$ and if $m$ goes to infinity as well, $k_1 \sim \frac{m^2r^2}{2}$.

## References

[ABC+22] Martin Albrecht, Daniel J. Bernstein, Tung Chou, Carlos Cid, Jan Gilcher, Tanja Lange, Varun Maram, Ingo von Maurich, Rafael Mizoczki, Ruben Niederhagen, Edoardo Persichetti, Kenneth Paterson, Christiane Peters, Peter Schwabe, Nicolas Sendrier, Jakub Szefer, Cen Jung Tjhai, Martin Tomlinson, and Wang Wen. Classic McEliece (merger of Classic McEliece and NTS-KEM). https://classic.mceliece.org, November 2022. Fourth round finalist of the NIST post-quantum cryptography call.

[BMT23] Magali Bardet, Rocco Mora, and Jean-Pierre Tillich. Polynomial time key-recovery attack on high rate random alternant codes. CoRR, abs/2304.14757, 2023. To appear in the Transactions on Information Theory.

[CMT23a] Alain Couvreur, Rocco Mora, and Jean-Pierre Tillich. A new approach based on quadratic forms to attack the McEliece cryptosystem. In Jian Guo and Ron Steinfeld, editors, Advances in Cryptology - ASIACRYPT 2023 - 29th International Conference on the Theory and Application of Cryptology and Information Security, Guangzhou, China, December 4-8, 2023, Proceedings, Part IV, volume 14441 of LNCS, pages 3-38. Springer, 2023.
[CMT23b] Alain Couvreur, Rocco Mora, and Jean-Pierre Tillich. A new approach based on quadratic forms to attack the McEliece cryptosystem. *arXiv preprint arXiv:2306.10294*, 2023.

[FGO$^+$11] Jean-Charles Faugère, Valérie Gauthier, Ayoub Otmani, Ludovic Perret, and Jean-Pierre Tillich. A distinguisher for high rate McEliece cryptosystems. In *Proc. IEEE Inf. Theory Workshop- ITW 2011*, pages 282–286, Paraty, Brasil, October 2011.

[McE78] Robert J. McEliece. *A Public-Key System Based on Algebraic Coding Theory*, pages 114–116. Jet Propulsion Lab, 1978. DSN Progress Report 44.

[MS77] F. J. MacWilliams and N. J. A. Sloane. *The Theory of Error Correcting Codes*. North Holland, 1977.

[MT23] Rocco Mora and Jean-Pierre Tillich. On the dimension and structure of the square of the dual of a Goppa code. *Des. Codes Cryptogr.*, 91(4):1351–1372, 2023.

[Wim12] Michael Wimmer. Algorithm923: Efficient numerical computation of the Pfaffian for dense and banded skew-symmetric matrices. *ACM Trans. Math. Software*, 38(4), aug 2012.