# How arithmetic and geometry
make error correcting codes better

Alain Couvreur  Inria  Laboratoire LIX, CNRS UMR 7161, École Polytechnique,
91120 Palaiseau, France<EMAIL_ADDRESS>
###### Abstract

This note completes a talk given at the conference Curves over Finite Fields:
past, present and future celebrating the publication the book Rational Points
on Curves over Finite Fields by J.-P. Serre and organised at Centro de
ciencias de Benasque in june 2021. It discusses a part of the history of
algebraic geometry codes together with some of their recent applications. A
particular focus is done on the “multiplicative” structure of these codes,
i.e. their behaviour with respect to the component wise product. Some open
questions are raised and discussed.

###### Contents

  1. 1 Prerequisites in coding theory
  2. 2 Algebraic geometry codes
  3. 3 Component wise product
  4. 4 Decoding
    1. 4.1 Algebraic decoding in a nutshell
    2. 4.2 Back to AG codes
    3. 4.3 The story continues
  5. 5 Code–based cryptography and McEliece encryption scheme
  6. 6 Secret sharing
    1. 6.1 Which codes have small squares?
    2. 6.2 The quadratic hull of a code
  7. 7 A concluding remark

## Introduction

The story of algebraic geometry codes is a fascinating one for both
mathematicians and computer scientists. It lies at the crossroad of coding
theory, number theory and algebraic geometry and testifies of the need for
such interactions between different communities to provide efficient but also
elegant solutions to practical problems.

Coding theory began in the 50’s after the works of Claude Shannon [Sha48] and
Richard Hamming [Ham50]. The former developing a stochastic approach for error
correction and building the foundations of information theory and the latter
proposing a more combinatorial point of view. The original motivations came
from the need for error correction in computations and communications. Our
history is full of technologies who would never have been as efficient as they
were without error correcting codes. One can for instance mention NASA’s
program Mariner 9 whose objective was to transmit pictures from Mars and where
the error tolerance has been guaranteed by Reed–Muller codes.

Today, coding theory has become a rich and wide mathematical theory with
strong connections with combinatorics, probabilities, arithmetic, geometry and
algorithmics. More importantly, the field of applications of coding theory
impressively broadened in 70 years and introducing codes as objects permitting
good communications across noisy channels would be indisputably a very
restrictive description. Coding theory finds now numerous other applications,
for instance in symmetric cryptography, in public key cryptography or in cloud
storage. Results from coding theory are also used to address problems in other
mathematical areas such as combinatorics or number theory, or in theoretical
computer science with famous results such as the celebrated PCP theorem
[ALM+98].

Inside coding theory, algebra always played a particular rule. The use of
algebraic structures to design codes is almost as old as coding theory itself.
Reed–Muller codes [Ree54] have been designed using multivariate polynomials
over $\mathbf{F}_{2}$, then Reed–Solomon ones [RS60] are constructed thanks to
univariate polynomials and Berlekamp [Ber68, Ber15] developed a decoding
algorithm based on algebraic features. Interestingly, Berlekamp’s interest on
algebraic codes encouraged him to focus on some computational aspects of
finite fields which lead him to discover his famous algorithm for factorizing
polynomials over finite fields. In summary, algebra had an indisputable impact
on the development of coding theory but the converse is also true.

Algebraic geometry enters the game in the early 80’s with Goppa’s seminal
article [Gop81], followed by the unexpected and rather counter intuitive
result proved by Tsfasman, Vlăduţ and Zink [TVZ82] showing that, some codes
from modular or Shimura curves have better parameters than random codes. This
breakthrough motivated the impressive development of the theory of algebraic
geometry codes which today represent a broad and rich research area with a
significant number of independent applications. The present article presents a
part of this story. Then a particular focus is done on the behaviour of
algebraic geometry codes with respect to the component wise product and its
various applications, to decoding, cryptanalysis or secret sharing.

##  1 Prerequisites in coding theory

The central objects of our study are linear error correcting codes. In the
sequel, we denote by code any linear subspace $\mathcal{C}$ of
$\mathbf{F}_{q}^{n}$ endowed with the Hamming metric. The latter being defined
as

$\forall{\boldsymbol{x}},{\boldsymbol{y}}\in\mathbf{F}_{q}^{n},\qquad
d_{H}({\boldsymbol{x}},{\boldsymbol{y}})\stackrel{{\scriptstyle\text{def}}}{{=}}\Big{|}\Big{\\{}i\in\\{1,\dots,n\\}\leavevmode\nobreak\
|\leavevmode\nobreak\ x_{i}\neq y_{i}\Big{\\}}\Big{|}.$

The Hamming weight of a vector ${\boldsymbol{x}}\in\mathbf{F}_{q}^{n}$ is
defined as
$w_{H}({\boldsymbol{x}})\stackrel{{\scriptstyle\text{def}}}{{=}}d_{H}({\boldsymbol{x}},0)$.

Given a code $\mathcal{C}$, its parameters denoted $[n,k,d]_{q}$ are
respectively:

  * •

its length $n$, i.e the dimension of its ambient space $\mathbf{F}_{q}^{n}$;

  * •

its dimension $k$ as an $\mathbf{F}_{q}$–linear space;

  * •

its minimum distance $d_{\text{min}}(\mathcal{C})$ or $d$ when there is no
ambiguity on the considered code, is the minimum Hamming distance between two
distinct elements of $\mathcal{C}$ which can be formally defined as

$d_{\text{min}}(\mathcal{C})\stackrel{{\scriptstyle\text{def}}}{{=}}\min_{\boldsymbol{c}\in\mathcal{C}\setminus\\{0\\}}\Big{|}\\{i\in\\{1,\dots,n\\}\leavevmode\nobreak\
|\leavevmode\nobreak\ c_{i}\neq 0\\}\Big{|}.$

A decoding algorithm takes as input an ambient vector
${\boldsymbol{y}}\in\mathbf{F}_{q}^{n}$ and outputs a word $\boldsymbol{c}$
close to ${\boldsymbol{y}}$ (preferently the closest one) or fails (for
instance if ${\boldsymbol{y}}$ is too far from any element of $\mathcal{C}$).
Finally, given a code $\mathcal{C}\subseteq\mathbf{F}_{q}^{n}$ one sometimes
need to consider its dual $\mathcal{C}^{\perp}$ which is its orthogonal space
with respect to the canonical inner product:

$\langle{\boldsymbol{x}},{\boldsymbol{y}}\rangle\stackrel{{\scriptstyle\text{def}}}{{=}}\sum_{i=1}^{n}x_{i}y_{i}.$

If it is elementary to generate a code, the estimate of its minimum distance
such as the design of an efficient (let us say polynomial time) decoding
algorithm are very difficult tasks111The decoding problem has even been proved
to be NP–complete in [BMvT78]. which turn out to be intractable for the
majority of the codes. Actually, the aforementioned problems are solvable only
for very particular codes which are equipped with a particular structure. For
this sake, algebra provides remarkable constructions. The most elementary one
being that of Reed and Solomon [RS60].

######  Definition 1 (Reed–Solomon codes).

Let ${\boldsymbol{x}}=(x_{1},\dots,x_{n})$ be an $n$–tuple of distinct
elements of $\mathbf{F}_{q}$ and a positive integer $k<n$, we define

$RS_{k}({\boldsymbol{x}})\stackrel{{\scriptstyle\text{def}}}{{=}}\\{(f(x_{1}),\dots,f(x_{n})))\leavevmode\nobreak\
|\leavevmode\nobreak\ f\in\mathbf{F}_{q}[X],\ \deg f<k\\}.$

Such a code is known to have parameters $[n,k,n-k+1]$ and the proof of that
fact rests essentially on the elementary property that a nonzero polynomial of
degree $<k$ has less than $k$ distinct roots. Moreover, these codes are
optimal in the sense that they reach the so called Singleton bound asserting
that any $[n,k,d]$ code satisfies

$d\leqslant n-k+1.$ (1)

Finally, after the works of Berlekamp [WB83, Ber15], such codes benefit from a
decoding algorithm correcting in polynomial time an amount of errors up to
half the minimum distance. Using fast arithmetic, decoding can actually be
performed in quasi–linear time. Finally, after the works of Sudan and
Guruswami–Sudan in the late 90’s [Sud97, GS99] it is now known that correcting
efficiently an amount of errors beyond half the minimum distance is possible
for such codes at the cost of possibly (and rarely) returning a list of
closest vectors instead of a single one.

##  2 Algebraic geometry codes

Reed–Solomon codes are also known to have a drawback: they should be defined
over a field which is at least as large as the length of the code. On the
other hand, many computer science applications look for long codes over very
small fields. This issue has been addressed in the early 80’s by the Russian
mathematician V.D. Goppa [Gop81] who suggested to replace polynomials by
functions222Actually, Goppa’s original publication proposed to design codes by
evaluating residues of some differential forms living in some Riemann–Roch
space of differentials. However, its presentation can easily be reformulated
into an equivalent one with rational functions. in a Riemann–Roch space of a
given curve $\mathscr{X}$ and the evaluation values $x_{1},\dots,x_{n}$ by
some rational points of $\mathscr{X}$.

######  Definition 2.

Let $\mathscr{X}$ be a smooth projective absolutely irreducible curve over a
field $\mathbf{F}_{q}$. Let $\mathcal{P}=(P_{1},\dots,P_{n})$ be an ordered
$n$–tuple of distinct rational points of $\mathscr{X}$ and $G$ be a rational
divisor on $\mathscr{X}$ whose support avoids333This restriction on the
support of $G$ can easily be relaxed. See [CR21, Rem. 15.3.8]. $\mathcal{P}$.
The algebraic geometry code (AG code) associated to the triple
$(\mathscr{X},\mathcal{P},G)$ is defined as

$\mathcal{C}_{L}({\mathscr{X}},{\mathcal{P}},{G})\stackrel{{\scriptstyle\text{def}}}{{=}}\\{(f(P_{1}),\dots,f(P_{n}))\leavevmode\nobreak\
|\leavevmode\nobreak\ f\in L(G)\\},$

where $L(G)$ denotes the Riemann–Roch space associated to $G$.

This code construction is of deep interest for many reasons. First, because of
their excellent parameters and second, because the algebraic decoding
algorithms existing for Reed–Solomon naturally extend to AG codes.

######  Proposition 3.

In the context of Definition 2, let $g$ be the genus of $\mathscr{X}$. Then,
the code $\mathcal{C}_{L}({\mathscr{X}},{\mathcal{P}},{G})$ has parameters
$[n,k,d]$ where

$\displaystyle k$ $\displaystyle\geqslant\deg G+1-g\quad\text{with equality
if}\quad\deg G>2g-2;$ $\displaystyle d$ $\displaystyle\geqslant n-\deg G.$

Reed–Solomon codes are nothing but codes from $\mathbf{P}^{1}$ and, as already
mentioned, their main drawback is that for a fixed base field $\mathbf{F}_{q}$
the length of a Reed–Solomon code is bounded from above by
$|\mathbf{P}^{1}(\mathbf{F}_{q})|=q+1$. On the other hand, for AG codes, the
length is allowed to reach the number $|\mathscr{X}(\mathbf{F}_{q})|$ of
rational points, which can be arbitrarily large. Considering sequences of
curves whose number of rational points goes to infinity, it is possible to
design sequences of codes whose length goes to infinity while the dimension
and the minimum distance are linear in the length. Indeed, regarding
Proposition 3, the parameters of an AG code satisfy

$k+d\geqslant n+1-g.$

Set $R\stackrel{{\scriptstyle\text{def}}}{{=}}\frac{k}{n}$ and
$\delta\stackrel{{\scriptstyle\text{def}}}{{=}}\frac{d}{n}$ then,

$R+\delta\geqslant 1+\frac{1}{n}-\frac{g}{n}\cdot$ (2)

Introducing the Ihara constant

$A(q)\stackrel{{\scriptstyle\text{def}}}{{=}}\limsup_{g\rightarrow+\infty}\max_{\mathscr{X}}\frac{|\mathscr{X}(\mathbf{F}_{q})|}{g},$

where the max is taken over all the curves of genus $g$, we deduce the
existence of sequences of codes whose asymptotic rates and relative distances
satisfy

$R+\delta\geqslant 1-\frac{1}{A(q)}\cdot$ (3)

In the early 80’s, Tsfasman, Vlăduţ and Zink [TVZ82] and independently Ihara
[Iha81] proved that $A(q)\geqslant\sqrt{q}-1$ when $q$ is a square and this
quantity is reached by some sequences of modular curves for $q=p^{2}$ with $p$
prime and by some sequences of Shimura curves for general squares $q$. Later
on, Drinfeld and Vlăduţ [VD83] proved that $A(q)\leqslant\sqrt{q}-1$ for any
prime power $q$, showing that the aforementioned lower bound for $q$ square
was actually optimal. These results lead to an impressive breaktrhough in
coding theory since for a square $q\geqslant 49$ this lower bound exceeds the
famous Gilbert Varshamov bound which is safisfied by “almost any code”. In
short, some sequences of AG codes are asymptotically better than random codes,
a particularly striking and unexpected result. Inequality (3) is usually
referred to as the Tsfasman–Vlăduţ–Zink bound and, because of its famous
coding theoretic consequences, has been the first stone of an impressive line
of works in order to obtain better estimates for the Ihara constant when $q$
was not a square. Hundreds of papers have been published in this direction by
using either class field towers or the so–called recursive towers introduced
by Garcia and Stichtenoth [GS95]. Actually, the point of this paper is not to
develop the presentation of these lines of works which would require a fully
independent study. See for instance [B22]. The objective of the previous
discussion was only to explain why AG codes became so famous in the 80’s. They
now represent a wide research area and it is worth mentioning that their
interest and their applications actually exceed the single question of which
optimal pairs $(R,\delta)$ are reachable.

Indeed, in many situations where Reed–Solomon codes have been proposed as a
first solution, AG codes appear immediately after as a more flexible option
permitting to circumvent the issues raised by the inherent drawback of
Reed–Solomon codes : their bounded length for a fixed alphabet. This appears
for instance in cloud computing where Locally Recoverable Codes (LRC) are
introduced in order to address the practical issues raised by server failures
in data centers. In [TB14], Tamo and Barg propose a construction derived from
Reed–Solomon codes which turns out to be optimal with respect to some
Singleton–like bound but requiring the length to be bounded. Later on, Barg,
Tamo and Vlăduţ [BTV17] propose an AG–based construction providing the
expected flexibility in terms of blocklength. We refer the reader to [CR21, §
15.9] for further details.

In the sequel, we discuss other coding theoretic issues where AG codes have
been involved. We also discuss open coding theoretic questions where the use
of algebraic geometry could be crucial.

##  3 Component wise product

In the last decades, an apparently elementary operation which took an
increasing importance in coding theory is the component wise product of
vectors or codes, i.e. the multiplication operation in $\mathbf{F}_{q}^{n}$
regarded as a product of rings:

$\forall\boldsymbol{a},\boldsymbol{b}\in\mathbf{F}_{q}^{n},\quad\boldsymbol{a}\star\boldsymbol{b}\stackrel{{\scriptstyle\text{def}}}{{=}}(a_{1}b_{1},\dots,a_{n}b_{n}).$

This operation extends to codes where, to keep a linear structure, the product
of two codes is defined as the span of the products of their vectors

######  Definition 4.

Given two codes $\mathcal{A},\mathcal{B}\subseteq\mathbf{F}_{q}^{n}$,

$\mathcal{A}\star\mathcal{B}\stackrel{{\scriptstyle\text{def}}}{{=}}\text{Span}_{\mathbf{F}_{q}}\left\\{\boldsymbol{a}\star\boldsymbol{b}\leavevmode\nobreak\
|\leavevmode\nobreak\
\boldsymbol{a}\in\mathcal{A},\boldsymbol{b}\in\mathcal{B}\right\\}.$

Importing such a ring structure over $\mathbf{F}_{q}^{n}$ is actually rather
natural when studying codes such as AG codes which are obtained by evaluation
of functions living in a ring. Reconsidering Definition 2 and denoting by
$\mathcal{O}_{\mathscr{X},\mathcal{P}}$ the semi-local ring
$\bigcap_{P\in\mathcal{P}}\mathcal{O}_{\mathscr{X},P}$, the evaluation map

$\text{ev}_{\mathcal{P}}:\left\\{\begin{array}[]{ccc}\mathcal{O}_{\mathscr{X},\mathcal{P}}&\longrightarrow&\mathbf{F}_{q}^{n}\\\
f&\longmapsto&(f(P_{1}),\dots,f(P_{n}))\end{array}\right.$

is a ring homomorphism from $\mathcal{O}_{\mathscr{X},\mathcal{P}}$ to
$\mathbf{F}_{q}^{n}$ equipped with the $\star$ product. Moreover,
$\mathcal{C}_{L}({\mathscr{X}},{\mathcal{P}},{G})$ is nothing but the image of
$L(G)$ by this map. In summary, considering the $\star$ product is natural in
order to take into account the rich algebraic structure of AG codes coming
from the parent curve.

In the last decades the $\star$ product took an increasing importance in
coding theory. For instance, we explain in § 4 and 6 that the design of
algebraic decoding algorithms or the properties of some secret sharing schemes
can easily be interpreted in terms of this operation. The reader interested in
an in–depth study of the arithmetic of this operation together with some of
its applications is encouraged to look at the excellent survey [Ran14].

For now, and because of the underlying algebraic geometric structure, AG codes
have a very peculiar behaviour with respect to the $\star$ product. Indeed,
for a general code $\mathcal{C}\subseteq\mathbf{F}_{q}^{n}$, we have

$\dim\mathcal{C}\star\mathcal{C}\leqslant\min\left\\{n,\
{\dim\mathcal{C}+1\choose 2}\right\\}.$ (4)

Moreover, it is proved in [CCMZ15] that for a random code the above inequality
is an equality with a high probability. Typically, the $\star$–square of a
random code either fills in its ambient space or has the same dimension as the
symmetric square $S^{2}\mathcal{C}$ of $\mathcal{C}$ (note that there is a
surjective canonical map
$S^{2}\mathcal{C}\rightarrow\mathcal{C}\star\mathcal{C}$). For non symmetric
products, one can observe very similar behaviours. Namely, given two codes
$\mathcal{C},\mathcal{D}\subseteq\mathbf{F}_{q}^{n}$, we have

$\dim\mathcal{C}\star\mathcal{D}\leqslant\min\left\\{n,\
\dim\mathcal{C}\cdot\dim\mathcal{D}-{\dim\mathcal{C}\cap\mathcal{D}\choose
2}\right\\},$

where again the inequality is typically an equality when
$\mathcal{C},\mathcal{D}$ are random.

On the other hand, the behaviour of AG codes with respect to the $\star$
operation strongly differs from that of random codes.

######  Theorem 5.

Let $\mathscr{X},\mathcal{P}$ be as in Definition 2 and $F,G$ be two rational
divisors of $\mathscr{X}$ then

$\mathcal{C}_{L}({\mathscr{X}},{\mathcal{P}},{F})\star\mathcal{C}_{L}({\mathscr{X}},{\mathcal{P}},{G})\subseteq\mathcal{C}_{L}({\mathscr{X}},{\mathcal{P}},{F+G}).$

Moreover, the above inclusion is an equality when $\deg F\geqslant 2g$ and
$\deg G\geqslant 2g+1$.

###### Proof.

This is a direct consequence of [Mum70, Thm. 6]. See [CMCP17, Cor. 9]. ∎

In particular, for a random code $\mathcal{R}$ whose square does not fill in
the ambient space, according to (4) and the subsequent discussion, the
dimension of $\mathcal{R}\star\mathcal{R}$ is quadratic in $\dim\mathcal{R}$.
On the other hand, for an AG code
$\mathcal{C}_{L}({\mathscr{X}},{\mathcal{P}},{G})$ from a genus $g$ curve
$\mathscr{X}$ with $2g<\deg G<\frac{n}{2}$, Theorem 5 together with
Riemann–Roch Theorem entail

$\dim\mathcal{C}_{L}({\mathscr{X}},{\mathcal{P}},{G})\star\mathcal{C}_{L}({\mathscr{X}},{\mathcal{P}},{G})=2\dim\mathcal{C}_{L}({\mathscr{X}},{\mathcal{P}},{G})-1+g.$

In short, for low genera, the dimension of the square of an AG code is somehow
linear in the original dimension instead of being quadratic for random codes.
This significant difference is actually a strength for AG codes for instance
in order to perform an efficient error correction. On the other hand, as
explained further in § 5, it is also a weakness making AG codes bad candidates
for public key encryption. The subsequent sections discuss several
consequences of this observation on the behaviour of AG codes with respect to
the $\star$–product.

##  4 Decoding

The design of efficient decoding algorithms for AG codes is an important part
of the theory starting in the late 80’s with the work of Justesen, Larsen,
Jensen, Havemose and Høholdt [JLJ+89] and and culminating around 2000 with the
works of Guruswami and Sudan [GS99] on the list decoding of Reed–Solomon and
AG codes. We refer the reader to the excellent surveys [HP95, BH08] for
further details on this history.

Interestingly, the first works on the decoding of AG codes [JLJ+89, SV90]
strongly involved the arithmetic of the underlying curve. A few years later,
Pellikaan [Pel92] and independently Kötter [Köt92] noticed that one could get
rid from geometry in the algorithm’s description and only take into account
the non generic behaviour of AG codes with respect to the $\star$–product.
This point of view leads to an observation, the very reason why AG codes are
equipped with polynomial time decoders while arbitrary codes are not is their
peculiar behaviour with respect to the $\star$–product.

###  4.1 Algebraic decoding in a nutshell

The decoding paradigm presented by Pellikaan, is now known as Error Correcting
Pairs. We give here a rather unusual presentation of this algorithm that we
expect to be somehow more elementary to understand.

Consider a code $\mathcal{C}$ and a received vector
${\boldsymbol{y}}=\boldsymbol{c}+\boldsymbol{e}$ where
$\boldsymbol{c}\in\mathcal{C}$ and $\boldsymbol{e}\in\mathbf{F}_{q}^{n}$ has
weight $w_{H}(\boldsymbol{e})\leqslant t$, where $w_{H}(\cdot)$ is defined in
§ 1 and $t$ is a constant that will be clarified further. Obviously,
${\boldsymbol{y}}$ should be considered as known while
$\boldsymbol{c},\boldsymbol{e}$ are not. The key of algebraic decoding is to
introduce an auxiliary code $\mathcal{A}$ in order to localise the error
positions. The code $\mathcal{A}$ should be chosen so that $\dim\mathcal{A}>t$
and the product $\mathcal{A}\star\mathcal{C}$ is “not too large”. In
particular $\mathcal{A}\star\mathcal{C}\varsubsetneq\mathbf{F}_{q}^{n}$.

The first step of the algorithm consists in computing the space

$K\stackrel{{\scriptstyle\text{def}}}{{=}}\left\\{\boldsymbol{a}\in\mathcal{A}\leavevmode\nobreak\
|\leavevmode\nobreak\
\boldsymbol{a}\star{\boldsymbol{y}}\in\mathcal{A}\star\mathcal{C}\right\\}.$

This space can be computed by Gaussian elimination with the very knowledge of
${\boldsymbol{y}}$ and $\mathcal{A},\mathcal{C}$ while, by definition of
$\mathcal{A}\star\mathcal{C}$ it actually equals

$K=\left\\{\boldsymbol{a}\in\mathcal{A}\leavevmode\nobreak\
|\leavevmode\nobreak\
\boldsymbol{a}\star\boldsymbol{e}\in\mathcal{A}\star\mathcal{C}\right\\}.$

Next, the hope is that for any $\boldsymbol{a}\in K$, the product
$\boldsymbol{a}\star\boldsymbol{e}$ is $0$. This is in particular what should
happen when the minimum distance of $\mathcal{A}\star\mathcal{C}$ exceeds $t$
since $w_{H}(\boldsymbol{a}\star\boldsymbol{e})\leqslant
w_{H}(\boldsymbol{e})\leqslant t$. In this situation, any $\boldsymbol{a}\in
K$ actually vanishes at any nonzero position of $\boldsymbol{e}$ and hence one
can expect that the common zero positions of the elements of $K$ permit to
identify the nonzero positions of $\boldsymbol{e}$. Once the errors are
localised, decoding turns out to be solvable by the resolution of a linear
system.

In summary, correcting $t$ errors for a code $\mathcal{C}$ is possible as soon
as there exists an auxiliary code $\mathcal{A}$ such that

  1. (i)

$\dim\mathcal{A}>t$;

  2. (ii)

$d_{\text{min}}(\mathcal{A}\star\mathcal{C})>t$;

  3. (iii)

$d_{\text{min}}(\mathcal{A})+d_{\text{min}}(\mathcal{C})>n$.

###### Sketch of proof.

First, note that $K$ contains the so–called shortening of $\mathcal{A}$ at the
error positions, i.e. the subcode of $\mathcal{A}$ of words vanishing where
$\boldsymbol{e}$ does not. Under Condition (i), this shortening of
$\mathcal{A}$ is nonzero and hence $K\neq 0$. Next, because of this previous
discussion, Condition (ii) asserts that $K$ actually equals this shortening of
$\mathcal{A}$. Finally, Condition (iii) permits to make sure that, once the
error positions are known, the resolution of a linear system will provide
$\boldsymbol{e}$ as the unique solution. See [HP95, Prop. 2.4] for further
details. ∎

######  Remark 6.

Actually, Condition (ii) is rather restrictive and can be relaxed to
$\dim\mathcal{A}-t+\dim\mathcal{A}\star\mathcal{\mathcal{C}}\leqslant n$ which
permits to typically expect that
$(K\star\boldsymbol{e})\cap\mathcal{A}\star\mathcal{C}=\\{0\\}$, which is
sufficient to obtain that $K$ is the shortening of $\mathcal{A}$ we look for.
Similarly, Condition (iii) may be removed. Relaxing these conditions is
possible at the cost that the algorithm may fail for some rare error patterns
$\boldsymbol{e}$.

######  Remark 7.

Pellikaan’s original description of the so–called Error Correcting pairs
involves two auxiliary codes $\mathcal{A}$ and $\mathcal{B}$ (see for instance
[HP95, Def. 12.1]). One can actually prove that the code
$\mathcal{B}=(\mathcal{A}\star\mathcal{C})^{\perp}$ satisfies the conditions
of Error Correcting Pairs.

###  4.2 Back to AG codes

Now, if the code $\mathcal{C}$ is the AG code
$\mathcal{C}_{L}({\mathscr{X}},{\mathcal{P}},{G})$, then, given a divisor $F$
of degree $\geqslant t+g$, the code
$\mathcal{A}\stackrel{{\scriptstyle\text{def}}}{{=}}\mathcal{C}_{L}({\mathscr{X}},{\mathcal{P}},{F})$
satisfies all the expected requirements as soon as $n-\deg(F+G)>t$ which leads
to

$t\leqslant\frac{d^{*}-1}{2}-\frac{g}{2},$ (5)

where $d^{*}\stackrel{{\scriptstyle\text{def}}}{{=}}n-\deg G$ is the Goppa
designed distance, i.e. the lower bound on the minimum distance given by
Proposition 3.

###  4.3 The story continues

Somehow the “$-g/2$” term in (5) seems disappointing since one can expect a
unique decoding up to $\frac{d-1}{2}$ errors. If the previous algorithm is
proved to reach the decoding radius (5), it turns out to be able to correct
“almost any” error pattern of weight up to half the designed distance (more or
less because of Remark 6). During the 90’s, many publications targeted to get
rid of this $g/2$ term. This has been completed in [Ehr93] and [FR93] using
two distinct approaches. Interestingly, if the radius (5) is reached using a
rather generic algorithm which does almost not use the arithmetic of the
underlying curves, the two aforementioned papers improve the decoding radius
while considering again the curve’s arithmetic.

Later on, a new question has been raised: “can one correct errors beyond half
the minimum distance at the cost of possibly returning a list of codewords
instead of a single one”. A positive answer has been given by Sudan for
Reed–Solomon codes [Sud97] and Guruswami and Sudan for AG codes [GS99]. The
latter paper providing a polynomial time algorithm correcting up to the
so–called Johnson bound, a radius under which any decoder is guaranteed to
return a list whose size is polynomial in the code length.

The reason why all the aforementioned algorithms succeed to decode AG codes
and not arbitrary ones, can somehow be understood in terms of the peculiar
behaviour of these codes with respect to the $\star$ product. See for instance
[Ros18, CP20, PRS21].

##  5 Code–based cryptography and McEliece encryption scheme

Code–based cryptography dates back to 1978 with the seminal paper of McEliece
[McE78] proposing a public key encryption scheme whose security is related to
the hardness of the decoding problem. Informally, the principle is to take a
code for which a decoding algorithm correcting up to $t$ errors is known and
to publish one of its bases. Encryption consists in encoding the plaintext
into a codeword and add some randomly chosen error pattern of weight $t$ while
decryption consists in decoding, which is a possible task for the legitimate
receiver.

In terms of security, one expects the published version of the code to be
computationally indistinguishable from a random code. Thus, under this
indistinguishability assumption an attacker cannot do better than trying to
solve the decoding problem for an apparently random code. The latter problem
is proved to be NP–complete [BMvT78] but more importantly, it is supposed to
be hard in average, i.e. hard for randomly chosen inputs. Still, up to now the
best known algorithms for generic decoding have a time complexity which is
exponential in the weight of the error.

Among the various proposals to instantiate McEliece scheme, Reed–Solomon and
AG codes have been proposed [Nie86, JM96]. It turns out that the algebraic
structure of these codes and in particular their structure with respect to the
component wise product mentioned in § 3, which is the key of the algebraic
decoding as explained in § 4, also represents a strong weakness of these
codes. Indeed, because of Theorem 5 and the subsequent discussion, the
operation $\mathcal{C}\mapsto\mathcal{C}\star\mathcal{C}$ precisely provides a
polynomial time distinguisher between AG codes and random ones making the
latter ones unusable for public key encryption. To turn this distinguisher
into a full key recovery attack, we refer the reader to [CMCP17].

Therefore, if the raw use of AG codes is not a secure, it is still possible to
use “deteriorate” versions of them for which decoding is still possible but
with a much lower decoding radius $t$. For instance, one can consider some
random subcodes of AG codes with a large enough codimension or take subfield
subcodes, that is to say, start from an AG code in $\mathbf{F}_{q^{m}}^{n}$
and only keep vectors whose entries are all in the subfield $\mathbf{F}_{q}$.
In some sense, McEliece’s original proposal was based on the latter idea with
a genus 0 underlying curve. We refer the reader to [CR21, § 15.7] for further
details on the history of cryptanalysis of AG codes.

##  6 Secret sharing

In [Sha79], A. Shamir proposes a secure scheme for a set of players to share a
secret so that a coalition of $k$ of them can get the secret while any
coalition of less than $k$ players cannot get even a partial information on
the secret. The scheme is based on Lagrange interpolation and can actually be
interpreted in terms of codes. For $n-1$ players and a given secret
$s\in\mathbf{F}_{q}$, take an $[n,k,d]_{q}$ code
$\mathcal{C}\subseteq\mathbf{F}_{q}^{n}$, choose an arbitrary vector
$\boldsymbol{c}\in\mathcal{C}$ whose last entry $c_{n}=s$ and distribute the
$n-1$ other entries to the players. The reconstruction and security properties
of the scheme can actually be interpreted in terms of the minimum distance of
$\mathcal{C}$ and its dual $\mathcal{C}^{\perp}$.

######  Lemma 8.

A coalition of $r>n-d_{\text{min}}(\mathcal{C})$ players can recover the
secret while any coalition of
$r^{\prime}<d_{\text{min}}(\mathcal{C}^{\perp})-1$ players cannot get any
information on the secret.

###### Proof.

Given $I\subseteq\\{1,\dots,n\\}$, denote by $\mathcal{C}_{I}$ the image of
$\mathcal{C}$ under the canonical projection on the entries with index in $I$:

$\boldsymbol{c}\longmapsto\boldsymbol{c}_{I}\stackrel{{\scriptstyle\text{def}}}{{=}}{(c_{i})}_{i\in
I}\leavevmode\nobreak\ .$

The first assertion is due to the fact that if
$|I|>n-d_{\text{min}}(\mathcal{C})$, then this canonical projection
$\mathcal{C}\rightarrow\mathcal{C}_{I}$ is injective. Hence, the knowledge of
$\boldsymbol{c}_{I}$ is enough to recover the whole vector $\boldsymbol{c}$
and in particular the secret $s=c_{n}$.

On the other hand, if $|I|<d_{\text{min}}(\mathcal{C}^{\perp})-1$, then one
can prove that $\mathcal{C}_{I\cup\\{n\\}}=\mathbf{F}_{q}^{|I|+1}$ and hence
for any $s^{\prime}\in\mathbf{F}_{q}$ there exists
$\boldsymbol{c}^{\prime}\in\mathcal{C}$ such that
$\boldsymbol{c}^{\prime}_{n}=s^{\prime}$ and
$\boldsymbol{c}^{\prime}_{I}=\boldsymbol{c}_{I}$. Thus, with the only
knowledge of $\boldsymbol{c}_{I}$, the possible values of the secret are
uniformly distributed. ∎

The coding theoretic interpretation of Shamir’s scheme rests on a
$k$–dimensional Reed–Solomon code. It permits the secret recovery by any
$k$–tuple of users while coalitions of $r<k$ users cannot get any information
on the secret.

Another interesting feature of Shamir’s scheme is that it is linear: if one
wants to perform linear combinations of secrets, the users only have to
perform separately the linear combination of their own shares and the result
of a legal coalition will be the expected linear combination. Next, one could
expect to be able to perform further arithmetic operations on the secrets such
as multiplications. In such situations the code $\mathcal{C}\star\mathcal{C}$
enters the game again. This is at the core of the so–called arithmetic secret
sharing schemes which can serve as a basis for secure multiparty computation
protocols [CDM00]. Here we refer the reader to [CDN15, Chap. 12] and [CR21, §
15.8.4] for further details on the expected properties a code should have to
provide a good arithmetic secret sharing scheme. Note that very similarly to
other applications, Reed–Solomon codes — yielding Shamir’s scheme — are
somehow optimal but suffer from the length restriction: the number of players
cannot exceed the size of the ground field i.e. the cardinality of the set of
secrets. Next, AG codes appear to be the best solution to address this
limitation.

In this context, an open question remains: which codes may be suitable for
arithmetic secret sharing? At least a first question could be which codes
$\mathcal{C}$ satisfy the property that $\mathcal{C}\star\mathcal{C}$ is
“small”?. According to [CDM00, Thm. 12.19], the coding theoretic requirements
to design a multiplicative secret sharing scheme consist in lower bounds on
the minimum distances of $\mathcal{C}^{\perp}$ and
$\mathcal{C}\star\mathcal{C}$. According to Singleton bound (1), this entails
a lower bound on the dimension of $\mathcal{C}$ and an upper bound on that of
$\mathcal{C}\star\mathcal{C}$. Then, finding codes $\mathcal{C}$ of fixed
dimension $k$ such that $\mathcal{C}\star\mathcal{C}$ has the least possible
dimension is a question of interest and classifying such codes is a crucial
question which remains widely open up to now and that is discussed in the
sequel.

###  6.1 Which codes have small squares?

Let us focus on the following problem, which codes
$\mathcal{C}\subseteq\mathbf{F}_{q}^{n}$ of dimension $k$ have a square of
small dimension? We first need to clarify what is meant by “small”. For this
we need the following definition.

######  Definition 9.

A code $\mathcal{A}\subseteq\mathbf{F}_{q}^{n}$ is said to be degenerate if it
is the direct sum of two subcodes with disjoint supports. Equivalently, there
exist subcodes $\mathcal{A}_{1},\mathcal{A}_{2}\subseteq\mathbf{F}_{q}^{n}$
such that $\mathcal{A}=\mathcal{A}_{1}\oplus\mathcal{A}_{2}$ and
$\mathcal{A}_{1}\star\mathcal{A}_{2}=\\{0\\}$.

Now, according to [HLX02, Thm. 2.4], as soon as $\mathcal{C}\star\mathcal{C}$
is non degenerate, there is an analog of Cauchy–Davenport formula in additive
combinatorics which asserts that

$\dim\mathcal{C}\star\mathcal{C}\geqslant 2\dim\mathcal{C}-1.$

Next, for any positive integer $\gamma$, what can one say about codes
satisfying

$\dim\mathcal{C}\star\mathcal{C}=2\dim\mathcal{C}-1+\gamma?$ (6)

The quantity $\gamma$ should be “small” and inspired by additive
combinatorics, one can first target Freiman–like results [TV06, Thm. 5.11] and
study the case where $\gamma\leqslant\dim\mathcal{C}-3$.

First, one can note that AG codes yield a solution of the raised problem.
Indeed, Theorem 5 asserts that an AG code
$\mathcal{C}_{L}({\mathscr{X}},{\mathcal{P}},{G})$ from a curve of genus
$\gamma$ with $\deg G>2\gamma$ precisely satisfies this property. However,
they are not the only ones. It is also possible for some subcodes of AG codes
from curves of genus $<\gamma$ to satisfy (6). For instance, for $\gamma=1$,
Property (6) is clearly satisfied by AG codes from elliptic curves but also by
some codes from a curve of genus $0$ as explained in the example below.

######  Example 10.

Consider the projective line $\mathbf{P}^{1}$, denote by $P_{\infty}$ the
place at infinity and by $\mathcal{P}$ an ordered sequence of distinct degree
$1$ finite places. The code
$\mathcal{C}_{L}({\mathbf{P}^{1}},{\mathcal{P}},{kP_{\infty}})$ is nothing but
a $(k+1)$–dimensional Reed–Solomon code and let $\mathcal{C}$ be its subcode
spanned by the evaluations of the functions $1,x^{2},x^{3},\dots,x^{k}$, that
is to say, removing $x$. The code $\mathcal{C}\star\mathcal{C}$ will be
spanned by the evaluations of $1,x^{2},x^{3},\dots,x^{2k}$ and hence will have
dimension $2k=2\dim\mathcal{C}$ while being constructed from a genus $0$
curve.

######  Question 1.

Let $k$ be a positive integer and $0<\gamma\leqslant k-3$. Are there
$k$–dimensional codes $\mathcal{C}\subseteq\mathbf{F}_{q}^{n}$, such that
$\mathcal{C}\star\mathcal{C}$ is non degenerate, satisfies

$\dim\mathcal{C}\star\mathcal{C}=2\dim\mathcal{C}-1+\gamma$

and $\mathcal{C}$ is not contained in an AG code from a curve of genus
$g\leqslant\gamma$?

For $\gamma=0$, it has been proved by Mirandola and Zémor [MZ15] that MDS
codes (i.e. codes whose minimum distance reaches the Singleton bound (1))
which satisfy $\dim\mathcal{C}\star\mathcal{C}=2\dim\mathcal{C}-1$ are
equivalent to Reed–Solomon codes. Interestingly, this fact was already known
from an algebraic geometry point of view as Castelnuovo’s Lemma (see for
instance [ACGH85, § III.2, p. 120]).

For larger $\gamma$’s, the problem is still open. The following paragraphs
discuss a possible geometric approach to study this problem. We acknowledge
that this discussion raises more questions than answers.

###  6.2 The quadratic hull of a code

At least a first question could be: do such codes always arise from curves? In
[Ran21] a notion called quadratic hull of a code, associates an algebraic
variety to an arbitrary code in the following manner. Given a $k$–dimensional
code $\mathcal{C}\subseteq\mathbf{F}_{q}^{n}$, consider a generator matrix $G$
for $\mathcal{C}$, i.e. a $k\times n$ matrix whose rows span $\mathcal{C}$.
Assuming that the columns of $G$ are pairwise independent, and regarding these
columns as points of $\mathbf{P}^{k-1}$, we associate to $\mathcal{C}$ the
corresponding $n$–tuple $V(\mathcal{C})$ of elements of
$\mathbf{P}^{k-1}(\mathbf{F}_{q})$. By this manner, $\mathcal{C}$ can be
regarded as an evaluation code: it is the code of evaluations of
$H^{0}(\mathbf{P}^{k-1},\mathcal{O}(1))$ at the points of $V(\mathcal{C})$.
Moreover, $\mathcal{C}\star\mathcal{C}$ can be regarded in this way as the
code of evaluations of $H^{0}(\mathbf{P}^{k-1},\mathcal{O}(2))$ at these same
points! Let $I_{2}(V(\mathcal{C}))$ be the space of quadratic forms vanishing
on $V(\mathcal{C})$, we have the following exact sequence

$0\longrightarrow I_{2}(V(\mathcal{C}))\longrightarrow
H^{0}(\mathbf{P}^{k-1},\mathcal{O}(2))\longrightarrow\mathcal{C}\star\mathcal{C}\longrightarrow
0.$ (7)

The quadratic hull $\mathscr{H}_{2}(\mathcal{C})$ of $\mathcal{C}$ is the
variety defined by the homogeneous ideal of
$\mathbf{F}_{q}[X_{0},\dots,X_{k-1}]$ spanned by $I_{2}(V(\mathcal{C}))$.
Equivalently, it is the intersection of quadrics containing $V(\mathcal{C})$.
Clearly, $\mathscr{H}_{2}(\mathcal{C})$ contains $V(\mathcal{C})$ but may
contain further elements.

######  .

Let $\mathscr{X}$ be a curve of genus $g$, $\mathcal{P}$ be an ordered
$n$–tuple of rational points of $\mathscr{X}$ and $G$ be a divisor such that
$2g+2\leqslant\deg G<\frac{n}{2}$. Then, the quadratic hull of
$\mathcal{C}_{L}({\mathscr{X}},{\mathcal{P}},{G})$ equals $\mathscr{X}$.

###### Proof.

The proof can be found in [MCMMP14, Thm. 2], we adapt it here to the current
notation and terminology. The condition $\deg G\geqslant 2g+2$ entails the
very ampleness of $G$ and, up to projective equivalence the corresponding
embedding
$\varphi_{G}:\mathscr{X}\rightarrow\mathbf{P}(L(G))\simeq\mathbf{P}^{k-1}$
sends precisely $\mathcal{P}$ onto $V(\mathcal{C})$. The curve
$\varphi_{G}(\mathscr{X})$ has embedding degree $\deg G$ in $\mathbf{P}^{k-1}$
and hence, any quadric hypersurface containing $V(\mathcal{C})$ contains the
whole $\mathscr{X}$. Indeed, if not, the quadric hypersurface would intersect
$\varphi_{G}(\mathscr{X})$ at $n>2\deg G$ points (by assumption on $\deg G$)
which would contradict Bézout’s Theorem. Therefore, the quadratic hull of
$\mathcal{C}$ contains $\varphi_{G}(\mathscr{X})$. Next, using Saint Donat’s
result [SD72], such an embedding of $\mathscr{X}$ is an intersection of
quadrics, which concludes the proof. ∎

Now the question is, what if $\mathcal{C}$ is not supposed to arise from a
curve but $\mathcal{C}\star\mathcal{C}$ is non degenerate and
$\dim\mathcal{C}\star\mathcal{C}\leqslant 2\dim\mathcal{C}-1+\gamma$ with
$\gamma\leqslant\dim\mathcal{C}-3$? Is it possible that this code is not
contained in an AG code from a curve of genus $g\leqslant\gamma$? The point is
that if $\dim\mathcal{C}\star\mathcal{C}$ is small, then $\dim
I_{2}(V(\mathcal{C}))$ is large and one could reasonably expect the quadratic
hull to have a small dimension. Actually, one can prove the following
statement.

######  Theorem 11.

Let $\mathcal{C}\subseteq\mathbf{F}_{q}^{n}$ such that
$\mathcal{C}\star\mathcal{C}$ is non degenerate and
$\dim\mathcal{C}\star\mathcal{C}\leqslant 3\dim\mathcal{C}-4$. Assume moreover
that the quadratic hull $\mathscr{H}_{2}(\mathcal{C})$ of $\mathcal{C}$ is a
reduced absolutely irreducible variety. Then, $\mathscr{H}_{2}(\mathcal{C})$
is a curve.

######  Remark 12.

The above statement is mentioned in [Ran21, § 2.11] where the proof is
sketched.

To prove of Theorem 11 we need the following Lemma.

######  Lemma 13.

Under the hypotheses of Theorem 11, let $I_{2}(\mathscr{H}_{2}(\mathcal{C}))$
be the subspace of $H^{0}(\mathbf{P}^{k-1},\mathcal{O}(2))$ of quadratic forms
vanishing on $\mathscr{H}_{2}(\mathcal{C})$. Then,

$I_{2}(\mathscr{H}_{2}(\mathcal{C}))=I_{2}(V(\mathcal{C})).$

###### Proof.

Using the hypothesis that $\mathscr{H}_{2}(\mathcal{C})$ is reduced, the
result is a direct consequence of Hilbert Nullstellensatz. ∎

###### Proof of Theorem 11.

Assuming that the quadratic hull is reduced and irreducible, one can define
its field of functions $K$. After fixing an arbitrary choice of coordinates in
$\mathbf{P}^{k-1}$, one can regard $H^{0}(\mathbf{P}^{k-1},\mathcal{O}(1))$ as
a space of rational fractions and there is a canonical restriction map

$H^{0}(\mathbf{P}^{k-1},\mathcal{O}(1))\longrightarrow K$

whose image is denoted by $C$. Since $\mathcal{C}$ has dimension $k$, the
$k\times n$ generator matrix $G$ has full rank and hence its columns span
$\mathbf{F}_{q}^{k}$. Consequently, $V(\mathcal{C})$ spans $\mathbf{P}^{k-1}$
or equivalently is not contained in any hyperplane. Thus, so does
$\mathscr{H}_{2}(\mathcal{C})$ and hence, the above restriction map is an
isomorphim: $C$ has dimension $k$ and is isomorphic to $\mathcal{C}$.
Moreover, since $C$ contains the restrictions to
$\mathscr{H}_{2}(\mathcal{C})$ of a coordinate system of $\mathbf{P}^{k-1}$,
it generates the field $K$ as an $\mathbf{F}_{q}$–algebra.

Consider the space

$C\cdot C\stackrel{{\scriptstyle\text{def}}}{{=}}\text{Span}\left\\{uv\in
K\leavevmode\nobreak\ |\leavevmode\nobreak\ u,v\in C\right\\}.$

We have a canonical surjective map from the symmetric square $S^{2}C$ into
$C\cdot C$. Since $C$ is isomorphic to
$H^{0}(\mathbf{P}^{k-1},\mathcal{O}(1))$, its symmetric square is isomorphic
to $H^{0}(\mathbf{P}^{k-1},\mathcal{O}(2))$. In short, $C\cdot C$ is the space
of quadratic forms on $\mathbf{P}^{k-1}$ restricted to
$\mathscr{H}_{2}(\mathcal{C})$. Hence, the kernel of the canonical surjective
map $S^{2}C\rightarrow C\cdot C$ is nothing but the space
$I_{2}(\mathscr{H}_{2}(\mathcal{C}))$ of quadratic forms vanishing on
$\mathscr{H}_{2}(\mathcal{C})$. By Lemma 13, we deduce that the latter kernel
$I_{2}(\mathscr{H}_{2}(\mathcal{C}))$ is nothing but $I_{2}(V(\mathcal{C}))$.
In summary, we have the following diagram

$0$$I_{2}(V(\mathcal{C}))$$S^{2}C$$C\cdot
C$$0$$0$$I_{2}(V(\mathcal{C}))$$H^{0}(\mathbf{P}^{k-1},\mathcal{O}(2))$$\mathcal{C}\star\mathcal{C}$$0$$\sim$

Consequently, $C\cdot C$ is isomorphic to $\mathcal{C}\star\mathcal{C}$. We
already mentioned that $C$ generates $K$ as an $\mathbf{F}_{q}$–algebra and
just proved that $\dim C\cdot C\leqslant 3\dim C-4$. Then, from [BCZ18, Thm.
4.2], the transcendence degree of $K$ over $\mathbf{F}_{q}$ cannot lie in the
range $\\{2,\dots,k-1\\}$ and hence should be $1$. This proves that
$\mathscr{H}_{2}(\mathcal{C})$ is a curve. ∎

As a conclusion, we could get partial answers on the original problem if we
were able to get criteria on the code for its quadratic hull to be a reduced
irreducible variety.

######  Question 2.

Given a code $\mathcal{C}\subseteq\mathbf{F}_{q}^{n}$ such that
$\mathcal{C}\star\mathcal{C}$ is non degenerate and
$\dim\mathcal{C}\star\mathcal{C}\leqslant 3\dim\mathcal{C}-4$, under which
conditions the quadratic hull of $\mathcal{C}$ is reduced and irreducible?

Note that some conditions should hold for the hull to be irreducible as
suggests the example below.

######  Example 14.

This example appears in [Ran21, § 7.9]. Let
$\mathscr{Y}\subseteq\mathbf{P}^{3}$ be the union of a plane and a line not
contained in it. Let $\mathcal{P}$ be the set of rational points of
$\mathscr{Y}$ and consider the code $\mathcal{C}$ obtained as the set of
evaluations of linear forms, i.e. the elements of
$H^{0}(\mathbf{P}^{3},\mathcal{O}(1))$ at the elements of $\mathcal{P}$. For
$q$ large enough, it is simple to observe that any quadric containing
$\mathcal{P}$ contains $\mathscr{Y}$. Hence, the quadratic hull of the code
equals $\mathscr{Y}$. Moreover, the dimension of the space of quadratic forms
vanishing on $\mathscr{Y}$ is $2$ which entails that
$\dim\mathcal{C}\star\mathcal{C}=\dim
H^{0}(\mathbf{P}^{3},\mathcal{O}(2))-2=8=2\dim\mathcal{C}$. On the other hand,
for $q$ large enough, one can prove that $\mathcal{P}$ cannot be contained in
a curve of genus $\leqslant 1$ since $|\mathcal{P}|=q^{2}+2q+1$ while Weil’s
bound asserts that curves of genus $\leqslant 1$ have at most $q+1+2\sqrt{q}$
rational points.

##  7 A concluding remark

The present note dealt with codes from curves while one could also consider
codes from higher dimensional varieties. The latter topic, without being as
investigated in the literature as codes from curves remains of deep interest:
we refer the reader to the survey [Lit08]. However, our focus was on the
behaviour of codes with respect to the component wise product and codes from
curves are very particular from this point of view. It can be related to the
fact that Hilbert polynomials of curves are linear while they are quadratic
for surfaces. Using this point of view, it seems that one cannot expect to
decode codes from higher dimensional varieties as efficiently as codes from
curves. Similarly, higher dimensional varieties are probably much less
interesting for secret sharing applications. On the other hand, codes from
higher dimensional varieties may remain of deep interest for other
applications such as cloud storage and the design of locally recoverable
codes.

## Acknowledgement

The author expresses his deep gratitude to Hugues Randriambololona for his
very valuable comments.

## References

  * [ACGH85] Enrico Arbarello, Maurizio Cornalba, Phillip Griffiths, and Joseph Daniel Harris.  Geometry of algebraic curves I, volume 267.  Springer-Verlag, First edition, 1985.
  * [ALM+98] Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy.  Proof verification and the hardness of approximation problems.  J. ACM, 45(3):501–555, May 1998.
  * [BCZ18] Christine Bachoc, Alain Couvreur, and Gilles Zémor.  Towards a function field version of Freiman’s theorem.  Algebraic Combin., 1(4):501–521, 2018.
  * [B22] Peter Beelen.  A survey on recursive towers and Ihara’s constant.  ArXiv:2203.03310, 2022.
  * [BH08] Peter Beelen and Tom Høholdt.  The decoding of algebraic geometry codes.  In Advances in algebraic geometry codes, volume 5 of Ser. Coding Theory Cryptol., pages 49–98. World Sci. Publ., Hackensack, NJ, 2008\.
  * [Ber68] Elwyn R. Berlekamp.  Algebraic coding theory.  McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1968.
  * [Ber15] Elwyn R. Berlekamp.  Algebraic coding theory.  World Scientific Publishing Co. Pte. Ltd., Hackensack, NJ, revised edition, 2015.
  * [BMvT78] Elwyn Berlekamp, Robert McEliece, and Henk van Tilborg.  On the inherent intractability of certain coding problems.  IEEE Trans. Inform. Theory, 24(3):384–386, May 1978.
  * [BTV17] Alexander Barg, Itzhak Tamo, and Sergei G. Vlăaduţ.  Locally recoverable codes on algebraic curves.  IEEE Trans. Inform. Theory, 63(8):4928–4939, 2017.
  * [CCMZ15] Ignacio Cascudo, Ronald Cramer, Diego Mirandola, and Gilles Zémor.  Squares of random linear codes.  IEEE Trans. Inform. Theory, 61(3):1159–1173, 2015.
  * [CDM00] Ronald Cramer, Ivan Damgård, and Ueli Maurer.  General secure multi-party computation from any linear secret-sharing scheme.  In Bart Preneel, editor, Advances in Cryptology — EUROCRYPT 2000, volume 1807 of Lecture Notes in Computer Science, pages 316–334. Springer-Verlag Berlin Heidelberg, 2000.
  * [CDN15] Ronald Cramer, Ivan Damgård, and Jesper Nielsen.  Secure multiparty computation and secret sharing.  Cambridge University Press, Cambridge, 2015.
  * [CMCP17] Alain Couvreur, Irene Márquez-Corbella, and Ruud Pellikaan.  Cryptanalysis of McEliece cryptosystem based on algebraic geometry codes and their subcodes.  IEEE Trans. Inform. Theory, 63(8):5404–5418, Aug 2017.
  * [CP20] Alain Couvreur and Isabella Panaccione.  Power error locating pairs.  Des. Codes Cryptogr., 88:1561–1593, 2020.
  * [CR21] Alain Couvreur and Hugues Randriambololona.  Algebraic geometry codes and some applications.  In W. Cary Huffman, Jon-Lark Kim, and Patrick Solé, editors, Concise Encyclopedia of Coding Theory. Chapman and Hall/CRC, 2021.
  * [Ehr93] Dirk Ehrhard.  Achieving the designed error capacity in decoding algebraic–geometric codes.  IEEE Trans. Inform. Theory, 39(3):743–751, 1993.
  * [FR93] Gui-Liang Feng and T. R. N. Rao.  Decoding algebraic-geometric codes up to the designed minimum distance.  IEEE Trans. Inform. Theory, 39(1):37–45, Jan 1993.
  * [Gop81] Valerii D. Goppa.  Codes on algebraic curves.  Dokl. Akad. Nauk SSSR, 259(6):1289–1290, 1981.  In Russian.
  * [GS95] Arnaldo Garcia and Henning Stichtenoth.  A tower of Artin-Schreier extensions of function fields attaining the Drinfeld-Vladut bound.  Invent. Math., 121:211–222, 1995.
  * [GS99] Venkatesan Guruswami and Madhu Sudan.  Improved decoding of Reed–Solomon and Algebraic–Geometry codes.  IEEE Trans. Inform. Theory, 45(6):1757–1767, 1999.
  * [Ham50] Richard W. Hamming.  Error detecting and error correcting codes.  Bell System Technical Journal, 29:147–160, 1950.
  * [HLX02] X. Hou, K. H. Leung, and Q. Xiang.  A generalization of an addition theorem of Kneser.  J. Number Theory, 97:1–9, 2002.
  * [HP95] Tom Høholdt and Ruud Pellikaan.  On the decoding of algebraic–geometric codes.  IEEE Trans. Inform. Theory, 41(6):1589–1614, Nov 1995.
  * [Iha81] Yasutaka Ihara.  Some remarks on the number of rational points of algebraic curves over finite fields.  J. Fac. Sci. Univ. Tokyo Sect. IA Math., 28:721–724, 1981.
  * [JLJ+89] Jørn Justesen, Knud J. Larsen, Helge E. Jensen, Allan Havemose, and Tom Høholdt.  Construction and decoding of a class of algebraic geometry codes.  IEEE Trans. Inform. Theory, 35(4):811–821, July 1989.
  * [JM96] Heeralal Janwa and Oscar Moreno.  McEliece public key cryptosystems using algebraic-geometric codes.  Des. Codes Cryptogr., 8(3):293–307, 1996.
  * [Köt92] Ralf Kötter.  A unified description of an error locating procedure for linear codes.  In Proceedings Algebraic and Combinatorial Coding Theory III, pages 113–117. Hermes, 1992.
  * [Lit08] John B. Little.  Algebraic geometry codes from higher dimensional varieties.  In Advances in algebraic geometry codes, volume 5 of Ser. Coding Theory Cryptol., pages 257–293. World Sci. Publ., Hackensack, NJ, 2008\.
  * [McE78] Robert J. McEliece.  A Public-Key System Based on Algebraic Coding Theory, pages 114–116.  Jet Propulsion Lab, 1978.  DSN Progress Report 44.
  * [MCMMP14] Irene Márquez-Corbella, Edgar Martínez-Moro, and Ruud Pellikaan.  On the unique representation of very strong algebraic geometry codes.  Des. Codes Cryptogr., 70(1-2):215–230, 2014.
  * [Mum70] D. Mumford.  Varieties defined by quadratic equations.  In Questions on algebraic varieties, C.I.M.E., III Ciclo, Varenna, 1969, pages 29–100. Edizioni Cremonese, Rome, 1970.
  * [MZ15] Diego Mirandola and Gilles Zémor.  Critical pairs for the product Singleton bound.  IEEE Trans. Inform. Theory, 61(9):4928–4937, 2015.
  * [Nie86] Harald Niederreiter.  Knapsack-type cryptosystems and algebraic coding theory.  Problems of Control and Information Theory, 15(2):159–166, 1986\.
  * [Pel92] Ruud Pellikaan.  On decoding by error location and dependent sets of error positions.  Discrete Math., 106–107:369–381, 1992.
  * [PRS21] Sven Puchinger, Johan Rosenkilde, and Grigory Solomatov.  Improved power decoding of algebraic geometry codes.  In 2021 IEEE International Symposium on Information Theory (ISIT), pages 509–514, 2021.
  * [Ran14] Hugues Randriambololona.  On products and powers of linear codes under componentwise multiplication.  In Stéphane Ballet, Marc Perret, and Alexey Zaytsev, editors, Algorithmic Arithmetic, Geometry, and Coding Theory, volume 637 of Contemp. Math., pages 3–77. American Mathematical Society, 2014.
  * [Ran21] Hugues Randriambololona.  The quadratic hull of a code and the geometric view on multiplication algorithms.  In Stéphane Ballet, Gaetan Bisson, and Irene Bouw, editors, Arithmetic, Geometry, Cryptography and Coding Theory, Contemp. Math., pages 267–296. American Mathematical Society, 2021.
  * [Ree54] Irving S. Reed.  A class of multiple-error-correcting codes and the decoding scheme.  Transactions of the IRE Professional Group on Information Theory, 4(4):38–49, 1954.
  * [Ros18] Johan Rosenkilde.  Power decoding Reed–Solomon codes up to the Johnson radius.  Adv. Math. Commun., 12(1):81–106, 2018.
  * [RS60] Irving S. Reed and Gustave Solomon.  Polynomial codes over certain finite fields.  Journal of the Society for Industrial and Applied Mathematics, 8(2):300–304, 1960.
  * [SD72] Bernard Saint-Donat.  Sur les équations définissant une courbe algébrique.  C. R. Acad. Sc. Paris, 274:324–327, 487–489, 1972.
  * [Sha48] Claude E. Shannon.  A mathematical theory of communication.  Bell System Technical Journal, 27:379–423, 623–656, 1948.
  * [Sha79] Adi Shamir.  How to share a secret.  Commun. ACM, 22(11):612–613, November 1979.
  * [Sud97] Madhu Sudan.  Decoding of Reed–Solomon Codes beyond the Error-Correction Bound.  J. Complexity, 13(1):180–193, 1997.
  * [SV90] Aleksei N. Skorobogatov and Sergei G. Vlăduţ.  On the decoding of algebraic-geometric codes.  IEEE Trans. Inform. Theory, 36(5):1051–1060, Sep. 1990.
  * [TB14] Itzhak Tamo and Alexander Barg.  A family of optimal locally recoverable codes.  IEEE Trans. Inform. Theory, 60(8):4661–4676, 2014.
  * [TV06] T. Tao and V. H. Vu.  Additive combinatorics, volume 105 of Cambridge studies in advanced mathematics.  Cambridge University Press, 2006.
  * [TVZ82] Michael A. Tsfasman, Serge G. Vlăduţ, and Th. Zink.  Modular curves, Shimura curves, and Goppa codes, better than Varshamov-Gilbert bound.  Math. Nachr., 109:21–28, 1982.
  * [VD83] Sergei G. Vlăduţ and Vladimir G. Drinfeld.  Number of points of an algebraic curve.  Funct. Anal. Appl., 17:53–54, 1983.
  * [WB83] Lloyd R. Welch and Elwyn R. Berlekamp.  Error correction for algebraic block codes, 1983.  US patent number 4,633,470.