On the security of Some Compact Keys for McEliece Scheme
Élise Barelli∗

arXiv:1803.05289v1 [cs.IT] 14 Mar 2018

INRIA Saclay and LIX, CNRS UMR 7161 École Polytechnique,
91120 Palaiseau Cedex
email: elise.barelli@inria.fr
March 15, 2018

Abstract
In this paper we study the security of the key of compact McEliece schemes based
on alternant/Goppa codes with a non-trivial permutation group, in particular quasi-cyclic
alternant codes. We show that it is possible to reduce the key-recovery problem on the
original quasi-cyclic code to the same problem on a smaller code derived from the public
key. This result is obtained thanks to the invariant code operation which gives the subcode
whose elements are fixed by a permutation σ ∈ Perm(C). The fundamental advantage is that
the invariant subcode of an alternant code is an alternant code. This approach improves
the technique of Faugère, Otmani, Tillich, Perret and Portzamparc which uses folded codes
of alternant codes obtained by using supports globally stable by an affine map. We use
a simpler approach with a unified view on quasi-cyclic alternant codes and we treat the
case of automorphisms arising from a non affine homography. In addition, we provide an
efficient algorithm to recover the full structure of the alternant code from the structure of
the invariant code.

1

Introduction

In 1978, McEliece [16] introduced a public key encryption scheme based on linear codes and
suggested to use classical Goppa codes which belong to the family of alternant codes. This
proposition still remains secure but leads to very large public keys compared to other publickey cryptosystems. That is why, in despite of its fast encryption and decryption, McEliece
scheme is limited for practical applications. To overcome this limitation, lot of activity devote
to decrease the key size by choosing codes which admit a very compact public matrix. For
instance, quasi-cyclic (QC) codes enable to build public key encryption schemes with short keys
[11, 3]. These first papers were followed by proposals using alternant and Goppa codes with
different automorphism groups like quasi-dyadic (QD) Goppa codes [17].
The cryptanalisis of code-based schemes can be split in two categories: the message recovery
attacks and the key-recovery attacks. The first kind of attacks consists in generic methods for
decoding a random linear code. These methods are known as Information Set Decoding (ISD)
methods. The second kind of attacks consists in recovering the secret elements of the code
used in the scheme. In this case, the methods are specific to the code family. Recently, in
the category of key-recovery attacks, new methods appeared, known as algebraic attacks. This
method consists in recovering the secret element of an alternant code by solving a system of
∗

A short version of this paper was presented at Workshop on Coding and Cryptography (WCC) 2017.

1

polynomial equations. In [9], the authors improved this new method to attack QC and QD
alternant codes. Such attacks use the specific structure of QC/QD codes in order to build an
algebraic system with much fewer unknowns compared to the generic case. A new approach has
been used in [8, 7] to explain that the reduction of the number of unknowns in the algebraic
system comes from a smaller code easily computable from the public generator matrix. This
smaller code can be obtained by summing up the codewords which belong to the same orbit
under the action of the permutation group and is referred to as the folded code. (We advertise
the reader that the folded codes referenced in [13] are not the same codes as in this paper.) A
relation between the support and multiplier defining the alternant code and those of the folded
code exists and is sufficient to find the original alternant code. This relation comes from the
structure of the folded code: [7] shows that the folding operation preserves the structure of the
dual code. That is, the folding of the dual of an alternant code (resp. a Goppa code) is the dual
of an alternant code (resp. a Goppa code).
In [7], the authors attack only codes with an automorphism induced by an affine transformation acting on the support and the multiplier, we call them affine induced automorphims.
Another kind of quasi-cyclic alternant codes can be built from the action of the projective linear
group on the support and multiplier. We use in this paper another alternant code built from the
public generator matrix of a quasi-cyclic alternant code induced by a projective linear transformation, called the invariant code and introduced by Loidreau in [14]. This invariant code can
be built easily from the public generator matrix of the alternant code C since it is the kernel
of the linear map: c ∈ C 7→ c − σ(c), where σ is a permutation of C. We remark also that the
folded code used by [7] is included in the invariant code with equality when the characteristic of
the field not divide the order of the permutation.
Our main contribution is to consider more general tools coming from algebraic geometry
and use the invariant code instead of folded code. This approach has two advantages. First the
geometric point of view simplifies the attack by giving a unified view of quasi-cyclic alternant
codes. It also simplifies some proofs and enables to consider alternant codes as algebraic geometric codes on the projective line. This method allows us to treat the general case of projective
linear transformations. The second advantage is that the invariant code operation is applied
directly on the alternant code and not on the dual code. More precisely, we prove the following
results.
Theorem 3.5. Let GRSk (x, y) ⊂ Fnqm be a quasi-cyclic GRS code, and σ ∈ Sn of order ℓ, such that ℓ|n, the permutation acting on the code GRSk (x, y). Then the invariant code
GRSk (x, y)σ is a GRS code of length n/ℓ and dimension ⌊k/ℓ⌋.
Corollary 3.6. Let Ar (x, y) ∩ Fnq be a quasi-cyclic alternant code, and σ ∈ Sn of order ℓ,
such that ℓ|n, the permutation acting on the code Ar (x, y) . Then the invariant code Ar (x, y)σ
is an alternant code of length n/ℓ and order r/ℓ.
In the last section we show that this means that the key security of compact McEliece
scheme based on alternant codes with some induced permutation reduces to the key
security of the invariant code, which has smaller parameters. We provide an algorithm to
recover the secret elements of the alternant code from the knowledge of the its invariant code.
This algorithm uses only linear algebra.
However we can notice that key-recovery is generally more expensive than message recovery.
With a good choice of parameters it is still possible to construct quasi-cyclic codes with high
complexity of key recovery attack on the invariant code.

2

2

Quasi-cyclic Alternant Codes

In this section, we introduce some notation about alternant codes. We denote by Fq the finite
field with q elements, where q is a power of a prime p.
Let x = (x1 , . . . , xn ) be an n-tuple of distinct elements of Fq , and y = (y1 , . . . , yn ) be an
n-tuple of nonzero elements of Fq . The generalized Reed-Solomon (GRS) code of dimension k,
denoted GRSk (x, y), consists of vectors (y1 f (x1 ), . . . , yn f (xn )) where f ranges over all polynomials of degree < k, with coefficients in Fq . The vector x is called the support and y a multiplier
of the code GRSk (x, y). In order to define alternant codes, we use the following property whose
proof can be found in [15, Chap. 12].
Proposition 2.1. The dual of GRSk (x, y) is GRSn−k (x, y ⊥ ) for some y ⊥ ∈ (Fq \ {0})n .
Definition 1. Let m be a positive integer, x be an n-tuple of distinct elements of Fqm and y
be an n-tuple of nonzero elements of Fqm . The alternant code Ak (x, y) over Fq is the subfield
subcode of GRSk (x, y)⊥ , i.e. Ak (x, y) := GRSk (x, y)⊥ ∩ Fnq .

2.1

Representation of Ak (x, y) as a subfield subcode of an AG code

For the rest of our work, it is convenient to use a projective representation of alternant codes.
This is possible thanks to algebraic geometric codes introduced by Goppa in [12]. To avoid the
confusion with classical Goppa codes which are specific alternant codes, we refer to algebraic
geometric codes as AG codes. Any GRS code is an AG code on P1 , the projective line over Fqm .
Recall some definitions in this case (cf [10, 19] for further details).
For brevity we denote by P1 the projective line over Fqm . We can consider Fqm (P1 ), the
function field over Fqm associated to the curve P1 . We recall that a closed point of P1 is an orbit
of a point, with coordinates in a finite extension of Fqm , under the Frobenius transformation:
m
m
(x : y) 7→ (xq : y q ). The degree of a closed point is the cardinality of the orbit. A rational
point is a closed point of degree 1, or equivalently a point whose coordinates are in Fqm . The set
of rational points is denoted P1 (Fqm ). A divisor of P1 is a formal sum, with integers coefficients,
of closed points of P1 and for f ∈ Fqm (P1 ), the principal divisor of f , denoted by (f ), is defined
as the formal sum of zeros and poles of f , counted with multiplicity. For a divisor G, we denote
by deg(G) the degree of G and by L(G) := {f ∈ Fqm (P1 ) | (f ) ≥ −G} ∪ {0}, the Riemann-Roch
space associated to G. Let P = {P1 , . . . , Pn } be a set of n distinct points of P1 with coordinates
in Fqm and G be a divisor such that deg(G) < n and G does not contain any point of P. We
consider the subspace V ⊂ Fqm (P1 ) of functions without poles in P and the following map:
EvP : V
f

−→ Fnqm
7−→ (f (P1 ), . . . , f (Pn )).

The AG code CL (P1 , P, G) is defined by CL (P1 , P, G) := {EvP (f ) | f ∈ L(G)}.
Let x = (x1 , . . . , xn ) be an n-tuple of distinct elements of Fqm , and y = (y1 , . . . , yn ) be
an n-tuple of nonzero elements of Fqm . Then GRSk (x, y) is the AG code CL (P1 , P, G) where
P := {(xi : 1)| i ∈ {1, . . . , n}} and G := (k − 1)P∞ − (f ), with f ∈ Fqm (P1 ) a function with pole
order n − 1 at P∞ , which is the interpolation polynomial of degree n − 1 of y1 , . . . , yn through
the points x1 , . . . , xn . With the same notation, we have Ak (x, y) := CL (P1 , P, G)⊥ ∩ Fnq .

2.2

Induced permutations of Alternant Codes

We explain how we can construct an alternant code invariant under a prescribed permutation of
the support {1, . . . , n}, with n the length of the code. In [6], Dür determines the automorphism
3

group of GRS codes and in [1, 2], Berger uses this to construct families of alternant codes
invariant under a permutation. In particular, Berger deals with some alternant codes invariant
under a permutation induced by the action of an element of the projective semi-linear group
PΓL2 (Fqm ) on the support and the multiplier. Here we will only be interested in projective linear
transformations. First of all, we recall the definition of the projective linear group PGL2 (Fqm ).
It is the automorphism group of the projective line P1 defined by:
(
(
)
a, b, c, d ∈ Fqm ,
P1
−→ P1
PGL2 (Fqm ) :=
.
(x : y) 7−→ (ax + by : cx + dy)
ad − bc 6= 0
The elements of PGL2 (Fqm ) have also a matrix representation, i.e.


a b
∀σ ∈ PGL2 (Fqm ), we write σ :=
, with ad − bc 6= 0.
c d

(1)

Where the elements a, b, c and d are defined up to a multiplication by a nonzero scalar. That is
to say:



α 0
∗
m
m
PGL2 (Fq ) ≃ GL2 (Fq )/
, α ∈ Fq m
0 α
Now, we deal with permutations of an alternant code. We recall the following definition.
Definition 2. Let C be a linear code of length n over Fqm . Let σ ∈ Sn be a permutation, acting
on C via σ(c1 , . . . , cn ) = (cσ(1) , . . . , cσ(n) ). Then the permutation group of a code C ⊂ Fnqm , is
P erm(C) := {σ ∈ Sn | σ(C) = C}.
In the case of GRS codes, for appropriate dimension, Dür [6] shows that the whole permutation group is induced by the action of the projective linear group on the support of the
code. The same property has been shown by Stichtenoth [18], with the representation of GRS
codes as AG rational codes. More precisely, for appropriate parameters, every permutation of
CL (P1 , P, G) is induced by a projective linear transformation. We give the main definitions and
theorems of [18].
We keep the notation of the previous section. Let G and G′ be divisors of P1 , we note
G ≈P G′ if there exists f ∈ Fqm (P1 ), f 6= 0, such that G − G′ = (f ) and f (P ) = 1, for all
P ∈ P. With this definition we have the following lemma:
Lemma 2.2 ([18]). If G ≈P G′ then CL (P1 , P, G) = CL (P1 , P, G′ ).
Before giving the theorem which allows us to construct any GRS code invariant under a
permutation, we define:
Definition 3. AutP,G (P1 ) := {σ ∈ Aut(P1 ) | σ(P) = P and σ(G) ≈P G}.
Theorem 2.3 ([18]). Let C = CL (P1 , P, G) be an AG code with 1 ≤ deg(G) ≤ n − 3. Then
Perm(C) = AutP,G (P1 ).
Now we have all the properties required to construct some alternant codes invariant under
a permutation. We consider σ ∈ PGL2 (Fqm ) and ℓ = ord(σ). We define the support:
P :=

n/ℓ
a

Orbσ (Pi ),

i=1

4

(2)

where the points Pi ∈ P1 (Fqm ) are pairwise distinct with trivial stabilizer subgroup and Orbσ (Pi ) :=
{σ j (Pi ) | j ∈ {1..ℓ}}. We define the divisor:
G :=

s
X

X

ti

i=1

(3)

Q,

Q∈Orbσ (Qi )

with Qi closed points of P1 , s ∈ N, ti ∈ Z for i ∈ {1, . . . , s} and deg(G) =

s
P

ti ℓ.

i=1

The automorphism σ of P1 induces a permutation σ̃ of C = CL (P1 , P, G) defined by:
σ̃ :

C
−→
C
(f (P1 ), . . . , f (Pn )) 7−→ (f (σ(P1 )), . . . , f (σ(Pn )))·

Then σ̃ is also a permutation of A := C ⊥ ∩ Fnq . For short, we denote by σ ∈ PGL2 (Fqm ) both
the homography and the induced permutation on the code C.

3

Subcodes of Alternant Codes

We can construct subcodes of Ar (x, y) with smaller parameters, by simple operations, which can
be used to recover the alternant code Ar (x, y). We describe in the next section two subcodes:
the folded code and the invariant code. Their interactions are also discussed. In the papers
[8, 7], the folding operation was used to recover dual of the considered alternant code. Here we
do not need to consider the dual code. More precisely, we show that for alternant codes with a
non trivial permutation group, the invariant code is an alternant code.

3.1

Invariant and Folded Codes

This section deals with subcodes called the invariant code and the folded code whose definitions
are the following.
Definition 4. Let C be a linear code and σ ∈ P erm(C) of order ℓ, we consider the following
map:
ψ: C → C
c 7→

ℓ−1
X

σ i (c).

i=0

The folded code of C is defined by Foldσ (C) := Im(ψ) = Im(Id + σ + · · · + σ ℓ−1 ). The invariant
code of C is defined by C σ := ker(σ − Id).
The folded code was used in [8, 7], in order to construct a structured subcode invariant by a
given permutation σ. Indeed, by the previous definition, we remark that Foldσ (C) is σ-invariant.
Proposition 3.1. The codes Foldσ (C) and C σ are subcodes of C and we have:
Foldσ (C) ⊆ C σ .
These two codes are not equal in the general case but we have the following lemma. We
recall that p is the characteristic of Fq and ℓ = ord(σ).
5

Lemma 3.2. If p ∤ ℓ then Foldσ (C) = C σ .
Proof. Let ψ be the map of Definition 4, by the previous proposition we know that:
Im(ψ) ⊆ ker(σ − Id).
Now, we will show that dim(Im(ψ)) = dim(ker(σ − Id)).
By the rank–nullity theorem we know that:
dim(Im(ψ)) = dim(C) − dim(ker(ψ)).
Moreover, σ ℓ − Id = (Id +σ + · · · + σ ℓ−1 )(σ − Id). Since p ∤ ℓ, we have:
ℓ−1
X
X i , X − 1) = 1.
gcd(
i=0

Hence, C = ker(ψ) ⊕ ker(σ − Id) and
dim(ker(σ − Id)) = dim(C) − dim(ker(ψ)).
Therefore ker(σ − Id) = Im(ψ) and F old(C) = C σ .
Remark 1. In [7, Example 1] an example of the folded and the invariant codes of a σ-invariant
alternant code A is given. In this example, the authors wrote that Foldσ (A) ( Aσ but in this
case these two codes must be equal. Indeed, for this example, p = 3 ∤ 2 = ord(σ) and by the
previous lemma we have Foldσ (A) = Aσ . Actually, the computation of the subfield subcode of
the folded code in [7, Example 1] contains a mistake.
Remark 2. If c ∈ Foldσ (C) or c ∈ C σ , then c takes constant value on the orbits under the action
of σ: {i, σ(i), . . . , σ ℓ−1 (i)}. In order to work with codes without repeated coordinates, we choose
I ⊂ {1, . . . , n} a set of representatives of orbits {σ j (i)|j ∈ {0, . . . , ℓ − 1}} and we consider the
codes punctured on this set: Foldσ (C)|I and C σ |I . For short, we keep the notations Foldσ (C)
and C σ , for the restricted codes.
Remark 3. The folding operation is Fq -linear so to apply this operation on a linear code C it
suffices to apply folding operation on a basis of C. This property will be useful in §3.2.3.

3.2

The Invariant Code of Ar (x, y)

In order to study the invariant code of Ar (x, y), we first notice that the invariant operation
commutes with the subfield subcode operation. Indeed, if C is a linear code over Fqm , σ-invariant
then:
(C ∩ Fnq )σ = {c ∈ C | c ∈ Fnq and σ(c) = c} = C σ ∩ Fnq .
In order to prove that the invariant code of Ar (x, y) is also an alternant code we have to prove
that the invariant code of a GRS code is a GRS code. Later on, the GRS codes will be described
by CL (P1 , P, G), as in Section 2.2. The two lemmata to follow describe the action of an element
σ ∈ PGL2 on the codes CL (P1 , P, G) and provide a description of CL (P1 , P, G)σ .
Lemma 3.3. Let c = EvP (f ) ∈ CL (P1 , P, G)σ such that σ(c) = c, then f is σ-invariant, i.e.
f ◦ σ = f.

6

Proof. Let c = (f (P1 ), . . . , f (Pn )) ∈ C such that σ(c) = c, then:
∀i ∈ {1, . . . , n}, f (Pσ(i) ) = f (Pi ) ⇔ ∀i ∈ {1, . . . , n}, f ◦ σ(Pi ) = f (Pi )
⇔ ∀i ∈ {1, . . . , n}, (f ◦ σ − f )(Pi ) = 0.
Since σ(G) = G, f ◦ σ ∈ L(G), and then (f ◦ σ − f ) ∈ L(G). Hence if (f ◦ σ − f ) was nonzero, it
should have at most deg(G) < n zeros on P1 , which is a contradiction. Therefore (f ◦ σ − f ) ≡ 0
and f is σ-invariant.
Lemma 3.4. Let C := CL (P1 , P, G) be an AG code such that σ(C) = C and ρ ∈ PGL2 (Fqm ).
Then σ ′ := ρ ◦ σ ◦ ρ−1 induces the same permutation on C as σ.
Proof. We first prove that:
CL (P1 , ρ−1 (P), ρ−1 (G)) = CL (P1 , P, G).
Let c = (f (P1 ), . . . , f (Pn )) be a codeword of CL (P1 , P, G). Then, we have c = (f ◦ ρ ◦
ρ−1 (P1 ), . . . , f ◦ ρ ◦ ρ−1 (Pn )). As f ∈ L(G), the function h = f ◦ ρ ∈ L(ρ−1 (G)). Hence,
c ∈ {Evρ−1 (P) (h) | h ∈ L(ρ−1 (G))} = CL (P1 , ρ−1 (P), ρ−1 (G)).
Now, for all c = (f (P1 ), . . . , f (Pn )) ∈ C, we have:
σ ′ (c) = (f ◦ ρ ◦ σ ◦ ρ−1 (P1 ), . . . , f ◦ ρ ◦ σ ◦ ρ−1 (Pn ))
= (h ◦ σ(ρ−1 (P1 )), . . . , h ◦ σ(ρ−1 (Pn )))
with h = f ◦ ρ ∈ L(ρ−1 (G)). Since CL (P1 , ρ−1 (P), ρ−1 (G)) = CL (P1 , P, G), σ ′ induces the same
permutation of the code C as σ.
Theorem 3.5. Let CL (P1 , P, G) ⊆ Fnqm be an AG code of length n and dimension k, and
σ ∈ PGL2 (Fqm ) of order ℓ acting on it, with ℓ|n. Let P and G as in (2) and (3). Then the
invariant code CL (P1 , P, G)σ is an AG code of length n/ℓ and dimension ⌊k/ℓ⌋.
Corollary 3.6. Let A(P1 , P, G) := CL (P1 , P, G) ∩ Fnq be an alternant AG code of length n and
order r, and σ ∈ PGL2 (Fqm ) of order ℓ acting on it, with ℓ|n. Let P and G as in (2) and (3).
Then the invariant code A(P1 , P, G)σ is an alternant AG code of length n/ℓ and order ⌊r/ℓ⌋.
In order to prove Theorem 3.5, we consider σ ∈ PGL2 (Fqm ) with ℓ = ord(σ) and we define
the support P and the divisor G as in (2) and (3). Later on, to simplify the proofs we assume
that G is constructed from single rational point Q, but the result remains true in the general
case.
We denote:
σ j (Pi ) := (αiℓ+j : βiℓ+j ), for i ∈ {0, . . . , nℓ − 1}, j ∈ {0, . . . , ℓ − 1}
σ j (Q) := (γj : δj ), for j ∈ {0, . . . , ℓ − 1}.
Lemma 3.7. With the previous notation, we have:
(
)
F (X, Y )
L(G) = ℓ−1
F ∈ Fqm [X, Y ] homogeneous polynomial of degree tℓ.
Q
t
(δj X − γj Y )

(4)

j=0

To the automorphism σ ∈ PGL2 (Fqm ), we associate a matrix M :=
cases are possibles, depending on the eigenvalues of the matrix M :
7




a b
as in (1). Three
c d




a 0
1. M ∼
, with a ∈ Fqm (case diagonalizable in Fqm ),
0 1


1 b
2. M ∼
, with b ∈ Fqm (case trigonalizable in Fqm ),
0 1


α 0
3. M ∼
, with α ∈ Fq2m (case diagonalizable in Fq2m ),
0 αq
where M ∼ N , with M, N ∈ PGL2 (Fqm ), means there exist P ∈ PGL2 (Fqm ) such that M =
P N P −1 . In the following, we study these three cases.
3.2.1

Case σ diagonalizable over Fqm

We suppose σ = ρ ◦ σd ◦ ρ−1 with σd diagonal and ρ ∈ PGL2 (Fqm ) an automorphism of P1Fqm .
W.l.o.g and by Lemma 3.4, one can assume that:
σ:

P1
→
P1
(x : y) 7→ (ax : y),

(5)

with a ∈ F∗qm .
Proposition 3.8. Let F ∈ Fq [X, Y ] be a homogeneous polynomial of degree tℓ, and a ∈ Fqm of
order ℓ. If F (aX, Y ) = F (X, Y ), then F (X, Y ) = R(X ℓ , Y ℓ ), with R ∈ Fqm [X, Y ] a homogeneous polynomial of degree t.
A proof is given in [7, Prop 4]. Here, we present a simpler proof of Proposition 3.8.
Proof. The homogeneous polynomial F can be written as:
X
F (X, Y ) =
fij X i Y j ,
i+j=tℓ

with fij ∈ Fqm . Since F (aX, Y ) = F (X, Y ), we have:
X
X
fij X i Y j =
fij ai X i Y j ·
i+j=tℓ

i+j=tℓ

Hence fij = ai fij , ∀i, j ∈ N such that i + j = tℓ. As the order of a is ℓ, we have ai 6= 1, ∀i ∈ N
such that ℓ ∤ i. Therefore fij = 0, ∀i ∈ N such that ℓ ∤ i. So F (X, Y ) = R(X ℓ , Y ℓ ), with
R ∈ Fqm [X, Y ] an homogeneous polynomial of degree t.
Proposition 3.9. Let C := CL (P1 , P, G) be an AG code as in Theorem 3.5, with σ as in (5).
ℓ(ℓ−1)

Let P̃i = (αℓi : βiℓ ) and G̃ = tQ̃, where either Q̃ = ((−1)ℓ−1 a 2 ( γδ00 )ℓ : 1) or Q̃ = P∞ . Then
C σ = CL (P1 , P̃, G̃), which is a GRS code.

Proof. Let c = f (P1 ), f (σ(P1 )), . . . , f (σ ℓ−1 (P nℓ )) ∈ C such that σ(c) = c, by Lemma 3.3,
f ∈ L(G) is σ-invariant, so f (aX, Y ) = f (X, Y ). By Lemma 3.7, we have:
F (aX, Y )
ℓ−1
Q

j=0

!t =

(aδj X − γj Y )

8

F (X, Y )
ℓ−1
Q

j=0

!t

(δj X − γj Y )

(6)

with F ∈ Fqm [X, Y ] a homogeneous polynomial of degree tℓ. Moreover the support of G is
σ-invariant, so:
ℓ−1
Y

(aδj X − γj Y ) =

ℓ−1
Y

(aδj X − aγj Y ) = aℓ

(δj X − γj Y ) =

ℓ−1
Y

(δj X − γj Y )·

j=0

j=0

j=0

j=0

ℓ−1
Y

Hence, (6) becomes F (aX, Y ) = F (X, Y ), because ℓ = ord(a). By Proposition 3.8:
F (X, Y ) = R(X ℓ , Y ℓ ),
with R ∈ Fqm [X, Y ] an homogeneous polynomial of degree t.
ℓ−1
Q
The product
(δj X − γj Y ) is also σ-invariant and, by Proposition 3.8, we have:
j=0

ℓ−1
Y

ℓ−1
Y

(δj X − γj Y ) =

j=0

j=0

Therefore:
f (X, Y ) = 
ℓ−1
Q

ℓ−1
Y 

δj X ℓ + (−1)ℓ
γj Y ℓ ·
j=0

R(X ℓ , Y ℓ )


δj X ℓ − (−1)ℓ−1

j=0

j=0

Forall i ∈ {1, . . . , nℓ }, we have f (Pi ) = f˜(P̃i ), with:
f˜(X, Y ) = 
ℓ−1
Q

j=0

ℓ−1
Q

and P̃i := (αℓi : βiℓ ). We denote δ̃ =
(

R(X, Y )


γ̃X − δ̃Y

t

j=0

ℓ−1
Q

R(X, Y )


δj X − (−1)ℓ−1

ℓ−1
Q

j=0



γj Y ℓ

(7)

t ·

·
 t
γj Y

ℓ−1

Q 
δj and γ̃ = (−1)ℓ−1
γj . By Lemma 3.7, we have:
j=0

)

R ∈ Fqm [X, Y ] homogeneous polynomial of degree t.

∪ {0} = L(G̃),

with G̃ = t(γ̃ : δ̃) = tQ̃.Hence the codeword c ∈ CL (P1 , P̃, G̃).
If Q̃ 6= P∞ , then ∀j, δj 6= 0 and we can write:
Q̃ = (−1)ℓ−1

ℓ−1
Y

j=0


γj
:1 .
δj

Moreover we have:
ℓ−1
Y

j=0

ℓ−1
ℓ−1
Y γ0
Y  γ0
ℓ(ℓ−1) γ0
γj
aj
aj ( )ℓ = a 2 ( )ℓ .
=
=
δj
δ0
δ0
δ0
j=0

j=0

Reciprocally, for c ∈ CL (P1 , P̃, G̃) it is easy to see that we have c = (f (P1 ), . . . , f (σ ℓ−1 (P nℓ )),
with f as in (7). Then c ∈ C σ .

9

3.2.2

Case σ trigonalizable over Fqm

Here we consider the case where σ is trigonalizable in Fqm . As in the previous section we only
have to treat the case where σ is upper triangular. So w.l.o.g one can assume that:
P1
→
P1
(x : y) 7→ (x + by : y)

σ:

(8)

with b ∈ F∗qm . In this case, we have ℓ = ord(σ) = p.
Proposition 3.10 ([7, Prop 4]). Let F ∈ Fq [z] be a polynomial of degree deg(F ) ≤ tp and
b ∈ F∗q . If F (z + b) = F (z), then F (z) = R(z p − bp−1 z), with R ∈ Fq [z] a polynomial of degree
deg(R) ≤ t.
Proposition 3.11. Let C := CL (P1 , P, G) be a σ-invariant AG code as in Theorem 3.5, with σ
as in (8). Let P̃i = (αpi − bp−1 αi βip−1 : βip ) and G̃ = t(Q̃), where either Q̃ = (( γδ00 )p − bp−1 γδ00 : 1)
or Q̃ = P∞ . Then C σ = CL (P1 , P̃, G̃), which is a GRS code.

Proof. Let c = f (P1 ), f (σ(P1 )), . . . , f (σ ℓ−1 (P nℓ )) ∈ C such that σ(c) = c. By Lemma 3.3, f is
σ-invariant so: f (X + bY, Y ) = f (X, Y ). By Lemma 3.7, we have:
F (X + bY, Y )

 p−1
Q

δj (X + bY ) − γj Y

j=0

t

=

F (X, Y )

 p−1
Q

δj X − γj Y

j=0

t

,

(9)

with F ∈ Fq [X, Y ] an homogeneous polynomial of degree tp. Moreover the support of G is
σ-invariant, so:
p−1
Y

(δj (X + bY ) − γj Y ) =

p−1
Y

(δj X − (γj − bδj )Y ) =

(δj X − γj Y ).

j=0

j=0

j=0

p−1
Y

Hence, (9) becomes F (X + bY, Y )) = F (X, Y ). If we write z = X
Y , then we have F (z + b, 1) =
p
p−1
F (z, 1). By Proposition 3.10, we have F (z) = R(z − b z), with R ∈ Fq [z] a polynomial of
degree deg(R) ≤ t.
p−1
Q
The product
(δj z − γj ) is also σ-invariant and, by Proposition 3.10, we have:
j=0

p−1
Y

(δj z − γj ) =

f (X, Y ) =

δj

j=0

j=0

Hence:

p−1
Y



p−1
Y

γj ·
z p − bp−1 z + (−1)p
j=0

R(X p − bp−1 XY p−1 , Y p )
·
 p−1
p−1

 t
Q  p
Q
δj X − bp−1 XY p−1 − (−1)p−1
γj Y p
j=0

j=0

The arguments to conclude this proof are the same that in Proposition 3.9.
Moreover, if Q̃ 6= P∞ , ∀j, δj 6= 0 and we can write:
Q̃ =

p−1
Y
j=0

We have:

p−1
Y
j=0


γj
:1 .
δj

p−1
Y γ0
γ0
γ0
γj
( + jb) = ( )p − bp−1 ·
=
δj
δ0
δ0
δ0
j=0

10

3.2.3

Case σ diagonalizable in Fq2m \Fqm

We suppose that σ = ρ ◦ σd ◦ ρ−1 with σd diagonal in GL2 (F2m
q ) and ρ ∈ PGL2 (Fq 2m ). We want
to extend the code C defined on Fqm to the field Fq2m . So we consider the set SpanFq2m < C >,
i.e. C ⊗ Fq2m .


α 0
The order ℓ of σd :=
is the order of α ∈ Fq2m , so ℓ | (q 2m − 1). Since q := ps , where
0 αq
s ∈ N∗ , we have ℓ | (ps2m − 1) and so p ∤ ℓ. By Lemma 3.2, Foldσ = Invσ , and so we have the
following diagram:
C ⊗ Fq2m = {EvP (f )|f ∈ LFq2m (G)}

Foldσd

O

/ Invσ (C ⊗ F 2m )
q
d
O
Subfield Subcode

Subfield Subcode

?

C = {EvP (f )|f ∈ LFqm (G)}

Foldσ

?

/ Invσ (C)

By Section 3.2.1, the code Invσ (C ⊗ Fq2m ) is a GRS code. Since the application Foldσ is
Fq -linear and C ⊗ Fq2m has, by definition, a basis in Fnqm , the code Invσ (C ⊗ Fq2m ) also has a
basis in Fnqm . Therefore, the subfield subcode on Fqm of the GRS code Invσ (C ⊗ Fq2m ) is a GRS
code.

4

Security of σ-invariant Alternant Codes

In this section, we study the security of keys of the McEliece scheme based alternant codes,
with σ an automorphism of the projective line acting on it. We consider an automorphism
σ ∈ PGL2 (Fqm ), and a σ-invariant alternant code A(P1 , P, G) = CL (P1 , P, G)⊥ ∩ Fnq , with P a
σ-invariant set of distinct points of P1 defined as (2) and G a σ-invariant divisor of P1 defined
as (3). By Section 3.2 and Corollary 3.6, the invariant code A(P1 , P, G)σ is an alternant code
A(P1 , P̃, G̃), with smaller parameters.
Here we assume that it is possible to recover P̃ and G̃ from a generator matrix of the code
A(P1 , P̃, G̃). This can be done by a brute force attack, if the parameters of A(P1 , P̃, G̃) are
smaller enough. Otherwise, we assume that an algebraic attack, proposed in [9], can recover P̃
and G̃.
We will show that thanks to the knowledge of P̃ and G̃ we are able to recover P and G. We
already know that there is a link between the form of P̃ and G̃ of the invariant code and the
form of P and G of the original alternant code. The link is described by Propositions 3.9 and
3.11 of the previous section. 
Later on, we denote P̃ := (α̃i : 1) | i ∈ {1, . . . , nℓ } the support of the invariant code. All
the α̃i are known. We denote by (αi,j : 1) for i ∈ {1, . . . , nℓ } and j ∈ {0, . . . , ℓ − 1} the elements
Pℓ−1 j
of P. We assume that G is constructed from one rational point Q, ie: G = t j=0
σ (Q), with
j
σ (Q) := (γj : δj ), for all j ∈ {0, . . . , ℓ − 1}. The result remains true for the general case.

4.1

Recover the divisor and guess the support

As previously, we know three cases are possibles: σ is diagonalizable over Fqm , σ is trigonalizable,
or σ is diagonalizable over Fq2m . In this section we treat the two first cases, the third case will
be treated at the end of Section 4. The order ℓ of σ is known, hence we know the form of σ.

11

4.1.1

Case σ diagonalizable over Fqm

In this case, we recall that the form is:
σ:

P1
→
P1
(x : y) 7→ (ax : y),

(10)

with a ∈ F×
q m , an ℓ-th root of unity. There exist only ϕ(ℓ) < n possibilities for a , where ϕ the
Euler’s phi function, hence we are able to test all the possibilities. W.l.o.g we assume for now
that we know the element a. The first step is to recover G from G̃. By Proposition 3.9, we know
ℓ(ℓ−1)
that G̃ = tQ̃, where either Q̃ = ((−1)ℓ−1 a 2 ( γδ00 )ℓ : 1) or Q̃ = P∞ . Since we know a, we can
recover the support of G thanks to the support Q̃ of G̃.
ℓ(ℓ−1)

Remark 4. For all i ∈ {0, . . . , ℓ − 1}, we have Q̃ = ((−1)ℓ−1 σ i (a) 2 ( γδii )ℓ : 1) . We denote
A := {σ i (a) | i ∈ {0, . . . , ℓ − 1}} and then from every a ∈ A we are able to recover the support
of G. The set A is exactly the set of roots of the unity.
Algorithm 1: Recover the divisor in the case σ diagonalizable in Fqm

1
2
3
4

Input : The divisor G̃ of the invariant code A(P, G)σ .
Output: Return the support G
a ← a primitive ℓ-th root of Fqm
if Q̃ 6= P∞ then
ℓ(ℓ−1)
2

Γ ← roots(a
P
(γ : 1)
G′ ← t

Xℓ

− γ̃)

// G̃ = t ∗ Q̃, with Q̃ = (γ̃ : 1)
// a ∈ A

γ∈Γ

6

else
G′ = tP∞

7

return G.

5

The second step is to recover a support P ′ such as A(P ′ , G) = A(P, G) . By Proposition
3.9, we know that a point P = (x : y) in P satisfies:
(
xℓ − α̃i = 0
(11)
y ℓ − β̃i = 0,
for some i ∈ {1, . . . , nℓ } such that (α̃i : β̃i ) = P̃i . Since we know P̃, we are able to recover
all elements of P but as an unordered set. We choose one solution (αi , βi ) of (11) for each
i ∈ {1, . . . , nℓ } and we choose a ∈ A, then the set:
n
αi 
n o
P ′ := aj
(12)
: 1 j ∈ {0, . . . , ℓ − 1}, i ∈ {1, . . . , }
βi
ℓ

is a support such as A(P ′ , G) is a permutation of the code A(P, G). For each choice of set
of solutions S := {(αi , βi ) | i ∈ {1, . . . , nℓ }} and each choice of a ∈ A, we have a different
support P ′ . In Section 4.2 we give an algorithm to find a good choice for S and a and hence the
permutation between A(P ′ , G) and A(P, G).

12

4.1.2

Case σ trigonalisable over Fqm

In the case where σ is trigonalisable, it is more complicated to know exactly σ. In this case we
know that σ has the following form:
σ:

P1
→
P1
(x : y) 7→ (x + by : y),

(13)

with b ∈ F×
q m . Here the order of σ is ℓ = p := Char(Fq m ) and the first step is to recover b.
Lemma 4.1. b is a root of the polynomial:


m
m
n
Pb := gcd
ResX (X p − Y p−1 X − α̃i , X q − X) | i ∈ {1, . . . , } , Y q − Y ,
ℓ

where ResX (P, Q) denotes the resultant of the two polynomials P and Q with respect to X.
Proof. By Proposition 3.11, b is a root of the polynomial αpi,j − Y p−1 αi,j − α̃i ∈ Fqm [Y ] for all
i ∈ {1, . . . , np } and j ∈ {0, . . . , p − 1}. As αi,j ∈ F×
q m for all i, j, we can also write that b is a root
m
p
p−1
q
of the polynomial ResX (X − Y
X − α̃i , X − X) ∈ Fqm [Y ] for all i ∈ {1, . . . , np }.
All the elements of the orbit of b under the action of σ are roots of the polynomial Pb defined
previously, i.e: the elements of the set B := {b, 2b, . . . , (ℓ − 1)b}. In practice, and according to
computer aided experiment, the degree of the polynomial Pb is ℓ and the set B is exactly the
set of its roots. Then there exist only ℓ < n possibilities for b, so we assume for now that we
know the element b.
The second step is to recover the divisor G from G̃. By Proposition 3.11, we know that
G̃ = tQ̃, where either Q̃ = (( γδ00 )p − bp−1 γδ00 : 1) or Q̃ = P∞ .. Since we know a, we can recover
the support of G thanks to the support Q̃ of G̃.
Since we know b, we can recover the support of G thanks to the support Q̃ of G̃.
Algorithm 2: Recover the divisor in the case σ trigonalizable over Fqm
Input : The divisor G̃ of the invariant code A(P, G)σ .
Output: Return G and B the set of possible values of b in (13)
1

3

R ← gcd {ResX (X p − Y p−1 X − α̃i , X
B ← roots(R)

4

/* Recover G′ from G̃ */

5

if Q̃ 6= P∞ then
p − bp−1 X − γ̃)
Γ ← roots(X
P
(γ : 1)
G′ ← t

2

6
7

// P̃ = {α̃i | i ∈ {1, . . . , nℓ }}
n
qm

/* Recover B := {b, 2b, . . . , (p − 1)b} */
qm

− X) | i ∈ {1, . . . , p }}, Y

−Y

// G̃ = t ∗ Q̃, with Q̃ = (γ̃ : 1)
// b ∈ B

γ∈Γ

9

else
G′ = tP∞

10

return G′ , B

8

Proposition 4.2. Algorithm 2 finds the set B and the divisor G in O(n(q m + p)ω+1 ) operations
in Fqm , where ω is the exponent of the linear algebra.

13

Proof. We only prove the cost of the algorithm, its correctness is a consequence of Lemma 4.1
and Lemma 3.7.
The resultant of two polynomials can be computed with an "evaluation-interpolation" method, which reduces to compute determinants of scalar matrices and one interpolation. Here the
degree of the resultant that we must compute is at most (q m + p)(p − 1), so we must compute
(q m + p)(p − 1) + 1 determinants with scalar coefficients. The only polynomial to evaluate here is
Y (p−1) , so the cost of the evaluation is O((q m + p)(p − 1) log2 (p − 1)). Computing determinants
costs O((q m + p)ω ((q m + p)(p − 1))) operations, where ω is the exponent of the cost of linear
algebra. Then the interpolation cost (q m + p)2 (p − 1)2 operations, using Lagrange interpolation,
but this is negligible behind the cost of the previous determinants.
With Euclid Algorithm we can compute
the gcd of two polynomials in Fqm [Y ] of degree at most

m
m
2
(q + p)(p − 1) in O (q + p)p) operations in Fqm . We compute at most np resultants and
gcd, so the cost of the first step is O(n(q m + p)ω+1 ) operations in Fqm .
The second step is negligible behind the first step event if we use Berlekamp algorithm.
The third step is to recover a support P ′ such as A(P ′ , G) = A(P, G) . By Proposition 3.11,
we know that a point P = (x : y) in P satisfies:
(
xp − bp−1 x − α̃i = 0
y p − β̃i = 0

for i ∈ {1, . . . , nℓ }, such that (α̃i : β̃i ) = P̃i . Since we know P̃, we are able to recover all elements
of P but as an unordered set. Hence we know a support P ′ such as A(P ′ , G) is a permutation
of the code A(P, G).

4.2

Recover the permutation

At this point the problem is to recover the permutation between A(P ′ , G) and A(P, G). Let
GenA(P,G) be a generator matrix of the code A(P, G), and HA(P ′ ,G) be a parity check matrix
of the code A(P ′ , G), the permutation between A(P, G) and A(P ′ , G) is represented by matrix
Π such that
T
GenA(P,G) ΠHA(P
(14)
′ ,G) = 0.
If we have no assumption on the permutation between P ′ and P, to find the permutation
Π we must resolve a linear system with n2 unknowns, while (14) is a system of k(n − k) linear
equations which is not enough to find an unique solution.
Now we assume that we made the good choice for a ∈ A (or b ∈ B). Then the permutation
matrix Π has the following form:


ℓ


P
0 1
0


x1,i J i
 i=1





 1❁
0


·
❁
Π=
(15)
 where J := 
ℓ

 0 ❁❁❁
P


i
❁


n

x ℓ ,i J 
❁


i=1
0 0 1 0

(0)

(0)

J is an ℓ × ℓ matrix, and xj,i ∈ {0, 1} are unknowns, for j ∈ {1, . . . , nℓ } and i ∈ {1, . . . , ℓ}.
With this form we have n unknowns. Assume that n − k ≤ n2 , then n ≤ (n − k)k. In this case,
we can hope to find a unique solution for Π. In all our computer aided experiments we got a
unique solution for Π. If the choice for a ∈ A (or b ∈ B) is wrong, then there was no solution
for the system in all our experiments.
14

We present an algorithm to recover the permutation matrix Π and so the good choice for
a ∈ A (or b ∈ B). The algorithm is only written for the first case, where σ is diagonalizable,
but the other case is similar.
Algorithm 3: Recover the support
Input : A generator matrix of a quasi-cyclic alternant code: GenA(P,G) , the divisor G,
and the support P̃ of the invariant code.
Output: Returns FALSE if no solution is found. Else, returns TRUE and P ′ such that
A(P ′ , G) = A(P, G)
n
1 for i ∈ {1, . . . , ℓ } do
2
αi ← roots(xℓ − α̃i )[1]
// cf (12)
ℓ
3
βi ← roots(y − β̃i )[1]
4
5
6
7
8
9
10
11
12
13
14

15

forall a ∈ A do
/* Guess P ′ */

P ′ ← {(aj αβii : 1) | j ∈ {0 . . . ℓ − 1}, i ∈ {1 . . . nℓ }}
C ← A(P ′ , G)
if C = A(P, G) then
return TRUE, P ′
else
H ← ParityCheckMatrix(C)
S ← solve(GenA(P,G) ΠH T = 0, with Π a permutation matrix of the form (15))
if |S| = 1 then
return TRUE, (P ′ ∗ Π)
return FALSE

Proposition 4.3. Algorithm 3 finds a support P ′ such that A(P ′ , G) = A(P, G) in O(ℓn2 (n −
k)k) operations in Fqm , where n is the length of A(P, G), k is the dimension of A(P, G), ℓ is
the order of σ.
Proof. We only prove the cost of the algorithm. We must to resolve a linear system of (n − k)k
equations with n unknowns, this is possible in O(n2 (n − k)k) operations in Fqm . This step is
repeated at most ℓ times so the cost is in O(ℓn2 (n − k)k) operations in Fqm .
In order to give practical running times for this part of the attack, we implemented Algorithm
3 in Magma [4]. The platform used in the experiments is a 2.27GHz Intel R Xeon R Processor
E5520. For each set of parameters, we give the average time obtained after 10 tests. In the
following table we use notation:
• m : extension degree of the field of definition of the support and divisor over Fq
• n length of the quasi–cyclic code
• k dimension of the quasi–cyclic code
• ℓ denotes the order of quasi–cyclicity of the code
• wISD denotes the logarithm of the work factor for message recovery attacks. It is computed
using CaWoF library [5].

15

q
2
2
2

4.3

m
12
12
12

n
3600
3500
3510

k
2825
2665
2579

ℓ
3
5
13

wISD
129
130
132

Algorithm 3
1659 s (≈ 27 min)
2572 s (≈ 42 min)
8848 s (≈ 2h27)

Case σ diagonalizable in Fq2m \Fqm

In this case, we recall that σ = ρ ◦ σd ◦ ρ−1 with ρ ∈ GL2 (Fq2m ) and:
σd :

P1
→
P1
(x : y) 7→ (αx : αq y),

where α ∈ Fq2m is an ℓ-th root of unity. As σd is diagonal in Fq2m , we can recover a support P ′
and a divisor G′ in Fq2m , using the same method as in Sections 4.1 and 4.2.
Now we want to recover a support P and a divisor G in Fqm . We consider πα := X + aX + b
the minimal polynomial of α, with a, b ∈ Fqm . Then:

 

0 −b
α 0
= Mσ′
∼
Mσd =
1 −a
0 αq
and there exist ρ′ ∈ GL2 (Fq2m ) such that σd = ρ′ ◦σ ′ ◦ρ′−1 , where σ ′ is the element of PGL2 (Fqm )
associated to Mσ′ . We can assume that σ = σ ′ , then we want to recover ρ′ . Thanks to Section
4.2, we know α and it is easy to compute a and b. To recover ρ′ it suffices to diagonalize the
matrix Mσ′ . From ρ′ and a support P ′ and a divisor G′ in Fq2m , we can recover a support
P = ρ′−1 (P ′ ) and a divisor G = ρ′−1 (G′ ) in Fqm .

5

Conclusion

To summarise, we showed that the key security of compact McEliece schemes based on alternant
codes with some induced permutation is not better than the key security of the short code
obtained from the invariant operation. A similar result was showed for permutations induced by
the affine group with the folded code. Our new approach simplifies the reduction and extend the
result to the projective linear group. Moreover, we present a simpler lifting from the invariant
code to recover the original code, with method from linear algebra.
Another kind of quasi-cyclic alternant codes could be obtained from the action of the semilinear projective group on the support. By semilinear projective group, we mean transformation
qi

of the form: x 7→ axqi +b , with a, b, c, d ∈ Fnqm . These transformations induce a permutation on
cx +d
the alternant code C ∩ Fnq but not on the GRS code C. So we cannot use the same property of
the invariant of a GRS code to study this kind of quasi-cyclic alternant code.
We can notice that key-recovery is generally more expensive than message recovery. With a
good choice of parameters it is still possible to construct quasi-cyclic codes with high complexity
of key recovery attack on the invariant code.
Acknowledgements
This work is partially supported by a DGA-MRIS scholarship, by French ANR-15-CE39-001301 "Manta", and by European grant CORDIS ICT-645622 "PQCrypto". We would like to
thank J.P. Tillich and J. Lavauzelle for helpful discussions, and A. Couvreur for many valuable
comments on the preliminary versions of this paper.

16

References
[1] Thierry P. Berger, Goppa and related codes invariant under a prescribed permutation, IEEE
Trans. Inform. Theory 46 (2000), no. 7, 2628–2633.
[2]

, On the cyclicity of Goppa codes, parity-check subcodes of Goppa codes and extended
Goppa codes, Finite Fields Appl. 6 (2000), no. 3, 255–281.

[3] Thierry P. Berger, Pierre-Louis Cayrel, Philippe Gaborit, and Ayoub Otmani, Reducing
key length of the McEliece cryptosystem, International Conference on Cryptology in Africa,
Springer, 2009, pp. 77–97.
[4] Wieb Bosma, John Cannon, and Catherine Playoust, The Magma algebra system I: The user language, J. Symbolic Comput. 24 (1997), no. 3/4, 235–265,
http://dx.doi.org/10.1006/jsco.1996.0125.
[5] Rodolfo Canto Torres, CaWoFa, C library for computing asymptotic exponents of generic
decoding work factors, 2016, https://gforge.inria.fr/projects/cawof/.
[6] Arne Dür, The automorphism groups of Reed-Solomon codes, J. Combin. Theory Ser. A 44
(1987), 69–82.
[7] Jean-Charles Faugère, Ayoub Otmani, Ludovic Perret, Frédéric de Portzamparc, and JeanPierre Tillich, Folding alternant and Goppa codes with non-trivial automorphism groups,
IEEE Trans. Inform. Theory 62 (2016), no. 1, 184–198.
[8]

, Structural cryptanalysis of McEliece schemes with compact keys, Des. Codes Cryptogr. 79 (2016), no. 1, 87–112.

[9] Jean-Charles Faugere, Ayoub Otmani, Ludovic Perret, and Jean-Pierre Tillich, Algebraic
cryptanalysis of McEliece variants with compact keys, Annual International Conference on
the Theory and Applications of Cryptographic Techniques, Springer, 2010, pp. 279–298.
[10] William Fulton, Algebraic curves: an introduction to algebraic geometry, Addison-Wesley
Redwood City California, 1989.
[11] Philippe Gaborit, Shorter keys for code based cryptography, Proceedings of the 2005 International Workshop on Coding and Cryptography (WCC 2005), 2005, pp. 81–91.
[12] V. D. Goppa, Codes on algebraic curves, Dokl. Akad. Nauk SSSR 259 (1981), no. 6, 1289–
1290.
[13] Venkatesan Guruswami, Linear-algebraic list decoding of folded Reed-Solomon codes, Computational Complexity (CCC), 2011 IEEE 26th Annual Conference on, IEEE, 2011, pp. 77–
85.
[14] Pierre Loidreau, Codes derived from binary Goppa codes, Probl. Inf. Transm. 37 (2001),
no. 2, 91–99.
[15] Florence J. MacWilliams and Neil J. A. Sloane, The theory of error-correcting codes, fifth
ed., North–Holland, Amsterdam, 1986.
[16] Robert J. McEliece, A public-key system based on algebraic coding theory, pp. 114–116, Jet
Propulsion Lab, 1978, DSN Progress Report 44.

17

[17] Rafael Misoczki and Paulo S.L.M. Barreto, Compact McEliece keys from Goppa codes,
International Workshop on Selected Areas in Cryptography, Springer, 2009, pp. 376–392.
[18] Henning Stichtenoth, On automorphisms of geometric Goppa codes, Journal of Algebra 130
(1990), no. 1, 113–121.
[19]

, Algebraic function fields and codes, Universitext, Springer, 1993.

18

