# Understanding the new distinguisher of alternating 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 alternating codes at degree 2. Designs, Codes and Cryptography, 2025, 93 (8), pp.3083-3105. 10.1007/S10623-025-01626-8. hal-05461754

HAL Id: hal-05461754

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

Submitted on 16 Jan 2026

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 CC BY 4.0 - Attribution - International License
# Understanding the new distinguisher of
alternating 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.**

**Abstract.** Distinguishing Goppa codes or al-
ternant codes from generic linear codes [?] has been shown
to be a first step before being able to attack McEliece
cryptosystem based on those codes [?]. Whereas the dis-
tinguisher of [?] is only able to distinguish Goppa codes or
alternant codes of rate very close to 1, in [?] a much more
powerful (and more general) distinguisher was proposed. It
is based on computing the Hilbert series {HF(d), d ∈ N} of
a Pfaffian modeling. The distinguisher of [?] can be inter-
preted 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 al-
ternant codes in a much broader regime of rates as the one
of [?]. 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) provides a lower bound in gen-
eral. The value of 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. This shows that the new distinguisher improves
significantly upon the one given in [?].

# 1 Introduction

McEliece cryptosystem [?] 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 [?] 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 expensive than message recovery attacks. The
latter ignore completely the algebraic structure and aim just at decoding
a generic linear code.
In [?] 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 from 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 alternant codes, as long as their rate is high enough [?]. It took a while to transform this distinguisher into an algorithm recovering the algebraic structure of the Goppa or the alternant code. This has recently been (partly) achieved in [?, ?]. Unfortunately, the specific case of binary Goppa codes could not be handled by these two papers.

Interestingly enough, [?] 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 odd characteristic and rank 2 in even characteristic, 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 [?] 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 \in \mathbb{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 [?, Conjecture 1] and the smallest degree for which the Hilbert series vanishes can be computed. Interestingly in the case 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_R(d), d \in \mathbb{N}$} of a generic linear code is well understood in [?], the Hilbert series {$HF_A(d), d \in \mathbb{N}$} that corresponds to an alternant code is much more difficult to analyze. 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 [?].

The aim of this work is to understand the value of $HF_A(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_A(2)$ in general. It turns out that the distinguisher based on $HF_A(2) \neq HF_R(2)$ works for a much broader set of parameters than the distinguisher $HF_A(1) \neq HF_R(1)$ (which is equivalent to the one of [?]). It also shows that the parameter range for which $HF_A(2) \neq HF_R(2)$ is much broader than the range of parameters for which $HF_R(2) = 0$. This improves for certain parameters the distinguisher of [?] and could also open the way to key attacks in the regime of parameters for which $HF_A(2) \neq HF_R(2)$, much in the same way that [?, ?] were a first step before the attacks of [?, ?]. 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. It is also worthwhile to note that another generalization of the distinguisher of [?] has been proposed recently in [?] and has lead to a breakthrough result, namely a distinguisher of subexponential complexity of Goppa or alternant codes which works even in the constant rate regime and for any finite characteristic. A crucial ingredient to get this subexponential complexity is shortening the dual of the alternant or Goppa code and then applying the algebraic distinguisher to it. It would be interesting to understand how the $HF_A$ distinguisher behaves at degree 2 when applied to such shortened codes.

## 2 Preliminaries

**General notation.** 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. If we just want to indicate that we deal with an arbitrary field we simply write $\mathbb{F}$.

**Vector and matrix notation.** Vectors are indicated by lowercase bold letters $\mathbf{x}$ and matrices by uppercase bold letters $\mathbf{M}$. Given a function $f$ acting on $\mathbb{F}$ and a vector $\mathbf{x} = (x_i)_{1\le i\le n} \in \mathbb{F}^n$, the expression $f(\mathbf{x})$ is the component-wise mapping of $f$ on $\mathbf{x}$, i.e. $f(\mathbf{x}) = (f(x_i))_{1\le i\le n}$. We will even apply this to functions $f$ acting on $\mathbb{F} \times \mathbb{F}$: for instance for two vectors $\mathbf{x}$ and $\mathbf{y}$ in $\mathbb{F}^n$ and two positive integers $a$ and $b$ we denote by $\mathbf{x}^a \mathbf{y}^b$ the vector $(x_i^a y_i^b)_{1\le i\le n}$.

### Reed-Solomon and alternant codes.

**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 (GRS in short) 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}\}. $$

Alternant codes are subfield subcodes of GRS codes. It will be convenient here to follow the point of view of [?] which defines them in terms of the dual GRS code (which is itself a GRS code [?]).

**Definition 2 (Alternant code).** Let $r, m$ be two integers, $\mathbf{x} \in \mathbb{F}_{q^m}^n$ be a support (i.e. an $n$-tuple of distinct elements of $\mathbb{F}_{q^m}$), and $\mathbf{y} \in (\mathbb{F}_{q^m}^\times)^n$ be a multiplier. The alternant code over $\mathbb{F}_q$ of degree $r$, support $\mathbf{x}$ and multiplier $\mathbf{y}$ is the subfield subcode over $\mathbb{F}_q$ of $\mathbf{GRS}_r(\mathbf{x}, \mathbf{y})^\perp$:

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

$m$ is called the extension degree of the alternant code.

We know that $[?]\dim_{\mathbb{F}_q}\mathcal{A}_r(\mathbf{x}, \mathbf{y}) \ge n - rm$ and this bound is generally tight. Goppa codes are a particular family of alternant codes. They are defined as

**Definition 3 (Goppa code).** Let $\mathbf{x} \in \mathbb{F}_{q^m}^n$ be a support vector and $\Gamma \in \mathbb{F}_{q^m}^m[z]$ a polynomial of degree $r$ such that $\Gamma(x_i) \ne 0$ for all $i \in \{1, \dots, n\}$. The Goppa code of degree $r$ with support $\mathbf{x}$ and Goppa polynomial $\Gamma$ is defined as $\mathcal{G}(\mathbf{x}, \Gamma) \stackrel{\text{def}}{=} \mathcal{A}_r(\mathbf{x}, \mathbf{y})$, where $\mathbf{y} \stackrel{\text{def}}{=} \left( \frac{1}{\Gamma(x_1)}, \dots, \frac{1}{\Gamma(x_n)} \right)$.

**Schur/component-wise product.** The family of codes defined above can be conveniently generated by vectors that are component-wise (also called Schur) products of $\mathbf{x}$ and $\mathbf{y}$. Recall that this product is defined as

**Definition 4.** The component-wise product of two vectors $\mathbf{a}, \mathbf{b} \in \mathbb{F}^n$ is defined as

$$ \mathbf{a} \star \mathbf{b} \stackrel{\text{def}}{=} (a_1 b_1, \dots, a_n b_n). $$

The $i$-th power of a vector $\mathbf{a}$ is defined by $\mathbf{a}^i = \underbrace{\mathbf{a} \star \dots \star \mathbf{a}}_{i \text{ times}}$. This notation is compatible with the notation $f(\mathbf{x})$ introduced above. Sometimes we will drop the star, i.e. $\mathbf{y}\mathbf{x}^i = \mathbf{y} \star \mathbf{x}^i$.

Since any polynomial $P$ in $\mathbb{F}[z]$ of degree $< r$ can be written as a linear combination over $\mathbb{F}$ of powers of $z$ of degree $< r$, by using the notation given above we can view a GRS code as

$$ \mathbf{GRS}_r(\mathbf{x}, \mathbf{y}) \stackrel{\text{def}}{=} \langle \mathbf{x}^a \mathbf{y} \mid 0 \le a < r \rangle_{\mathbb{F}_q}. $$

The Schur product is also an essential ingredient for distinguishing GRS codes or alternant codes from random codes. The Schur/component-wise product of codes is defined by
**Definition 5.** The component-wise product of codes $\mathcal{C}, \mathcal{D}$ over $\mathbb{F}$ with the same length $n$ is defined as

$$ \mathcal{C} \star \mathcal{D} \stackrel{\text{def}}{=} \langle \mathbf{c} \star \mathbf{d} | \mathbf{c} \in \mathcal{C}, \mathbf{d} \in \mathcal{D} \rangle_{\mathbb{F}}. $$

If $\mathcal{C} = \mathcal{D}$, we call $\mathcal{C}^{*2} \stackrel{\text{def}}{=} \mathcal{C} \star \mathcal{C}$ the square code of $\mathcal{C}$.

GRS codes turn out to display a very peculiar property with respect to the square of codes. It is readily seen that $\dim \mathcal{C}^{*2} \le \min(n, \binom{k+1}{2})$ where $k$ and $n$ are respectively the dimension and length of $\mathcal{C}$. For random codes, the upper-bound is almost always an equality [?], whereas the situation for GRS codes is completely different: in this case, we namely have

$$ \dim \mathcal{C}^{*2} = \min(n, 2k-1). \qquad (1) $$

The reason of this particular behavior comes from the fact that GRS codes are polynomial evaluation codes. Since the Schur product of two polynomial evaluations of degree $\deg P \le k-1$ and $\deg Q \le k-1$ respectively is itself a polynomial evaluation of degree $\deg(P \cdot Q) = \deg P + \deg Q < 2k-1$:

$$ (y_i P(x_i))_i \star (y_i Q(x_i))_i = (y_i^2 P \cdot Q(x_i))_i, $$

it is readily seen that

$$ \mathbf{GRS}_k(\mathbf{x}, \mathbf{y})^{*2} = \mathbf{GRS}_{2k-1}(\mathbf{x}, \mathbf{y} \star \mathbf{y}), \qquad (2) $$

which explains (??). In a sense, the square code construction “sees” the polynomial structure of the GRS code. Similarly, alternant codes inherit the polynomial structure of the GRS super-code and can also be detected by taking the square of them [?] (or their dual code [?]).

**Quadratic relations over a basis of a code.** The aforementioned distinguisher is based on computing the dimension of square codes or on computing related quantities. A new way of approaching the problem of distinguishing such codes has been introduced in [?] and consists instead in considering *linear relations* between the Schur products of basis elements of the code or the dual code. Higher order relations were studied in [?] and lead to a powerful distinguisher. This new approach may be described using the framework detailed below.

For any integer $k$, we denote with

$$ S_k \stackrel{\text{def}}{=} \mathbb{F}[x_1, \dots, x_k] = \bigoplus_{d \ge 0} S_k^{(d)} $$

the polynomial ring in $k$ variables over $\mathbb{F}$, graded by degree, where $S_k^{(d)}$ stands for the homogeneous component of degree $d$. Elements of $S_k^{(2)}$ are referred to as *quadratic forms*. Given a list $\mathcal{V} = (\mathbf{v}_1, \dots, \mathbf{v}_k)$ of $k$ vectors of length $n$ over $\mathbb{F}$, there is a natural evaluation map

$$ \mathrm{ev}_{\mathcal{V}} : S_k \to \mathbb{F}^n $$
defined on each homogeneous component by

$$ \mathrm{ev}_{\mathcal{V}}^{(d)} \stackrel{\mathrm{def}}{=} \mathrm{ev}_{\mathcal{V}}|_{S_k^{(d)}} : \left\{ \sum_{i_1 \le \dots \le i_d} S_k^{(d)} \underset{\mathbb{F}^n}{\longrightarrow} \sum_{i_1 \le \dots \le i_d} c_{i_1, \dots, i_d} \mathbf{v}_{i_1} \star \dots \star \mathbf{v}_{i_d} \right. $$

and then extended to $S_k$ by linearity.

**Definition 6.** Let $\mathcal{C}$ be an $[n, k]$-linear code over $\mathbb{F}$, and let $\mathcal{V} \stackrel{\mathrm{def}}{=} (\mathbf{v}_1, \dots, \mathbf{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}_{\mathrm{rel}}(\mathcal{V}) \stackrel{\mathrm{def}}{=} \ker \mathrm{ev}_{\mathcal{V}}^{(2)}$.

In this setting, the code of quadratic relations is seen as a linear subspace of $S_k^{(2)}$. A quadratic form

$$ f = \sum_{i \le j} c_{i,j} x_i x_j \in S_k^{(2)} $$

is associated to a matrix

$$ \mathrm{Mat}(f) \stackrel{\mathrm{def}}{=} \begin{pmatrix} 2c_{1,1} & c_{1,2} & c_{1,3} & \dots & c_{1,k} \\ c_{1,2} & 2c_{2,2} & c_{2,3} & \dots & c_{2,k} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ c_{1,k} & c_{2,k} & c_{3,k} & \dots & 2c_{k,k} \end{pmatrix}, $$

which is skew-symmetric, i.e symmetric with a zero diagonal, when $\mathbb{F}$ has characteristic 2. We may thus define the code of matrices

$$ \mathcal{C}_{\mathrm{mat}}(\mathcal{V}) \stackrel{\mathrm{def}}{=} \{\mathrm{Mat}(f) \mid f \in \mathcal{C}_{\mathrm{rel}}(\mathcal{V})\}. $$

This link between quadratic forms and matrices is a powerful tool for analyzing quadratic relations. For instance, the rank of the matrix of a quadratic form may provide insightful information about the “shortness” of the form. In the following of this work, we may refer to the rank of $\mathrm{Mat}(f)$ as the *rank* of the quadratic form $f$.

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

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

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

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

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

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

The key for understanding $\mathrm{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

The behavior of $\mathcal{C}_{rel}$ for a GRS code is easily seen using the very struc- tured basis of these codes that we introduce in the following.

**Definition 7 (Canonical basis).** $\mathcal{A} = (a_0, \dots, a_{r-1})$, where $a_i = x^i y^j$ forms a basis of $\text{GRS}_r(x, y)$, which we call a canonical basis.

The codewords of a canonical basis $\mathcal{A}$ are subject to very simple quadratic relations, that we will call fundamental.

**Definition 8 (Fundamental relations).** We define the space of fundamental quadratic forms as

$$ \mathcal{F}_r \stackrel{\text{def}}{=} \langle x_i x_j - x_k x_l \mid 0 \le i, j, k, l < r, i + j = k + l \rangle_{\mathbb{F}_q}. $$

It turns out that

**Proposition 1.** $\dim \mathcal{F}_r = \binom{r-1}{2}$.

*Proof.* Consider the Veronese embedding

$$ \nu: \left\{ \begin{array}{l} \mathbb{P}^1 \quad \to \mathbb{P}^{r-1} \\ (x:y) \quad \mapsto (y^{r-1} : xy^{r-2} : \dots : x^{r-1}), \end{array} \right. $$

and define $\mathcal{Y}$ as the image of $\nu$. Clearly the ideal generated by $\mathcal{F}_r$ is a subset of the ideal of $\mathcal{Y}$. Besides, it is well-known (see [?]) that the ideal of $\mathcal{Y}$ is given by the determinantal ideal generated by the $2 \times 2$ minors of the following $2 \times (r-1)$ matrix

$$ \begin{pmatrix} x_0 & x_1 & \dots & x_{r-2} \\ x_1 & x_2 & \dots & x_{r-1} \end{pmatrix}. \qquad (3) $$

Since each of these minors actually belong to $\mathcal{F}_r$, we conclude that the ideal generated $\mathcal{F}_r$ is the same as the above-mentioned determinantal ideal, i.e the ideal of $\mathcal{Y}$. Their homogeneous component of degree 2 coin- cide as well, one being given by $\mathcal{F}_r$ exactly, the other one being spanned by the $\binom{r-1}{2}$ minors of size $2 \times 2$ of (3). Therefore we only need to show that these minors are linearly independent to prove the proposition. As- suming they are not, there must exist two indices $i < j$ such that the minor

$$ \begin{vmatrix} x_i & x_j \\ x_{i+1} & x_{j+1} \end{vmatrix} = x_i x_{j+1} - x_{i+1} x_j $$

is a linear combination of other minors of (3). Now consider the poly- nomial matrix

$$ \begin{pmatrix} x_0 & \dots & x_{i-1} & x_{i+1} & \dots & x_{j-1} & x_{j+1} & \dots & x_{r-2} \\ x_1 & \dots & x_i & x_{i+2} & \dots & x_j & x_{j+2} & \dots & x_{r-1} \end{pmatrix}, $$

which is nothing but (3) where columns $i$ and $j$ have been removed. Our assumption implies that if the above matrix is of rank $< 2$, then so is (3). Note that this is the case if and only if the two rows are proportional. For (3), this translates into the $x_i$'s being in geometric progression, but not for the submatrix given above, since its two rows
being proportional does not require $x_{i+1}$ to be a multiple of $x_i$. One may therefore choose a specialization (which may lie in an extension of $\mathbb{F}$) where the rows of the submatrix are proportional without the rows of (??) being proportional. The submatrix would have rank < 2 while (??) would not. This contradicts the minor produced by columns $i, j$ being linearly dependent from the others. □

It is readily seen that whenever $\mathcal{A}$ is a canonical basis of some GRS code, then $\mathcal{F}_r \subseteq \mathcal{C}_{\text{rel}}(\mathcal{A})$. The following proposition gives a condition for the last inclusion to be an equality.

**Proposition 2.** If $2r - 1 \le n$, then $\mathcal{C}_{\text{rel}}(\mathcal{A}) = \mathcal{F}_r$.

*Proof.* We first recall that $\mathbf{GRS}_r(\mathbf{x}, \mathbf{y})^{*2} = \mathbf{GRS}_{2r-1}(\mathbf{x}, \mathbf{y}^2)$. We have

$$ \begin{aligned} \dim\mathcal{C}_{\text{rel}}(\mathcal{A}) &= \binom{r+1}{2} - \dim\mathbf{GRS}_r(\mathbf{x}, \mathbf{y})^{*2} \quad (\text{by } [?]||\text{Prop. 5}] \\ &= \frac{1}{2}r(r+1) - (2r-1) \quad (\text{by (??)}) \\ &= \frac{1}{2}(r^2 - 3r + 2) \\ &= \frac{1}{2}(r-1)(r-2) \\ &= \binom{r-1}{2}. \end{aligned} $$

By Proposition ??, $\mathcal{F}_r$ is a subspace of $\mathcal{C}_{\text{rel}}(\mathcal{A})$ of codimension 0, i.e $\mathcal{C}_{\text{rel}}(\mathcal{A}) = \mathcal{F}_r$. □

We are therefore interested in the vector space $\mathcal{F}_r$. One could write a basis of $\mathcal{F}_r$ using the determinantal ideal introduced in the proof of Proposition ?? . We will use a different method so as to extract a basis from the generators of $\mathcal{F}_r$ which give a nice structure to the matrix space spanned by the matrices of the fundamental quadratic forms. Start with the following decomposition

$$ \mathcal{F}_r = \bigoplus_{s=2}^{2r-4} \mathcal{F}_{r,s}, $$

where $\mathcal{F}_{r,s} \stackrel{\text{def}}{=} \langle x_ix_j - x_kx_l \mid 0 \le i, j, k, l < r, i + j = k + l = s \rangle_{\mathbb{F}_q}$. The indices of the sum run from 2 to $2r-4$ since $\mathcal{F}_{r,s} = \{0\}$ when $s$ is outside this range. To write a basis of $\mathcal{F}_r$, it suffices to write a basis of $\mathcal{F}_{r,s}$ for all possible values of $s$. To this end, our idea is to first choose $k \le l$ as close to $\lfloor \frac{s}{2} \rfloor$ as possible, then choose the lowest $i$ and the greatest $j$ such that $i + j = s$. A basis of $\mathcal{F}_{r,s}$ will then be given by the sequence $(x_{i+t}x_{j-t} - x_kx_l)_{0 \le t < k-i}$. The first bases may be found in the following table.

More formally, we get a basis of $\mathcal{F}_r$ by running Algorithm ?? .

**Theorem 1.** *Algorithm ?? generates a basis of $\mathcal{F}_r$.*
<table><caption>**Table 1.** Basis of $\mathcal{F}_{r,s}$ for the first values of $s$.</caption><thead><tr><th>value of s</th><th>Basis of F<sub>r,s</sub></th></tr></thead><tbody><tr><td>2</td><td>x<sub>0</sub>x<sub>2</sub> - x<sub>1</sub><sup>2</sup></td></tr><tr><td>3</td><td>x<sub>0</sub>x<sub>3</sub> - x<sub>1</sub>x<sub>2</sub></td></tr><tr><td>4</td><td>x<sub>0</sub>x<sub>4</sub> - x<sub>2</sub><sup>2</sup>, x<sub>1</sub>x<sub>3</sub> - x<sub>2</sub><sup>2</sup></td></tr><tr><td>...</td><td>...</td></tr></tbody></table>

**Algorithm 1** Generation of a basis $\mathcal{B} = (f_1, \dots, f_N)$ of $\mathcal{F}_r$

**Input:** an integer $r \ge 3$
**Output:** A basis $(f_1, \dots, f_N)$ of $\mathcal{F}_r$
$\mathcal{B} \leftarrow \emptyset$
$s \leftarrow 2$
**while** $s \le 2r - 4$ **do**
  $i \leftarrow \max\{0, s - r + 1\}$
  $j \leftarrow s - i$
  **if** $s \bmod 2 = 0$ **then**
    $k \leftarrow s/2$
    $l \leftarrow s/2$
  **else**
    $k \leftarrow \frac{s-1}{2}$
    $l \leftarrow \frac{s+1}{2}$
  $\mathcal{B} \leftarrow \mathcal{B} \cup \{x_{i+t}x_{j-t} - x_kx_l \mid 0 \le t < k - i\}$
  $s \leftarrow s + 1$
**return** $\mathcal{B}$

$\triangleright N = \binom{r-1}{2}$.

*Proof.* Let $F = \{f_1, \dots, f_N\}$ be the sequence of quadratic forms returned by Algorithm ?? . Let us prove that $F$ generates $\mathcal{F}_r$. Consider a nonzero quadratic form $f = x_i x_j - x_k x_l$ such that $i + j = k + l = s$. Without loss of generality, we may assume $i < j$ and $k \le l$. If $l - k \in \{0, 1\}$, then $f$ actually is an element of $F$. Now suppose that $l - k \ge 2$, and define $k', l'$ by

$$ (k', l') = \begin{cases} \left(\frac{s}{2}, \frac{s}{2}\right) & \text{if } s \bmod 2 = 0 \\ \left(\frac{s-1}{2}, \frac{s+1}{2}\right) & \text{otherwise.} \end{cases} $$

We notice that both $g = x_i x_j - x_{k'} x_{l'}$ and $h = x_k x_l - x_{k'} x_{l'}$ belong to $F$, and that $f = g - h$. Therefore $F$ is a generating set of $\mathcal{F}_r$.

Now, for each quadratic form $f = x_i x_j - x_k x_l \in F$, with $i < j$ and $k \le l$, we see that $f$ is the only quadratic form in $F$ having $x_i x_j$ among its monomials. This implies that the elements of $F$ are linearly independent.

□

Combining Proposition ?? and Theorem ?? , we get

**Corollary 1.** When $2r - 1 \le n$, Algorithm ?? returns a basis of $\mathcal{C}_{rel}(\mathcal{A})$.
The reason why we wrote this algorithm instead of simply considering the determinantal ideal will be clarified in Remark ??.

## 3.2 Rank 2 matrices in $\mathcal{C}_{\text{mat}}$

Among the fundamental relations, the ones of the form

$$x_i x_j - x_k^2,$$

when $i + j = 2k$, give a matrix of rank 2 when the base field $\mathbb{F}_q$ of $S_r$ is of characteristic 2. This suggests that there are many quadratic relations of rank 2 in $\mathcal{C}_{\text{mat}}$. We may detect this interesting feature of the matrix code of relations related to a GRS code using an algebraic system.

**Implicit modeling of [?].** To find rank 2 matrices in $\mathcal{C}_{\text{mat}}$, we may adopt the inverse point of view, i.e finding matrices belonging to $\mathcal{C}_{\text{mat}}$ inside the variety of skew-symmetric matrices of rank $\le 2$. To describe this variety, we first recall the following fact.

**Fact 1** Let $\mathbf{A} = (a_{i,j})_{1\le i,j\le n}$ be a square matrix such that $a_{i,j} = -a_{j,i}$ for all $i, j$, and $a_{i,i} = 0$ for all $i$. Then the determinant of $\mathbf{A}$ can be expressed as the square of a polynomial expression in the coefficients $a_{i,j}$. This polynomial is 0 if $n$ is odd, and has degree $n/2$ otherwise. We denote with $\text{Pf}(\mathbf{A})$ this polynomial expression, and call it the Pfaffian of $\mathbf{A}$. For example,

$$\text{Pf} \begin{pmatrix} 0 & a & b & c \\ -a & 0 & d & e \\ -b & -d & 0 & f \\ -c & -e & -f & 0 \end{pmatrix} = af - be + dc.$$

We will now describe the algebraic variety of rank $\le 2$ skew-symmetric matrices in characteristic 2. To begin with, write 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 [?]:

$$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 (4)$$

The left-hand side of Equation (??) is nothing but the Pfaffian of the submatrix of $M$ obtained by taking rows and columns indexed by $i, j, k, l$. This is why we will call it a Pfaffian of $M$. More generally, if $N$ is any skew-symmetric matrix whose coefficients lie in some polynomial ring, we denote by $\text{Pf}(N, 2)$ the set of polynomials given by the Pfaffians
of all submatrices of size 4 × 4 extracted from N using the same set of indices for rows and columns (such submatrices are sometimes called *principal submatrices*). Adding linear equations expressing the fact that M belongs to C<sub>mat</sub>, we obtain the first algebraic modeling of rank ≤ 2 matrices in C<sub>mat</sub>:

**Modeling 2 (Implicit modeling)** The implicit modeling of rank ≤ 2 matrices in C<sub>mat</sub> consists of the ideal I generated by the (r/4) Pfaffians of the generic skew-symmetric r × r matrix M and parity-check equations expressing the fact that M belongs to C<sub>mat</sub>.

**Remark 1.** We call this modeling *implicit* because the matrix code is defined through implicit (i.e parity-check) equations. In the following section, we will detail another algebraic modeling, called *explicit*, because in this modeling the matrix code is defined by a parametrization.

**Explicit modeling.** Another strategy is to compute a basis (B<sub>1</sub>, ..., B<sub>N</sub>) of C<sub>mat</sub> and solve algebraically the MinRank problem with matrix

$$ M \stackrel{\text{def}}{=} \sum_{i=1}^{N} X_i B_i \qquad (5) $$

by writing that all the Pfaffians corresponding to the 4 × 4 principal minors are zero. For example, when C<sub>mat</sub> is the matrix code of relations of a square-distinguishable GRS code of dimension r with respect to a canonical basis, the matrices B<sub>i</sub> may be taken as the matrices of the quadratic forms f<sub>i</sub> returned by Algorithm ?? . Here are a few examples of M for small values of r in such a case.

$$ M_{(r=5)} = \begin{pmatrix} 0 & 0 & X_1 & X_2 & X_4 \\ 0 & 0 & X_2 & X_3 & 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_2 & X_3 & X_5 & X_8 \\ 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 & X_{11} & X_{12} \\ X_6 & X_8 & X_{13} & X_{14} & X_{15} & X_{16} \end{pmatrix}, $$

$$ M_{(r=8)} = \begin{pmatrix} 0 & 0 & X_1 & X_2 & X_4 & X_6 & X_9 & X_{12} \\ 0 & 0 & X_2 & X_3 & X_5 & X_8 & X_{11} & X_{15} \\ X_1 & X_2 & 0 & X_5 + X_6 & X_7 & X_{10} & X_{14} & X_{17} \\ X_2 & X_3 & X_5 + X_6 & 0 & X_{10} + X_{11} + X_{12} & X_{13} & X_{16} & X_{19} \\ X_4 & X_5 & X_7 & X_{10} + X_{11} + X_{12} & 0 & X_{16} + X_{17} & X_{18} & X_{20} \\ X_6 & X_8 & X_{10} & X_{13} & X_{16} + X_{17} & 0 & X_{20} & X_{21} \\ X_9 & X_{11} & X_{14} & X_{16} & X_{18} & X_{20} & 0 & 0 \\ X_{12} & X_{15} & X_{17} & X_{19} & X_{20} & X_{21} & 0 & 0 \end{pmatrix}. $$

These matrices have a very special shape that is produced on purpose by Algorithm ?? :

**Remark 2.** When M is written using the matrices returned by Algorithm ?? ,
- the coefficient of $\mathcal{M}$ at $(i, j)$ is a single variable, unless $i = j \pm 1$;

- any variable $X_i$ appears in exactly one anti-diagonal of $\mathcal{M}$;

- when the coefficient of $\mathcal{M}$ at $(i, j)$ is not a single variable (i.e $i = j \pm 1$), it actually is nothing but the sum of all variables appearing in the same anti-diagonal defined by $i' + j' = i + j$.

These remarks will be crucial in the proof of Theorem ?? thereafter. Let us now detail the explicit modeling. The matrix $\mathcal{M}$ is the generic matrix in $\mathcal{C}_{\text{mat}}$. Since it is skew-symmetric, one may consider its Pfaffians of degree 2, i.e the Pfaffians of all $4 \times 4$ principal submatrices of $\mathcal{M}$, which leads to the following algebraic modeling.

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

$$m_{i,j}m_{k,l} + m_{i,k}m_{j,l} + m_{i,l}m_{j,k} = 0.$$

where each coefficient $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 $\text{Pf}(\mathcal{M}, 2)$. We recall the concept of Hilbert function.

**Definition 9 (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

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

Experimentally, we always find that the elements of $\text{Pf}(\mathcal{M}, 2)$ are linearly independent when $2r - 1 \le n$, i.e when the matrix $\mathcal{M}$ is the generic matrix in the matrix space of fundamental relations. This leads us to state the following as a conjecture.

**Conjecture 1.** When $2r - 1 \le n$, the Hilbert function at degree 2 for the explicit Pfaffian modeling for rank $\le 2$ matrices in $\mathcal{C}_{\text{mat}}$ is given by

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

**Remark 3.** We emphasize that the generic matrix $\mathcal{M}$ in $\mathcal{C}_{\text{mat}}(\mathcal{A})$ obtained by taking the matrices of the forms $f_i$'s returned by Algorithm ?? only depends on $r$. Therefore, Conjecture ?? may be checked easily for all parameters $r, q$ used in cryptography.

We have introduced two algebraic modelings for solving the same problem: finding rank $\le 2$ matrices in $\mathcal{C}_{\text{mat}}(\mathcal{A})$ when $\mathcal{A}$ is a canonical basis of some GRS code. 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 2.** Let $I$ (resp. $J$) be the ideal of the polynomial ring $R$ (resp. $S$) produced by the implicit (resp. explicit) modeling. $R/I$ and $S/J$ both have a structure of graded $\mathbb{F}$-algebra. There exists a map

$$ \Phi : R/I \to S/J $$

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

This theorem is proved in the appendix. Note that it implies that the Hilbert function of the (implicit or explicit) Pfaffian modeling is also invariant under a change of basis. In the following, we sometimes talk about the Pfaffian modeling associated with 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}_{\text{mat}}$ is to consider $[?]$ the extension to $\mathbb{F}_{q^m}$ of the dual code. Let us then recall the following fact.

**Proposition 3** ([?], **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} \text{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 $[?]$ that $\mathcal{C}_{\text{rel}}(\mathcal{A})$ is spanned by

$$ x_{rl+a}x_{rl+b} - x_{rl+c}x_{rl+d} $$

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

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

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

**Remark 4.** In other words, when $\mathcal{A} = (\mathcal{A}_0, \mathcal{A}_0^q, \dots, \mathcal{A}_0^{q^{m-1}})$ where $\mathcal{A}_0 = (\mathbf{y}, \dots, \mathbf{x}^{r-1}\mathbf{y})$, we have $\mathcal{C}_{\text{mat}}(\mathcal{A}) \simeq \mathcal{C}_{\text{mat}}(\mathcal{A}_0)^m$, the isomorphism being given explicitly by

$$ \left\{ \begin{array}{ll} \mathcal{C}_{\text{mat}}(\mathcal{A}_0)^m & \to \mathcal{C}_{\text{mat}}(\mathcal{A}) \\ (\mathcal{A}_0, \dots, \mathcal{A}_{m-1}) & \mapsto \mathcal{A}_0 \oplus \dots \oplus \mathcal{A}_{m-1}. \end{array} \right. $$
## 4.2 The Hilbert function at degree 2

The authors of [?] 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 [?]. We recall that a generic alternant code is square-distinguishable if it is 1-distinguishable in the sense of [?]. 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 square-distinguishable, assuming $r < q + 1$. According to the previous discussion, the generic matrix $M$ in $\mathscr{C}_{\mathrm{mat}}(\mathcal{A})$ also has a block-diagonal structure in the generic case. More precisely, it can be written like

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

where each $M_i = X_{N_{i+1}}B_1 + \dots + X_{(N+1)_i}B_N$ and where the $B_j$'s stand for the matrices of the quadratic forms $f_j$'s returned by Algorithm ?? . For such a block-diagonal structure, computing the Hilbert function at degree 2 becomes doable.

**Theorem 3.** Assume that Conjecture ?? holds. Let $M$ be the generic matrix of Equation (??). The Hilbert function $HF_A$ at degree 2 of the ideal generated by $\mathbf{Pf}(M, 2)$ is given by

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

*Proof.* Here we use the explicit modeling for performing the analysis. The theorem is thus about the dimension of the vector space spanned by $\mathbf{Pf}(M, 2)$. We will describe all the nonzero elements of $\mathbf{Pf}(M, 2)$ and inspect their linear dependencies. To do so, we will consider 4 cases. If $1 \le i_1 < \dots < i_p$, the notation $M[i_1, \dots, i_p]$ denotes the extracted matrix of $M$ where rows and columns $i_1, \dots, i_p$ have been taken. Let $1 \le i < j < k < l \le rm$.

* Case 1: the submatrix $M[i, j, k, l]$ is a submatrix of some $M_s$. The corresponding Pfaffian of $M$ is actually a Pfaffian of $M_s$. Conjecture ?? states that these polynomials are linearly independent. Moreover, the Pfaffians of different blocks $M_s, M_t$ are linearly independent since they are polynomials in different variables.

* Case 2: the submatrix $M[i, j]$ is a submatrix of some $M_s$ and the submatrix $M[k, l]$ is a submatrix of some $M_t$ with $s < t$, and no coefficient is taken right above/under the diagonal. In such a case, the submatrix has the form

$$ M[i, j, k, l] = \begin{pmatrix} 0 & X_a & 0 & 0 \\ X_a & 0 & 0 & 0 \\ 0 & 0 & 0 & X_b \\ 0 & 0 & X_b & 0 \end{pmatrix} $$

with $N_s + 1 \le a < (N+1)s$, $N_t + 1 \le b < (N+1)t$ and its Pfaffian is $X_a X_b$. Indeed, the coefficients $m_{i,k}$ and $m_{j,l}$ are 0 because of
the block-diagonal structure, and $m_{i,j}$ and $m_{k,l}$ are single variables since $i \neq j \pm 1$ and $k \neq l \pm 1$ (see Section 3). This gives $N \times \binom{m}{2}$ polynomials that are linearly independent. They are also not in the vector space spanned by the polynomials of case 1 since none of the latter polynomials have a monomial in common with the Pfaffians of case 2.

* Case 3: same as case 2, but some coefficients may be taken right above/under the diagonal. The thing here is that there is no simple way to express the corresponding coefficients, as they might be sums of variables and not variables alone. However, as we noticed in Section 3, when a coefficient of $M$ is not a single variable, then it is the sum of other coefficients of $M$ that are single variables. Each time some coefficient of $M$ is a sum of variables, all variables appearing in the coefficient also appear alone in the same anti-diagonal. In other words, we may have to consider some Pfaffians of the form

$$ \mathrm{Pf}(M[i, j, k, l]) = \mathrm{Pf} \begin{pmatrix} 0 & \alpha & 0 & 0 \\ \alpha & 0 & 0 & 0 \\ 0 & 0 & 0 & \beta \\ 0 & 0 & \beta & 0 \end{pmatrix} = \alpha(X_{sN+1}, \dots, X_{(s+1)N}) \times \beta(X_{tN+1}, \dots, X_{(t+1)N}) $$

where $\alpha, \beta$ are degree-1 polynomials of the appropriate variables. We see that the Pfaffian we obtain is a linear combination of the Pfaffians obtained in case 2, hence they do not change the dimension of the Pfaffian ideal at degree 2.

* Case 4: at least one of the indices $i, j, k, l$ is alone in its range $[sN+1, (s+1)N]$, say $i$. In this case, the first column of the corresponding submatrix is zero, hence its Pfaffian itself is zero.

The Hilbert function at degree 2 is the number of monomials of degree 2 minus the number of algebraically independent Pfaffians of $M$. Among all monomials of degree 2, we have the monomials $X_a X_b$ where the variables $X_a, X_b$ do not appear in the same submatrix $M_s$. We saw in case 2 that these monomials appear in the Pfaffians of $M$. All the other monomials are of the form $X_a X_b$ where $X_a$ and $X_b$ do appear in the same block. For each block $M_s$, the number of monomials $X_a X_b$ minus the number of algebraically independent Pfaffians of $M_s$ is exactly given by $\frac{1}{12}(r-1)(r-2)(r^2-3r+6)$, as stated in Conjecture ?? . Since there are $m$ blocks, we conclude that

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

Which ends the proof. □

**Corollary 2.** Let $\mathcal{A}_r(\mathbf{x}, \mathbf{y})$ be a generic square-distinguishable alter- nant code with $r < q+1$. If Conjecture ?? holds, then the Hilbert function at degree 2 associated with the (implicit or explicit) Pfaffian modeling for rank $\le 2$ matrices in $\mathcal{C}_{\mathrm{mat}}$ is given by

$$ HF_A(2) = \frac{m}{12}(r-1)(r-2)(r^2-3r+6). $$
Proof. With the genericity and square-distinguishability assumptions, the generic matrix in $\mathcal{C}_{\text{mat}}(\mathcal{A})$ is the one described in Equation (??). Therefore the corollary follows directly from Theorem ??.

Corollary ?? requires Conjecture ?? 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 [?], the value provided by Theorem ?? for degree 2 still represents a lower bound.

**Corollary 3.** 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).$$

Before proving Corollary ??, we need a pair of auxiliary results.

**Lemma 2.** Let $\mathbf{X} = (X_1, \dots, X_a)$ and $\mathbf{Y} = (Y_1, \dots, Y_b)$ be two vectors of variables. Let $M, N$ be two $s \times t$ matrices whose entries are linear homogeneous polynomials in $\mathbb{F}[\mathbf{X}], \mathbb{F}[\mathbf{X}, \mathbf{Y}]$ respectively and such that

$$n_{i,j}(\mathbf{X}, \mathbf{Y}) = m_{i,j}(\mathbf{X}) + l_{i,j}(\mathbf{Y}).$$

Let $f(\mathbf{Z})$ be a multivariate polynomial function over a field $\mathbb{F}$, where the variables are viewed as the entries $z_{i,j}$ of an $s \times t$ matrix $\mathbf{Z}$. Let $\langle Y_i \rangle_i \subset \mathbb{F}[\mathbf{X}, \mathbf{Y}]$ the ideal generated by $\mathbf{Y}$'s variables.

$$f(N) - f(M) \in \langle Y_i \rangle_i$$

Proof. Let $f(\mathbf{Z}) = \sum_{a \in A} \alpha_a \mathbf{Z}^a$, where $A$ is a finite subset of $\mathbb{N}^{s \times t}$ and $\alpha_a \in \mathbb{F}$ and we define $\mathbf{Z}^a = \prod_{i,j} z_{i,j}^{a_{i,j}}$. Similarly we write

$$M^{\mathbf{a}} \stackrel{\text{def}}{=} \prod_{i,j} m_{i,j}^{a_{i,j}}$$

$$N^{\mathbf{a}} \stackrel{\text{def}}{=} \prod_{i,j} n_{i,j}^{a_{i,j}}$$

When the input is $N$, we obtain

$$f(N) = \sum_{a \in A} \alpha_a N^a = \sum_{a \in A} \alpha_a \prod_{i,j} (m_{i,j} + l_{i,j}(\mathbf{Y}))^{a_{i,j}}.$$

By expanding the product, we obtain

$$f(N) = \left( \sum_{a \in A} \alpha_a M^a \right) + g(\mathbf{X}, \mathbf{Y})$$

where each monomial appearing in $g$ is a multiple of at least a variable $y_i$. Therefore

$$f(N) - f(M) = g(\mathbf{X}, \mathbf{Y}) \in \langle Y_i \rangle_i.$$

□
The previous lemma can be used to show that the Hilbert function for the Pfaffian ideal can only increase by letting the underlying matrix code grow.

**Lemma 3.** Let $\mathbb{F}$ be a finite field of characteristic 2. Let $M_1, \dots, M_l \in \mathbb{F}^{s \times t}$ be linearly independent (skew-)symmetric matrices and $\mathcal{C} = \langle M_1, \dots, M_l \rangle_{\mathbb{F}}, \mathcal{C}' = \langle M_1, \dots, M_{l'} \rangle_{\mathbb{F}} \subseteq \mathbb{F}^{s \times t}$ with $l' < l$ be two matrix codes. Let $\mathcal{I} \subseteq \mathbb{F}[X_1, \dots, X_l]$ (resp. $\mathcal{I}' \subseteq \mathbb{F}[X_1, \dots, X_{l'}]$) be the Pfaffian ideal corresponding to the explicit modeling for $\mathcal{C}$ (resp. $\mathcal{C}'$) expressing that the entries of an element of the matrix code is of rank $\le 2$. Then for all $d \in \mathbb{N}$,

$$ \mathrm{HF}_{\mathbb{F}[X_1, \dots, X_l]/\mathcal{I}}(d) \ge \mathrm{HF}_{\mathbb{F}[X_1, \dots, X_l]/\mathcal{I}'}(d) $$

*Proof.* Pfaffians of order 4 are homogeneous polynomial in the matrix entries. Therefore, from Lemma ??, any element $P$ of the Pfaffian ideal $\mathcal{I} \subseteq \mathbb{F}[X_1, \dots, X_l]$ can be written as an element of $\mathcal{I}' + \langle X_{l'+1}, \dots, X_l \rangle$, thus $P \subseteq \mathcal{I}' + \langle X_{l'+1}, \dots, X_l \rangle$, or equivalently

$$ \mathbb{F}[X_1, \dots, X_l]/\mathcal{I} \supseteq \mathbb{F}[X_1, \dots, X_l]/(\mathcal{I}' + \langle X_{l'+1}, \dots, X_l \rangle) \cong \mathbb{F}[X_1, \dots, X_l]/\mathcal{I}' $$

By definition of Hilbert series, we obtain

$$ \mathrm{HF}_{\mathbb{F}[X_1, \dots, X_l]/\mathcal{I}}(d) \ge \mathrm{HF}_{\mathbb{F}[X_1, \dots, X_l]/\mathcal{I}'}(d) $$

for any degree $d$. $\square$

With Lemma ?? at hand, we can finally prove Corollary ??.

*Proof (of Corollary ??).* Even without the condition $r < q + 1$ (resp. $r < q - 1$) for the degree of an alternant (resp. Goppa) code and without Conjecture ??, the matrix code $\mathcal{C}$ of relationships still contains the block-diagonal matrix code generated by the matrices corresponding to the fundamental relations. Let $\mathcal{C}'$ be the space spanned by such matrices and for which Theorem ?? provides the value of the Hilbert function at degree 2 as

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

Since $\mathcal{C}' \subseteq \mathcal{C}$, from Lemma ??, we derive

$$ \mathrm{HF}_{\mathbb{F}[\mathbf{x}]/\mathcal{I}}(2) \ge \frac{m}{12}(r-1)(r-2)(r^2 - 3r + 6). $$

$\square$

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

**Definition 10.** An alternant code is $d$-distinguishable if the associated Hilbert function $\mathrm{HF}_A$ satisfies

$$ \mathrm{HF}_A(d) > \mathrm{HF}_R(d) $$

where $\mathrm{HF}_R$ is the Hilbert series of a random linear code of the same length and dimension as the alternant code.
**Corollary 4.** 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 alternant code was always equal to $\frac{m}{12}(r-1)(r-2)(r^2-3r+6)$.

# 5 The new distinguisher regime

From [?], 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 (7)$$

where $s \stackrel{\text{def}}{=} rm$. Indeed, the Hilbert function associated to a 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 at degree 2 by $HF_R(2) = \max(0, \binom{k}{2}h(0) - \binom{k}{1}h(1) + \binom{k}{0}h(2))$ where $h(d) \stackrel{\text{def}}{=} \frac{1}{rm+d-1} \binom{rm+d-1}{d+1} \binom{rm+d-1}{d}$. Moreover, we notice that

$$\begin{aligned}
h(2) &= \frac{1}{rm+1} \binom{rm+1}{3} \binom{rm+1}{2} \\
&= \frac{1}{rm+1} \frac{(rm+1)rm(rm-1)}{6} \frac{(rm+1)rm}{2} \\
&= \frac{(rm)^2(rm+1)(rm-1)}{12} \\
&= \frac{s^4 - s^2}{12},
\end{aligned}$$

where $s \stackrel{\text{def}}{=} rm$. If we plug this expression in the expression we have for $HF_R(2)$, namely $HF_R(2) = \max(0, \binom{k}{2}h(0) - \binom{k}{1}h(1) + \binom{k}{0}h(2))$ and using the fact that $h(0) = 1$ and $h(1) = \binom{mr}{2}$ we obtain

$$\begin{aligned}
HF_R(2) &= \max \left( 0, \frac{k(k-1)}{2} - k \frac{mr(mr-1)}{2} + \frac{s^4 - s^2}{12} \right) \\
&= \max \left( 0, \frac{k^2}{2} - k \frac{s^2 - s + 1}{2} + \frac{s^4 - s^2}{12} \right).
\end{aligned}$$

Combined with Corollary ??, this implies

**Proposition 4.** 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.
Proof. $k_0$ is defined as the smallest root of the equation (in $X$)

$$ \frac{1}{2} \left( X^2 - X(s^2 - s + 1) + \frac{s^4 - s^2}{6} \right) = \frac{m(r-1)(r-2)(r^2 - 3r + 6)}{12}. \qquad (8) $$

Clearly, when the dimension $k$ of an alternant code of degree $r$ and extension degree $m$ is bigger than this $k_0$, we have $HF_R(2) < HF_A(2)$ and it is distinguishable at degree 2. (??) is equivalent to

$$ X^2 - X(s^2 - s + 1) + \frac{s^4 - s^2 - H}{6} = 0, $$

where $H \stackrel{\text{def}}{=} m(r-1)(r-2)(r^2 - 3r + 6)$. Therefore

$$ k_0 = \frac{s^2 - s + 1 - \sqrt{\Delta}}{2} $$

$$ \begin{aligned} \text{where } \Delta &\stackrel{\text{def}}{=} (s^2 - s + 1)^2 - \frac{2}{3}(s^4 - s^2 - H) \\ &= s^4 + s^2 + 1 - 2s^3 + 2s^2 - 2s - \frac{2}{3}s^4 + \frac{2}{3}s^2 + \frac{2}{3}H \\ &= \frac{s^4}{3} + \frac{2}{3}H - 2s^3 + \frac{11}{3}s^2 - 2s + 1. \end{aligned} $$

□

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 \sim_{r \to \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 [?]. 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} - \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^2 r^2 + o(m^2 r^2)$ as $r \to \infty$ and if $m$ goes to infinity as well, $k_1 \sim \frac{m^2 r^2}{2}$.

**Comparison with the distinguisher given in [?]** The syzygy distinguisher given in [?], like the Pfaffian distinguisher we consider here, can be viewed as a broad generalization of the original distinguisher given in [?]. However it relies on a distinct approach and is the first one that has been shown to be able to distinguish constant rate alternant or Goppa
codes with subexponential complexity. This is quite an achievement. It
is worthwhile to compare both distinguishers for parameters for which
they have roughly the same complexity. Both distinguishers rely on com-
puting the rank of certain matrices. In the case of the distinguisher we
consider here, we compute the rank of a matrix of size $a \times b$ where $a$ and
$b$ are of order $O((rm)^4)$ when $n$ is say of order $(rm)^2$ which will be our
assumption to make the comparison. To make a fair comparison between
both approaches it makes sense to consider the syzygy distinguisher pro-
posed in [?] without the additional trick of shortening the dual of the
alternant/Goppa code, since the Pfaffian distinguisher could also benefit
from this trick but it remains to analyze its impact precisely.

The syzygy distinguisher considers the rank of matrices with a number of
rows and columns of size $O((rm)^4)$ when computing the Betti number
$\beta_{p-1,p}$ when $p=4$. It distinguishes an alternant code from a random code
when the Betti number corresponding to the dual of the alternant code
is different from the Betti number of the random code. In the parameter
regime we consider, namely $n$ of order $(rm)^2$, $m$ of order $\log_q n$ and
letting $n$ go to infinity, it turns out by using Theorem 1 of [?] giving a
lower bound on the Betti number $\beta_{p-1,p}$ of an alternant code together
with [?, Prop. 10] estimating the Betti number $\beta_{p-1,p}$ of a generic linear
code, one is able to distinguish up to values of $n$ satisfying $n \ge \frac{(rm)^2}{4}(1-o(1))$, which gives in terms of the dimension $k$ of the code $k \ge \frac{(rm)^2}{4}(1+o(1))$. This is slightly worse than the Pfaffian distinguisher in this regime
of parameters.

# 6 Concluding Remarks

This work shows that the lower bound HF<sub>A</sub>(2) > 0 of [?, Prop. 18] is
very pessimistic and can be significantly improved. Understanding the
precise behavior of HF<sub>A</sub>(d) is really desirable not only to assess precisely
the power of the Pfaffian distinguisher given in [?] but should also be
very helpful in understanding this distinguisher if instead of applying it
to the dual of the alternant or Goppa code we want to distinguish, we
apply it to a shortening of this latter code. This paper can be seen as a
first step towards this goal. It is tempting to conjecture that similarly to
what happened in [?] which resulted in a much improved distinguisher,
we should observe the same behavior for the Pfaffian distinguisher. This
work also shows that the Pfaffian distinguisher at degree 2 seems a little
bit more powerful than the syzygy distinguisher of [?] at degree 4 which
has a similar complexity. In light of this result and the fact that the
syzygy distinguisher is of subexponential complexity when applied to
the right shortened code, this raises the issue whether the same also
applies to the Pfaffian distinguisher studied here when applied to the
suitable shortened code.
A Proof of Theorem ??: a slightly more general version

As we have already mentioned, several equivalent modelings can be applied to find rank $\le 2$ matrices in $\mathscr{C}_{\mathrm{mat}}$. However, we are not interested in solving the algebraic system yet, but rather in computing algebraic quantities such as Hilbert functions. It is then mandatory to wonder whether the Hilbert function of all these modelings are the same. The varieties produced by each ideals being isomorphic is not sufficient at all to conclude that their Hilbert series coincide, since this object strongly depends on how the equations defining the variety are written. In this appendix, we will be interested in two different modelings of the same problem and will show that they are equivalent, i.e produce the same Hilbert series. The problem in question is to find the intersection between an algebraic variety and a linear subspace. This is formally defined in the following.

**Problem 1.** Let $f_1, \dots, f_N$ be homogeneous polynomials in $\mathbb{F}[X_1, \dots, X_n]$ and $V \subset \mathbb{F}^n$ a linear subspace of $\mathbb{F}^n$. The goal is to compute

$$V(f_1, \dots, f_N) \cap V = \{\boldsymbol{x} \in V \mid \forall i \in [1, N], f_i(\boldsymbol{x}) = 0\}.$$

**Example 1.** The linear MinRank problem, i.e the problem aiming at finding rank $\le r$ matrices in some subspace, can be seen as an instance of Problem ??.

We will be interested in two modelings of Problem ??.

**Modeling 4 (Implicit modeling)** Let $k \stackrel{\mathrm{def}}{=} \dim_{\mathbb{F}}(V)$. There exists linearly independent linear forms $L_1, \dots, L_{n-k}$ such that

$$V = \{\boldsymbol{x} \in \mathbb{F}^n \mid \forall i \in [1, n-k], L_i(\boldsymbol{x}) = 0\}.$$

The implicit algebraic modeling corresponding to Problem ?? is defined by the ideal

$$I \stackrel{\mathrm{def}}{=} (f_1, \dots, f_N, L_1, \dots, L_{n-k}).$$

I is an ideal of $\mathbb{F}[X_1, \dots, X_n]$.

**Modeling 5 (Explicit modeling)** Let $k \stackrel{\mathrm{def}}{=} \dim_{\mathbb{F}}(V)$ and let $\{v_1, \dots, v_k\}$ be an $\mathbb{F}$-basis of $V$. The explicit algebraic modeling corresponding to Problem ??, with respect to the basis $\{v_1, \dots, v_k\}$, is defined by the ideal

$$J \stackrel{\mathrm{def}}{=} (f_1(Y_1v_1 + \dots + Y_kv_k), \dots, f_N(Y_1v_1 + \dots + Y_kv_k)).$$

J is an ideal of $\mathbb{F}[Y_1, \dots, Y_k]$.

Modeling ?? corresponds to the implicit modeling detailed in Section ??, and Modeling ?? corresponds to the explicit modeling of Section ???. The first thing to notice here is that if $f_1, \dots, f_N$ are homogeneous (which
is required by the specification of Problem ??), then both modelings produce homogeneous ideals. Therefore, both ideals have a structure of graded F-algebra. From now on, we will denote with $\mathbf{R}$ (resp. $\mathbf{S}$) the polynomial ring in $X_1, \dots, X_n$ (resp. $Y_1, \dots, Y_k$) over $\mathbb{F}$. The equivalence between the two modelings is stated by the following.

**Theorem 4.** Let $f_1, \dots, f_N \in \mathbf{R}$ be homogeneous polynomials, and let $V \subset \mathbb{F}^n$ be a subspace of dimension $k < n$. Let $I$ (resp. $J$) denote the ideal produced by the implicit (resp. explicit) modeling. There exists a map

$$ \bar{\Phi}: \mathbf{R}/I \to \mathbf{S}/J $$

which defines an isomorphism of graded F-algebras.

This statement clearly implies that the Hilbert functions associated with both modelings are equal, and therefore ensures the validity of Theorem ??.

Note that the change of modelings, from the implicit version to the explicit one, is nothing but a change of variables :

$$ (X_1, \dots, X_n) = (Y_1, \dots, Y_k)\mathbf{P}, $$

where each row of $\mathbf{P} \in \mathbb{F}^{k \times n}$ corresponds to the coordinates of a vector of a basis of $V$. In a more coding-theoretic vocabulary, $\mathbf{P}$ is a generator matrix of $V$. This implies that $\mathbf{P}$ is necessarily of rank $k$. We will assume, without loss of generality, that $\mathbf{P}$ is in systematic form, i.e $\mathbf{P} = (I_k | *)$. In the following, we will try to construct the isomorphism $\bar{\Phi}$. To begin with, let us introduce the map

$$ \Phi: \left\{ \begin{array}{r \to \mathbf{S}} \mathbf{R} & \\ f & \mapsto f \left( \sum_{j=1}^{k} P_{j,1} Y_j, \dots, \sum_{j=1}^{k} P_{j,n} Y_j \right) \end{array} \right. $$

Applying $\Phi$ is actually doing the change of variables. Before proving Theorem ??, we need the following auxiliary results.

**Lemma 4.** The map $\Phi$ is a surjective morphism of graded F-algebras.

*Proof.* It is clear that $\Phi$ is a morphism of F-algebras. Furthermore, applying $\Phi$ on a polynomial $f$ boils down to composing $f$ with homogeneous polynomials of degree 1, therefore $\Phi$ preserves the degree, i.e sends homogeneous components onto homogeneous components of same degree. Hence $\Phi$ is a morphism of graded F-algebras.

Finally, since $\mathbf{P}$ is in systematic form, we have $\Phi(X_i) = Y_i$ for all $1 \le i \le k$. Since all generators of $\mathbf{S}$ as an F-algebra lie in the image of the F-algebra morphism $\Phi$, we conclude that $\Phi$ is surjective. $\square$

**Lemma 5.** $J = \Phi(I)$.

*Proof.* Since $J = (\Phi(f_1), \dots, \Phi(f_N))$, we know that any element of $J$ can be written as the image of an element of $I$ by the map $\Phi$, i.e $J \subseteq \Phi(I)$. To prove that $\Phi(I)$ is not strictly bigger than $J$, it only remains to show that $\Phi(L_i) \in J$ for all $i = 1, \dots, n-k$.
Remember that the rows of $\mathbf{P}$ are the vectors of a basis of $V$. Hence, for all $(y_1, \dots, y_k) \in \mathbb{F}^k$, we have

$$ \forall 1 \le i \le n-k, L_i \left( \sum_{j=1}^{k} y_j \mathbf{P}_j \right) = 0, $$

where $\mathbf{P}_j$ denotes the $j$-th row of $\mathbf{P}$. In other words, the polynomials $\Phi(L_i)$ are linear forms that vanish over $\mathbb{F}^k$ entirely. This implies that $\Phi(L_i) = 0$ for all $i \in [0, n-k]$. As a consequence, we have both $\Phi(f_i) \in J$ and $\Phi(L_i) \in J$ for all $i$, therefore $\Phi(I) \subseteq J$. $\square$

Now that we know how the image of $\Phi$ behaves, it only remains to investigate its kernel.

**Lemma 6.** $\ker \Phi = (L_1, \dots, L_{n-k})$.

*Proof.* This fact is not trivial because we cannot assume that $\mathbb{F}$ is algebraically closed$^3$. To deal with it, we introduce

$$ \bar{V} = \{ \boldsymbol{x} \in \bar{\mathbb{F}}^n \mid \forall 1 \le i \le n-k, L_i(\boldsymbol{x}) = 0 \} = \langle V \rangle_{\bar{\mathbb{F}}}, $$

where $\bar{\mathbb{F}}$ is the algebraic closure of $\mathbb{F}$. By Hilbert's Nullstellensatz, we have

$$ I(\bar{V}) = \sqrt{(L_1, \dots, L_{n-k})} = (L_1, \dots, L_{n-k}), $$

the last equality comes from the fact that all the $L_i$'s have degree 1. Now, let $f \in \ker \Phi$. By definition,

$$ f \left( \sum_{j=1}^{k} P_{j,1} Y_j, \dots, \sum_{j=1}^{k} P_{j,n} Y_j \right) = 0. $$

We may apply this polynomial on any element $\boldsymbol{y} \in \bar{\mathbb{F}}^k$, which means that

$$ \forall \boldsymbol{x} \in \bar{V}, f(\boldsymbol{x}) = 0. $$

This implies that $f \in (L_1, \dots, L_{n-k})$, as an ideal of $\bar{\mathbb{F}}[X_1, \dots, X_n]$, but since the coefficients of $f$ lie in $\mathbb{F}$, we have $f \in (L_1, \dots, L_{n-k})$ as an ideal of $\mathbb{R}$. We have thus proven that $\ker \Phi \subseteq (L_1, \dots, L_{n-k})$. The other inclusion is already proven in the previous lemma. $\square$

We are now ready to provide a proof of Theorem ??.

*Proof (Proof of Theorem ??).* Lemma ?? implies that if $f$ is defined modulo an element of $I$, then $\Phi(f)$ is *well-defined* modulo an element of $J$. In other words, $\Phi$ induces a morphism $\bar{\Phi}$ which is the only one such that the following diagram commutes :

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

<footnote>$^3$ In our case, $\mathbb{F} = \mathbb{F}_q$ is a finite field which is not algebraically closed.</footnote>
On the above diagram, we used the symbol $\pi$ to write both canonical projections. Since $\Phi$ is a surjective morphism of graded F-algebras, and since $\Phi(I) = J$ (Lemma ??), so is $\bar{\Phi}$. Finally, let us prove that $\Phi$ is injective. Let $f \in R$ such that $\bar{\Phi} \circ \pi(f) = 0$, or equivalently, $\Phi(f) \in J$. Since $J = \Phi(I)$, there exists $g \in I$ such that $\Phi(f) = \Phi(g)$, hence $f - g \in \ker \Phi$. By Lemma ??, we have $\ker \Phi \subseteq I$, which implies that $f \in I$, or equivalently $\pi(f) = 0$.