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

Rocco Mora  Inria, 2 rue Simone Iff, 75012 Paris, France
Sorbonne Universités, UPMC Univ Paris 06<EMAIL_ADDRESS>and  Jean–Pierre
Tillich  Inria, 2 rue Simone Iff, 75012 Paris, France  jean-
<EMAIL_ADDRESS>
###### 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.

##  1\. Introduction

### The McEliece scheme.

The McEliece encryption scheme [McE78], 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 [KT17] has exponential
complexity and the corresponding exponent barely improves the exponent of the
best classical algorithm [BM17] 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 [LB88, Ste88,
CC98, MMT11, BJMM12, MO15, BM17], 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 [McE78] 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 [CFS01]. 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
[Sen10]. 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.

### A distinguisher for high rate.

However, this belief was severely questioned in [FGO+11, FGO+13] 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 cryptosystem 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 [MCP12], where it was proved that this
dimension is related to the dimension of the square of the dual of the public
code. The algebraic explanations given in [FGO+13] 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
[FGO+13] 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 general 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.

### 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 [MCP12].
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 [MCP12], this also gives a lower bound on the dimension
of the kernel of the matrix considered in [FGO+13]. Together with results
about the typical dimension of the square of random codes [CCMZ15], this
provides the first rigorous analysis about the effectiveness of the approach
pioneered in [FGO+11], 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
[Wie10]) 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 $\mathscr{C}$ can be interpreted as a sum of
traces of 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 23). This accounts for the remarkably low dimension of the square
of the dual of Goppa codes in all cases considered in [FGO+13].

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 [FGO+11], 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.

McEliece parameter | $n$ | $m$ |  $r$ in |  $R$ in | Largest | Corresponding
---|---|---|---|---|---|---
set |  |  | [BCL+19] | [BCL+19] | distinguishable $r$ | $R$
kem/mceliece348864 | 3488 | 12 | 64 | 0.77982 | 12 | 0.95872
kem/mceliece460896 | 4608 | 13 | 96 | 0.72917 | 12 | 0.96615
kem/mceliece6688128 | 6688 | 13 | 128 | 0.75120 | 15 | 0.97084
kem/mceliece6960119 | 6960 | 13 | 119 | 0.77773 | 16 | 0.97011
kem/mceliece8192128 | 8192 | 13 | 128 | 0.79688 | 19 | 0.96985
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$. We see in this
table that the code rates suggested for Classic McEliece oscillate between 0.7
and 0.8 [BCL+19, 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.

##  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 $\boldsymbol{v}_{1},\dots,\boldsymbol{v}_{k}\in\mathbb{F}^{n}$, we
denote with
$\left\langle\,\boldsymbol{v}_{1},\dots,\boldsymbol{v}_{k}\,\right\rangle_{\mathbb{F}}$
the subspace of vectors in $\mathbb{F}^{n}$ spanned by
$\\{\boldsymbol{v}_{1},\dots,\boldsymbol{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\leqslant i\leqslant n}$ in $\mathbb{F}^{n}$ by
$f({\boldsymbol{x}})$ the vector $(f(x_{i}))_{1\leqslant i\leqslant 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
$\operatorname{Tr}_{\mathbb{F}_{q^{m}}/\mathbb{F}_{q}}\colon\mathbb{F}_{q^{m}}\to\mathbb{F}_{q}$
for all $x\in\mathbb{F}_{q^{m}}$ as

$\operatorname{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:

$\operatorname{Tr}_{\mathbb{F}_{q^{m}}/\mathbb{F}_{q}}({\boldsymbol{x}})=(\operatorname{Tr}_{\mathbb{F}_{q^{m}}/\mathbb{F}_{q}}(x_{1}),\dots,\operatorname{Tr}_{\mathbb{F}_{q^{m}}/\mathbb{F}_{q}}(x_{n}))$

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

$\operatorname{Tr}_{\mathbb{F}_{q^{m}}/\mathbb{F}_{q}}(\mathscr{C})=\\{\operatorname{Tr}_{\mathbb{F}_{q^{m}}/\mathbb{F}_{q}}(\boldsymbol{c})\mid\boldsymbol{c}\in\mathscr{C}\\}.$

We remark that if $\mathscr{C}=\left\langle\,\boldsymbol{c}_{i}\mid 1\leq
i\leq k\,\right\rangle_{\mathbb{F}_{q^{m}}}$ then
$\operatorname{Tr}_{\mathbb{F}_{q^{m}}/\mathbb{F}_{q}}(\mathscr{C})$ is a
linear code over $\mathbb{F}_{q}$ and

$\operatorname{Tr}_{\mathbb{F}_{q^{m}}/\mathbb{F}_{q}}(\mathscr{C})=\left\langle\,\operatorname{Tr}_{\mathbb{F}_{q^{m}}/\mathbb{F}_{q}}(\alpha_{j}\boldsymbol{c}_{i})\mid
0\leq j<m,1\leq i\leq k\,\right\rangle_{\mathbb{F}_{q}}.$

Informally, multiplying the generators of $\mathscr{C}$ inside the trace by
each element $\alpha_{j}$ of the extension field basis takes into account the
fact that $\mathscr{C}$ is a code over $\mathbb{F}_{q^{m}}$, while
$\operatorname{Tr}_{\mathbb{F}_{q^{m}}/\mathbb{F}_{q}}(\mathscr{C})$ over the
subfield $\mathbb{F}_{q}$. So, if $\dim_{\mathbb{F}_{q^{m}}}\mathscr{C}=k$
then typically
$\dim_{\mathbb{F}_{q}}\operatorname{Tr}_{\mathbb{F}_{q^{m}}/\mathbb{F}_{q}}(\mathscr{C})=mk$,
unless $\operatorname{Tr}_{\mathbb{F}_{q^{m}}/\mathbb{F}_{q}}(\mathscr{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
$\operatorname{Tr}$, whenever the former is clear from the context.

The main classical result linking trace codes to subfield subcodes is
Delsarte’s theorem.

######  Theorem 2.

(Delsarte’s theorem [Del75]) Let $\mathscr{C}$ be a code over
$\mathbb{F}_{q^{m}}$. Then

$(\mathscr{C}_{\rvert\mathbb{F}_{q}})^{\perp}=\operatorname{Tr}(\mathscr{C}^{\perp}),$

where
$\mathscr{C}_{\rvert\mathbb{F}_{q}}\stackrel{{\scriptstyle\text{def}}}{{=}}\mathscr{C}\cap\mathbb{F}_{q}$
denotes the subfield subcode over $\mathbb{F}_{q}$ of $\mathscr{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 ${\boldsymbol{x}}=(x_{1},\dots,x_{n})\in\mathbb{F}^{n}$ be a vector of
pairwise distinct entries and
${\boldsymbol{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
${\boldsymbol{x}}$ and multiplier ${\boldsymbol{y}}$ is

$\text{\bf
GRS}_{r}({\boldsymbol{x}},{\boldsymbol{y}})\stackrel{{\scriptstyle\text{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 ${\boldsymbol{x}}$ and ${\boldsymbol{y}}$.
Recall that this product is defined as

######  Definition 4.

The component-wise product of two vectors
$\boldsymbol{a},\boldsymbol{b}\in\mathbb{F}^{n}$ is defined as

${\boldsymbol{a}}\star{\boldsymbol{b}}\stackrel{{\scriptstyle\text{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

$\text{\bf
GRS}_{r}({\boldsymbol{x}},{\boldsymbol{y}})\stackrel{{\scriptstyle\text{def}}}{{=}}\left\langle\,{\boldsymbol{x}}^{a}{\boldsymbol{y}}\mid
0\leq a<r\,\right\rangle_{\mathbb{F}_{q}},$

where ${\boldsymbol{x}}^{a}$ stands for the component-wise product $\star$ of
the vector ${\boldsymbol{x}}$ with itself repeated $a$ times and where we
omitted the component-wise product symbol between ${\boldsymbol{x}}$ and
${\boldsymbol{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_{\boldsymbol{x}}(z)\stackrel{{\scriptstyle\text{def}}}{{=}}\prod_{i=1}^{n}(z-x_{i})\in\mathbb{F}[z].$

######  Proposition 5.

[MS86, Theorem 4, p. 304] Let $\text{\bf
GRS}_{r}({\boldsymbol{x}},{\boldsymbol{y}})$ be a GRS code of length $n$. Its
dual is also a GRS code. In particular

$\text{\bf GRS}_{r}({\boldsymbol{x}},{\boldsymbol{y}})^{\perp}=\text{\bf
GRS}_{n-r}({\boldsymbol{x}},{\boldsymbol{y}}^{\perp}),$

where

${\boldsymbol{y}}^{\perp}\stackrel{{\scriptstyle\text{def}}}{{=}}\left(\frac{1}{\pi^{\prime}_{\boldsymbol{x}}(x_{1})y_{1}},\dots,\frac{1}{\pi^{\prime}_{\boldsymbol{x}}(x_{n})y_{n}}\right)$

and $\pi^{\prime}_{\boldsymbol{x}}$ is the derivative of
$\pi_{\boldsymbol{x}}$.

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

######  Definition 6.

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

$\mathscr{A}_{r}({\boldsymbol{x}},{\boldsymbol{y}})\stackrel{{\scriptstyle\text{def}}}{{=}}\text{\bf
GRS}_{r}({\boldsymbol{x}},{\boldsymbol{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:

$\mathscr{A}_{r}({\boldsymbol{x}},{\boldsymbol{y}})\stackrel{{\scriptstyle\text{def}}}{{=}}\text{\bf
GRS}_{n-r}({\boldsymbol{x}},{\boldsymbol{y}}^{\perp})\cap\mathbb{F}_{q}^{n}.$

We use the same notation as in [MS86] and use the dimension $r$ and the
multiplier ${\boldsymbol{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,

$\displaystyle\mathscr{A}_{r}({\boldsymbol{x}},{\boldsymbol{y}})^{\perp}$
$\displaystyle=\left(\text{\bf
GRS}_{r}({\boldsymbol{x}},{\boldsymbol{y}})^{\perp}\cap\mathbb{F}_{q}^{n}\right)^{\perp}$
$\displaystyle=\operatorname{Tr}\left((\text{\bf
GRS}_{r}({\boldsymbol{x}},{\boldsymbol{y}})^{\perp})^{\perp}\right)$ (1)
$\displaystyle=\operatorname{Tr}\left(\text{\bf
GRS}_{r}({\boldsymbol{x}},{\boldsymbol{y}})\right).$

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 ${\boldsymbol{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 ${\boldsymbol{x}}$ and Goppa polynomial $\Gamma$ is defined
as

$\mathscr{G}({\boldsymbol{x}},\Gamma)\stackrel{{\scriptstyle\text{def}}}{{=}}\mathscr{A}_{r}({\boldsymbol{x}},{\boldsymbol{y}}),$

where
${\boldsymbol{y}}\stackrel{{\scriptstyle\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.

[Pat75] Let $\mathscr{G}({\boldsymbol{x}},\Gamma)$ be a binary Goppa
polynomial $\Gamma$ of degree $r$ and without multiple roots. Then

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

where
$y_{i}\stackrel{{\scriptstyle\text{def}}}{{=}}\frac{1}{\Gamma(x_{i})^{2}}$ for
all $1\leq i\leq n$.

$\mathscr{A}_{r}({\boldsymbol{x}},{\boldsymbol{y}})=\text{\bf
GRS}_{r}({\boldsymbol{x}},{\boldsymbol{y}})^{\perp}\cap\mathbb{F}_{q}^{n}.$

### 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 $\mathscr{C},\mathscr{D}$ over
$\mathbb{F}$ with the same length $n$ is defined as

${\mathscr{C}}\star{\mathscr{D}}\stackrel{{\scriptstyle\text{def}}}{{=}}\left\langle\,{\boldsymbol{c}}\star{\boldsymbol{d}}\mid\boldsymbol{c}\in\mathscr{C},\boldsymbol{d}\in\mathscr{D}\,\right\rangle_{\mathbb{F}}.$

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

It is easy to see that if
$\mathscr{C}=\left\langle\,\boldsymbol{c}_{1},\dots,\boldsymbol{c}_{k_{1}}\,\right\rangle_{\mathbb{F}}$
and
$\mathscr{D}=\left\langle\,\boldsymbol{d}_{1},\dots,\boldsymbol{d}_{k_{2}}\,\right\rangle_{\mathbb{F}}$,
a generating set for ${\mathscr{C}}\star{\mathscr{D}}$ over $\mathbb{F}$ is
given by a set of $k_{1}k_{2}$ vectors,

$\\{{\boldsymbol{c}_{i}}\star{\boldsymbol{d}_{j}}\mid 1\leq i\leq k_{1},1\leq
j\leq k_{2}\\}.$

However, when $\mathscr{C}\cap\mathscr{D}\neq\\{\mathbf{0}\\}$, some of the
above elements are obviously redundant. In the extreme case, i.e. when
$\mathscr{C}=\mathscr{D}$, the square code dimension is much smaller than
$k^{2}$, where $k=\dim_{\mathbb{F}}\mathscr{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 [CCMZ15].

######  Proposition 10.

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

$\dim_{\mathbb{F}_{q}}\mathscr{C}^{\star
2}\leq\min\left(n,\binom{k+1}{2}\right).$

For a random linear code $\mathscr{C}$ whose square does not fill the full
space, the dimension of its square code is $\binom{k+1}{2}$ with high
probability, where $k$ is the dimension of $\mathscr{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 [Wie10]. We namely have

######  Proposition 11.

Let $\text{\bf GRS}_{r}({\boldsymbol{x}},{\boldsymbol{y}})$ be a GRS code with
support ${\boldsymbol{x}}$, multiplier ${\boldsymbol{y}}$ and dimension $k$.
We have $\text{\bf GRS}_{k}({\boldsymbol{x}},{\boldsymbol{y}})^{\star
2}=\text{\bf GRS}_{2k-1}({\boldsymbol{x}},{\boldsymbol{y}}^{2})$. Hence, if
$k\leq\frac{n+1}{2}$,

$\dim_{\mathbb{F}_{q^{m}}}(\text{\bf
GRS}_{r}({\boldsymbol{x}},{\boldsymbol{y}}))^{\star 2}=2k-1.$

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

$\displaystyle\text{\bf GRS}_{k}({\boldsymbol{x}},{\boldsymbol{y}})^{\star 2}$
$\displaystyle=\left\langle\,{({\boldsymbol{x}}^{a}{\boldsymbol{y}})}\star{({\boldsymbol{x}}^{b}{\boldsymbol{y}})}\mid
0\leq a,b<k\,\right\rangle_{\mathbb{F}_{q^{m}}}$
$\displaystyle=\left\langle\,{\boldsymbol{x}}^{a+b}{\boldsymbol{y}}^{2}\mid
0\leq a,b<k\,\right\rangle_{\mathbb{F}_{q^{m}}}$
$\displaystyle=\left\langle\,{\boldsymbol{x}}^{c}{\boldsymbol{y}}^{2}\mid
0\leq c<2k-1\,\right\rangle_{\mathbb{F}_{q^{m}}}.$

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.

### The distinguisher of Goppa/alternant codes of [FGO+11, FGO+13] 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 [FGO+11]. 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 $\boldsymbol{P}=(p_{ij})_{i,j}$ be a
generator matrix of an $[n,k]$ alternant (or Goppa) code $\mathscr{C}$ in
systematic form, i.e. with its first $k$ columns that form an identity block
and consider the following linear system

$\mathscr{L}_{p}=\left\\{\sum_{k+1\leq j<j^{\prime}\leq
n}p_{ij}p_{ij^{\prime}}Z_{jj^{\prime}}=0\mid 1\leq i\leq 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 formula for $D$ coinciding with experimental evidence was given in
[FGO+13] together with a convincing algebraic explanation for alternant and
binary Goppa codes.

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

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

In terms of dimensions of the square codes, the formula for $D$ given in
[FGO+13] together with (2) predicts for a generic alternant code
$\mathbb{F}_{q}$ of length $n$ and extension degree $m$ that

(3)
$\dim_{\mathbb{F}_{q}}(\mathscr{A}_{r}({\boldsymbol{x}},{\boldsymbol{y}})^{\perp})^{\star
2}=\min\left\\{n,\binom{rm+1}{2}-\frac{m}{2}(r-1)\left((2e_{\mathscr{A}}+1)r-2\frac{q^{e_{\mathscr{A}}}-1}{q-1}\right)\right\\},$

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

(4) $\displaystyle\dim(\mathscr{G}({\boldsymbol{x}},\Gamma)^{\perp})^{\star
2}$ $\displaystyle=$
$\displaystyle\min\left\\{n,\binom{rm+1}{2}-\frac{m}{2}(r-1)(r-2)\right\\},\;\;\text{if
$r<q-1$}$ (5)
$\displaystyle\dim(\mathscr{G}({\boldsymbol{x}},\Gamma)^{\perp})^{\star 2}$
$\displaystyle=$
$\displaystyle\min\left\\{n,\binom{rm+1}{2}-\frac{m}{2}r\left((2e_{\mathscr{G}}+1)r-2(q-1)q^{e_{\mathscr{G}}-1}-1\right)\right\\},\;\;\text{else,}$

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

$\displaystyle e_{\mathscr{A}}$
$\displaystyle\stackrel{{\scriptstyle\text{def}}}{{=}}$
$\displaystyle\max\\{i\in\mathbb{N}\mid r\geq
q^{i}+1\\}=\left\lfloor\log_{q}(r-1)\right\rfloor$ $\displaystyle
e_{\mathscr{G}}$ $\displaystyle\stackrel{{\scriptstyle\text{def}}}{{=}}$
$\displaystyle\min\\{i\in\mathbb{N}\mid
r\leq(q-1)^{2}q^{i}\\}+1=\left\lceil\log_{q}\left(\frac{r}{(q-1)^{2}}\right)\right\rceil+1.$

As shown in [FGO+13], these formulas agree with extensive experimental
evidence.

##  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 abnormally 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 $\mathscr{C}$ and $\mathscr{D}$ over $\mathbb{F}_{q^{m}}$ of length
$n$ is smaller than
$\min(n,\dim_{\mathbb{F}_{q^{m}}}\mathscr{C}\cdot\dim_{\mathbb{F}_{q^{m}}}\mathscr{D})$
(which is the dimension we expect for random codes $\mathscr{C}$ and
$\mathscr{D}$) then this property survives for trace codes, namely do we have
in this case

$\dim_{\mathbb{F}_{q}}{\operatorname{Tr}(\mathscr{C})}\star{\operatorname{Tr}(\mathscr{D})}<\min(n,\dim_{\mathbb{F}_{q}}\operatorname{Tr}(\mathscr{C})\cdot\dim_{\mathbb{F}_{q}}\operatorname{Tr}(\mathscr{D}))?$

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

######  Proposition 12.

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

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

###### Proof.

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

$\displaystyle\operatorname{Tr}(c)\cdot\operatorname{Tr}(d)$
$\displaystyle=\left(\sum_{0\leq i\leq
m-1}c^{q^{i}}\right)\cdot\left(\sum_{0\leq i\leq m-1}d^{q^{i}}\right)$
$\displaystyle=\sum_{\begin{smallmatrix}0\leq i\leq m-1\\\ 0\leq j\leq
m-1\end{smallmatrix}}c^{q^{i}}\cdot d^{q^{j}}$ $\displaystyle=\sum_{0\leq
j\leq m-1}\sum_{0\leq i\leq m-1}c^{q^{i}}\cdot d^{q^{(i+j\mod m)}}$
$\displaystyle=\sum_{0\leq j\leq m-1}\sum_{0\leq i\leq m-1}c^{q^{i}}\cdot
d^{q^{i+j}}$ $\displaystyle=\sum_{0\leq i\leq m-1}\operatorname{Tr}(c\cdot
d^{q^{i}}).$

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

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

Hence

$\displaystyle\operatorname{Tr}(\mathscr{C})\star\operatorname{Tr}(\mathscr{D})$
$\displaystyle=\left\langle\,\operatorname{Tr}(\boldsymbol{c})\star\operatorname{Tr}(\boldsymbol{d})\mid\boldsymbol{c}\in\mathscr{C},\boldsymbol{d}\in\mathscr{D}\,\right\rangle_{\mathbb{F}_{q}}$
$\displaystyle=\left\langle\,\sum_{i=0}^{m-1}\operatorname{Tr}\left({\boldsymbol{c}}\star{\boldsymbol{d}^{q^{i}}}\right)\mid\boldsymbol{c}\in\mathscr{C},\boldsymbol{d}\in\mathscr{D}\,\right\rangle_{\mathbb{F}_{q}}$
$\displaystyle\subseteq\sum_{i=0}^{m-1}\left\langle\,\operatorname{Tr}\left({\boldsymbol{c}}\star{\boldsymbol{d}^{q^{i}}}\right)\mid\boldsymbol{c}\in\mathscr{C},\boldsymbol{d}\in\mathscr{D}\,\right\rangle_{\mathbb{F}_{q}}$
$\displaystyle=\sum_{i=0}^{m-1}\operatorname{Tr}\left(\mathscr{C}\star\mathscr{D}^{q^{i}}\right).$

∎

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

######  Corollary 13.

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

$\dim_{\mathbb{F}_{q}}\left(\operatorname{Tr}(\mathscr{C})\star\operatorname{Tr}(\mathscr{D})\right)-\dim_{\mathbb{F}_{q}}\operatorname{Tr}(\mathscr{C})\cdot\dim_{\mathbb{F}_{q}}\operatorname{Tr}(\mathscr{D})\leqslant
m\cdot\left(\dim_{\mathbb{F}_{q^{m}}}({\mathscr{C}}\star{\mathscr{D}})-\dim_{\mathbb{F}_{q^{m}}}\mathscr{C}\cdot\dim_{\mathbb{F}_{q^{m}}}\mathscr{D}\right)$

###### 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

$\displaystyle\dim\left(\operatorname{Tr}(\mathscr{C})\star\operatorname{Tr}(\mathscr{D})\right)$
$\displaystyle\leqslant$
$\displaystyle\sum_{i=0}^{m-1}\dim\operatorname{Tr}\left({\mathscr{C}}\star{\mathscr{D}^{q^{i}}}\right)\;\;\text{(by
Prop. \ref{pr:general})}$ $\displaystyle\leqslant$ $\displaystyle
m\cdot\dim\left({\mathscr{C}}\star{\mathscr{D}}\right)+\sum_{i=1}^{m-1}m\cdot\dim\left({\mathscr{C}}\star{\mathscr{D}^{q^{i}}}\right)$
$\displaystyle\leqslant$ $\displaystyle
m\left(\dim({\mathscr{C}}\star{\mathscr{D}})-\dim(\mathscr{C})\dim(\mathscr{D})\right)+m\cdot\dim\mathscr{C}\cdot\dim\mathscr{D}+m\sum_{i=1}^{m-1}\dim\mathscr{C}\cdot\dim\left(\mathscr{D}^{q^{i}}\right)$
$\displaystyle\leqslant$ $\displaystyle
m\left(\dim({\mathscr{C}}\star{\mathscr{D}})-\dim\mathscr{C}\cdot\dim\mathscr{D}\right)+m^{2}\dim\mathscr{C}\cdot\dim\mathscr{D}$
$\displaystyle\leqslant$ $\displaystyle
m\left(\dim({\mathscr{C}}\star{\mathscr{D}})-\dim\mathscr{C}\cdot\dim\mathscr{D}\right)+\dim\operatorname{Tr}(\mathscr{C})\cdot\dim\operatorname{Tr}(\mathscr{D}).$

∎

######  Remark 14.

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

$\dim_{\mathbb{F}_{q}}({\operatorname{Tr}(\mathscr{C})}\star{\operatorname{Tr}(\mathscr{D})})<\dim_{\mathbb{F}_{q}}\operatorname{Tr}(\mathscr{C})\cdot\dim_{\mathbb{F}_{q}}\operatorname{Tr}(\mathscr{D}).$

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

######  Proposition 15.

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

(6)
$\displaystyle\operatorname{Tr}\left({\mathscr{C}}\star{\mathscr{C}^{q^{u}}}\right)$
$\displaystyle=$
$\displaystyle\operatorname{Tr}\left({\mathscr{C}}\star{\mathscr{C}^{q^{m-u}}}\right)$
(7) $\displaystyle\left(\operatorname{Tr}(\mathscr{C})\right)^{\star 2}$
$\displaystyle\subseteq$ $\displaystyle\sum_{u=0}^{\lfloor
m/2\rfloor}\operatorname{Tr}\left({\mathscr{C}}\star{\mathscr{C}^{q^{u}}}\right)$
(8)
$\displaystyle\dim_{\mathbb{F}_{q}}\left(\operatorname{Tr}\left({\mathscr{C}}\star{\mathscr{C}^{q^{m/2}}}\right)\right)$
$\displaystyle\leqslant$ $\displaystyle
m\frac{(\dim_{\mathbb{F}_{q^{m}}}(\mathscr{C}))^{2}}{2}\;\;\text{if $m$ is
even}$

###### Proof.

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

$\operatorname{Tr}\left({\boldsymbol{c}}\star{\boldsymbol{d}^{q^{u}}}\right)=\operatorname{Tr}\left(({\boldsymbol{c}}\star{\boldsymbol{d}^{q^{u}}})^{q^{m-u}}\right)=\operatorname{Tr}\left({\boldsymbol{c}^{q^{m-u}}}\star{\boldsymbol{d}^{q^{m}}}\right)=\operatorname{Tr}\left({\boldsymbol{d}}\star{\boldsymbol{c}^{q^{m-u}}}\right)\in\operatorname{Tr}\left({\mathscr{C}}\star{\mathscr{C}^{(q^{m-u})}}\right).$

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

Proof of (7).

$\displaystyle\left(\operatorname{Tr}(\mathscr{C})\right)^{\star 2}$
$\displaystyle\subseteq$
$\displaystyle\sum_{u=0}^{m-1}\operatorname{Tr}\left({\mathscr{C}}\star{\mathscr{C}^{q^{u}}}\right)\;\;\text{(by
Prop. \ref{pr:general} )}$ $\displaystyle\subseteq$
$\displaystyle\sum_{u=0}^{\lfloor
m/2\rfloor}\operatorname{Tr}\left({\mathscr{C}}\star{\mathscr{C}^{q^{u}}}\right)\;\;\text{(by
\eqref{eq:symmetry}).}$

Proof of (8). Let $\\{\boldsymbol{c}_{1},\cdots,\boldsymbol{c}_{r}\\}$ be a
basis of $\mathscr{C}$ where
$r\stackrel{{\scriptstyle\text{def}}}{{=}}\dim(\mathscr{C})$.
$\operatorname{Tr}\left({\mathscr{C}}\star{\mathscr{C}^{q^{m/2}}}\right)$ is
generated by the
$\operatorname{Tr}\left(\beta^{q^{\ell}}{\boldsymbol{c}_{i}}\star{\boldsymbol{c}_{j}^{q^{m/2}}}\right)$
where $\\{\beta,\beta^{q},\cdots,\beta^{q^{m-1}}\\}$ is a normal basis of
$\mathbb{F}_{q^{m}}$ and $\ell$ ranges over $\\{0,\cdots,m-1\\}$ and $i$, $j$
over $\\{1,\cdots,r\\}$. Since for any $0\leq\ell\leq\frac{m}{2}-1$, $1\leq
i,j\leq r$,

$\operatorname{Tr}\left(\beta^{q^{\ell}}{\boldsymbol{c}_{i}}\star{\boldsymbol{c}_{j}^{q^{m/2}}}\right)=\operatorname{Tr}\left(\beta^{q^{\ell+\frac{m}{2}}}{\boldsymbol{c}_{i}^{q^{m/2}}}\star{\boldsymbol{c}_{j}}\right)=\operatorname{Tr}\left(\beta^{q^{\ell+\frac{m}{2}}}{\boldsymbol{c}_{j}}\star{\boldsymbol{c}_{i}^{q^{m/2}}}\right),$

this implies that
$\operatorname{Tr}\left(\mathscr{C}*\mathscr{C}^{q^{\frac{m}{2}}}\right)$ is
generated by the (smaller) set
$\operatorname{Tr}\left(\beta^{q^{\ell}}{\boldsymbol{c}_{i}}\star{\boldsymbol{c}_{j}^{q^{m/2}}}\right)$
where $\ell$ ranges over $\\{0,\cdots m/2-1\\}$ and $i$, $j$ over
$\\{1,\cdots,r\\}$. This is a set of cardinality $\frac{mr^{2}}{2}$. ∎

Proposition 15 has a corollary which is similar to Corollary 13, namely that

######  Corollary 16.

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

(9) $\dim_{\mathbb{F}_{q}}\left(\operatorname{Tr}(\mathscr{C})\right)^{\star
2}\leqslant m\cdot\dim_{\mathbb{F}_{q^{m}}}\mathscr{C}^{\star
2}+\binom{m}{2}\left(\dim_{\mathbb{F}_{q^{m}}}\mathscr{C}\right)^{2}.$

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

(10) $\dim_{\mathbb{F}_{q}}\left(\operatorname{Tr}(\mathscr{C})\right)^{\star
2}-\binom{\dim_{\mathbb{F}_{q}}\operatorname{Tr}(\mathscr{C})+1}{2}\leqslant
m\left[\dim_{\mathbb{F}_{q^{m}}}\mathscr{C}^{\star
2}-\binom{\dim_{\mathbb{F}_{q^{m}}}\mathscr{C}+1}{2}\right].$

###### Proof.

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

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

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

$\displaystyle\dim\left(\operatorname{Tr}(\mathscr{C})\right)^{\star 2}$
$\displaystyle\leqslant$ $\displaystyle m\cdot\dim\mathscr{C}^{\star
2}+\sum_{i=1}^{\lfloor\frac{m}{2}\rfloor}m\cdot\dim{\mathscr{C}}\star{\mathscr{C}^{q^{i}}}$
$\displaystyle\leqslant$ $\displaystyle m\cdot\dim\mathscr{C}^{\star
2}+m\sum_{i=1}^{\lfloor\frac{m}{2}\rfloor}\dim\mathscr{C}\cdot\dim\mathscr{C}^{q^{i}}$
$\displaystyle\leqslant$ $\displaystyle m\cdot\dim\mathscr{C}^{\star
2}+\frac{m(m-1)}{2}\left(\dim\mathscr{C}\right)^{2}$ $\displaystyle\leqslant$
$\displaystyle m\cdot\dim\mathscr{C}^{\star
2}+\binom{m}{2}\left(\dim\mathscr{C}\right)^{2}.$

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

$\displaystyle\dim\left(\operatorname{Tr}(\mathscr{C})\right)^{\star 2}$
$\displaystyle\leqslant$ $\displaystyle m\cdot\dim\mathscr{C}^{\star
2}+\sum_{i=1}^{\frac{m}{2}-1}m\cdot\dim\mathscr{C}\cdot\dim\mathscr{C}^{q^{i}}+\dim\operatorname{Tr}\left({\mathscr{C}}\star{\mathscr{C}^{q^{m/2}}}\right)$
$\displaystyle\leqslant$ $\displaystyle m\cdot\dim\mathscr{C}^{\star
2}+\frac{m(m-2)}{2}\left(\dim\mathscr{C}\right)^{2}+\frac{m(\dim\mathscr{C})^{2}}{2}\;\;\text{(by
using \eqref{eq:dimension} of Proposition \ref{pr:square_general})}$
$\displaystyle\leqslant$ $\displaystyle m\cdot\dim\mathscr{C}^{\star
2}+\binom{m}{2}\left(\dim\mathscr{C}\right)^{2}.$

Proof of (10):

$\displaystyle\dim\left(\operatorname{Tr}(\mathscr{C})\right)^{\star
2}-\binom{\dim\operatorname{Tr}(\mathscr{C})+1}{2}$ $\displaystyle\leqslant$
$\displaystyle m\cdot\dim\mathscr{C}^{\star
2}+\binom{m}{2}\left(\dim\mathscr{C}\right)^{2}-\binom{\dim\operatorname{Tr}(\mathscr{C})+1}{2}\;\;\text{(by
using \eqref{eq:cor_dimension})}$ $\displaystyle\leqslant$ $\displaystyle
m\cdot\dim\mathscr{C}^{\star
2}+\frac{m(m-1)}{2}\left(\dim\mathscr{C}\right)^{2}-\binom{m\dim\mathscr{C}+1}{2}$
$\displaystyle\leqslant$ $\displaystyle m\cdot\dim\mathscr{C}^{\star
2}+m\cdot\dim\mathscr{C}\cdot\left[\frac{m-1}{2}\dim\mathscr{C}-\frac{m\dim\mathscr{C}+1}{2}\right]$
$\displaystyle\leqslant$ $\displaystyle m\cdot\dim\mathscr{C}^{\star
2}-m\cdot\dim\mathscr{C}\cdot\frac{\dim\mathscr{C}+1}{2}$
$\displaystyle\leqslant$ $\displaystyle m\left[\dim\mathscr{C}^{\star
2}-\binom{\dim\mathscr{C}+1}{2}\right].$

∎

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

$\dim\left(\operatorname{Tr}(\mathscr{C})\right)^{\star
2}<\binom{\dim\operatorname{Tr}(\mathscr{C})+1}{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 a direct application of the
general results of Section 3 from which we derive:

######  Theorem 17.

Let $\mathscr{A}_{r}({\boldsymbol{x}},{\boldsymbol{y}})$ be an alternant code
over $\mathbb{F}_{q}$. Then

(12)
$\dim_{\mathbb{F}_{q}}\left(\mathscr{A}_{r}({\boldsymbol{x}},{\boldsymbol{y}})^{\perp}\right)^{\star
2}\leq\binom{rm+1}{2}-\frac{m}{2}(r-1)(r-2).$

######  Remark 18.

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 [FGO+13] used together with [MCP12, 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 [FGO+13] 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{{\scriptstyle\text{def}}}{{=}}\text{\bf
GRS}_{r}({\boldsymbol{x}},{\boldsymbol{y}})$. Note that
$\mathscr{A}_{r}({\boldsymbol{x}},{\boldsymbol{y}})^{\perp}=\operatorname{Tr}(\mathscr{C})$.
We apply Corollary 16 with such a $\mathscr{C}$ and get that

$\displaystyle\dim_{\mathbb{F}_{q}}\left(\operatorname{Tr}(\mathscr{C})\right)^{\star
2}$ $\displaystyle\leqslant$ $\displaystyle
m\cdot\dim_{\mathbb{F}_{q^{m}}}\mathscr{C}^{\star
2}+\binom{m}{2}\left(\dim_{\mathbb{F}_{q^{m}}}\mathscr{C}\right)^{2}$
$\displaystyle=$ $\displaystyle m(2r-1)+\frac{m(m-1)r^{2}}{2}\;\;\text{(by
Proposition \ref{pr: square_GRS})}$ $\displaystyle=$
$\displaystyle\left(2(2r-1)+(m-1)r^{2}\right)\frac{m}{2}$ $\displaystyle=$
$\displaystyle\left(r(mr+1)-(r-1)(r-2)\right)\frac{m}{2}$ $\displaystyle=$
$\displaystyle\binom{rm+1}{2}-\frac{m}{2}(r-1)(r-2).$

∎

##  5\. Alternant case with $e_{\mathscr{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\geq q+1$,
i.e. $e_{\mathscr{A}}>0$. Our main result in this section is that

######  Theorem 19.

Let $\mathscr{A}_{r}({\boldsymbol{x}},{\boldsymbol{y}})$ be an alternant code
over $\mathbb{F}_{q}$. Then

(13)
$\dim_{\mathbb{F}_{q}}(\mathscr{A}_{r}({\boldsymbol{x}},{\boldsymbol{y}})^{\perp})^{\star
2}\leq\binom{rm+1}{2}-\frac{m}{2}(r-1)\left((2{e_{\mathscr{A}}}+1)r-2\frac{q^{{e_{\mathscr{A}}}+1}-1}{q-1}\right).$

######  Remark 20.

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 [FGO+13] 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 17 for
values of $r$ for which ${e_{\mathscr{A}}}>0$ comes from the fact that when we
apply Proposition 15 with
$\mathscr{C}\stackrel{{\scriptstyle\text{def}}}{{=}}\text{\bf
GRS}_{r}({\boldsymbol{x}},{\boldsymbol{y}})$ (which is the relevant quantity
here since
$\operatorname{Tr}(\mathscr{C})=\mathscr{A}_{r}({\boldsymbol{x}},{\boldsymbol{y}})^{\perp}$)
we get terms of the form
$\operatorname{Tr}\left({\mathscr{C}}\star{\mathscr{C}^{q^{u}}}\right)$ which
will have a smaller dimension than the generic upper bound $mr^{2}$. This is
due to the fact that these
$\operatorname{Tr}\left({\mathscr{C}}\star{\mathscr{C}^{q^{u}}}\right)$ will
actually be duals of alternant codes for small values of $u$ as shown by the
following lemma

######  Lemma 21.

Let $\mathscr{C}\stackrel{{\scriptstyle\text{def}}}{{=}}\text{\bf
GRS}_{r}({\boldsymbol{x}},{\boldsymbol{y}})$ and
$f\stackrel{{\scriptstyle\text{def}}}{{=}}\lfloor\log_{q}(r)\rfloor$. We have

(14)
$\displaystyle\operatorname{Tr}\left({\mathscr{C}}\star{\mathscr{C}^{q^{u}}}\right)$
$\displaystyle\subseteq$
$\displaystyle\mathscr{A}_{(r-1)(1+q^{u})+1}({\boldsymbol{x}},{\boldsymbol{y}}^{1+q^{u}})^{\perp}\;\;\text{for
all non-negative integers $u$,}$ (15)
$\displaystyle\operatorname{Tr}\left({\mathscr{C}}\star{\mathscr{C}^{q^{u}}}\right)$
$\displaystyle=$
$\displaystyle\mathscr{A}_{(r-1)(1+q^{u})+1}({\boldsymbol{x}},{\boldsymbol{y}}^{1+q^{u}})^{\perp}\;\text{for
all integers $u$ in $\\{0,\cdots,f\\}$.}$

###### Proof.

We first notice that

$\operatorname{Tr}\left({\mathscr{C}}\star{\mathscr{C}^{q^{u}}}\right)=\left\langle\,\operatorname{Tr}\left(\alpha_{l}{\boldsymbol{x}}^{a+bq^{u}}{\boldsymbol{y}}^{1+q^{u}}\right)\mid
0\leq l<m,0\leq a,b\leqslant r-1\,\right\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,\cdots,(r-1)(1+q^{u})\\}$ as long
as $r-1\geqslant q^{u}-1$, that is $r\geqslant q^{u}$ which is equivalent to
$u\leqslant\lfloor\log_{q}(r)\rfloor$. ∎

The previous lemma implies that

######  Corollary 22.

Let $\mathscr{C}\stackrel{{\scriptstyle\text{def}}}{{=}}\text{\bf
GRS}_{r}({\boldsymbol{x}},{\boldsymbol{y}})$. For all non-negative integers
$u$, we have

$\dim_{\mathbb{F}_{q}}\operatorname{Tr}\left({\mathscr{C}}\star{\mathscr{C}^{q^{u}}}\right)\leq
m((r-1)(q^{u}+1)+1).$

From this corollary we obtain directly Theorem 19. The proof goes as follows.

###### Proof of Theorem 19.

Let $\mathscr{C}\stackrel{{\scriptstyle\text{def}}}{{=}}\text{\bf
GRS}_{r}({\boldsymbol{x}},{\boldsymbol{y}})$.

$\displaystyle\dim_{\mathbb{F}_{q}}(\mathscr{A}_{r}({\boldsymbol{x}},{\boldsymbol{y}})^{\perp})^{\star
2}$
$\displaystyle\leq\dim_{\mathbb{F}_{q}}\sum_{u=0}^{\left\lfloor\frac{m}{2}\right\rfloor}\operatorname{Tr}\left({\mathscr{C}}\star{\mathscr{C}^{q^{u}}}\right)\;\;\text{(by
Prop. \eqref{pr:square_general})}$
$\displaystyle\leq\sum_{u=0}^{\left\lfloor\frac{m}{2}\right\rfloor}\dim_{\mathbb{F}_{q}}\operatorname{Tr}\left({\mathscr{C}}\star{\mathscr{C}^{q^{u}}}\right)$
$\displaystyle\leq\sum_{u=0}^{e}m((r-1)(q^{u}+1)+1)+\left(\frac{m-1}{2}-e\right)mr^{2}$
$\displaystyle\leq\binom{rm+1}{2}-\frac{m}{2}(r-1)\left((2e+1)r-2\frac{q^{e+1}-1}{q-1}\right).$

Here, this inequality holds for any integer $e$ in
$\\{0,\cdots,\left\lfloor\frac{m}{2}\right\rfloor\\}$. To get the sharpest
upper-bound, we minimize the function
$\binom{rm+1}{2}-\frac{m}{2}(r-1)\left((2e+1)r-2\frac{q^{e+1}-1}{q-1}\right)$
with respect to $e$. Obviously, this is equivalent to find the maximum over
$\\{0,\cdots,\left\lfloor\frac{m}{2}\right\rfloor\\}$ of the function

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

in the discrete domain of non-negative integers. We compute the discrete
derivative $\Delta T:e\mapsto T(e+1)-T(e)$,

$\displaystyle\Delta T(e)=T(e+1)-T(e)$
$\displaystyle=\left((e+1)r-\frac{q^{e+2}}{q-1}\right)-\left(er-\frac{q^{e+1}}{q-1}\right)$
$\displaystyle=r-q^{e+1}.$

This function is decreasing with $e$ and the smallest value of $e$ for which
$\Delta T(e)\leqslant 0$ corresponds to its maximum. It is the smallest value
of $e$ for which $r\leqslant q^{e+1}$, i.e.
$e=\left\lfloor\log_{q}(r-1)\right\rfloor={e_{\mathscr{A}}}$.

∎

##  6\. Goppa case with $r\geq q-1$

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

######  Theorem 23.

Let $\mathscr{C}\stackrel{{\scriptstyle\text{def}}}{{=}}\text{\bf
GRS}_{r}({\boldsymbol{x}},{\boldsymbol{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$

(16)
$\mathscr{B}_{v}\stackrel{{\scriptstyle\text{def}}}{{=}}\mathscr{A}_{r(q^{v}-q^{v-1}+1)}({\boldsymbol{x}},{\boldsymbol{y}}^{q^{v}+1})^{\perp},\quad\text{and}\quad\mathscr{B}_{0}\stackrel{{\scriptstyle\text{def}}}{{=}}\mathscr{A}_{2r-1}({\boldsymbol{x}},{\boldsymbol{y}}^{2})^{\perp}.$

Let $f\stackrel{{\scriptstyle\text{def}}}{{=}}\lfloor\log_{q}(r)\rfloor$. Then

(17)
$\displaystyle\operatorname{Tr}\left({\mathscr{C}}\star{\mathscr{C}^{q^{v}}}\right)\subseteq\mathscr{B}_{v}\quad\text{for
all positive integers $v$,}$ (18)
$\displaystyle\operatorname{Tr}\left({\mathscr{C}}\star{\mathscr{C}^{q^{u}}}\right)=\mathscr{B}_{u}\quad\text{for
$0\leqslant u\leqslant f$,}$ (19)
$\displaystyle\operatorname{Tr}\left({\mathscr{C}}\star{\mathscr{C}}\right)\subseteq\operatorname{Tr}\left({\mathscr{C}}\star{\mathscr{C}^{q}}\right)\subseteq\dots\subseteq\operatorname{Tr}\left({\mathscr{C}}\star{\mathscr{C}^{q^{u}}}\right)\quad\text{for
$0\leqslant u\leqslant f$.}$

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

$\displaystyle\operatorname{Tr}\left({\mathscr{C}}\star{\mathscr{C}^{q^{v}}}\right)$
$\displaystyle\subseteq$
$\displaystyle\left\\{\operatorname{Tr}\left(\frac{P({\boldsymbol{x}})}{\Gamma({\boldsymbol{x}})^{q^{v}+1}}\right)\mid\deg
P<(r-1)(q^{v}+1)+1\right\\}$ $\displaystyle=$
$\displaystyle\mathscr{A}_{(r-1)(q^{v}+1)+1}({\boldsymbol{x}},{\boldsymbol{y}}^{q^{v}+1})^{\perp}.$

On the other hand, by definition of $\mathscr{B}_{v}$ we have

(21)
$\mathscr{B}_{v}=\left\\{\operatorname{Tr}\left(\frac{P({\boldsymbol{x}})}{\Gamma({\boldsymbol{x}})^{q^{v}+1}}\right)\mid\deg
P<r(q^{v}-q^{v-1}+1)\right\\}.$

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
$\operatorname{Tr}\left({\mathscr{C}}\star{\mathscr{C}^{q^{v}}}\right)\subseteq\mathscr{B}_{v}$
will be to show that under certain conditions a codeword of the form
$\operatorname{Tr}\left(\frac{P({\boldsymbol{x}})}{\Gamma({\boldsymbol{x}})^{q^{v}+1}}\right)$
can be written as
$\operatorname{Tr}\left(\frac{Q({\boldsymbol{x}})}{\Gamma({\boldsymbol{x}})^{q^{v}+1}}\right)+\boldsymbol{c}$
for some codeword $\boldsymbol{c}\in\mathscr{B}_{v}$ with a polynomial $Q$
such that $\deg Q<\deg P$. For performing this task we will use the following
lemma.

######  Lemma 24.

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

(22)
$\displaystyle\operatorname{Tr}\left(\frac{P({\boldsymbol{x}})}{\Gamma({\boldsymbol{x}})^{q^{v}+1}}\right)$
$\displaystyle=$
$\displaystyle\operatorname{Tr}\left(\frac{A({\boldsymbol{x}})^{q}\Gamma({\boldsymbol{x}})}{\Gamma({\boldsymbol{x}})^{q^{v}+1}}\right)+\boldsymbol{c},\;\text{for
some $\boldsymbol{c}\in\mathscr{B}_{v}$}$ (23) $\displaystyle\deg A^{q}\Gamma$
$\displaystyle<$ $\displaystyle\deg P\quad\text{if $\deg P<r(q^{v}+1)$.}$

###### Proof.

For the first point, we just have to observe that

$\displaystyle\operatorname{Tr}\left(\frac{P({\boldsymbol{x}})}{\Gamma({\boldsymbol{x}})^{q^{v}+1}}\right)$
$\displaystyle=$
$\displaystyle\operatorname{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)$
$\displaystyle=$
$\displaystyle\operatorname{Tr}\left(\frac{A({\boldsymbol{x}})}{\Gamma({\boldsymbol{x}})^{q^{v-1}}}\right)+\operatorname{Tr}\left(\frac{B({\boldsymbol{x}})}{\Gamma({\boldsymbol{x}})^{q^{v}+1}}\right)$
$\displaystyle=$
$\displaystyle\operatorname{Tr}\left(\frac{A({\boldsymbol{x}})^{q}}{\Gamma({\boldsymbol{x}})^{q^{v}}}\right)+\operatorname{Tr}\left(\frac{B({\boldsymbol{x}})}{\Gamma({\boldsymbol{x}})^{q^{v}+1}}\right)\quad\text{(since
$\operatorname{Tr}(\alpha^{q})=\operatorname{Tr}(\alpha)$ for
$\alpha\in\mathbb{F}_{q^{m}}$)}$ $\displaystyle=$
$\displaystyle\operatorname{Tr}\left(\frac{A({\boldsymbol{x}})^{q}\Gamma({\boldsymbol{x}})}{\Gamma({\boldsymbol{x}})^{q^{v}+1}}\right)+\boldsymbol{c}\quad\quad\text{with
$\boldsymbol{c}\in\mathscr{B}_{v}$.}$

The last equality follows immediately from the definition of $\mathscr{B}_{v}$
(see (21)) 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 (23) clearly holds
or

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

in which case

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

Clearly

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

∎

The second lemma shows that the $\mathscr{B}_{v}$’s form a nested family of
codes:

######  Lemma 25.

We have for all $v\geqslant 0$:

$\mathscr{B}_{0}\subseteq\mathscr{B}_{1}\subseteq\cdots\subseteq\mathscr{B}_{v}\subseteq\mathscr{B}_{v+1}\subseteq\cdots$

###### Proof.

We will first prove that $\mathscr{B}_{v}\subseteq\mathscr{B}_{v+1}$ for
$v\geqslant 1$. Let us notice that

$\displaystyle\mathscr{B}_{v}$
$\displaystyle=\left\langle\,\operatorname{Tr}\left(\alpha_{l}{\boldsymbol{x}}^{c}{\boldsymbol{y}}^{q^{v}+1}\right)\mid
0\leq l<m,0\leq c<r(q^{v}-q^{v-1}+1)\,\right\rangle_{\mathbb{F}_{q}}$ (24)
$\displaystyle=\left\\{\operatorname{Tr}\left(\frac{P({\boldsymbol{x}})}{\Gamma({\boldsymbol{x}})^{q^{v}+1}}\right):P\in\mathbb{F}_{q^{m}}[X],\;\deg(P)<r(q^{v}-q^{v-1}+1)\right\\}$

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

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

Then, let us notice that

$\displaystyle\operatorname{Tr}\left(\frac{P({\boldsymbol{x}})}{\Gamma({\boldsymbol{x}})^{q^{v}+1}}\right)$
$\displaystyle=$
$\displaystyle\operatorname{Tr}\left(\frac{P({\boldsymbol{x}})\Gamma({\boldsymbol{x}})^{q^{v+1}-q^{v}}}{\Gamma({\boldsymbol{x}})^{q^{v+1}+1}}\right)$
$\displaystyle=$
$\displaystyle\operatorname{Tr}\left(\frac{A^{q}({\boldsymbol{x}})\Gamma({\boldsymbol{x}})}{\Gamma({\boldsymbol{x}})^{q^{v+1}+1}}\right)+\boldsymbol{c}$

where $\boldsymbol{c}\in\mathscr{B}_{v+1}$, $A$ is the quotient of the
division of $P\Gamma^{q^{v+1}-q^{v}}$ by $\Gamma^{q^{v+1}-q^{v}+1}$, and we
used Lemma 24 (with $v+1$ instead of $v$ and $P\Gamma^{q^{v+1}-q^{v}}$ instead
of $P$). Either $A=0$ and it follows immediately that
$\operatorname{Tr}\left(\frac{P({\boldsymbol{x}})}{\Gamma({\boldsymbol{x}})^{q^{v}+1}}\right)$
belongs to $\mathscr{B}_{v+1}$, or else, if $v\geq 1$,

$\displaystyle\deg A^{q}\Gamma$ $\displaystyle=$ $\displaystyle q\left(\deg
P+\deg\Gamma(q^{v+1}-q^{v})-\deg\Gamma(q^{v+1}-q^{v}+1)\right)+\deg\Gamma$
$\displaystyle<$ $\displaystyle
q\left(r(q^{v}-q^{v-1}+1)+r(q^{v+1}-q^{v})-r(q^{v+1}-q^{v}+1)\right]+r\;\;\text{(by
definition of $\mathscr{B}_{v}$ -see \eqref{eq:BCv_definition})}$
$\displaystyle=$ $\displaystyle q\left(r(q^{v}-q^{v-1})\right)+r$
$\displaystyle=$ $\displaystyle r(q^{v+1}-q^{v}+1).$

This shows that in this case too, we have that
$\operatorname{Tr}\left(\frac{P({\boldsymbol{x}})}{\Gamma({\boldsymbol{x}})^{q^{v}+1}}\right)$
belongs to $\mathscr{B}_{v+1}$. If $v=0$ we proceed similarly, the only
difference being that now the definition of $\mathscr{B}_{0}$ is not obtained
by plugging $v=0$ into (21), but is given by

$\displaystyle\mathscr{B}_{0}$
$\displaystyle=\left\\{\operatorname{Tr}\left(\frac{P({\boldsymbol{x}})}{\Gamma({\boldsymbol{x}})^{2}}\right):P\in\mathbb{F}_{q^{m}}[X],\;\deg(P)<2r-1\right\\}.$

Consider a codeword
$\operatorname{Tr}\left(\frac{P({\boldsymbol{x}})}{\Gamma({\boldsymbol{x}})^{2}}\right)$
in $\mathscr{B}_{0}$ and let us prove that it belongs to $\mathscr{B}_{1}$. We
proceed similarly as before and write

$\displaystyle\operatorname{Tr}\left(\frac{P({\boldsymbol{x}})}{\Gamma({\boldsymbol{x}})^{2}}\right)$
$\displaystyle=$
$\displaystyle\operatorname{Tr}\left(\frac{P({\boldsymbol{x}})\Gamma({\boldsymbol{x}})^{q-1}}{\Gamma({\boldsymbol{x}})^{q+1}}\right).$

We can again apply Lemma 24 with $v=1$ and
$P({\boldsymbol{x}})\Gamma({\boldsymbol{x}})^{q-1}$ (for the $P$ appearing in
this lemma). Notice that

$\displaystyle\deg P({\boldsymbol{x}})\Gamma({\boldsymbol{x}})^{q-1}$
$\displaystyle<$ $\displaystyle 2r-1+r(q-1)$ $\displaystyle<$ $\displaystyle
r(q+1).$

This shows that we can write

$\operatorname{Tr}\left(\frac{P({\boldsymbol{x}})\Gamma({\boldsymbol{x}})^{q-1}}{\Gamma({\boldsymbol{x}})^{q+1}}\right)=\operatorname{Tr}\left(\frac{Q({\boldsymbol{x}})}{\Gamma({\boldsymbol{x}})^{q^{v}+1}}\right)+\boldsymbol{c}$

with $\boldsymbol{c}$ belonging to $\mathscr{B}_{1}$ and $\deg Q<\deg
P\Gamma^{q+1}$. We can carry on this process further on
$\operatorname{Tr}\left(\frac{Q({\boldsymbol{x}})}{\Gamma({\boldsymbol{x}})^{q^{v}+1}}\right)$
by reducing the degree of $Q$ with Lemma 24 until getting at the end a
quotient $A$ of Lemma 24 equal to $0$, thus showing that
$\operatorname{Tr}\left(\frac{P({\boldsymbol{x}})}{\Gamma({\boldsymbol{x}})^{2}}\right)$
belongs to $\mathscr{B}_{1}$. ∎

We are now ready to prove Theorem 23.

###### Proof of Theorem 23.

Proof of (17). We start by using Lemma 21 which implies that

(26)
$\displaystyle\operatorname{Tr}\left({\mathscr{C}}\star{\mathscr{C}^{q^{v}}}\right)$
$\displaystyle\subseteq$
$\displaystyle\left\\{\operatorname{Tr}\left(\frac{P({\boldsymbol{x}})}{\Gamma({\boldsymbol{x}})^{q^{v}+1}}\right):\deg
P<(r-1)(q^{v}+1)+1\right\\}$ $\displaystyle=$
$\displaystyle\mathscr{A}_{(r-1)(q^{v}+1)+1}({\boldsymbol{x}},{\boldsymbol{y}}^{q^{v}+1})^{\perp}.$

We consider a codeword
$\operatorname{Tr}\left(\frac{P({\boldsymbol{x}})}{\Gamma({\boldsymbol{x}})^{q^{v}+1}}\right)$
in $\operatorname{Tr}\left({\mathscr{C}}\star{\mathscr{C}^{q^{v}}}\right)$ and
apply Lemma 24 to it. Since $\deg P\leqslant(r-1)(q^{v}+1)<r(q^{v}+1)$ we can
apply (23) and get that

$\operatorname{Tr}\left(\frac{P({\boldsymbol{x}})}{\Gamma({\boldsymbol{x}})^{q^{v}+1}}\right)=\operatorname{Tr}\left(\frac{Q({\boldsymbol{x}})}{\Gamma({\boldsymbol{x}})^{q^{v}+1}}\right)+\boldsymbol{c},$

where $\boldsymbol{c}\in\mathscr{B}_{v}$ and $\deg Q<\deg P$. We can continue
this process by applying iteratively Lemma 24 to $Q$ until the quotient $A$
becomes eventually the zero polynomial, which shows that

$\operatorname{Tr}\left(\frac{P({\boldsymbol{x}})}{\Gamma({\boldsymbol{x}})^{q^{v}+1}}\right)\in\mathscr{B}_{v}.$

Proof of (18). When $v\leqslant f$, Lemma 21 shows that the inclusion (26) is
actually an equality. We therefore have

$\operatorname{Tr}\left({\mathscr{C}}\star{\mathscr{C}^{q^{v}}}\right)=\mathscr{A}_{(r-1)(q^{v}+1)+1}({\boldsymbol{x}},{\boldsymbol{y}}^{q^{v}+1})^{\perp}.$

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

(27)
$\operatorname{Tr}\left({\mathscr{C}}\star{\mathscr{C}^{q^{v}}}\right)\subseteq\mathscr{B}_{v}=\mathscr{A}_{r(q^{v}-q^{v-1}+1)}({\boldsymbol{x}},{\boldsymbol{y}}^{q^{v}+1})^{\perp}.$

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

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

This shows that

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

which combined with the reverse inclusion (27) proves Equality (18).

Proof of (19). This is a direct consequence of Lemma 25 and that the
$\mathscr{B}_{v}$’s coincide with the
$\operatorname{Tr}\left({\mathscr{C}}\star{\mathscr{C}^{q^{v}}}\right)$’s in
this range from (18). ∎

A direct consequence of Theorem 23 is that

######  Corollary 26.

Let $\mathscr{G}({\boldsymbol{x}},\Gamma)$ be a Goppa code of order $r\geq
q-1$ over $\mathbb{F}_{q}$. Then

$(\mathscr{G}({\boldsymbol{x}},\Gamma)^{\perp})^{\star
2}\subseteq\mathscr{B}_{e}+\sum_{u=e+1}^{\left\lfloor\frac{m}{2}\right\rfloor}\operatorname{Tr}\left({\mathscr{C}}\star{\mathscr{C}^{q^{u}}}\right),$

for any non-negative integer $e$.

We can therefore conclude that

######  Corollary 27.

Let $\mathscr{G}({\boldsymbol{x}},\Gamma)$ be a Goppa code of order $r\geq
q-1$ over $\mathbb{F}_{q}$. Then

$\dim_{\mathbb{F}_{q}}(\mathscr{G}({\boldsymbol{x}},\Gamma)^{\perp})^{\star
2}\leq\binom{rm+1}{2}-\frac{m}{2}r\left((2{e_{\mathscr{G}}}+1)r-2(q-1)q^{{e_{\mathscr{G}}}-1}-1\right).$

###### Proof.

From Theorem 23 and Lemma 25, we have
$\operatorname{Tr}\left({\mathscr{C}}\star{\mathscr{C}^{q^{u}}}\right)\subseteq\mathscr{B}_{e}$,
for all $u\leq e$. Therefore

$\displaystyle\dim_{\mathbb{F}_{q}}(\mathscr{G}({\boldsymbol{x}},\Gamma)^{\perp})^{\star
2}$
$\displaystyle\leq\dim_{\mathbb{F}_{q}}\left(\sum_{u=0}^{\left\lfloor\frac{m}{2}\right\rfloor}\operatorname{Tr}\left({\mathscr{C}}\star{\mathscr{C}^{q^{u}}}\right)\right)$
$\displaystyle\leq\dim_{\mathbb{F}_{q}}(\mathscr{B}_{e})+\sum_{u=e+1}^{\left\lfloor\frac{m}{2}\right\rfloor}\dim_{\mathbb{F}_{q}}\operatorname{Tr}\left({\mathscr{C}}\star{\mathscr{C}^{q^{u}}}\right)\;\;\text{(for
arbitrary $e\in\\{0,\cdots,\left\lfloor\frac{m}{2}\right\rfloor\\}$)}$
$\displaystyle\leq rm(q^{e}-q^{e-1}+1)+\left(\frac{m-1}{2}-e\right)mr^{2}$
$\displaystyle=\binom{rm+1}{2}-\frac{m}{2}r\left((2e+1)r-2(q-1)q^{e-1}-1\right).$

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

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

over $\\{0,\cdots,\left\lfloor\frac{m}{2}\right\rfloor\\}$. We compute the
discrete derivative $\Delta T:e\rightarrow 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)\leqslant 0$. This corresponds to the least integer $e$ such that
$e\geqslant\log_{q}\left(\frac{r}{(q-1)^{2}}\right)+1$, i.e.
$\left\lceil\log_{q}\left(\frac{r}{(q-1)^{2}}\right)+1\right\rceil={e_{\mathscr{G}}}$
minimizes the function $T$ and consequently

$\dim_{\mathbb{F}_{q}}(\mathscr{G}({\boldsymbol{x}},\Gamma)^{\perp})^{\star
2}\leq\binom{rm+1}{2}-\frac{m}{2}r\left((2{e_{\mathscr{G}}}+1)r-2(q-1)q^{{e_{\mathscr{G}}}-1}-1\right).$

∎

######  Remark 28.

From the computation given in the proof of Corollary 27 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}}}}\operatorname{Tr}\left({\mathscr{C}}\star{\mathscr{C}^{q^{u}}}\right).$

This has been verified experimentally.

## Conclusion

In this article we revisited the distinguisher for random alternant and Goppa
codes presented for the first time in [FGO+13] 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 [FGO+13] 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 [FGO+13]. 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 [CGG+14]. 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 [COT17]. 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 generalized
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 aforementioned NIST competition, but this would break the 20 years old
signature scheme [CFS01] that is based on very high rate Goppa codes.

Acknowledgements. 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.

## References

  * [BCL+19] 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.
  * [BJMM12] 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\.
  * [BM17] Leif Both and Alexander May.  Optimizing BJMM with Nearest Neighbors: Full Decoding in $2^{2/21n}$ and McEliece Security.  In WCC Workshop on Coding and Cryptography, September 2017.  on line proceedings, see http://wcc2017.suai.ru/Proceedings_WCC2017.zip.
  * [CC98] 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.
  * [CCMZ15] 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.
  * [CFS01] 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.
  * [CGG+14] 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.
  * [COT17] 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.
  * [Del75] Philippe Delsarte.  On subfield subcodes of modified Reed-Solomon codes.  IEEE Trans. Inform. Theory, 21(5):575–576, 1975.
  * [FGO+11] Jean-Charles Faugère, Valérie Gauthier, Ayoub Otmani, Ludovic Perret, and Jean-Pierre Tillich.  A distinguisher for high rate McEliece cryptosystems.  In Proc. IEEE Inf. Theory Workshop- ITW 2011, pages 282–286, Paraty, Brasil, October 2011.
  * [FGO+13] 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.
  * [KT17] 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.
  * [LB88] 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.
  * [McE78] Robert J. McEliece.  A Public-Key System Based on Algebraic Coding Theory, pages 114–116.  Jet Propulsion Lab, 1978.  DSN Progress Report 44.
  * [MCP12] Irene Márquez-Corbella and Ruud Pellikaan.  Error-correcting pairs for a public-key cryptosystem.  CBC 2012, Code-based Cryptography Workshop, 2012.  Available on http://www.win.tue.nl/~ruudp/paper/59.pdf.
  * [MMT11] 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.
  * [MO15] 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.
  * [MS86] Florence J. MacWilliams and Neil J. A. Sloane.  The Theory of Error-Correcting Codes.  North–Holland, Amsterdam, fifth edition, 1986.
  * [Pat75] N. Patterson.  The algebraic decoding of Goppa codes.  IEEE Trans. Inform. Theory, 21(2):203–207, 1975.
  * [Ran15] 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\.
  * [Sen10] Nicolas Sendrier.  On the use of structured codes in code based cryptography.  In L. Storme S. Nikova, B. Preneel, editor, Coding Theory and Cryptography III, pages 59–68. The Royal Flemish Academy of Belgium for Science and the Arts, 2010.
  * [Ste88] 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.
  * [Wie10] 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.