# On the dimension and structure of the square of the dual of a Goppa code

Rocco Mora, Jean-Pierre Tillich

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

## To cite this version:

Rocco Mora, Jean-Pierre Tillich. On the dimension and structure of the square of the dual of a Goppa code. Designs, Codes and Cryptography, 2022, 91 (4), pp.1351-1372. 10.1007/s10623-022-01153-w. hal-03919898

HAL Id: hal-03919898

https://inria.hal.science/hal-03919898

Submitted on 3 Jan 2023

HAL is a multi-disciplinary open access archive for the deposit and dissemination of scientific research documents, whether they are published 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_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# On the dimension and structure of the square of the dual of a Goppa code

Rocco Mora<fnref n="1" />,<fnref n="2" />* and Jean-Pierre Tillich<fnref n="1" />

*Corresponding author(s). E-mail(s): rocco.mora@inria.fr;

Contributing authors: jean-pierre.tillich@inria.fr;

## Abstract

The Goppa Code Distinguishing (GD) problem asks to distinguish efficiently a generator matrix of a Goppa code from a randomly drawn one. We revisit a distinguisher for alternant and Goppa codes through a new approach, namely by studying the dimension of square codes. We provide here a rigorous upper bound for the dimension of the square of the dual of an alternant or Goppa code, while the previous approach only provided algebraic explanations based on heuristics. Moreover, for Goppa codes, our proof extends to the non-binary case as well, thus providing an algebraic explanation for the distinguisher which was missing up to now. All the upper bounds are tight and match experimental evidence. Our work also introduces new algebraic results about products of trace codes in general and of dual of alternant and Goppa codes in particular, clarifying their square code structure. This might be of interest for cryptanalysis purposes.

**Keywords:** Algebraic codes, Goppa codes, Alternant codes, Square codes, Distinguisher of Goppa codes, Code-based Cryptography

<footnote n="1">¹Team COSMIQ, Inria, 2 rue Simone Iff, Paris, 75012, France.</footnote>

<footnote n="2">²Sorbonne Universités, UPMC Univ Paris 06, 4 place Jussieu, Paris, 75005, France.</footnote>
# 1 Introduction

## 1.1 The McEliece scheme.

The McEliece encryption scheme [14], which dates back to 1978, is a code-based cryptosystem built upon the family of binary Goppa codes. It is equipped with very fast encryption and decryption algorithms and has very small ciphertexts. It is also widely viewed as a viable quantum safe cryptosystem, since the best quantum algorithm for breaking it [12] has exponential complexity and the corresponding exponent barely improves the exponent of the best classical algorithm [3] by about 40 percent.

Over the years, the attempts to attack McEliece scheme moved in two main directions. One hand, we have *message-recovery attacks*. They consist in inverting the McEliece encryption without finding a trapdoor and make use of general decoding algorithms. Despite considerable improvements [1, 3, 4, 13, 16, 17, 23], all these algorithms have exponential complexity. The parameters of McEliece-like schemes have then been intentionally chosen to thwart this attack, because it is considered as the main threat to the scheme. Despite all these efforts, the original McEliece cryptosystem [14] based on binary Goppa codes remains, after more than forty years, unbroken, be it by a classical or a quantum computer. It is now the oldest public-key cryptosystem with this feature.

The other way to attack the cryptosystem is by seeking to recover the private key. For a long time it was widely believed that even a simpler task which is just to distinguish efficiently a generator matrix of a Goppa code from a randomly drawn generator matrix with non negligible probability was unfeasible. This is the so called *Goppa Code Distinguishing (GD) problem* as introduced by the authors of [6]. The nice feature of this problem is that it is possible to devise a security proof for the McEliece scheme based solely on the intractability of this problem and decoding a generic linear code [22]. The belief about GD problem hardness was basically justified by the fact that Goppa codes behave like random codes in many aspects. For instance, they asymptotically meet the Gilbert-Varshamov bound, their weight distribution is roughly the same as those of random codes and they generally have a trivial permutation group. The absence of significant breakthrough in key-recovery attacks also strengthened the idea that the Goppa Code distinguishing problem is difficult. This problem was actually used for a long time as a problem which basically captures the hardness of recovering the private key of a Goppa code.

## 1.2 A distinguisher for high rate.

However, this belief was severely questioned in [10, 11] which gave a polynomial time algorithm that distinguishes between Goppa codes (or more generally alternant codes) and random ones from their generator matrices at least for very high rate codes. It is based on the kernel of a linear system related to
an algebraic system that encodes the key-recovery problem for McEliece cryp-
tosystem instantiated with alternant or Goppa codes. Indeed, it was shown to
have an unexpectedly high dimension. This distinguisher was later on given
another interpretation in [15], where it was proved that this dimension is
related to the dimension of the square of the dual of the public code. The alge-
braic explanations given in [11] do not represent however a rigorous proof of
the dimension of the kernel sought, but they rely on heuristic considerations.
Indeed, while a set of vectors is proposed as candidate for the kernel basis, its
elements are neither proved to be independent nor a set of generators. Despite
that the experiments run in [11] show a regular behavior when alternant codes
are defined by picking at random support and multiplier vectors, it is possible
to artificially choose alternant codes whose kernel dimensions are even larger
than for random ones. Moreover, in the case of Goppa codes, even if a gen-
eral formula for the dimension of the kernel was provided which matches the
experimental evidence, an algebraic explanation was only provided in the case
of binary Goppa codes with square free Goppa polynomials. This explanation
crucially relies on the fact that binary Goppa codes are in this case also Goppa
codes of a higher degree (with a Goppa polynomial being the square of the
original polynomial). Clearly, this approach does not generalize to non binary
Goppa codes.

1.3 Our contribution

In the present article, we revisit the distinguisher for random alternant codes
and Goppa codes. We do so by exploiting the link given by [15]. Indeed we
provide a rigorous upper bound on the dimension of the square code of the dual
of an alternant or a Goppa code that coincides with the experiments. By using
[15], this also gives a lower bound on the dimension of the kernel of the matrix
considered in [11]. Together with results about the typical dimension of the
square of random codes [5], this provides the first rigorous analysis about the
effectiveness of the approach pioneered in [10], because the typical dimension
of the square of a random code is way larger than this upper-bound on the
dimension of the square of the dual of a Goppa or alternant code.

Our approach relies on several new ingredients

* a new result about the square of trace codes showing that if essentially the square of a code is abnormally small then the square of its trace code is also abnormally small in a certain region of parameters. By interpreting the dual of an alternant code or a Goppa code as the trace of a generalized Reed-Solomon code (whose dimension of the square is known to be abnormally small [24]) this shows that the square of a dual of an alternant code or a Goppa code is abnormally small.

* While this approach explains rigorously why alternant codes or Goppa codes can be distinguished for extremely large rates, lower rates require a much delicate analysis, in particular in the Goppa case. We do so, by noticing that the square of a trace of a code $\mathcal{C}$ can be interpreted as a sum of traces of
4 On the dimension and structure of the square of the dual of a Goppa code

<table><caption>**Table 1** Comparison between Classic McEliece and smallest distinguishable code rates. This table provides a comparison between the parameters proposed for Classic McEliece and the largest order *r* of a binary Goppa code that is distinguishable, with the corresponding relative rate *R*. Such an order can be computed as the maximum value of *r* for which the upper bound of the dimension of the square of a binary Goppa code given in Corollary 29 (Classic McEliece uses binary Goppa codes) is strictly smaller than $\min(n, (\binom{mr+1}{2}))$. The latter quantity is the typical dimension of the square of a random code of the same length and dimension as the corresponding Goppa code (see [5]). We see in this table that the code rates suggested for Classic McEliece oscillate between 0.7 and 0.8 [2, Section 3], while for the same length *n* and degree of the field extension *m*, the distinguisher works for rates closer to 1, meaning that the Goppa order *r* must be smaller.</caption><thead><tr><th>McEliece parameter set</th><th>n</th><th>m</th><th>r in [2]</th><th>R in [2]</th><th>Largest distinguishable r</th><th>Corresponding R</th></tr></thead><tbody><tr><td>kem/mceliece348864</td><td>3488</td><td>12</td><td>64</td><td>0.77982</td><td>12</td><td>0.95872</td></tr><tr><td>kem/mceliece460896</td><td>4608</td><td>13</td><td>96</td><td>0.72917</td><td>12</td><td>0.96615</td></tr><tr><td>kem/mceliece6688128</td><td>6688</td><td>13</td><td>128</td><td>0.75120</td><td>15</td><td>0.97084</td></tr><tr><td>kem/mceliece6960119</td><td>6960</td><td>13</td><td>119</td><td>0.77773</td><td>16</td><td>0.97011</td></tr><tr><td>kem/mceliece8192128</td><td>8192</td><td>13</td><td>128</td><td>0.79688</td><td>19</td><td>0.96985</td></tr></tbody></table>

products of $\mathscr{C}$ with $\mathscr{C}^{q^i}$ (which denotes *i* applications of the Frobenius map to $\mathscr{C}$). In the case of Goppa codes, we show that the traces of these products turn out to be duals of alternant codes of a remarkably low degree at least for small values of *i* (see Theorem 24). This accounts for the remarkably low dimension of the square of the dual of Goppa codes in all cases considered in [11].

Interestingly enough, the latter argument applies to all kinds of Goppa codes, be they binary or not and provides now not only a rigorous explanation of the distinguisher found in [10], but also covers the non-binary Goppa code case as well. Note that even if this approach is not able to distinguish the Goppa codes proposed in the NIST competition as shown in Table 1, because it only works for very high rate Goppa codes, this still raises the issue whether this distinguishing approach can be improved to lower the dimension of the Goppa codes that can be distinguished by this approach. The better understanding of the distinguisher obtained here might help to address this issue.

## 2 Notation and prerequisites

In this section, we fix notation used throughout the article. We also recall basic definitions and well-known results about subfield subcodes and trace codes, component-wise products, square codes and some algebraic codes derived from generalized Reed-Solomon codes.

Let $\mathbb{F}$ be a generic finite field, $\mathbb{F}_q$ and $\mathbb{F}_{q^m}$ the finite fields with $q$ and $q^m$ elements respectively, where $q$ denotes a prime power, and $m$ is a positive integer. Given $v_1, \dots, v_k \in \mathbb{F}^n$, we denote with $\langle v_1, \dots, v_k \rangle_{\mathbb{F}}$ the subspace of vectors in $\mathbb{F}^n$ spanned by $\{v_1, \dots, v_k\}$. An $[n, k]$-code over $\mathbb{F}$ is a linear subspace of vectors in $\mathbb{F}^n$ of dimension $k$. The positive integer $n$ is called the *code length*.
Vectors and matrices will be denoted by bold letters $\boldsymbol{x}$, $\boldsymbol{M}$, and are capitalized for matrices. We will also use for a function $f$ acting on $\mathbb{F}$ and a vector $\boldsymbol{x} = (x_i)_{1\le i\le n}$ in $\mathbb{F}^n$ by $f(\boldsymbol{x})$ the vector $(f(x_i))_{1\le i\le n}$.

## 2.1 Subfield subcodes and trace codes

In this article we will often consider a finite field $\mathbb{F}_{q^m}$ and its subfield $\mathbb{F}_q$. It is therefore useful to fix a basis of $\mathbb{F}_{q^m}$ over $\mathbb{F}_q$:

$$ \{\alpha_0, \dots, \alpha_{m-1}\}. $$

We will also make use of a normal basis

$$ \{\beta, \beta^q, \dots, \beta^{q^{m-1}}\} $$

whenever fruitful.

A useful linear map from $\mathbb{F}_{q^m}$ to its subfield $\mathbb{F}_q$ is the trace operator.

**Definition 1.** Given the finite field extension $\mathbb{F}_{q^m}/\mathbb{F}_q$, we define the trace operator $\text{Tr}_{\mathbb{F}_{q^m}/\mathbb{F}_q} : \mathbb{F}_{q^m} \to \mathbb{F}_q$ for all $x \in \mathbb{F}_{q^m}$ as

$$ \text{Tr}_{\mathbb{F}_{q^m}/\mathbb{F}_q}(x) = \sum_{i=0}^{m-1} x^{q^i}. $$

The definition extends to vectors $\boldsymbol{x} \in \mathbb{F}_{q^m}^n$ so that the trace acts component-wise:

$$ \text{Tr}_{\mathbb{F}_{q^m}/\mathbb{F}_q}(\boldsymbol{x}) = (\text{Tr}_{\mathbb{F}_{q^m}/\mathbb{F}_q}(x_1), \dots, \text{Tr}_{\mathbb{F}_{q^m}/\mathbb{F}_q}(x_n)) $$

and to codes $\mathcal{C}$ over $\mathbb{F}_{q^m}$

$$ \text{Tr}_{\mathbb{F}_{q^m}/\mathbb{F}_q}(\mathcal{C}) = \{\text{Tr}_{\mathbb{F}_{q^m}/\mathbb{F}_q}(\mathbf{c}) \mid \mathbf{c} \in \mathcal{C}\}. $$

We remark that if $\mathcal{C} = \langle \mathbf{c}_i \mid 1 \le i \le k \rangle_{\mathbb{F}_{q^m}}$ then $\text{Tr}_{\mathbb{F}_{q^m}/\mathbb{F}_q}(\mathcal{C})$ is a linear code over $\mathbb{F}_q$ and

$$ \text{Tr}_{\mathbb{F}_{q^m}/\mathbb{F}_q}(\mathcal{C}) = \langle \text{Tr}_{\mathbb{F}_{q^m}/\mathbb{F}_q}(\alpha_j \mathbf{c}_i) \mid 0 \le j < m, 1 \le i \le k \rangle_{\mathbb{F}_q}. $$

Informally, multiplying the generators of $\mathcal{C}$ inside the trace by each element $\alpha_j$ of the extension field basis takes into account the fact that $\mathcal{C}$ is a code over $\mathbb{F}_{q^m}$, while $\text{Tr}_{\mathbb{F}_{q^m}/\mathbb{F}_q}(\mathcal{C})$ over the subfield $\mathbb{F}_q$. So, if $\text{dim}_{\mathbb{F}_{q^m}}\mathcal{C} = k$ then typically $\text{dim}_{\mathbb{F}_q}\text{Tr}_{\mathbb{F}_{q^m}/\mathbb{F}_q}(\mathcal{C}) = mk$, unless $\text{Tr}_{\mathbb{F}_{q^m}/\mathbb{F}_q}(\mathcal{C})$ coincides with the ambient space. From now on, we will omit the extension field $\mathbb{F}_{q^m}/\mathbb{F}_q$ and simply write $\text{Tr}$, whenever the former is clear from the context.

The main classical result linking trace codes to subfield subcodes is Delsarte's theorem.
6 On the dimension and structure of the square of the dual of a Goppa code

**Theorem 2.** (Delsarte's theorem [9]) Let $\mathcal{C}$ be a code over $\mathbb{F}_{q^m}$. Then

$$ (\mathcal{C}|_{\mathbb{F}_q})^{\perp} = \mathrm{Tr}(\mathcal{C}^{\perp}), $$

where $\mathcal{C}|_{\mathbb{F}_q} \stackrel{\mathrm{def}}{=} \mathcal{C} \cap \mathbb{F}_q$ denotes the subfield subcode over $\mathbb{F}_q$ of $\mathcal{C}$.

## 2.2 Reed-Solomon, alternant and Goppa codes

We first recall the definitions of some well-known classes of algebraic codes. In the following we will always denote with $r$ the dimension of a generalized Reed-Solomon code. We start with the definition of the latter, seen as an *evaluation code*:

**Definition 3.** Let $\mathbf{x} = (x_1, \dots, x_n) \in \mathbb{F}^n$ be a vector of pairwise distinct entries and $\mathbf{y} = (y_1, \dots, y_n) \in \mathbb{F}^n$ a vector of nonzero entries. The $[n, r]$ generalized Reed-Solomon (GRS) code with support $\mathbf{x}$ and multiplier $\mathbf{y}$ is

$$ \mathbf{GRS}_r(\mathbf{x}, \mathbf{y}) \stackrel{\mathrm{def}}{=} \{(y_1 P(x_1), \dots, y_n P(x_n)) \mid P \in \mathbb{F}[z], \deg P < r\} $$

This code 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{\mathrm{def}}{=} (a_1 b_1, \dots, a_n b_n). $$

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 see the GRS code as

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

where $\mathbf{x}^a$ stands for the component-wise product $\star$ of the vector $\mathbf{x}$ with itself repeated $a$ times and where we omitted the component-wise product symbol between $\mathbf{x}$ and $\mathbf{y}$.

The dual of a GRS code is also a GRS code, where the support and the multiplier are related to the ones of the primal code. In order to explicit such relation we introduce the polynomial

$$ \pi_{\mathbf{x}}(z) \stackrel{\mathrm{def}}{=} \prod_{i=1}^{n} (z - x_i) \in \mathbb{F}[z]. $$
**Proposition 5.** [18, Theorem 4, p. 304] Let $\mathbf{GRS}_r(\mathbf{x}, \mathbf{y})$ be a GRS code of length $n$. Its dual is also a GRS code. In particular

$$ \mathbf{GRS}_r(\mathbf{x}, \mathbf{y})^{\perp} = \mathbf{GRS}_{n-r}(\mathbf{x}, \mathbf{y}^{\perp}), $$

where

$$ \mathbf{y}^{\perp} \stackrel{\text{def}}{=} \left( \frac{1}{\pi'_{\mathbf{x}}(x_1)y_1}, \dots, \frac{1}{\pi'_{\mathbf{x}}(x_n)y_n} \right) $$

and $\pi'_{\mathbf{x}}$ is the derivative of $\pi_{\mathbf{x}}$.

An *alternant code* can be defined as the subfield subcode of a GRS code:

**Definition 6.** Let $n \le q^m$, for some positive integer $m$. Let $\mathbf{GRS}_r(\mathbf{x}, \mathbf{y})$ be the GRS code over $\mathbb{F}_{q^m}$ of dimension $r$ with support $\mathbf{x} \in \mathbb{F}_{q^m}^n$ and multiplier $\mathbf{y} \in (\mathbb{F}_{q^m}^*)^n$. The *alternant code* with support $\mathbf{x}$ and multiplier $\mathbf{y}$ and degree $r$ over $\mathbb{F}_q$ is

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

The integer $m$ is called *extension degree* of the alternant code.

Note that by Proposition 5 an alternant code is the subfield subcode of a GRS code:

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

We use the same notation as in [18] and use the dimension $r$ and the multiplier $\mathbf{y}$ of the dual GRS code, which turns out to be more convenient in our setting. A well-known polynomial time decoding algorithm for the family of alternant codes allows to decode up to $\frac{r}{2}$ errors. We observe that for $m = 1$ an alternant code is simply a GRS code. Therefore from now on we will always assume $m > 1$.

From Delsarte's theorem (Theorem 2) and by duality,

$$ \begin{aligned} \mathcal{A}_r(\mathbf{x}, \mathbf{y})^{\perp} &= (\mathbf{GRS}_r(\mathbf{x}, \mathbf{y})^{\perp} \cap \mathbb{F}_q^n)^{\perp} \\ &= \mathrm{Tr}((\mathbf{GRS}_r(\mathbf{x}, \mathbf{y})^{\perp})^{\perp}) \\ &= \mathrm{Tr}(\mathbf{GRS}_r(\mathbf{x}, \mathbf{y})). \end{aligned} \quad (1) $$

The dimension of an alternant code of order $r$ built upon an extension field of degree $m$ has therefore dimension at least $n - rm$. There exists a subclass of alternant codes which is particularly attractive for cryptographic purposes:

**Definition 7.** Let $\mathbf{x} \in \mathbb{F}_{q^m}^n$ be a support vector and $\Gamma \in \mathbb{F}_{q^m}[z]$ a polynomial of degree $r$ such that $\Gamma(x_i) \neq 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}), $$
8 On the dimension and structure of the square of the dual of a Goppa code

where $\mathbf{y} \stackrel{\text{def}}{=} \left( \frac{1}{\Gamma(x_1)}, \dots, \frac{1}{\Gamma(x_n)} \right)$.

The reason why binary Goppa codes are preferable to instantiate McEliece-like schemes is that, if the Goppa polynomial has no multiple roots, there exists a polynomial time algorithm to decode up to r errors. This is a direct consequence of

**Theorem 8.** [19] Let $\mathcal{G}(\mathbf{x}, \Gamma)$ be a binary Goppa polynomial $\Gamma$ of degree $r$ and without multiple roots. Then

$$ \mathcal{G}(\mathbf{x}, \Gamma) = \mathcal{G}(\mathbf{x}, \Gamma^2) = \mathcal{A}_{2r}(\mathbf{x}, \mathbf{y}), $$

where $y_i \stackrel{\text{def}}{=} \frac{1}{\Gamma(x_i)^2}$ for all $1 \le i \le n$.

## 2.3 Square of codes

GRS codes turn out to display a very peculiar property with respect to the component-wise/Schur product of codes which is defined from the component-wise/Schur product of vectors by

**Definition 9.** 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} \mid \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}$.

It is easy to see that if $\mathcal{C} = \langle \mathbf{c}_1, \dots, \mathbf{c}_{k_1} \rangle_{\mathbb{F}}$ and $\mathcal{D} = \langle \mathbf{d}_1, \dots, \mathbf{d}_{k_2} \rangle_{\mathbb{F}}$, a generating set for $\mathcal{C} \star \mathcal{D}$ over $\mathbb{F}$ is given by a set of $k_1 k_2$ vectors,

$$ \{ \mathbf{c}_i \star \mathbf{d}_j \mid 1 \le i \le k_1, 1 \le j \le k_2 \}. $$

However, when $\mathcal{C} \cap \mathcal{D} \neq \{\mathbf{0}\}$, some of the above elements are obviously redundant. In the extreme case, i.e. when $\mathcal{C} = \mathcal{D}$, the square code dimension is much smaller than $k^2$, where $k = \text{dim}_{\mathbb{F}} \mathcal{C}$. This is a consequence of the commutative property of the component-wise product: $c_i \star c_j = c_j \star c_i$. Thus we can give the following folklore result appearing for instance in [5].

**Proposition 10.** Let $\mathcal{C}$ be a linear code over $\mathbb{F}$ of dimension $k$ and length $n$. Then

$$ \dim_{\mathbb{F}_q} \mathcal{C}^{*2} \le \min \left( n, \binom{k+1}{2} \right). $$

For a random linear code $\mathcal{C}$ whose square does not fill the full space, the dimension of its square code is $\binom{k+1}{2}$ with high probability [5], where $k$ is the
dimension of $\mathcal{C}$. However, there exist families of codes for which the inequality in Proposition 10 is strict. This clearly translates into a distinguisher from random codes. Generalized Reed-Solomon codes represent an example of such behavior [24]. We namely have

**Proposition 11.** Let $\text{GRS}_k(\mathbf{x}, \mathbf{y})$ be a GRS code with support $\mathbf{x}$, multiplier $\mathbf{y}$ and dimension $k$. We have $\text{GRS}_k(\mathbf{x}, \mathbf{y})^{*2} = \text{GRS}_{2k-1}(\mathbf{x}, \mathbf{y}^2)$. Hence, if $k \le \frac{n+1}{2}$,

$$ \dim_{\mathbb{F}_{q^m}} (\text{GRS}_k(\mathbf{x}, \mathbf{y}))^{*2} = 2k-1. $$

This follows immediately from the fact that the square of a $\text{GRS}_k(\mathbf{x}, \mathbf{y})$ can be written as

$$ \begin{aligned} \text{GRS}_k(\mathbf{x}, \mathbf{y})^{*2} &= \langle (\mathbf{x}^a \mathbf{y}) \star (\mathbf{x}^b \mathbf{y}) | 0 \le a, b < k \rangle_{\mathbb{F}_{q^m}} \\ &= \langle \mathbf{x}^{a+b} \mathbf{y}^2 | 0 \le a, b < k \rangle_{\mathbb{F}_{q^m}} \\ &= \langle \mathbf{x}^c \mathbf{y}^2 | 0 \le c < 2k-1 \rangle_{\mathbb{F}_{q^m}}. \end{aligned} $$

Note that the square code dimension is here $2k-1$, i.e. it is linear in $k$ and not quadratic. Since the dual of a Reed-Solomon code is again a Reed-Solomon code, it turns out that this algebraic class is distinguishable for any rate. For other families, a square code-based distinguisher may occur only for certain rates. For instance Goppa codes (and more in general alternant codes) are distinguishable whenever the rate is high enough as we now recall. Again this is related to such square code considerations as we will explain.

## 2.4 The distinguisher of Goppa/alternant codes of [10, 11] and its relationship with square code considerations

The dual of an alternant (or Goppa) code can also be distinguished from random codes when the primal code has a high enough rate, using the square code tool. The different behavior was already observed in [10]. Here however, the distinguisher was presented in terms of the kernel dimension $D$ of a linear system obtained by linearizing in the proper way the algebraic system that encodes the key-recovery problem for McEliece cryptosystem endowed with alternant or Goppa codes. Indeed let $\mathbf{P} = (p_{ij})_{i,j}$ be a generator matrix of an $[n, k]$ alternant (or Goppa) code $\mathcal{C}$ in systematic form, i.e. with its first $k$ columns that form an identity block and consider the following linear system

$$ \mathcal{L}_p = \left\{ \sum_{k+1 \le j < j' \le n} p_{ij} p_{ij'} Z_{jj'} = 0 \mid 1 \le i \le k \right\}. $$

The dimension $D$ of the solution space of this system turns out to be much smaller in the case of high rate Goppa or alternant codes than for random codes. A conjecture for $D$ coinciding with experimental evidence was given in
10 On the dimension and structure of the square of the dual of a Goppa code

[11] together with a convincing algebraic explanation for alternant and binary
Goppa codes.

It has been proved in [15] that such $D$ is related to the dimension of the
square of the dual code $\mathscr{C}^{\perp}$. Indeed, from [15, Proposition 1],

$$
\dim_{\mathbb{F}} (\mathscr{C}^{\perp})^{*2} = \left( \dim_{\mathbb{F}} (\mathscr{C}^{\perp}) + 1 \right) - D. \qquad (2)
$$

In terms of dimensions of the square codes, the formula for *D* given in [11]
together with (2) predicts that

**Conjecture 12.** For a generic alternant code $\mathbb{F}_q$ of length $n$ and extension degree $m$ we have

$$
\dim_{\mathbb{F}_q}(\mathcal{A}_r(\mathbf{x}, \mathbf{y})^{\perp})^{*2} = \min \left\{ n, \binom{rm+1}{2} - \frac{m}{2}(r-1) \left( (2e_{\mathcal{A}}+1)r - 2\frac{q^{e_{\mathcal{A}}}-1}{q-1} \right) \right\}, \tag{3}
$$

whereas for a generic Goppa code $\mathscr{G}(\mathbf{x}, \Gamma)$ of length $n$ over $\mathbb{F}_q$ with Goppa polynomial $\Gamma(X) \in \mathbb{F}_{q^m}[X]$ of degree $r$:

$$
\dim(\mathcal{G}(\mathbf{x}, \Gamma)^{\perp})^{*2} = \min \left\{ n, \binom{rm+1}{2} - \frac{m}{2}(r-1)(r-2) \right\}, \quad \text{if } r < q-1 \tag{4}
$$

$$
\dim(\mathcal{G}(\mathbf{x}, \Gamma)^{\perp})^{*2} = \min \left\{ n, \binom{rm+1}{2} - \frac{m}{2}r \left( (2e_{\mathcal{G}}+1)r - 2(q-1)q^{e_{\mathcal{G}}-1} - 1 \right) \right\}, \quad \text{else,} \tag{5}
$$

where $e_{\mathcal{A}}$ and $e_{\mathcal{G}}$ are respectively defined by

$$
e_{\mathcal{A}} \stackrel{\text{def}}{=} \max\{i \in \mathbb{N} \mid r \ge q^i + 1\} = \lfloor \log_q(r-1) \rfloor
$$

$$
e_{\mathcal{G}} \stackrel{\text{def}}{=} \min\{i \in \mathbb{N} \mid r \le (q-1)^2 q^i + 1 = \left\lfloor \log_q \left( \frac{r}{(q-1)^2} \right) \right\rfloor + 1.
$$

As shown in [11], these formulas agree with extensive experimental evi-
dence. Notice that even if [11] did not prove the validity of these formulas, it
gave algebraic explanations making them very likely. One of the aims of this
article is to rigorously prove that at least the $\le$ inequality is ensured in (3),
(4) and (5).

3 A general result about the square of a trace
code

The dual of alternant codes and Goppa codes are trace codes of GRS codes.
From Proposition 11 we know that square codes of GRS codes have an abnor-
mally small dimension. A natural question is whether or not this implies that
the square of the trace of a GRS code has itself a small dimension. More generally, this raises the following fundamental issue of whether or not when the product of two codes $\mathcal{C}$ and $\mathcal{D}$ over $\mathbb{F}_{q^m}$ of length $n$ is smaller than $\min(n, \dim_{\mathbb{F}_{q^m}} \mathcal{C} \cdot \dim_{\mathbb{F}_{q^m}} \mathcal{D})$ (which is the dimension we expect for random codes $\mathcal{C}$ and $\mathcal{D}$) then this property survives for trace codes, namely do we have in this case

$$ \dim_{\mathbb{F}_q} \mathrm{Tr}(\mathcal{C}) \star \mathrm{Tr}(\mathcal{D}) < \min(n, \dim_{\mathbb{F}_q} \mathrm{Tr}(\mathcal{C}) \cdot \dim_{\mathbb{F}_q} \mathrm{Tr}(\mathcal{D}))? $$

This is related to open questions raised in [21, C.4]. This is indeed the case up to some extent, due to the following proposition:

**Proposition 13.** Let $\mathcal{C}$ and $\mathcal{D}$ be two linear codes over $\mathbb{F}_{q^m}$ with the same length $n$. Then

$$ \mathrm{Tr}(\mathcal{C}) \star \mathrm{Tr}(\mathcal{D}) \subseteq \sum_{i=0}^{m-1} \mathrm{Tr} \left( \mathcal{C} \star \mathcal{D}^{q^i} \right), \quad \text{where } \mathcal{D}^{q^i} \stackrel{\mathrm{def}}{=} \{d^{q^i} \mid d \in \mathcal{D}\}. $$

*Proof* It is readily verified that $\mathcal{D}^{q^i}$ is a linear code over $\mathbb{F}_{q^m}$. Let $c, d \in \mathbb{F}_{q^m}$. We have

$$ \begin{aligned} \mathrm{Tr}(c) \cdot \mathrm{Tr}(d) &= \left( \sum_{0 \le i \le m-1} c^{q^i} \right) \cdot \left( \sum_{0 \le i \le m-1} d^{q^i} \right) \\ &= \sum_{\substack{0 \le i \le m-1 \\ 0 \le j \le m-1}} c^{q^i} \cdot d^{q^j} \\ &= \sum_{0 \le j \le m-1} \sum_{0 \le i \le m-1} c^{q^i} \cdot d^{q^{(i+j) \mod m}} \\ &= \sum_{0 \le j \le m-1} \sum_{0 \le i \le m-1} c^{q^i} \cdot d^{q^{i+j}} \\ &= \sum_{0 \le i \le m-1} \mathrm{Tr}(c \cdot d^{q^i}). \end{aligned} $$

Because the trace acts component-wise on vectors, we also have for $c, d \in \mathbb{F}_q^n$,

$$ \mathrm{Tr}(c) \star \mathrm{Tr}(d) = \sum_{0 \le i \le m-1} \mathrm{Tr}(c \star d^{q^i}). $$

Hence

$$ \begin{aligned} \mathrm{Tr}(\mathcal{C}) \star \mathrm{Tr}(\mathcal{D}) &= \langle \mathrm{Tr}(c) \star \mathrm{Tr}(d) \mid c \in \mathcal{C}, d \in \mathcal{D} \rangle_{\mathbb{F}_q} \\ &= \left\langle \sum_{i=0}^{m-1} \mathrm{Tr} \left( c \star d^{q^i} \right) \mid c \in \mathcal{C}, d \in \mathcal{D} \right\rangle_{\mathbb{F}_q} \\ &\subseteq \sum_{i=0}^{m-1} \langle \mathrm{Tr} \left( c \star d^{q^i} \right) \mid c \in \mathcal{C}, d \in \mathcal{D} \rangle_{\mathbb{F}_q} \end{aligned} $$
12 On the dimension and structure of the square of the dual of a Goppa code

$$ = \sum_{i=0}^{m-1} \mathrm{Tr} (\mathcal{C} \star \mathcal{D}^{q^i}). \qquad \square $$

Note that for an $\mathbb{F}_{q^m}$-linear code $\mathcal{C}$, $\dim_{\mathbb{F}_q} \mathrm{Tr}(\mathcal{C}) \le \min(m \cdot \dim_{\mathbb{F}_{q^m}} \mathcal{C}, n)$, where $n$ is the code length of $\mathcal{C}$ and $\mathcal{D}$, and equality generally holds. An easy corollary of this proposition is that

**Corollary 14.** Let $\mathcal{C}$ and $\mathcal{D}$ be two $\mathbb{F}_{q^m}$-linear codes of a same length and which are such that $\dim_{\mathbb{F}_q} \mathrm{Tr}(\mathcal{C}) = m \cdot \dim_{\mathbb{F}_{q^m}} \mathcal{C}$ and $\dim_{\mathbb{F}_q} \mathrm{Tr}(\mathcal{D}) = m \cdot \dim_{\mathbb{F}_{q^m}} \mathcal{D}$. We have

$$ \dim_{\mathbb{F}_q} \mathrm{Tr}(\mathcal{C}) \cdot \dim_{\mathbb{F}_q} \mathrm{Tr}(\mathcal{D}) - \dim_{\mathbb{F}_q} (\mathrm{Tr}(\mathcal{C}) \star \mathrm{Tr}(\mathcal{D})) \\ \ge m \cdot (\dim_{\mathbb{F}_{q^m}} \mathcal{C} \cdot \dim_{\mathbb{F}_{q^m}} \mathcal{D} - \dim_{\mathbb{F}_{q^m}} (\mathcal{C} \star \mathcal{D})) $$

*Proof* We will drop in what follows the subscript indicating in the dimension if it is taken by considering the corresponding code as an $\mathbb{F}_{q^m}$ subspace or as an $\mathbb{F}_q$ subspace– it will be clear from the context.

We have

$$ \begin{aligned} \dim (\mathrm{Tr}(\mathcal{C}) \star \mathrm{Tr}(\mathcal{D})) &\le \sum_{i=0}^{m-1} \dim \mathrm{Tr} (\mathcal{C} \star \mathcal{D}^{q^i}) \quad (\text{by Prop. 13}) \\ &\le m \cdot \dim (\mathcal{C} \star \mathcal{D}) + \sum_{i=1}^{m-1} m \cdot \dim (\mathcal{C} \star \mathcal{D}^{q^i}) \\ &\le m (\dim (\mathcal{C} \star \mathcal{D}) - \dim \mathcal{C} \cdot \dim \mathcal{D}) + m \cdot \dim \mathcal{C} \cdot \dim \mathcal{D} \\ &\quad + m \sum_{i=1}^{m-1} \dim \mathcal{C} \cdot \dim (\mathcal{D}^{q^i}) \\ &= m (\dim (\mathcal{C} \star \mathcal{D}) - \dim \mathcal{C} \cdot \dim \mathcal{D}) + m^2 \dim \mathcal{C} \cdot \dim \mathcal{D} \\ &= m (\dim (\mathcal{C} \star \mathcal{D}) - \dim \mathcal{C} \cdot \dim \mathcal{D}) + \mathrm{dim} \mathrm{Tr}(\mathcal{C}) \cdot \mathrm{dim} \mathrm{Tr}(\mathcal{D}). \end{aligned} \qquad \square $$

**Remark 15.** In particular, this result implies that if we have two codes $\mathcal{C}$ and $\mathcal{D}$ over $\mathbb{F}_{q^m}$ for which $\dim_{\mathbb{F}_{q^m}} (\mathcal{C} \star \mathcal{D}) < \dim_{\mathbb{F}_{q^m}} \mathcal{C} \cdot \dim_{\mathbb{F}_{q^m}} \mathcal{D}$, then the same property survives for the corresponding trace codes:

$$ \dim_{\mathbb{F}_q} (\mathrm{Tr}(\mathcal{C}) \star \mathrm{Tr}(\mathcal{D})) < \dim_{\mathbb{F}_q} \mathrm{Tr}(\mathcal{C}) \cdot \dim_{\mathbb{F}_q} \mathrm{Tr}(\mathcal{D}). $$

In the case $\mathcal{C} = \mathcal{D}$, namely if we consider square codes, Proposition 13 can be refined to give

**Proposition 16.** Let $\mathcal{C}$ be a linear code over $\mathbb{F}_{q^m}$. We have

$$ \mathrm{Tr} (\mathcal{C} \star \mathcal{C}^{q^u}) = \mathrm{Tr} (\mathcal{C} \star \mathcal{C}^{q^{m-u}}) \qquad (6) $$
$$ (\mathrm{Tr}(\mathcal{C}))^{*2} \subseteq \sum_{u=0}^{\lfloor m/2 \rfloor} \mathrm{Tr}(\mathcal{C} \star \mathcal{C}^{q^u}) \quad (7) $$

$$ \dim_{\mathbb{F}_q} \left( \mathrm{Tr} \left( \mathcal{C} \star \mathcal{C}^{q^{m/2}} \right) \right) \le m \frac{(\dim_{\mathbb{F}_{q^m}} (\mathcal{C}))^2}{2} \quad \text{if m is even} \quad (8) $$

**Proof of (6).** Let $\mathbf{c}, \mathbf{d} \in \mathcal{C}$. Since the trace acts component-wise on vectors and $\mathrm{Tr}(x) = \mathrm{Tr}(x^{q^u})$ for any $x \in \mathbb{F}_{q^m}$ and natural number $u$,

$$ \mathrm{Tr} (\mathbf{c} \star \mathbf{d}^{q^u}) = \mathrm{Tr} ((\mathbf{c} \star \mathbf{d}^{q^u})^{q^{m-u}}) = \mathrm{Tr} (\mathbf{c}^{q^{m-u}} \star \mathbf{d}^{q^m}) = \mathrm{Tr} (\mathbf{d} \star \mathbf{c}^{q^{m-u}}) \in \mathrm{Tr} (\mathcal{C} \star \mathcal{C}^{(q^{m-u})}). $$

This shows that $\mathrm{Tr}(\mathcal{C} \star \mathcal{C}^{q^u}) \subseteq \mathrm{Tr}(\mathcal{C} \star \mathcal{C}^{q^{m-u}})$. By replacing $u$ by $m-u$ in the equality above, we obtain the reverse inclusion, which finishes the proof of (6).

**Proof of (7).**

$$ (\mathrm{Tr}(\mathcal{C}))^{*2} \subseteq \sum_{u=0}^{m-1} \mathrm{Tr}(\mathcal{C} \star \mathcal{C}^{q^u}) \quad (\text{by Prop. 13}) $$

$$ \subseteq \sum_{u=0}^{\lfloor m/2 \rfloor} \mathrm{Tr}(\mathcal{C} \star \mathcal{C}^{q^u}) \quad (\text{by (6)}). $$

**Proof of (8).** Let $\{\mathbf{c}_1, \dots, \mathbf{c}_r\}$ be a basis of $\mathcal{C}$ where $r \stackrel{\text{def}}{=} \dim(\mathcal{C})$. The trace code $\mathrm{Tr}(\mathcal{C} \star \mathcal{C}^{q^{m/2}})$ is generated by the $\mathrm{Tr}(\beta^{q^\ell} \mathbf{c}_i \star \mathbf{c}_j^{q^{m/2}})$ where $\{\beta, \beta^q, \dots, \beta^{q^{m-1}}\}$ is a normal basis of $\mathbb{F}_{q^m}$ and $\ell$ ranges over $\{0, \dots, m-1\}$ and $i, j$ over $\{1, \dots, r\}$. Since for any $0 \le \ell \le \frac{m}{2}-1$, $1 \le i, j \le r$,

$$ \mathrm{Tr}(\beta^{q^\ell} \mathbf{c}_i \star \mathbf{c}_j^{q^{m/2}}) = \mathrm{Tr}(\beta^{q^\ell + \frac{m}{2}} \mathbf{c}_i^{q^{m/2}} \star \mathbf{c}_j) = \mathrm{Tr}(\beta^{q^\ell + \frac{m}{2}} \mathbf{c}_j \star \mathbf{c}_i^{q^{m/2}}), $$

this implies that $\mathrm{Tr}(\mathcal{C} \star \mathcal{C}^{q^{m/2}})$ is generated by the (smaller) set $\mathrm{Tr}(\beta^{q^\ell} \mathbf{c}_i \star \mathbf{c}_j^{q^{m/2}})$ where $\ell$ ranges over $\{0, \dots, m/2-1\}$ and $i, j$ over $\{1, \dots, r\}$. This is a set of cardinality $\frac{mr^2}{2}$. $\square$

Note that [20] which solved the highly non trivial open problem of constructing a family of asymptotically good binary linear codes whose square is also asymptotically good proves some intermediate results in it which in some sense are equivalent to some of the results presented in this section. For instance, Proposition 4 in [20] gives a basis for the space of symmetric bilinear forms of $\mathbb{F}_{q^m}$ seen as vector space of dimension $m$ over $\mathbb{F}_q$, in terms of trace operators. In essence, our Proposition 16 is nothing but a corollary of Proposition 4.

Proposition 16 has a corollary which is similar to Corollary 14, namely that

**Corollary 17.** Let $\mathcal{C}$ be an $\mathbb{F}_{q^m}$-linear code. We have

$$ \dim_{\mathbb{F}_q} (\mathrm{Tr}(\mathcal{C}))^{*2} \le m \cdot \dim_{\mathbb{F}_{q^m}} \mathcal{C}^{*2} + \binom{m}{2} (\dim_{\mathbb{F}_{q^m}} \mathcal{C})^2. \quad (9) $$
14 On the dimension and structure of the square of the dual of a Goppa code

Furthermore if $\dim_{\mathbb{F}_q} \mathrm{Tr}(\mathscr{C}) = m \cdot \dim_{\mathbb{F}_{q^m}} \mathscr{C}$ then

$$ \dim_{\mathbb{F}_q} (\mathrm{Tr}(\mathscr{C}))^{*2} - \left( \dim_{\mathbb{F}_q} \mathrm{Tr}(\mathscr{C}) + 1 \right) \le m \left[ \dim_{\mathbb{F}_{q^m}} \mathscr{C}^{*2} - \left( \dim_{\mathbb{F}_{q^m}} \mathscr{C} + 1 \right) \right]. \quad (10) $$

Proof

Proof of (9): by using (7) of Proposition 16, we obtain

$$ \dim (\mathrm{Tr}(\mathscr{C}))^{*2} \le \sum_{i=0}^{\lfloor \frac{m}{2} \rfloor} \dim \mathrm{Tr} \left( \mathscr{C} \star \mathscr{C}^{q^i} \right). \quad (11) $$

In the case of odd $m$, we deduce that

$$ \begin{aligned} \dim (\mathrm{Tr}(\mathscr{C}))^{*2} &\le m \cdot \dim \mathscr{C}^{*2} + \sum_{i=1}^{\lfloor \frac{m}{2} \rfloor} m \cdot \dim \mathscr{C} \star \mathscr{C}^{q^i} \\ &= m \cdot \dim \mathscr{C}^{*2} + m \sum_{i=1}^{\lfloor \frac{m}{2} \rfloor} \dim \mathscr{C} \cdot \dim \mathscr{C}^{q^i} \\ &= m \cdot \dim \mathscr{C}^{*2} + \frac{m(m-1)}{2} (\dim \mathscr{C})^2 \\ &= m \cdot \dim \mathscr{C}^{*2} + \binom{m}{2} (\dim \mathscr{C})^2. \end{aligned} $$

On the other hand, if $m$ is even, we have

$$ \begin{aligned} \dim (\mathrm{Tr}(\mathscr{C}))^{*2} &\le m \cdot \dim \mathscr{C}^{*2} + \sum_{i=1}^{\frac{m}{2}-1} m \cdot \dim \mathscr{C} \cdot \dim \mathscr{C}^{q^i} + \dim \mathrm{Tr} \left( \mathscr{C} \star \mathscr{C}^{q^{m/2}} \right) \\ &\le m \cdot \dim \mathscr{C}^{*2} + \frac{m(m-2)}{2} (\dim \mathscr{C})^2 + \frac{m(\dim \mathscr{C})^2}{2} \\ &\qquad \text{(by using (8) of Proposition 16)} \\ &= m \cdot \dim \mathscr{C}^{*2} + \binom{m}{2} (\dim \mathscr{C})^2. \end{aligned} $$

Proof of (10):

$$ \begin{aligned} \dim (\mathrm{Tr}(\mathscr{C}))^{*2} - \left( \dim \mathrm{Tr}(\mathscr{C}) + 1 \right) &\le m \cdot \dim \mathscr{C}^{*2} + \binom{m}{2} (\dim \mathscr{C})^2 - \left( \dim \mathrm{Tr}(\mathscr{C}) + 1 \right) \\ &\qquad \text{(by using (9))} \\ &= m \cdot \dim \mathscr{C}^{*2} + \frac{m(m-1)}{2} (\dim \mathscr{C})^2 - \binom{m \dim \mathscr{C} + 1}{2} \\ &= m \cdot \dim \mathscr{C}^{*2} + m \cdot \dim \mathscr{C} \cdot \left[ \frac{m-1}{2} \dim \mathscr{C} - \frac{m \dim \mathscr{C} + 1}{2} \right] \\ &= m \cdot \dim \mathscr{C}^{*2} - m \cdot \dim \mathscr{C} \cdot \frac{\dim \mathscr{C} + 1}{2} \end{aligned} $$
$$= m \left[ \dim \mathscr{C}^{*2} - \left( \dim \mathscr{C} + 1 \right) \right].$$

□

Similarly to Corollary 14, Corollary 17 implies that if the dimension of a square code $\mathscr{C}^{*2}$ over $\mathbb{F}_{q^m}$ is smaller than what we expect from a random code, namely that $\dim(\mathscr{C}^{*2}) < (\dim_{\mathbb{F}_2} \mathscr{C}+1)$ (if $(\dim_{\mathbb{F}_2} \mathscr{C}+1)$ is smaller than the code length) then this property survives for the trace code:

$$\dim (\mathrm{Tr}(\mathscr{C}))^{*2} < \left( \dim \mathrm{Tr}(\mathscr{C}) + 1 \right) / 2.$$

## 4 Alternant case with $e_{\mathscr{A}} = 0$ and Goppa case with $e_{\mathscr{G}} = 0$

In this section, we are going to give a first upper bound on the dimension of the square of the dual of an alternant or Goppa code which is valid for all parameters and is tight when $e_{\mathscr{A}} = 0$ for random alternant codes and when $r < q - 1$ for Goppa codes. This will be a direct application of the general results of Section 3 from which we derive:

**Theorem 18.** Let $\mathscr{A}_r(\mathbf{x}, \mathbf{y})$ be an alternant code over $\mathbb{F}_q$. Then

$$\dim_{\mathbb{F}_q} (\mathscr{A}_r(\mathbf{x}, \mathbf{y})^{\perp})^{*2} \le \binom{rm+1}{2} - \frac{m}{2}(r-1)(r-2). \quad (12)$$

*Remark 19.* Notice that the upper bound appearing in this theorem coincides exactly with the prediction of the dimension of the square code derived from the predictions given in [11] used together with [15, Proposition 1] in the alternant case corresponding to $e_{\mathscr{A}} = 0$, see (3) or the Goppa case with $r < q - 1$, see (4). In other words, this theorem shows that this prediction is actually an upper bound on the dimension and the experimental evidence gathered in [11] actually shows that the dimensions of random alternant or Goppa codes agree with this upper bound in such a case.

*Proof* We let $\mathscr{C} \stackrel{\mathrm{def}}{=} \mathbf{GRS}_r(\mathbf{x}, \mathbf{y})$. Note that $\mathscr{A}_r(\mathbf{x}, \mathbf{y})^{\perp} = \mathrm{Tr}(\mathscr{C})$. We apply Corollary 17 with such a $\mathscr{C}$ and get that

$$\begin{align*}
\dim_{\mathbb{F}_q} (\mathrm{Tr}(\mathscr{C}))^{*2} &\le m \cdot \dim_{\mathbb{F}_{q^m}} \mathscr{C}^{*2} + \binom{m}{2} (\dim_{\mathbb{F}_{q^m}} \mathscr{C})^2 \\
&= m(2r-1) + \frac{m(m-1)r^2}{2} \quad \text{(by Proposition 11)} \\
&= (2(2r-1) + (m-1)r^2) \frac{m}{2} \\
&= (r(mr+1) - (r-1)(r-2)) \frac{m}{2}
\end{align*}$$
16 On the dimension and structure of the square of the dual of a Goppa code

$$ = \binom{rm+1}{2} - \frac{m}{2}(r-1)(r-2). $$

□

## 5 Alternant case with $e_{\mathcal{A}} > 0$

In this section, we will show new linear relationships arising for alternant codes (hence also for Goppa codes) of high enough order $r$. More precisely, the threshold value for which new relations are guaranteed is $r \ge q + 1$, i.e. $e_{\mathcal{A}} > 0$. Our main result in this section is that

**Theorem 20.** Let $\mathcal{A}_r(\mathbf{x}, \mathbf{y})$ be an alternant code over $\mathbb{F}_q$. Then

$$ \dim_{\mathbb{F}_q}(\mathcal{A}_r(\mathbf{x}, \mathbf{y})^{\perp})^{*2} \le \binom{rm+1}{2} - \frac{m}{2}(r-1) \left( (2e_{\mathcal{A}}+1)r - 2 \frac{q^{e_{\mathcal{A}}+1}-1}{q-1} \right). \quad (13) $$

*Remark 21.* Note that the upper bound on the dimension coincides with the prediction (3) given for generic alternant codes. In other words, this theorem shows that this prediction is actually an upper bound on the dimension and the experimental evidence gathered in [11] actually shows that the dimensions of random alternant codes agree with this upper bound in such a case.

The reason that we have a refinement of the upper bound of Theorem 18 for values of $r$ for which $e_{\mathcal{A}} > 0$ comes from the fact that when we apply Proposition 16 with $\mathcal{C} \stackrel{\text{def}}{=} \text{GRS}_r(\mathbf{x}, \mathbf{y})$ (which is the relevant quantity here since $\text{Tr}(\mathcal{C}) = \mathcal{A}_r(\mathbf{x}, \mathbf{y})^{\perp}$) we get terms of the form $\text{Tr}(\mathcal{C} \star \mathcal{C}^{q^u})$ which will have a smaller dimension than the generic upper bound $mr^2$. This is due to the fact that these $\text{Tr}(\mathcal{C} \star \mathcal{C}^{q^u})$ will actually be duals of alternant codes for small values of $u$ as shown by the following lemma

**Lemma 22.** Let $\mathcal{C} \stackrel{\text{def}}{=} \text{GRS}_r(\mathbf{x}, \mathbf{y})$ and $f \stackrel{\text{def}}{=} [\log_q(r)]$. We have

$$ \text{Tr}(\mathcal{C} \star \mathcal{C}^{q^u}) \subseteq \mathcal{A}_{(r-1)(1+q^u)+1}(\mathbf{x}, \mathbf{y}^{1+q^u})^{\perp} \quad \text{for all non-negative integers } u, \quad (14) $$

$$ \text{Tr}(\mathcal{C} \star \mathcal{C}^{q^u}) = \mathcal{A}_{(r-1)(1+q^u)+1}(\mathbf{x}, \mathbf{y}^{1+q^u})^{\perp} \quad \text{for all integers } u \text{ in } \{0, \dots, f\}. \quad (15) $$

*Proof* We first notice that

$$ \text{Tr}(\mathcal{C} \star \mathcal{C}^{q^u}) = \langle \text{Tr}(\alpha_l \mathbf{x}^{a+bq^u} \mathbf{y}^{1+q^u}) | 0 \le l < m, 0 \le a, b \le r-1 \rangle_{\mathbb{F}_q}. $$

Clearly the powers $a + bq^u$ are all smaller than or equal to $(r-1)(1+q^u)$. This directly implies (14). For the equality case, we observe that we get all the powers in
$\{0, \dots, (r-1)(1+q^u)\}$ as long as $r-1 \ge q^u - 1$, that is $r \ge q^u$ which is equivalent to $u \le \lfloor \log_q(r) \rfloor$. $\square$

The previous lemma implies that

**Corollary 23.** Let $\mathcal{C} \stackrel{\text{def}}{=} \text{GRS}_r(\mathbf{x}, \mathbf{y})$. For all non-negative integers $u$, we have

$$ \dim_{\mathbb{F}_q} \text{Tr} (\mathcal{C} \star \mathcal{C}^{q^u}) \le m((r-1)(q^u+1)+1). $$

When $r$ is large enough with respect to the field size $q$, this corollary provides a tighter upper bound with respect to the trivial $\dim_{\mathbb{F}_q} \text{Tr} (\mathcal{C} \star \mathcal{C}^{q^u}) \le mr^2$. More precisely, since

$$ r \ge q^u + 1 \Rightarrow r^2 \ge r(q^u + 1) \ge (r-1)(q^u + 1) + 1 $$

and

$$ r \le q^u \Rightarrow r^2 \le rq^u \le (r-1)(q^u + 1) + 1, $$

for any $0 \le u < m/2$, the inequality

$$ \dim_{\mathbb{F}_q} \text{Tr} (\mathcal{C} \star \mathcal{C}^{q^u}) \le m \cdot \min ((r-1)(q^u + 1) + 1, r^2) $$

becomes

$$ \dim_{\mathbb{F}_q} \text{Tr} (\mathcal{C} \star \mathcal{C}^{q^u}) \le \begin{cases} m((r-1)(q^u + 1) + 1) & \text{if } r > q^u \\ mr^2 & \text{else.} \end{cases} \quad (16) $$

From (16) we obtain directly Theorem 20. The proof goes as follows.

**Proof of Theorem 20** Let $\mathcal{C} \stackrel{\text{def}}{=} \text{GRS}_r(\mathbf{x}, \mathbf{y})$. Recalling that

$$ e_{\mathcal{A}} \stackrel{\text{def}}{=} \max\{i \in \mathbb{N} \mid r \ge q^i + 1\} = \lfloor \log_q(r-1) \rfloor, $$

we obtain

$$ \begin{aligned} \dim_{\mathbb{F}_q} (\mathcal{A}_r(\mathbf{x}, \mathbf{y})^{\perp})^{*2} &\le \dim_{\mathbb{F}_q} \sum_{u=0}^{\lfloor \frac{m}{2} \rfloor} \text{Tr} (\mathcal{C} \star \mathcal{C}^{q^u}) \quad (\text{by Prop. (16)}) \\ &\le \sum_{u=0}^{\lfloor \frac{m}{2} \rfloor} \dim_{\mathbb{F}_q} \text{Tr} (\mathcal{C} \star \mathcal{C}^{q^u}) \\ &\le \sum_{u=0}^{e_{\mathcal{A}}} m((r-1)(q^u+1)+1) + \left(\frac{m-1}{2} - e_{\mathcal{A}}\right) mr^2 \\ &= \binom{rm+1}{2} - \frac{m}{2}(r-1)\left((2e_{\mathcal{A}}+1)r - 2\frac{q^{e_{\mathcal{A}}+1}-1}{q-1}\right). \end{aligned} $$

$\square$
## 6 Goppa case with $r \ge q-1$

In the previous two sections, we found linear relationships within the individual $\mathrm{Tr}(\mathcal{C} \star \mathcal{C}^{q^u})$ subspaces, showing that they are spanned by less than $r^2m$ vectors if $r$ is large enough. We will see that the dimension of some $\mathrm{Tr}(\mathcal{C} \star \mathcal{C}^{q^u})$ is even smaller in the Goppa case with $r \ge q-1$ (see (18) below). Moreover, they are no more disjoint, i.e. $\dim_{\mathbb{F}_q}(\mathrm{Tr}(\mathcal{C} \star \mathcal{C}^{q^u}) \cap \mathrm{Tr}(\mathcal{C} \star \mathcal{C}^{q^v})) > 0$ for some $0 \le u < v \le e_g$. We will namely prove that

**Theorem 24.** Let $\mathcal{C} \stackrel{\mathrm{def}}{=} \mathrm{GRS}_r(\mathbf{x}, \mathbf{y})$, where $y_i = \frac{1}{\Gamma(x_i)}$ and $\Gamma$ is a polynomial of degree $r$. Let us define for any positive integer $v$

$$ \mathcal{B}_v \stackrel{\mathrm{def}}{=} \mathcal{A}_{r(q^v - q^{v-1} + 1)}(\mathbf{x}, \mathbf{y}^{q^v+1})^{\perp}, \quad \text{and} \quad \mathcal{B}_0 \stackrel{\mathrm{def}}{=} \mathcal{A}_{2r-1}(\mathbf{x}, \mathbf{y}^2)^{\perp}. \quad (17) $$

Let $f \stackrel{\mathrm{def}}{=} [\log_q(r)]$. Then

$$ \mathrm{Tr}(\mathcal{C} \star \mathcal{C}^{q^v}) \subseteq \mathcal{B}_v \quad \text{for all positive integers } v, \qquad (18) $$

$$ \mathrm{Tr}(\mathcal{C} \star \mathcal{C}^{q^u}) = \mathcal{B}_u \quad \text{for } 0 \le u \le f, \qquad (19) $$

$$ \mathrm{Tr}(\mathcal{C} \star \mathcal{C}) \subseteq \mathrm{Tr}(\mathcal{C} \star \mathcal{C}^q) \subseteq \dots \subseteq \mathrm{Tr}(\mathcal{C} \star \mathcal{C}^{q^u}) \quad \text{for } 0 \le u \le f. \quad (20) $$

Before proving this theorem it will be useful to state and prove two lemmas. The first one deals with the inclusion $\mathrm{Tr}(\mathcal{C} \star \mathcal{C}^{q^v}) \subseteq \mathcal{B}_v$. For this, we first recall Lemma 22 which when applied to Goppa codes yields immediately that for all integers $v$ we have:

$$ \mathrm{Tr}(\mathcal{C} \star \mathcal{C}^{q^v}) \subseteq \left\{ \mathrm{Tr} \left( \frac{P(\mathbf{x})}{\Gamma(\mathbf{x})^{q^v+1}} \right) \mid \deg P < (r-1)(q^v+1) + 1 \right\} \quad (21) \\ = \mathcal{A}_{(r-1)(q^v+1)+1}(\mathbf{x}, \mathbf{y}^{q^v+1})^{\perp}. $$

On the other hand, by definition of $\mathcal{B}_v$ we have

$$ \mathcal{B}_v = \left\{ \mathrm{Tr} \left( \frac{P(\mathbf{x})}{\Gamma(\mathbf{x})^{q^v+1}} \right) \mid \deg P < r(q^v - q^{v-1} + 1) \right\}. \quad (22) $$

Depending on how $q$ compares to $r$, $r(q^v - q^{v-1} + 1)$ might be either greater or smaller than $(r-1)(q^v + 1) + 1$. The key for showing the inclusion $\mathrm{Tr}(\mathcal{C} \star \mathcal{C}^{q^v}) \subseteq \mathcal{B}_v$ will be to show that under certain conditions a codeword of the form $\mathrm{Tr}(\frac{P(\mathbf{x})}{\Gamma(\mathbf{x})^{q^v+1}})$ can be written as $\mathrm{Tr}(\frac{Q(\mathbf{x})}{\Gamma(\mathbf{x})^{q^v+1}}) + \mathbf{c}$ for some codeword $\mathbf{c} \in \mathcal{B}_v$ with a polynomial $Q$ such that $\deg Q < \deg P$. For performing this task we will use the following lemma.
**Lemma 25.** Let $P(X)$ be a polynomial in $\mathbb{F}_{q^m}[X]$ and consider the Euclidean division of $P$ by $\Gamma^{q^v-q^{v-1}+1}$: $P = A\Gamma^{q^v-q^{v-1}+1} + B$ where $\deg B < \deg \Gamma^{q^v-q^{v-1}+1}$. We have

$$ \mathrm{Tr} \left( \frac{P(\boldsymbol{x})}{\Gamma(\boldsymbol{x})^{q^v+1}} \right) = \mathrm{Tr} \left( \frac{A(\boldsymbol{x})^q \Gamma(\boldsymbol{x})}{\Gamma(\boldsymbol{x})^{q^v+1}} \right) + \boldsymbol{c}, \quad \text{for some } \boldsymbol{c} \in \mathcal{B}_v \quad (23) $$

$$ \deg A^q \Gamma < \deg P \quad \text{if } \deg P < r(q^v + 1). \quad (24) $$

**Proof** For the first point, we just have to observe that

$$ \begin{aligned} \mathrm{Tr} \left( \frac{P(\boldsymbol{x})}{\Gamma(\boldsymbol{x})^{q^v+1}} \right) &= \mathrm{Tr} \left( \frac{A(\boldsymbol{x})\Gamma(\boldsymbol{x})^{q^v-q^{v-1}+1} + B(\boldsymbol{x})}{\Gamma(\boldsymbol{x})^{q^v+1}} \right) \\ &= \mathrm{Tr} \left( \frac{A(\boldsymbol{x})}{\Gamma(\boldsymbol{x})^{q^v-1}} \right) + \mathrm{Tr} \left( \frac{B(\boldsymbol{x})}{\Gamma(\boldsymbol{x})^{q^v+1}} \right) \\ &= \mathrm{Tr} \left( \frac{A(\boldsymbol{x})^q}{\Gamma(\boldsymbol{x})^{q^v}} \right) + \mathrm{Tr} \left( \frac{B(\boldsymbol{x})}{\Gamma(\boldsymbol{x})^{q^v+1}} \right) \quad (\text{since } \mathrm{Tr}(\alpha^q) = \mathrm{Tr}(\alpha) \text{ for } \alpha \in \mathbb{F}_{q^m}) \\ &= \mathrm{Tr} \left( \frac{A(\boldsymbol{x})^q \Gamma(\boldsymbol{x})}{\Gamma(\boldsymbol{x})^{q^v+1}} \right) + \boldsymbol{c} \quad \text{with } \boldsymbol{c} \in \mathcal{B}_v. \end{aligned} $$

The last equality follows immediately from the definition of $\mathcal{B}_v$ (see (22)) and the fact that $\deg B < r(q^v - q^{v-1} + 1)$. For the second point, let us just observe that either $A = 0$ in which case (24) clearly holds or

$$ \deg A = \deg P - r(q^v - q^{v-1} + 1) $$

in which case

$$ \deg A^q \Gamma = q \deg P - q r(q^v - q^{v-1} + 1) + r = q \deg P - r(q-1)(q^v + 1). $$

Clearly

$$ \begin{aligned} \deg A^q \Gamma < \deg P &\Leftrightarrow q \deg P - r(q-1)(q^v+1) < \deg P \\ &\Leftrightarrow \deg P < r(q^v+1). \end{aligned} $$

□

A consequence of Lemma 25 is that

**Corollary 26.** Let $\mathcal{B}_v$ be the dual code defined in Equation (17). Then, for any $r(q^v - q^{v-1} + 1) \le d \le r(q^v + 1)$,

$$ \mathcal{B}_v = \mathcal{A}_d(\boldsymbol{x}, \boldsymbol{y}^{q^v+1})^{\perp} = \mathcal{G}(\boldsymbol{x}, \Gamma^{q^v+1})^{\perp}. $$

**Proof** It follows from Lemma 25 that, if $P(X) \in \mathbb{F}_{q^m}[X]$ has degree strictly smaller than $r(q^v + 1)$, then

$$ \mathrm{Tr} \left( \frac{P(\boldsymbol{x})}{\Gamma(\boldsymbol{x})^{q^v+1}} \right) \in \mathcal{B}_v. $$

Since

$$ \mathcal{A}_{r(q^v+1)}(\boldsymbol{x}, \boldsymbol{y}^{q^v+1})^{\perp} = \left\{ \mathrm{Tr} \left( \frac{P(\boldsymbol{x})}{\Gamma(\boldsymbol{x})^{q^v+1}} \right) \mid \deg P < r(q^v+1) \right\}, $$
20 On the dimension and structure of the square of the dual of a Goppa code

we get

$$
\mathcal{B}_v \supseteq \mathcal{A}_{r(q^v+1)}(\mathbf{x}, \mathbf{y}^{q^v+1})^{\perp}.
$$

Since $\mathcal{B}_v \stackrel{\text{def}}{=} \mathcal{A}_{r(q^v - q^{v-1}+1)}(\mathbf{x}, \mathbf{y}^{q^v+1})^{\perp}$ we have also trivially the reverse inclusion
and therefore

$$
\mathcal{B}_v = \mathcal{A}_{r(q^v+1)}(\mathbf{x}, \mathbf{y}^{q^v+1})^{\perp}. \qquad (25)
$$

Since the coordinates of $\mathbf{y}^{q^v+1}$ are the inverse of the evaluation over the $x_i$'s of the
polynomial $\Gamma^{q^v+1}$ of degree $r(q^v+1)$, equality (25) shows that $\mathcal{B}_v$ is the dual of a
Goppa code of degree $r(q^v+1)$. Moreover, (25) implies that all the codes

$$
\mathcal{A}_d(\mathbf{x}, \mathbf{y}^{q^v+1})^{\perp},
$$

with $r(q^v - q^{v-1} + 1) \le d \le r(q^v + 1)$, collapse into the same code $\mathcal{B}_v$.

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

The second lemma shows that the $\mathcal{B}_v$'s form a nested family of codes:

**Lemma 27.** We have for all $v \ge 0$:

$$
\mathcal{B}_0 \subseteq \mathcal{B}_1 \subseteq \dots \subseteq \mathcal{B}_v \subseteq \mathcal{B}_{v+1} \subseteq \dots
$$

Proof We will first prove that $\mathcal{B}_v \subseteq \mathcal{B}_{v+1}$ for $v \ge 1$. Let us notice that

$$
\begin{align}
\mathcal{B}_v &= \left\langle \operatorname{Tr} \left( \alpha_l \mathbf{x}^c \mathbf{y}^{q^v+1} \right) \mid 0 \le l < m, 0 \le c < r(q^v - q^{v-1} + 1) \right\rangle_{\mathbb{F}_q} \nonumber \\
&= \left\{ \operatorname{Tr} \left( \frac{P(\mathbf{x})}{\Gamma(\mathbf{x})^{q^v+1}} \right) : P \in \mathbb{F}_{q^m}[X], \operatorname{deg}(P) < r(q^v - q^{v-1} + 1) \right\} \tag{26}
\end{align}
$$

Consider now a codeword $\mathrm{Tr} \left( \frac{P(\mathbf{x})}{\Gamma(\mathbf{x})^{q^v+1}} \right)$ in $\mathcal{B}_v$ and let us prove that it is in $\mathcal{B}_{v+1}$.
By (26) we know that

$$
\deg P < r(q^v - q^{v-1} + 1). \tag{27}
$$

Then, let us notice that

$$
\mathrm{Tr} \left( \frac{P(\mathbf{x})}{\Gamma(\mathbf{x})^{q^v+1}} \right) = \mathrm{Tr} \left( \frac{P(\mathbf{x})\Gamma(\mathbf{x})^{q^v+1-q^v}}{\Gamma(\mathbf{x})^{q^v+1+1}} \right)
$$

and that

$$
\deg P(X) \Gamma(X)^{q^{v+1}-q^v} < r(q^v - q^{v-1} + 1) + r(q^{v+1} - q^v) = rq^{v+1} - rq^{v-1} + r < r(q^{v+1} + 1).
$$

By Corollary 26, $\mathrm{Tr} \left( \frac{P(\mathbf{x})}{\Gamma(\mathbf{x})^{q^v+1}} \right) \in \mathcal{B}_{v+1}$ and the thesis follows. $\square$

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

We are now ready to prove Theorem 24.

*Proof of Theorem 24* *Proof of (18)*. Lemma 22 implies that

$$
\begin{align}
\mathrm{Tr} \left( \mathcal{C} \star \mathcal{C}^{q^v} \right) &\subseteq \left\{ \mathrm{Tr} \left( \frac{P(\mathbf{x})}{\Gamma(\mathbf{x})^{q^v+1}} \right) : \deg P < (r-1)(q^v+1) + 1 \right\} \nonumber \\
&= \mathcal{A}_{(r-1)(q^v+1)+1}(\mathbf{x}, \mathbf{y}^{q^v+1})^{\perp} \nonumber \\
&\subseteq \mathcal{A}_{r(q^v+1)}(\mathbf{x}, \mathbf{y}^{q^v+1})^{\perp} \nonumber \\
&= \mathcal{B}_v. \tag{28}
\end{align}
$$

*Proof of (19).* When $v \le f$, Lemma 22 shows that the inclusion (28) is actually an
equality. We therefore have

$$ \mathrm{Tr}(\mathcal{C} \star \mathcal{C}^{q^v}) = \mathcal{A}_{(r-1)(q^v+1)+1}(\mathbf{x}, \mathbf{y}^{q^v+1})^{\perp}. $$

On the other hand, from (18), we know that

$$ \mathrm{Tr}(\mathcal{C} \star \mathcal{C}^{q^v}) \subseteq \mathcal{B}_v = \mathcal{A}_{r(q^v-q^{v-1}+1)}(\mathbf{x}, \mathbf{y}^{q^v+1})^{\perp}. \quad (29) $$

Observe now that $r \ge q^v$ implies that $(r-1)(q^v+1) \ge r(q^v - q^{v-1} + 1) - 1$, since

$$ (r-1)(q^v+1) - r(q^v - q^{v-1} + 1) + 1 = (r-q)q^{v-1}. $$

This shows that

$$ \mathcal{B}_v = \mathcal{A}_{r(q^v-q^{v-1}+1)}(\mathbf{x}, \mathbf{y}^{q^v+1})^{\perp} \subseteq \mathcal{A}_{(r-1)(q^v+1)+1}(\mathbf{x}, \mathbf{y}^{q^v+1})^{\perp} $$

which combined with the reverse inclusion (29) proves Equality (19).

*Proof of (20).* This is a direct consequence of Lemma 27 and that the $\mathcal{B}_v$'s coincide with the $\mathrm{Tr}(\mathcal{C} \star \mathcal{C}^{q^v})$'s in this range from (19). $\square$

A direct consequence of Theorem 24 is that

**Corollary 28.** Let $\mathcal{G}(\mathbf{x}, \Gamma)$ be a Goppa code of order $r \ge q-1$ over $\mathbb{F}_q$. Then

$$ (\mathcal{G}(\mathbf{x}, \Gamma)^{\perp})^{\star 2} \subseteq \mathcal{B}_e + \sum_{u=e+1}^{\lfloor \frac{m}{2} \rfloor} \mathrm{Tr}(\mathcal{C} \star \mathcal{C}^{q^u}), $$

for any non-negative integer $e$.

We can therefore conclude that

**Corollary 29.** Let $\mathcal{G}(\mathbf{x}, \Gamma)$ be a Goppa code of order $r \ge q-1$ over $\mathbb{F}_q$. Then

$$ \dim_{\mathbb{F}_q}(\mathcal{G}(\mathbf{x}, \Gamma)^{\perp})^{\star 2} \le \left(\frac{rm+1}{2}\right) - \frac{m}{2}r \left((2eg+1)r - 2(q-1)q^{eg-1} - 1\right). $$

*Proof* From Corollary 28

$$ \begin{aligned} \dim_{\mathbb{F}_q}(\mathcal{G}(\mathbf{x}, \Gamma)^{\perp})^{\star 2} &\le \dim_{\mathbb{F}_q}(\mathcal{B}_e) + \sum_{u=e+1}^{\lfloor \frac{m}{2} \rfloor} \dim_{\mathbb{F}_q} \mathrm{Tr}(\mathcal{C} \star \mathcal{C}^{q^u}) \\ &\quad (\text{for arbitrary } e \in \{0, \dots, \lfloor \frac{m}{2} \rfloor\}) \\ &\le rm(q^e - q^{e-1} + 1) + \left(\frac{m-1}{2} - e\right) mr^2 \\ &= \left(\frac{rm+1}{2}\right) - \frac{m}{2}r \left((2e+1)r - 2(q-1)q^{e-1} - 1\right). \end{aligned} $$
22 On the dimension and structure of the square of the dual of a Goppa code

We want now to minimize the function $(\binom{rm+1}{2}) - \frac{m}{2}r$ ($2(e+1)r - 2(q-1)q^{e-1} - 1$) with respect to $e$. By removing the constant part in $e$, this clearly becomes equivalent to maximizing

$$T(e) \stackrel{\text{def}}{=} er - (q-1)q^{e-1}$$

over $\{0, \dots, \lfloor \frac{m}{2} \rfloor\}$. We compute the discrete derivative $\Delta T: e \to T(e+1) - T(e)$, $\Delta T(e) = T(e+1) - T(e) = ((e+1)r - (q-1)q^{e+1-1}) - (er - (q-1)q^{e-1}) = r - (q-1)^2 q^{e-1}$.

The maximum is attained at the least integer $e$ such that $\Delta T(e) \le 0$. This corresponds to the least integer $e$ such that $e \ge \log_q(\frac{r}{(q-1)^2}) + 1$, i.e. $\lfloor \log_q(\frac{r}{(q-1)^2}) + 1 \rfloor = e \in \mathbb{G}$ minimizes the function $T$ and consequently

$$\dim_{\mathbb{F}_q}(\mathscr{G}(\mathbf{x}, \Gamma)^{\perp})^{*2} \le \binom{rm+1}{2} - \frac{m}{2}r((2e\mathscr{G} + 1)r - 2(q-1)q^{e\mathscr{G}-1} - 1).$$

□

Remark 30. From the computation given in the proof of Corollary 29 and knowing that the upper bound is usually an equality, we also infer that with high probability

$$\mathscr{B}_{e, \mathscr{G}} = \sum_{u=0}^{e, \mathscr{G}} \mathrm{Tr} \left( \mathscr{C} \star \mathscr{C}^{q^u} \right).$$

This has been verified experimentally.

## 7 Conclusion

In this article we revisited the distinguisher for random alternant and Goppa codes presented for the first time in [11] through a different approach, namely using squares of codes. With this simple but powerful tool we were able to provide explicitly the linear relationships determining the distinguisher in a more straightforward way. We managed therefore to rigorously prove a tight upper bound for the dimension of the square of the dual of an alternant or Goppa code, while [11] only provides an algebraic explanation which does not however represent neither an upper or a lower bound. Our proof is also valid in the case of non-binary Goppa case, for which the conjectured distinguisher is only demonstrated experimentally in [11]. By doing this we got an unifying explanation for the behavior of all Goppa codes, which does not make use of specific features of the binary case. Finally, we illustrated an interesting property of the structure of the square of the dual of any Goppa code, relating it to the dual of another alternant code.

This connection could be of help for a potential key-recovery attack. Indeed a distinguisher can sometimes be turned into an attack. In the code-based cryptography setting, this is for instance the case for GRS codes. The uncommon dimension of the square of a GRS code leads to a successful key-recovery for several proposed variants of McEliece cryptosystem built upon this family of codes for any rate [7]. Despite the strong relation between generalized
Reed-Solomon codes and alternant codes, the same attacks cannot be carried
over from the former to the latter, because of the additional subfield subcode
structure. A similar idea has been successfully exploited for Wild Goppa codes
though [8]. But in this case, the distinguisher is based on considerations of
square of Goppa codes themselves, which only apply to a very restricted class
of parameters. Indeed the attack can only work for extensions of degree $m = 2$
and there is no way to go beyond it, because for $m > 2$ the square code fills
the whole space. In our case, our distinguisher is based on squaring the *dual* of
a Goppa code (or an alternant code) and works for any field extension degree.

However, the fact that the dual of a Goppa code is the trace of a gener-
alized Reed-Solomon code rather than the subfield subcode of a generalized
Reed-Solomon code seems to complicate significantly the attempts to turn this
distinguisher into an attack. But again, having now a much better algebraic
(and rigorous) explanation of why the distinguisher works, together with new
algebraic results about products involved in the square of the dual of the Goppa
code gives a much better understanding of the square code structure. This is
clearly desirable and needed if we want to mount a key recovery attack based
on these square code considerations. The hope is that this will ultimately lead
to being able to attack McEliece schemes based on very high Goppa codes.
As explained earlier, this will still not threaten the codes used in the afore-
mentioned NIST competition, but this would break the 20 years old signature
scheme [6] that is based on very high rate Goppa codes.

Declarations

Funding

This work was supported in part by the ANR CBCRYPT project, grant ANR-17-CE39-0007 and by the ANR BARRACUDA project, grant ANR-21-CE39-0009, both of the French Agence Nationale de la Recherche.

Acknowledgements

The authors would like to thank the anonymous reviewers for their careful
reading of the manuscript and their valuable comments or suggestions for
simplifying or reorganizing proofs which helped to improve significantly the
quality of the manuscript.

Conflict of interest

The authors have no competing interests to declare that are relevant to the
content of this article.

Code availability

Not applicable.
References

[1] Anja Becker, Antoine Joux, Alexander May, and Alexander Meurer. Decoding random binary linear codes in $2^{n/20}$: How $1+1=0$ improves information set decoding. In *Advances in Cryptology - EUROCRYPT 2012*, LNCS. Springer, 2012.

[2] Daniel J. Bernstein, Tung Chou, Tanja Lange, Ingo von Maurich, Rafael Mizoczki, Ruben Niederhagen, Edoardo Persichetti, Christiane Peters, Peter Schwabe, Nicolas Sendrier, Jakub Szefer, and Wang Wen. Classic McEliece: conservative code-based cryptography. https://classic.mceliece.org, March 2019. Second round submission to the NIST post-quantum cryptography call.

[3] Leif Both and Alexander May. Optimizing BJMM with Nearest Neighbors: Full Decoding in $2^{2/21^n}$ and McEliece Security. In *WCC Workshop on Coding and Cryptography*, September 2017. on line proceedings, see http://wcc2017.suai.ru/Proceedings_WCC2017.zip.

[4] Anne Canteaut and Florent Chabaud. A new algorithm for finding minimum-weight words in a linear code: Application to McEliece's cryptosystem and to narrow-sense BCH codes of length 511. *IEEE Trans. Inform. Theory*, 44(1):367–378, 1998.

[5] Igniacio Cascudo, Ronald Cramer, Diego Mirandola, and Gilles Zémor. Squares of random linear codes. *IEEE Trans. Inform. Theory*, 61(3):1159–1173, 3 2015.

[6] Nicolas Courtois, Matthieu Finiasz, and Nicolas Sendrier. How to achieve a McEliece-based digital signature scheme. In *Advances in Cryptology - ASIACRYPT 2001*, volume 2248 of LNCS, pages 157–174, Gold Coast, Australia, 2001. Springer.

[7] Alain Couvreur, Philippe Gaborit, Valérie Gauthier-Umaña, Ayoub Otmani, and Jean-Pierre Tillich. Distinguisher-based attacks on public-key cryptosystems using Reed-Solomon codes. *Des. Codes Cryptogr.*, (2):641–666, 2014.

[8] Alain Couvreur, Ayoub Otmani, and Jean-Pierre Tillich. Polynomial time attack on wild McEliece over quadratic extensions. *IEEE Trans. Inform. Theory*, 63(1):404–427, 1 2017.

[9] Philippe Delsarte. On subfield subcodes of modified Reed-Solomon codes. *IEEE Trans. Inform. Theory*, 21(5):575–576, 1975.
[10] 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.

[11] Jean-Charles Faugère, Valérie Gauthier, Ayoub Otmani, Ludovic Perret, and Jean-Pierre Tillich. A distinguisher for high rate McEliece cryptosystems. *IEEE Trans. Inform. Theory*, 59(10):6830–6844, October 2013.

[12] Ghazal Kachigar and Jean-Pierre Tillich. Quantum information set decoding algorithms. In *Post-Quantum Cryptography 2017*, volume 10346 of LNCS, pages 69–89, Utrecht, The Netherlands, June 2017. Springer.

[13] Pil J. Lee and Ernest F. Brickell. An observation on the security of McEliece's public-key cryptosystem. In *Advances in Cryptology - EUROCRYPT'88*, volume 330 of LNCS, pages 275–280. Springer, 1988.

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

[15] Irene Márquez-Corbella and Ruud Pellikaan. Error-correcting pairs for a public-key cryptosystem. CBC 2012, Code-based Cryptography Workshop, 2012. *IEEE Trans. Inform. Theory*, 63(1):404–427, 1 2017. Available on http://www.win.tue.nl/~ruudp/paper/59.pdf.

[16] Alexander May, Alexander Meurer, and Enrico Thomae. Decoding random linear codes in $O(2^{0.054n})$. In Dong Hoon Lee and Xiaoyun Wang, editors, *Advances in Cryptology - ASIACRYPT 2011*, volume 7073 of LNCS, pages 107–124. Springer, 2011.

[17] Alexander May and Ilya Ozerov. On computing nearest neighbors with applications to decoding of binary linear codes. In E. Oswald and M. Fischlin, editors, *Advances in Cryptology - EUROCRYPT 2015*, volume 9056 of LNCS, pages 203–228. Springer, 2015.

[18] Florence J. MacWilliams and Neil J. A. Sloane. *The Theory of Error-Correcting Codes*. North-Holland, Amsterdam, fifth edition, 1986.

[19] N. Patterson. The algebraic decoding of Goppa codes. *IEEE Trans. Inform. Theory*, 21(2):203–207, 1975.

[20] Hugues Randriambololona. Asymptotically good binary linear codes with asymptotically good self-intersection spans. *IEEE Trans. Inform. Theory*, 59(5):3038–3045, 1 2013.
[21] Hugues Randriambololona. On products and powers of linear codes under componentwise multiplication. In *Algorithmic arithmetic, geometry, and coding theory*, volume 637 of *Contemp. Math.*, pages 3–78. Amer. Math. Soc., Providence, RI, 2015.

[22] Nicolas Sendrier. On the use of structured codes in code based cryptography. In L. Storme S. Nikova, B. Preneel, editors, *Coding Theory and Cryptography III*, pages 59–68. The Royal Flemish Academy of Belgium for Science and the Arts, 2010.

[23] Jacques Stern. A method for finding codewords of small weight. In G. D. Cohen and J. Wolfmann, editors, *Coding Theory and Applications*, volume 388 of LNCS, pages 106–113. Springer, 1988.

[24] Christian Wieschebrink. Cryptanalysis of the Niederreiter public key scheme based on GRS subcodes. In *Post-Quantum Cryptography 2010*, volume 6061 of LNCS, pages 61–72. Springer, 2010.