Code-based Cryptography

Kim J. E. Jäämeri

School of Science

Thesis submitted for examination for the degree of Master of

Science in Technology.
Espoo 31.12.2019

Supervisor

Prof. Camilla Hollanti

Advisor

Prof. Camilla Hollanti

Copyright ⃝
c 2019 Kim J. E. Jäämeri
 Aalto University, P.O. BOX 11000, 00076 AALTO
[Link]
Abstract of the master’s thesis

Author Kim J. E. Jäämeri

Title Code-based Cryptography
Degree programme Master’s Programme in Mathematics and Operations Research
Major Mathematics Code of major SCI3054
Supervisor Prof. Camilla Hollanti
Advisor Prof. Camilla Hollanti
Date 31.12.2019 Number of pages 44+2 Language English
Abstract
Large enough quantum computers could run Shor’s algorithm to solve problems such
as the integer factorization problem or the discrete logarithm problem in time frames
unattainable by conventional computers. Popular implementations of public-key
cryptography rely on brute force computations for such problems being inefficient.
This threat has motivated the research of post-quantum cryptography, in which
code-based cryptography, making use of error-correcting codes, is one promising
research direction. The underlying hard problem in code-based cryptography is the
syndrome decoding problem, which is known to be NP-complete and believed to resist
brute force attack from quantum computers. The original code-based cryptosystem
was suggested in 1978 by Robert McEliece and since then extensive analysis on it
and later variants has been covered in the literature. Many of the proposed variants
have been shown to be insecure due to lack of sufficient concealment of the code
structure, which enables attackers to bypass the hard problem and exploit structural
vulnerabilities instead. Twisted codes are a relatively new family of codes, with
certain explicit constructions potentially being viable for implementation to code-
based cryptography, since previously deployed attack are not directly applicable to
them. This thesis surveys the literature on linear codes to present concepts necessary
to describe twisted codes in their cryptographic environment. The feasibility of
twisted codes in code-based cryptography is then discussed through experimental
simulation results.
Keywords Error-correcting codes, Post-quantum cryptography, Code-based
cryptography, Rank distance, Rank metric codes, Gabidulin codes,
Twisted codes
 Aalto-yliopisto, PL 11000, 00076 AALTO
[Link]
Diplomityön tiivistelmä

Tekijä Kim J. E. Jäämeri

Työn nimi Koodipohjainen kryptografia
Koulutusohjelma Matematiikan ja operaatiotutkimuksen maisteriohjelma
Pääaine Matematiikka Pääaineen koodi SCI3054
Työn valvoja Prof. Camilla Hollanti
Työn ohjaaja Prof. Camilla Hollanti
Päivämäärä 31.12.2019 Sivumäärä 44+2 Kieli Englanti
Tiivistelmä
Riittävän suurella kvanttitietokoneella on teoriassa kyky hyödyntää Shorin algoritmia
ja laskea nopeasti tiettyjä vaikeita ongelmia, kuten kokonaislukujen tekijöihinjako ja
diskreetti logaritmi. Suositut julkisen avaimen salausmenetelmät nojaavat näiden
ongelmien vaikeuteen ja ovat siksi alttiita kvanttilaskennalle. Tästä lähtökohdasta
on tutkittu useita vaihtoehtoisia kvanttilaskennan kestäviä salausmenetelmiä. Yksi
lupaavimmista tutkimussuunnista on virheenkorjauskoodeihin pohjautuva krypto-
grafia, jossa perustana on laskettavuusteoriassa tunnettu NP-täydellinen ongelma:
satunnaisen koodisyndrooman dekoodaus. Tämän ongelman uskotaan olevan vaativa
myös kvanttitietokoneille. Robert McEliecen vuonna 1978 esittämää alkuperäistä
koodipohjaista salausjärjestelmää on tutkittu paljon ja sille on esitetty lukuisia
muunnelmia. Näissä puutteellinen peite esitettyjen muunnelmien koodirakenteille on
osoittautunut yleiseksi haasteeksi. Salaisen koodirakenteen avulla voidaan ohittaa
kryptografinen vaativa ongelma ja purkaa salattu viesti suoraan hyödyntämällä
näitä rakenteellisia heikkouksia. Twist-koodit ovat tutkimuksessa suhteellisen uusi
koodiluokka ja niistä on ehdotettu tiettyjä rakennelmia tarkasteltavaksi myös kryp-
tografian suhteen. Näihin esiteltyihin rakennelmiin ei voida suoraan käyttää mitään
olemassa olevia hyökkäyksiä. Tässä työssä käydään aluksi läpi alan kirjallisuutta
liittyen koodipohjaiseen kryptografiaan. Tarkoituksena on kattaa riittävästi taus-
tateoriaa, jotta voidaan kuvata sen avulla twist-koodien käyttö kryptografisessa
salauksessa. Lopuksi tarkastellaa twist-koodien soveltuvuutta kokeellisten tulosten
valossa.
Avainsanat Virheenkorjauskoodit, kvanttilaskennan kestävät salausmenetelmät,
koodipohjainen kryptografia, rangietäisyys (engl. rank distance),
rangimetriikkakoodit (engl. rank metric code), Gabidulin-koodit,
twist-koodit
 5

Preface
I would like to extend my most sincere gratitude to Prof. Camilla Hollanti from the
Department of Mathematics and Systems Analysis at Aalto University for instructing
and supervising my thesis. I am deeply indebted from the past year and a half, during
which I have been supported by Prof. Hollanti’s invaluable guidance and expertise.
This thesis would not have been possible without her patience, encouragement and
good nature. In addition to being constantly steered in the right direction, I had
the pleasure of being introduced to her international colleagues and their leading
research in the field of code-based cryptography.

In the same spirit, I would also like to thank Dr. Sven Puchinger from the Al-
gebraic Coding Theory research group at the Technical University of Denmark; Dr.
Julien Lavauzelle from Institut de Recherche Mathématique de Rennes and [Link].
Julian Renner from the Institute for Communications and Engineering from the
Technical University of Munich. Thank you for sharing your ingenious research ideas
and granting me access to your SageMath libraries. Our fruitful discussions last
summer were a key source of insight and inspiration for my thesis work.

I am also thankful to the faculty at Aalto University as well as my fellow stu-

dents and friends. You created an outstanding learning environment and it was a
great privilege to have had the opportunity to study with such brilliant people.

Finally, I must express my profound gratitude towards my family for their un-
failing support throughout my years at Aalto University. My parents Kim and Marja
were always understanding and reassuring. Lastly, a special thanks to my partner
Elise, who has brought so much joy and enthusiasm to my master’s studies.

Helsinki, 12.12.2019

Kim J. E. Jäämeri
 6

Contents
Abstract 3

Abstract (in Finnish) 4

Preface 5

Contents 6

Symbols and abbreviations 8

1 Introduction 9
1.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.2 Thesis Scope and Structure . . . . . . . . . . . . . . . . . . . . . . . 9

2 Algebraic Preliminaries 11
2.1 Extension Fields . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2 Linearized Polynomials . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.3 The Schur Product . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

3 Linear Codes 12
3.1 Generator and Parity Check Matrices . . . . . . . . . . . . . . . . . . 13
3.2 The Dual Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.3 The Hamming Code . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.4 The Singleton Bound . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.5 Syndrome Decoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
3.6 Reed-Solomon Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

4 Rank Error-correcting Codes 18

4.1 Background and Motivation . . . . . . . . . . . . . . . . . . . . . . . 18
4.2 The Rank Metric . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
4.3 Maximum Rank Distance . . . . . . . . . . . . . . . . . . . . . . . . . 19
4.4 Gabidulin Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
4.5 Error Correction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

5 Code-based Cryptography 22
5.1 Post-Quantum Cryptography . . . . . . . . . . . . . . . . . . . . . . 23
5.2 The McEliece Cryptosystem . . . . . . . . . . . . . . . . . . . . . . . 24
5.3 Binary Goppa Codes and Implementation for McEliece . . . . . . . . 24
5.4 The GPT Cryptosystem . . . . . . . . . . . . . . . . . . . . . . . . . 27

6 Attacks and Countermeasures 29

6.1 Overbeck’s Attack . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
6.2 Twisted Gabidulin Codes . . . . . . . . . . . . . . . . . . . . . . . . . 31
6.3 Twisted Reed-Solomon Codes . . . . . . . . . . . . . . . . . . . . . . 33
6.4 Attack on Twisted Reed-Solomon Codes . . . . . . . . . . . . . . . . 34
 7

6.5 Analysis of the Same Attack on Twisted Gabidulin Codes . . . . . . . 35

7 Conclusion 39

A Appendix A 45

B Appendix B 46
 8

Symbols and abbreviations

Symbols
v vector v
M matrix M
M−1 inverse matrix of M
M⊺ transpose of M
Fq finite field with q elements, shortly F
C linear code
C⊥ the dual code of C
D decoding algorithm
Ĝk public generator matrix of a Gabidulin code of rank k

Operators
b
∑
sum over index i, going from a to b
i=a
v1 ⋆ v2 component-wise product of vectors v 1 and v 2
dH (v 1 , v 2 ) Hamming distance between vectors v 1 and v 2
dr (v 1 , v 2 ) rank distance between vectors v 1 and v 2
rk(v)
( ) rank weight of vector v
n
k
binomial coefficients
f :X→Y the map f from domain set X to codomain set Y
x ↦→ y, x ∈ X, y ∈ Y element-wise mapping of the element x ∈ X to y ∈ Y
i
M[i] Mq
mod g(x, α) modulo w.r.t. polynomial g, which is a polynomial with variables x and α
gdc(a, b) the greatest common divisor of integers a and b
Λi (·) Overbeck’s Frobenius operator (also referred to as q-sum)

Abbreviations
RSA Rivest–Shamir–Adleman (cryptosystem)
ECC elliptic curve cryptography
SDP syndrome decoding problem
NP non-deterministic polynomial-time
GPT Gabidulin-Paramonov-Tretjakov
XOR exclusive or (digital logic gate)
MDS maximum distance separable
MRD maximum rank distance
NIST National Institute of Standards and Technology
1 Introduction
1.1 Background
In recent decades, concern for post-quantum cryptography has given rise to a new
field of research in the study of techniques for secure communication. The concern
is that a sufficiently large quantum computer, if constructed, could run e.g. Shor’s
algorithm to break popular cryptographic systems such as RSA and ECC [52]. In
other words, popular methods for cryptography have relied on the hardness of certain
problems that are not, in theory, safe from being solved by means of quantum
computing.

Alternatives that are believed to resist attacks by large quantum computers have
been suggested in the literature [7]. Some of the most promising among these are
the code-based cryptosystems using error-correcting algebraic codes. While the origi-
nal purpose of such codes was to enable communication over noisy communication
channels [24], the defining properties of error-correcting codes have proved equally
convenient for applications in cryptography [7]. The European Commission funded
study group on post-quantum cryptography has recommended this approach for
long-term protection against quantum computers [2].

Code-based cryptography, originally suggested by Robert McEliece [33], is based on

the known NP-hardness of the Syndrome Decoding Problem (SDP). This corresponds
to decoding a general linear code. The private key decoding on the other hand is
based on the linear code secretly having some structure to which an efficient decoding
algorithm is known. The original scheme by McEliece uses binary Goppa codes
masked as general linear codes and an algorithm by Nicholas Patterson for decoding
[44].

1.2 Thesis Scope and Structure

The remainder of the thesis is structured as follows. We define some preliminary
algebraic notions in Chapter 2. These are used in the general definition for linear
codes, as well as some more specific code structures later on.

Chapter 3 introduces the reader to linear codes, the core of algebraic coding theory
and the fundamental basis for the remainder of this thesis. Extending on the general
definitions and discussion, Hamming codes are used to demonstrate a readily under-
stood, clear-cut example and Reed-Solomon codes are subsequently presented to set
the stage for the topics of Chapter 6.

The topic of Chapter 4 is the concept of implementing a rank metric for linear
codes as opposed to the original Hamming metric. The chapter explores the key
differences and parallels stemming from the rank metric and presents the original
construction method for this family of rank metric codes.
 10

Chapter 5 describes the cryptographic context for the algebraic linear codes covered
in Chapters 3 and 4. Namely, the cryptosystem presented by McEliece as well as a
similar construction by Gabidulin, Paramonov and Tretjakov (GPT) [13], designed
for codes in the rank metric.

The goal in Chapter 6 is to then delve into the ongoing back and forth process
of both finding new ways to attack the existing code structures as well as fixing them
by adding additional structure to the code [20][21][40][42][46][30].

Last but not least, Chapter 7 concludes the thesis with closing remarks and discussion,
as well as ideas for further research directions.
 11

2 Algebraic Preliminaries
2.1 Extension Fields
Finite fields are a core preliminary for constructing linear codes and we often want
to impose some further structure on them. This is especially true for rank metric
codes, which are generally constructed over extension fields. Hence, extension fields
will be introduced before defining linear codes. This is a well-known topic in algebra,
for further reference see e.g. [25].

Definition 1. Let Fq be a finite field with q elements and let f (x) be an irreducible
polynomial of degree m ≥ 1 over Fq [x]. An extension field of degree m over Fq is
defined as the triple (Fqm , +, ·), where Fqm is the set of all q-ary vectors of length m
and + and · are operations for vectors v 1 , v 2 ∈ Fqm defined as:

• v 1 + v 2 : component-wise addition of v 1 and v 2

• v 1 · v 2 : the coefficients of the polynomial v 1 (x) · v 2 (x) mod f (x)

An extension field can be easily generated using a primitive element of Fqm , an

element such that the powers of that element generate all other non-zero elements.
Such an element can be obtained by selecting f (x) to be a primitive irreducible
polynomial. Let us consider an illustrative example of an extension field over a
primitive irreducible polynomial:

Example 1. Let f (x) = x3 + x + 1 and set f (α) = 0 = α3 + α + 1. Then the powers

of α generate the elements of the extension field F23 as follows:

Table 1: The powers of α

Powers of α Element Binary vector

α0 1 [0 0 1]
α1 α [0 1 0]
α2 α2 [1 0 0]
α3 α+1 [0 1 1]
α4 α2 + α [1 1 0]
α5 α2 + α + 1 [1 1 1]
α6 α2 + 1 [1 0 1]
α7 = α0 1 [0 0 1]

The final element of the extension field is the zero element, corresponding to the
binary vector [0 0 0]. The addition and multiplication operations are easy to compute
in this framework. For example α4 · α5 = (α2 + α)(α2 + α + 1) = α4 + 2α3 + 2α2 + α
and since 2 ≡ 0 (mod 2), this simplifies to α4 + α and since α4 = α2 + α, we are left
 12

with α2 + 2α, which again is congruent to α2 (mod 2).

2.2 Linearized Polynomials

An important class of polynomials in abstract linear algebra is defined directly from
extension fields. Namely, linearized polynomials [36], defined as follows:
Definition 2. Let the elements from an extension field αi ∈ Fqm be coefficients for
i
monomials that are powers of q, so xq , i ∈ {0, . . . , n}, n ∈ N. A polynomial from
such components is known as a linearized polynomial L(x) of degree n, when α0 = ̸ 0.
A straightforward construction for a linearized polynomial can be done as:
n
i
αi xq .
∑
L(x) = (1)
i=0

One application for these is in code-based cryptography, where certain families of

codes draw their structure from clever use of linearized polynomials.

2.3 The Schur Product

The Schur product (also known as the Hadamard product) is a distributive, associative
and commutative operation for vectors of equal dimension [?].
Definition 3. For two vectors v, w ∈ Fnq the Schur product is defined via component-
wise multiplication as:

v ⋆ w := [v1 · w1 , v2 · w2 , . . . , vn · wn ].

From the above definition, we can later derive a Schur product for linear codes which
has many interesting applications.

3 Linear Codes
Linear codes are a family of error-correcting codes and are an essential pre-requisite
for topics to follow. A general code could technically admit to no specific structure
and the only way to describe it would be to list the entire codebook. Hence, in this
chapter we define the useful concept of a linear code and discuss its parameters and
properties [29].

Definition 4. A q-ary linear code C of rank k and length n is a linear subspace of

dimension k of the vector space Fnq , where Fq is a finite field with q elements, and q
is a prime power.

Codes over the binary field F2 are known as binary codes. The vectors of C are
called codewords and the size of the code, q k , is the number of codewords in C. A
codeword has Hamming weight wH equal to its number of non-zero coordinates. One
standard metric for distance d between two codewords is the Hamming distance.
 13

Definition 5. The Hamming distance dH between two codewords c1 and c2 is the

number of respective symbol positions in which the two codewords differ.

For example, the codewords [0 1 0 1 0 1] and [1 1 1 1 1 1] have a different coor-

dinate in exactly three positions and therefore dH ([0 1 0 1 0 1], [1 1 1 1 1 1]) = 3.
This distance between codewords is precisely the property which allows for two
codewords to remain unambiguously different, and also to be observed as different
codewords when we are able to correct sufficiently many of those errors via the code’s
error-correction capabilities.
For a linear code C then, the minimum (Hamming) distance d(C) is defined as
the minimum distance between two distinct codewords. A linear code of length n,
dimension k and minimum distance d over a finite field of size q is denoted as an
[n, k, d]q code.
Finally, the code C has code rate R = nk , which is the ratio of the number of
information symbols to the total number of data symbols. The n − k symbols in the
codeword are redundant, but allow for the desired error-correcting properties.

Definition 6. The error-correction parameter t is defined to be the number of errors

in a linear code, up to which any number of errors may be corrected.

For linear codes over Hamming distance, the error-correction parameter t is

equal to ⌊ dH2−1 ⌋, since this is precisely when a ball centered at any codeword c ∈ C
with radius t is restricted to being non-intersecting with other balls of radius t
centered around any other c′ = ̸ c, c′ ∈ C. Such balls are known as Hamming spheres.
dH −1
Consequently, if ⌊ 2 ⌋ errors occurred during the transmission of a received codeword
w, then there exists a unique codeword w′ ∈ C with dH (w, w′ ) ≤ t. Error-correction
and detection for Hamming metric codes is based in these properties.

3.1 Generator and Parity Check Matrices

The generator matrix G of an [n, k, d]q code is a k × n matrix, in which the rows of G
form a basis for the code. Consequently, the set of unique linear combinations of the
rows in G are the codewords in the code. Hence, the generator matrix is a compact
way to represent an otherwise extensive code. In standard form, the generator matrix
is given as:
G = [Ik |P], (2)
where Ik is the k × k identity matrix and P is a k × (n − k) matrix. From the
standard form of the generator matrix, it is possible to construct the parity check
matrix H for the code. Assuming G is in standard form, the parity check matrix is
constructed as:
H = [−P⊺ |In−k ], (3)
where P⊺ denotes the transpose of matrix P. Codewords c in the code C must satisfy
cH⊺ = 0. The parity check matrix also has further implications relating to the dual
code, which is covered in the next chapter.
The above concepts may be visualized by a simple example.
 14

Example 2. Let q = 2 and [ ]

1 0 1
G= .
0 1 1
We notice that G generates a set of codewords: {[0 0 0], [0 1 1], [1 0 1], [1 1 0]} when
multiplied by different binary vectors of length 2. For example, the codeword [0 1 1]
was obtained from [0 1]G. Note that the sum of any two codewords is also a codeword
in the binary field.
It is easy to see that each codeword differs from any other codeword in exactly 2
positions and therefore the minimum distance of the code is 2. The above observations
imply that G is the generator matrix of a [3, 2, 2]2 code. The parity check matrix for
this example code would be [ ]
H= 1 1 1 ,
having dimensions (n − k) × n = 1 × 3. The matrix −P⊺ in this example is [1 1]. It
can be verified that cH⊺ = 0 ∀ c ∈ C.

3.2 The Dual Code

The orthogonal complement of a code C can be described as the set of all vectors
which are orthogonal to every vector in C. This is known as the dual code of C and
denoted by C ⊥ . Since C ⊥ is also a linear subspace of the vector space Fnq , it is itself a
linear code.
The code and the dual code are related via their parity check and generator
matrices. Indeed, the parity check matrix of C is the generator matrix of C ⊥ and vice
versa: G(C) = H(C ⊥ ).

3.3 The Hamming Code

Hamming codes are a popular class of binary linear codes invented by Richard W.
Hamming in 1950 [35]. This class was designed to have both high minimum distance
d(C) and code rate R(C) to produce efficient codes that still retain well-structured
redundancy for error-correction.
The number of parity bits m = n − k ≥ 2 is selected, from which the [2m − 1, 2m −
m − 1, 3]2 Hamming code is constructed. This is done by carefully choosing the
error-correcting bits such that the XOR-operation over all the bit positions containing
a 1 is 0.

Example 3. One of the most famous Hamming Codes is the [7, 4, 3]2 code, which
has the following generator matrix:

1 0 0 0 1 1 0
⎡ ⎤
⎢ 0 1 0 0 1 0 1 ⎥
G=⎢ ⎥.
⎢ ⎥
⎣ 0 0 1 0 0 1 1 ⎦
0 0 0 1 1 1 1
 15

We can construct its parity check matrix as in (3):

⎡ ⎤
0 0 1 0 1 0 0
H = ⎣ 0 1 0 0 0 1 0 ⎦.
⎢ ⎥

1 0 0 0 0 0 1

The design for having the highest possible code rate while maintaining a minimum
distance d is characterized by the Hamming bound. This bound gives an important
limitation to the efficiency of error-correcting codes and any code achieving the
Hamming bound is said to be a perfect code. We now define the Hamming bound.

Definition 7. The Hamming bound is the limit for the maximum size A(n, d) of a
q-ary linear code of length n and minimum distance d:
qn
A(n, d) ≤ t ( )
, (4)
n
(q − 1)k
∑
k
k=0
⌊ ⌋
d−1
where t = 2
is the maximum number of errors the code can correct.
⌊ ⌋
Proof. Let C be a linear code capable of correcting t = d−1
2
errors and let c ∈ C be
a codeword. The unambiguous error-correction then implies that balls, or Hamming
spheres of radius t centered around each codeword c are non-intersecting. These
Hamming spheres cover q-ary words of length n, which deviate from the centre at
codeword c in at most t components.
These deviations for each component are chosen from (q − 1) possibilities and we
are choosing up to t of the n components to deviate from c. Hence there are a total
t ( )
n
(q − 1)k different possible words within each Hamming sphere.
∑
of k
k=0
We can then consider selecting A(n, d) of these Hamming spheres, that is, the
maximum number of codewords in C( and count the total number of words in the
t )
n
union of these spheres as A(n, d) · (q − 1)k . Clearly this number cannot exceed
∑
k
k=0
q n and hence we have the the bound
qn
A(n, d) ≤ t ( )
.
n
(q − 1)k
∑
k
k=0

3.4 The Singleton Bound

The Singleton Bound, credited to Richard C. Singleton, gives a loose upper bound
on the minimum distance of a linear code. This bound for a linear code C is often
expressed as d(C) ≤ n − k + 1, where d, n and k are the minimum Hamming distance,
the length, and dimension, respectively, of C. A short proof for the bound goes as
follows:
 16

Proof. The generator matrix for any linear code can be expressed in the standard
form given in Equation (2). One row in such a generator matrix consists of at most
n − k + 1 non-zero elements, since there are n − k elements in the rows of matrix P
and only one non-zero element in the rows of the identity matrix. Therefore, the
maximum weight of one row in the standard form generator matrix is n − k + 1
and this weight is precisely the Hamming distance to the zero codeword from any
codeword generated by the row in the generator matrix. The bound follows from
this observation.
Linear codes satisfying equality with the Singleton bound are called Maximum
Distance Separable (MDS).

3.5 Syndrome Decoding

The property for parity check matrices: cH⊺ = 0 for all c ∈ C allows us to do
syndrome decoding. Suppose we receive a word r. Then rH⊺ = 0 if and only if r is a
codeword in C.
The received word r may be expressed as a sum of some codeword c ∈ C and
error vector e of the same length, such that r = c + e. Multiplying this type of
received word r with H⊺ gives us what we call the error syndrome, denoted by S.

Note that

S = [c + e]H⊺ = cH⊺ + eH⊺

= eH⊺ ,

since cH⊺ = 0. The idea is then that each distinct S corresponds to a distinct error
vector, depending on the parity check matrix of the code. This correspondence may
be presented as a table, and for codes with small parity check matrices the table is
relatively compact.

If the number of errors in the received word is at most the error-correcting capacity
of the code t, then syndrome decoding yields the correct codeword and if wH (e) > t,
then this type of decoding corresponds to maximum likelihood decoding. This
equivalence assumes the probability of an error occurring at one given coordinate
as < 0.5 and that the probability is independent of other errors. Under these
assumptions, syndrome decoding yields the most probable codeword with respect to
the to the received word.
The general case of syndrome decoding a linear code was shown to be an NP-hard
problem by Berlekamp, McEliece, and van Tilborg in 1978 [6], when decoding a
linear code in the presence of t errors without having access to a parity check matrix.

Example 4. Consider the [7, 4, 3]2 Hamming code from Example 3. Let us receive
a word r = [0 1 1 0 1 1 1] and apply syndrome decoding. We compute the error
 17

syndrome as:
⎡ ⎤
0 0 1
0 1 0
⎢ ⎥
⎢ ⎥
⎢ ⎥
⎢
⎢ 1 0 0 ⎥
⎥
S = rH⊺ = [0 1 1 0 1 1 1] ⎢ 0 0 0 = [0 0 1] .
⎢ ⎥
⎥
⎢ ⎥
⎢
⎢ 1 0 0 ⎥
⎥
⎢
⎣ 0 1 0 ⎥
⎦
0 0 1

Since the syndrome is not equal to zero, there received word is not a codeword
and we may deduce which single error would produce the syndrome [0 0 1]. The third
row of the parity check matrix asserts that the first and last bits of any codeword
are the same, and hence there should be an error in either position 1 or position 7 as
the bit 1 in position 3 of the syndrome indicates this type of disparity.
If the error were in position 1, then we would have to correct the received word
to c∗ = [1 1 1 0 1 1 1]. This, however, is not a codeword in the code, so we deduce
that the error occurred in position 7 and c∗ = [0 1 1 0 1 1 0] is indeed a codeword.
Specifically, it is a linear combination of the second and third rows of the generator
matrix. Hence, this would be the output of a syndrome decoder with input r.

3.6 Reed-Solomon Codes

Irving S. Reed and Gustave Solomon introduced a class of linear codes in 1960, later
to be known as Reed-Solomon codes [49]. The code has optimal minimum distance for
a linear code of length n and rank k (i.e. it meets the Sinlgeton bound), and hence,
is a famous and widely utilized code structure with applications such as bar codes
and data storage in media. Similar to a general linear code, the Reed-Solomon code
can be parametrized as an [n, k, d]q code and it can be constructed via a generator
or parity check matrix. The formal definition of a general Reed-Solomon code is as
follows:

Definition 8. Let Fq be a finite field and let p denote a polynomial of degree less than
k over Fq . Let α1 , . . . , αn ∈ F denote n ≤ q distinct evaluation points for the polyno-
mial p. Then a Reed-Solomon code is defined as CRS = {(p(α1 ), p(α2 ), . . . , p(αn ))}.

The evaluation points α1 , . . . , αn ∈ Fq are often selected such that α is a primitive

element of F and n | q − 1, as this allows us to use Vandermonde matrices for a
simple and concise construction [57]:

···
⎡ ⎤
1 1 1 1
⎢
⎢ 1 α α2 ··· α(n−1) ⎥
⎥
GRS = ⎢ .. .. .. .. ⎥,
⎢
⎣ . . 1 . .
⎥
⎦
(k−1) 2(k−1)
1 α α ··· α(n−1)(k−1)
 18

α2 ··· α(n−1)
⎡ ⎤
1 α
⎢
⎢ 1 α2 α4 ··· α2(n−1) ⎥
⎥
HRS = ⎢ .. .. .. ... .. ⎥.
. . . .
⎢ ⎥
⎣ ⎦
1 α(n−k) α(n−k)2 · · · α(n−k)(n−1)
Messages of the form m = [m0 , m1 , . . . , mk−1 ], mi ∈ Fq can be encoded by
mapping them to a polynomial of degree (k − 1). Here the mapping M : m → p(α)
k−1
is defined by m ↦→ mi α i .
∑
i=0
Note that Reed-Solomon codes comply with the definition for linear codes, since
for a any b ∈ Fq and polynomials f (α), g(α) ∈ Fq [α] of degree ≤ k−1, the polynomials
bf (α) and f (α) + g(α) are also polynomials of degree ≤ k − 1 and the mapping for
message encoding clearly preserves this linearity.
The Singleton bound can also be verified for Reed-Solomon codes by recalling that
a non-zero polynomial of degree x over Fq has at most x roots in Fq , as the Hamming
weight of the difference between two encoded messages, wt(CRS (m2 ) − CRS (m1 ))
is equal to n minus the number of zeroes in CRS (m2 ) − CRS (m1 ). This number of
zeroes is precisely the number of roots the polynomial pm2 (α) − pm1 (α) has among
the evaluation points: k − 1. Thus, the weight of the difference for two encoded
messages is at least n − k + 1, which results in the Singleton bound.

4 Rank Error-correcting Codes

4.1 Background and Motivation
Rank metric codes are a special type of linear error-correcting code that use a rank
based metric instead of the Hamming metric. The rank metric was introduced by Loo-
Keng Hua in 1951 as an “arithmetic distance” [28],[14]. In 1978, Philippe Delsarte
applied the rank metric on a set of bilinear forms, or rectangular matrices [12]. He
also proposed the construction of optimal rank codes in bilinear form representation.
The rank metric for vector spaces over field extensions was introduced in 1985 by
Ernst M. Gabidulin, who also described optimal rank metric codes in vector form
and proposed fast encoding and decoding algorithms [14]. This was the only known
construction for optimal rank codes until recently, as John Sheekey presented a more
general family, including the construction by Gabidulin [51].

Useful applications for rank codes have been found in areas such as distributed
storage [54] and random linear network coding [55]. In cryptography, extensive study
of rank metric codes is motivated by the large public key sizes inherent to code-based
cryptography. Conventional schemes based on problems such as factorization of
integers or the discrete logarithm problem use much smaller public keys for commu-
nication compared to code-based approaches. Yet, rank codes provide a comparative
advantage with respect to the McEliece type implementations using Hamming metric
codes, such as Goppa codes. This property is due a large family of rank metric codes
being generated from a fixed size public key.
 19

4.2 The Rank Metric

We are now ready to define the rank weight of a vector and the rank distance between
two vectors:

Definition 9. Let v = {vi }, w = {wi } ∈ Fnqm be two vectors of length n in the

vector space over the extension field Fqm . The rank weight rk(v) is defined as the
dimension of the Fq subspace generated by {v1 , v2 , . . . , vn }.

The rank distance dr (v, w) for two vectors is defined as rk(v − w).

The definition of rank distance further induces a notion of “minimum rank distance”
to rank metric codes, similar for the minimum Hamming distance. Formally the
minimum distance for a rank metric code C can be expressed as minv,w∈C,v̸=w dr (v, w).
The rank weight can be equivalently defined by extending every coordinate of
a vector v ∈ Fnqm on a basis of the quotient field Fqm /Fq to form an m × n matrix
over Fq . The rank of such a matrix is equal to rk(v). This definition is useful for
computing the rank weight in practice.
Yet another equivalent definition is obtained from the dimension of the support of
a vector v ∈ Fnqm . The support of v is the Fq vector space spanned by its coordinates.
The dimension of the support of v is equal to rk(v).

Example 5. Let v ∈ F523 (α) and fix v = (α, α5 , 0, α, α6 ) = (α, α2 +α+1, 0, α, α2 +1).
Let us compute the rank weight rk(v) of the vector v.

To this end, let us form a 3 × 5 matrix by extending the coordinates of v onto a

basis of Fqm /Fq . We obtain the following matrix:
⎡ ⎤
0 1 0 0 1
⎣ 1 1 0 1 0 ⎦,
⎢ ⎥

0 1 0 0 1

where for example the second column [1 1 1]T corresponds to the binary vector [1 11],
which corresponds to α5 originating from the second coordinate of v. The first and
third row are clearly linearly dependent, so the rank of this matrix is 2. Therefore
according to the above discussion on equivalent definitions for rank weight, we have
rk(v) = 2.

4.3 Maximum Rank Distance

At the beginning of this section we referred to “optimal” rank metric codes vaguely
without a formal definition. There is a bound for rank metric codes, which is similar
to the Singleton bound for linear codes with the Hamming metric.
 20

Definition 10. Let C be a linear code with the rank metric over the vector space
Fnqm . If n ≤ m and k ≤ n, then dr ≤ n − k + 1 and rank codes satisfying equality
with this bound are defined to have Maximum Rank Distance (MRD).
An alternative bound for maximum rank distance was given by Pierre Loidreau in
[31]:
m
dr ≤ (n − k) + 1. (5)
n
This alternative bound is tighter for the case where n > m, whereas for n ≤ m, the
former bound remains the tighter one. This is why the former bound is defined for
n ≤ m. Each maximum rank distance code is also maximum distance separable.

4.4 Gabidulin Codes

Rank error-correcting codes are sometimes referred to as simply Gabidulin codes
due to the prevalence of the famous construction by Ernst Gabidulin [14]. Gabidulin
codes are designed to be maximum rank distance codes with length n ≤ m over an
extension field Fqm . Due to highly similar structure, this family of codes is often
seen as an analogue to the Reed-Solomon codes from the Hamming metric. There
are two straightforward approaches for constructing Gabidulin codes, the one via
parity check matrix being as follows:
Definition 11. Let h1 , h2 , . . . , hn ∈ Fqm be chosen such that they are linearly inde-
pendent over the base field Fq and let s be a positive integer such that gcd(s, m) = 1.
Then a Gabidulin code is defined by a parity check matrix of the form
⎡ ⎤
h1 h2 ... hn
s s s
hq1 hq2 ... hqn
⎢ ⎥
⎢ ⎥
⎢ 2s 2s
⎥
2s
hq1 hq2 ... hqn
⎢ ⎥
Hd−1 = ⎢ ⎥ (6)
.. .. .. ..
⎢ ⎥
.
⎢ ⎥
⎢
⎣ . . . ⎥
⎦
(d−2)s (d−2)s (d−2)s
hq1 hq2 ··· hqn
where d = n − k + 1 denotes the minimum distance of the code.
The other option is to construct a generator matrix for the code with a similar
pattern.
Definition 12. Let g1 , g2 , . . . , gn ∈ Fqm be chosen such that they are linearly inde-
pendent over the base field Fq and let s be a positive integer such that gcd(s, m) = 1.
Then a Gabidulin code is defined by a generator matrix of the form
⎡ ⎤
g1 g2 ... gn
s s s
g1q g2q ... gnq
⎢ ⎥
⎢ ⎥
⎢ 2s 2s
⎥
2s
g1q g2q ... gnq
⎢ ⎥
Gk = ⎢ ⎥ (7)
.. .. ... ..
⎢ ⎥
⎢ ⎥
⎢
⎣ . . . ⎥
⎦
(k−1)s (k−1)s (k−1)s
g1q g2q ··· gnq
where k = n − d + 1 denotes the dimension of the code.
 21

The parameter s is often fixed to be 1, which simplifies the code quite a bit. Also, the
substitution in notation of q i → [i] is often used and makes these types of definitions
easier to read.
Let us construct a simple Gabidulin code in another illustrative example.

Example 6. Set s = 1 and select from the extension field in Example 1 elements
α, α2 and α2 + 1. Following the construction for a generator matrix of a Gabidulin
code gives:
α2 α2 + 1
⎡ ⎤
α
G3 = ⎢⎣ α2 α2 + α α2 + α + 1 ⎥ ⎦.
α2 + α α α+1
We can verify that the maximum rank distance bound of dr = 1 = 3 − 3 + 1 holds
for the example, although it may not be exciting for such a small example.

Note how the columns in the generator matrix of a Gabidulin code follow the structure
for linearized polynomials defined in (1). We can express codewords in terms of
linearized polynomials as (L(g1 ), L(g2 ), . . . , L(gn )), given that the polynomial L(x)
has degree less than k. The set of all such linearized polynomials L(x) with degree
less than k forms the set of codewords C.
The proof to the following proposition makes use of this parallel and shows that
all Gabidulin codes are MRD.
Proposition 4.1. The Gabidulin code defined by Gk in (7) is MRD.
Proof. Let x = (L(g1 ), L(g2 ), . . . , L(gn )) denote a codeword generated by Gk and
associated to the linearized polynomial L(x), with degree less than k. The rank of x is
equivalent to the dimension of the Fq -vector space generated by (L(g1 ), L(g2 ), . . . , L(gn )).
Also, the Fq -vector space generated by (g1 , g2 , . . . , gn ) has dimension n, as gi were
selected to be linearly independent.
Let ker(L) = {a ∈ Fqm |L(a) = 0}. The n-dimensional Fq -vector space generated
by (g1 , g2 , . . . , gn ) contains the dimensions of ker(L), that are precisely not included
in the Fq -vector space generated by (L(g1 ), L(g2 ), . . . , L(gn )).
L(x) having degree up to k − 1 implies that ker(L) must have dimension up to
k − 1 and therefore rk(x) ≥ n − (k − 1) = n − k + 1. Hence, the rank distance dr for
the code is bounded according to the definition of MRD codes.

4.5 Error Correction

Errors in rank codes are evaluated with respect to the rank weight. This is not quite
as straightforward as looking for errors in binary codes with the Hamming metric.
Nevertheless, rank codes are known to have powerful error-correcting capabilities
due to their structure.
Consider again the channel model where the received word r = c + e is a sum of
a codeword and an error vector of the same length.

Definition 13. [14] We then say that a rank error of rank ϵ occurs if rk(e | e ∈
Fnqm ) = ϵ.
 22

Rank codes can generally correct error patterns of the following type:

etotal = erandom + erow + ecol , (8)

where the total rank error is seen as a sum of entirely random errors, as well as column
and row rank erasures. These error types are described in greater detail in [14]. The
random errors are characterized as vectors of the form erandom = e1 u1 +e2 u2 +. . .+et ut ,
where ei ∈ Fqm and uj ∈ Fq are assumed to be linearly independent over Fq and ui
are assumed to have coordinates in Fq . Any other information is presumed unknown,
including the rank t.
The row and column erasures have similar vector form, except the row and column
components replacing the ui in the random error case are presumed as known to the
decoder.
The following upper bound for the error-correction capacity of Gabidulin codes
was given by Gabidulin and Pilipchuk in [18]:

Lemma 4.2. An [n, k, dr = n − k + 1] MRD code may simultaneously correct v row

erasures, r column erasures and ϵ random rank errors, given that

2ϵ + v + r ≤ dr − 1. (9)

Proof. Consider any n × n square code matrix. Erasing v rows and r columns results
in a (n − v) × (n − r) matrix code with rank distance at least d′r = dr − v − r. Hence,
the code allows for the correction random rank errors of rank ϵ, if ϵ ≤ (dr −v−r−1)
2
or,
equivalently,

2ϵ + v + r ≤ dr − 1.

5 Code-based Cryptography
Public-key cryptography is founded on the idea of having pairs of keys, consisting of
widely distributed public keys as well as private keys, the access to which is restricted
to the owner. The ideal model for secure communication is such that the sender
encrypts a message using the receiver’s public key. This action produces a ciphertext,
which can be easily decoded using the receiver’s private key.
This core idea is illustrated in Figure 1. The difficulty of decoding the ciphertext
without a private key depends on the difficulty of the mathematical problem on
which the cryptographic algorithm is based. Exhaustive searches, known as brute
force attacks are generally inefficient and successful attacks tend to exploit the subtle
structures in the key design.
The focus of this section is to introduce the concept of post-quantum cryptography
and then present some of the cryptographic schemes using linear codes in their key
design.
 23

Figure 1: Public-key Cryptography

5.1 Post-Quantum Cryptography

In the present age, there is increasing demand for fast, flexible, preferably affordable
and last but not least, secure communication schemes. Two of the first design criteria
are met with ease via public-key cryptography, given that the implementation has a
suitable design. These schemes are put to use by our phones when we send messages
to our friends, by our internet browsers when we connect to (secure) websites and by
our smart cards when they give our digital signature to other authentication devices.
Unfortunately, the most convenient and popular methods of public-key cryptogra-
phy are directly threatened by Shor’s algorithm running on a large enough quantum
computer [52]. It makes use of the quantum Fourier transform to break down the
periodicity of functions into approximate superpositions and then measuring them
[9]. This process requires 2n + 3 quantum bits or qubits and O(n3 log n) operations
with them in the the variant of Shor’s algorithm in [3]. These processes may also be
set to run in parallel in order to deliver solutions to problems previously thought
to be time consuming, and with exponential speed-up [7]. Such problems include
the integer factorization problem, the discrete logarithm problem and addition of
points on an elliptic curve, each of which underpins a popular conventional public-key
encryption scheme.
Another well-known quantum algorithm to emerge in the 90s is Grover’s algorithm
[23]. It has a broader range of applications, but the potential speed-up for computation
is not as striking as it is for Shor’s algorithm. At the core √ of it, Grover’s algorithm
can search roots to a function by finding one root for every N quantum evaluations
from a an input where roots occur one out of N inputs [9]. In theory, the threat of
Grover’s algorithm applies pressure directly to security parameters, even in cases
where the cryptographic system has no explicit flaws. In practise though, it may
turn out that quantum computers need to allocate resources to maintain stability in
their qubits, and in that case Grover’s algorithm may not be feasible as quantum
computers are scaled up in size.
The appeal of code-based cryptography is a consequence of desiring to be secure
against quantum computers. There are currently no known ways to use Shor’s
algorithm and deploy to it speed up the decoding of a general linear code and this
 24

has stood test of time. Alternative directions to code-based cryptography include,

for example lattice based approaches and multivariate polynomials [10]. With the
research field being as dispersed as it is, there are also concerted efforts to standardize
some form of post-quantum cryptosystem [1].

5.2 The McEliece Cryptosystem

Code-based cryptography originated from the scheme presented in the 1978 paper
by Robert McEliece [33]. Based on then a recent proof that the syndrome decoding
problem is NP-complete [6], the idea was to “scramble” and “permute” a generator
matrix of an error-correcting linear code with matrix multiplications to make it
indistinguishable from the generator matrix of a random linear code. This apparently
random generator matrix could be used as a public key for encrypting a message,
where t random errors would also be added to it. Since the code is chosen to be
error-correcting with up to t errors, decoding can be achieved with the intial generator
matrix – a private key to the cryptosystem.

The general idea of the McEliece scheme can be applied to multiple code structures.
The original implementation used binary Goppa codes [22] and although uses of
other codes have been proposed, most of them have had a structural attack proposed
against them, making them insecure. The Goppa code implementation, however,
remains not only secure but also achieves faster encryption and decryption than the
popular RSA cryptosystem based on integer factorization. All the known attacks
against the Goppa code implementation of the McEliece scheme have exponential
complexity in the size of the code.
Unfortunately, the large public key sizes in the Goppa code implementation are
what keep it from being implemented more in practice.

5.3 Binary Goppa Codes and Implementation for McEliece

Binary Goppa codes [22] — a subset of the more general class of codes described by
V.D. Goppa — have interesting properties for cryptographic applications. Namely,
the codes have a high error-correcting capacity with respect to code rate and the
parity-check matrix is difficult to distinguish from a random, full-rank binary matrix.

As the name suggests, binary Goppa codes are defined over the binary field F2 .
Moreover, an extension field of degree m is used with an irreducible polynomial f (α)
of degree m used as the modulus for F2 . Note that the field F2m (α) can also be
expressed as F2 [α]/f (α) in this case, since any polynomial mod f (α) has at most
degree m and all the combinations of m bits result in exactly 2m coefficients to give
2m elements. Due to f (α) being irreducible, each polynomial of degree less than m
in F2m (α) is guaranteed to have an inverse — a property necessary for the definition
of the code later on.
Before presenting the definition a binary Goppa code, let us first briefly discuss
two of its properties: the code support and the error correction capacity. Denote by
 25

σ a sequence of n distinct elements from the binary extension field F2m (α). We call
this the support and it is a subset of F2m . We can express polynomials in F2m (α)
with binary coefficients and degree at most m − 1 as [34]:
m−1
pj α j .
∑
p(α) = (10)
j=0

Using similar notation, each element in the code support may be expressed as:
m−1
σi,j αj ,
∑
σi (α) = (11)
j=0

where σi,j is the jth coefficient of support element σi (α).

For an error correction capacity of t errors, a polynomial g(x) of degree t is used,
such that
g(σi (α)) ̸= 0, σi (α) ∈ σ. (12)
One simple way to meet the above condition is to select an irreducible g(x), since
irreducible polynomials are square-free and this ensures the substitution of any σi (α)
polynomial with each x from g(x) does not cause all coefficients to cancel out.
The code itself is then defined as follows:

Definition 14. [34] Let σ denote a support with elements in F2m and let f (x) denote
an irreducible polynomial of degree t. A binary Goppa code is defined as:
n−1
n
∑ ci
C = c ∈ {0, 1} | ≡ 0 mod g(x). (13)
i=0 x − σi (α)

The definition contains the inverse of an element mod g(x), while the element is itself
a function of both x and α. For the inverse of an element e(x) mod g(x) in a finite
field, the extended Euclidean algorithm is generally applied and yields the following
equation:

e(x) · Ie + g(x) · Ig = e(x) · Ie mod g(x) = 1, (14)

where Ie and Ig denote the inverse elements of e(x) mod g(x) and g(x), respectively.
Taking into account that g(x) is a polynomial in both x and α yields the equation

(x − σi (α)) · Ie (x, α) + g(x, α) · Ig (x, α) = (x − σi (α)) · Ie (x, α) mod g(x, α) = 1. (15)

Note that x is the main term in the polynomial g(x), which gets its coefficients as
a function of α. So, for example, letting σ0 = α + α2 gives x − σ0 = x + α + α2 =
x0 · (α + α2 ) + x1 · 1.
Contrary to some other code types, the generator matrix for a Goppa code is
usually not constructed directly, but is instead derived through the parity check
 26

matrix[22]. An explicit construction for the parity check matrix is as follows [11][34]:

⎡ ⎤⎡ ⎤
1 0 ··· 0 1 1 ··· 1
gt−1 1 ··· 0 ⎥ ⎢ σ0 (α) σ1 (α) · · · σn−1 (α)
⎢ ⎥⎢ ⎥
⎢ ⎥
2
σ12 (α) 2
⎢ ⎥⎢ ⎥
HΓ =
⎢
⎢ gt−2 gt−1 · · · 0 ⎥ ⎢ σ0 (α)
⎥ ⎢ · · · σn−1 (α) ⎥
⎥
⎢ .. .. . . .. ⎥ ⎢
⎥ ⎢ .. .. .. .. ⎥
⎢
⎣ . . . . ⎦⎣ . . . . ⎥
⎦
t−1 t−1 t−1
g1 g2 ··· 1 σ0 (α) σ1 (α) · · · σn−1 (α)
(16)
1
⎡ ⎤
g(σ0 (α))
0 ··· 0
⎢
1 .. ⎥
0 . 0
⎢ ⎥
g(σ1 (α))
⎢ ⎥
·⎢ ..
⎥.
⎢ .. ⎥
⎢
⎣ 0 0 . . ⎥
⎦
1
0 ··· ··· g(σn−1 (α))

Not all parity check matrices constructed as in (16) are convertible to generator
matrices. It is estimated that around 33% of parity check matrices constructed
from random code supports have linearly independent columns in the right-most
(n − k) × (n − k) block, allowing for the derivation of a generator matrix as described
in equations (2) and (3) [34].

Encryption and Decryption in McEliece

With a generator matrix GΓ for a Binary Goppa code constructed, the McEliece
cryptosystem instructs to first scramble and permute the generator matrix. For this
two matrices are needed:

• S, a random, k × k, non-singular scrambling matrix

• P, an n × n, permutation matrix with exactly one “1” in each row and column

These matrices are used to conceal the structure of the generator matrix by
multiplying them with GΓ as:

ĜΓ = SGΓ P. (17)

To send message M, we multiply it by ĜΓ and add some error vector e, such
that
T = MĜΓ + e (18)
is transmitted. This transmission is then received as R and the decryption process
starts with
RP−1 = MSGΓ + eP−1 , (19)
where the term eP−1 contains the same number of errors (and has the same Hamming
weight) as e. These errors are removed via a decoding algorithm, such as the one
presented by Patterson [44]. Effectively, the decoding algorithm extracts M from
MGΓ + e. Finally, it remains to multiply from the right by S−1 to fully recover M.
 27

Public and Private Keys

While each implementation of the McEliece cryptosystem retains as private keys
the matrices S and P, as well as a suitable decoding algorithm D for the code, the
Goppa code variant may add the support σ and the modulus g(x, α) to the list of
private keys. These keys are listed in Table (2).

Table 2: The public and private keys for McEliece (Goppa)

Public Private
Vector length n Permutation matrix P (n × n)
Field exponent m Scrambling matrix S (k × k)
Plain text length k Code support σ
Error correction capacity t mod g(x, α)
The (k × (n − k)) redundancy part of ĜΓ Efficient decoding algorithm D

Security
The McEliece cryptosystem with a binary Goppa code implementation is projected
to have a reasonable level of post-quantum security [8]. While Shor’s algorithm is
able to take advantage of certain periodic structures in other cryptography, Goppa
codes in McEliece do not admit such structure. However, information set decoding
based brute force attacks have been around since 1962 and have been improved on
over the years [45]. The quantum-based Grover’s algorithm could further speed up
these brute force attacks [23]. The authors of the Classic McEliece submission for the
National Institute of Standards and Technology (NIST) project for post-quantum
cryptography also point out how careless use of the cryptosystem could open up
attacks such as adaptive chosen ciphertext attacks [8]. Nevertheless, security remains
the prevalent competitive advantage of this approach in post-quantum cryptography,
while the most glaring disadvantage is the large public key size.

5.4 The GPT Cryptosystem

The Gabidulin-Paramonov-Tretjakov (GPT) cryptosystem was originally proposed
in 1991 [13] and has since then been refined [15][40]. It is often described as an
equivalent to the McEliece cryptosystem, implemented or codes over the rank metric
instead of the Hamming metric. As described in the chapter on rank error-correcting
codes, comparatively smaller public key sizes remain the driving motivation for
pursuing a rank metric based system over McEliece.
Using Gabidulin codes, the system is parametrized by the following [42]:
• Extension field parameters q and m

• Code size parameters n and k

 28

n−k−1
• Error-correction parameter t < 2

• Additional security parameter s ≤ min{k, t} introduced by Overbeck [42]

Key Generation, Encryption and Decryption in the GPT Cryptosystem

In addition to selecting a random generator matrix for our code, we randomly generate
some matrices used to obscure the original generator matrix. The following matrices
are generated randomly over Fqm :

• Gk , a k × n generator matrix of a Gabidulin code with parameters (n, k, d)

• X, an n × k random distortion matrix, having rank t over Fq and rank s over

Fq m

• S, a k × k non-singlar row scrambler matrix

An efficient decoding algorithm D is identified for the code and the structure of
Gk is concealed by computing Ĝk = S(G + X). Finally, we compute the error rank
weight ϵ = n−k
2
− t.
A plaintext message vector m ∈ Fkqm is converted into ciphertext c by:

c = mĜk + e, (20)

where e ∈ Fnqm is a random vector of rank weight ϵ.

For the decoding part, an application of the decoding algorithm yields

D(c) = mSG (21)

and the message can be retrieved. Since the ciphertext was only at a distance of n−k
2
from the code, and since the rank weight rk(mSX) ≤ t, the decoding should correct
all of the induced errors.

Public and Private Keys

The public and private keys for the system are listed in Table (3).

Table 3: The public and private keys for GPT (Gabidulin)

Public Private
Public generator matrix Ĝk (k × n) Efficient decoding algorithm D
Error rank parameter ϵ Distortion matrix X (n × k)
Row scrambling matrix S (k × k)

The volume of the public key is k · n · m · log2 (q) bits and the information rate is
 29

k
n
[40]. By comparison these public key sizes, as originally proposed would be up to
50 times smaller than respective public key sizes in the McEliece scheme.

Security
Confidence in Gabidulin code-based implementations has been shaken by effective
structural attacks, first by Gibson [20] and later by Overbeck [43]. Yet, it remains
an open question whether or not a suitable code structure, or some variant of the
cryptoystem itself could provide a reasonable level of security.
The key generation notably lacks an equivalent to the column permutation matrix
P in the McEliece scheme. There has been much optimism for such improvements
or similar to counteract the threat of structural attacks [17][40]. The rank metric
remarkably allows for the use of a column scrambler matrix in place of column
permutation matrix, since the necessary operations do not cause unwanted rank
errors as they would for the Hamming metric [40]. Unfortunately, such variants
among others have recently shown to be insecure [42][26].
Fairly recent improvements to non-structural attacks also pose somewhat of a
concern, as they restricts certain parameter sets as insecure without requiring any
structural weaknesses [19].
It remains to be seen how long other code structures designed to resist general-
izations for attacks by Gibson and Overbeck are able to do so. In the next chapter,
we look to twisted codes for a potential solution.

6 Attacks and Countermeasures

The literature on code-based cryptography has seen a consistent cycle of generating
ingenious solutions to counteract previous structural weaknesses, only to be shown
vulnerable to yet another attack [20][21][40][42][46][30].
On the attacking side, new distinguishers to exploit structural properties are
constantly found and existing key recovery algorithms are further combined and
generalized to break down elusive variants of the cryptosystems [20][41][26][30].
Meanwhile the countermeasure side have attempted everything from new code
families to modified column scramblers and twisted codes [13][40][46].
On some occasions, a vulnerability is averted by simply tweaking the parameter
set slightly. At other times, a powerful new structural attack emerges, proving
multiple implementations fundamentally insecure all at once.

6.1 Overbeck’s Attack

In the field of rank metric based cryptography, Overbeck’s attack has stirred waves
of uncertainty and many dismantled rank based cryptography schemes have since
been re-examined [41][42][43].
The impact of the specific attack merits a more detailed view into how the
weaknesses in the GPT cryptosystem surface in the first place and how an attacker
might recover the private keys.
 30

Source of structural weakness

In the process of computing the public generator matrix with

Ĝk = S(G + X),

the application of the distortion matrix X reduces the error-correction capability of

the code. In other words, the rank weight of the artificial error vector e has to be
reduced below what would otherwise still be correctable with the code [38].

Outline of the Attack

The attack applies Λi on the public generator matrix, an operator which applies
the Frobenius operation i ∈ N times. The expected outcome of such an operation
for a random linear code would be that the dimension of the code is increased by
k [38]. Instead, Overbeck showed that the dimension of Ĝk increases by only 1 for
each Frobenius operation. The rank Ĝk , as well as the underlying code, is then
distinguished by selecting i = n − k − 1, in which case the co-dimension (difference
between dimensions in this case) to the public generator matrix becomes 1. In other
words, the dimension of Ĝk is n, while the dimension of Λi (Ĝk ) is n − 1.
The Frobenius operator, or q-sum Λi is defined in [43] as follows:

Definition 15. Let M be a random l × n matrix over Fq and let i ∈ N. Then the
(i+1)l×n
mapping λi : Fl×n
q m ↦→ Fq m is defined as:
⎡ ⎤
M
M[1]
⎢ ⎥
⎢ ⎥
⎢ ⎥
Λi (M) :=
⎢
⎢ M[2] ⎥,
⎥
(22)
⎢ .. ⎥
⎢
⎣ . ⎥
⎦
M[i]
i
where M[i] denotes Mq .

So, the distinguisher effectively splits the two cases as:

• dim Λi (C) = min{n, ki}, on average for a random linear code C

• dim Λi (CG ) = min{n, k + i}, with high probability for a random Gabidulin
code CG

The step-by-step key recovery process is presented in Algorithm (2) found in

Appendix A.
The attack also relies on Λn−k−1 (Ĝk ) yielding a co-dimension of 1 and on any
column scrambler matrix P being selected from Fq . While both of these criteria
have been addressed since the publication of the attack (e.g. [48][16]), these further
improvements are out of the scope for this inspection, or have since then been shown
inadequate [38].
 31

6.2 Twisted Gabidulin Codes

Gabidulin codes were considered the only construction for maximum rank distance
codes for quite some time before [51] (and independently also [37]) had the idea of
using a variant of linearized polynomials to define MRD codes that are not equivalent
to Gabidulin codes. These codes were named twisted Gabidulin codes.
The linearized polynomials from [51] were later generalized to cover a broader
set with all possible linear combinations also included [47]. Hence the authors of
[47] refer to their own construction as twisted Gabidulin codes, implying that those
presented in [51] and [37] are special twists, since they are contained in the more
general construction.
There are two prominent open questions for twisted Gabidulin codes. The first
one being whether or not there exists an efficient decoding algorithm and the second
is to consider if an implementation in the GPT cryptosystem would be vulnera-
ble to structural attacks. The former issue is outside the scope of this thesis. For
the latter, on the other hand, the goal is to further continue the considerations in [46].

The authors of [46] describe twisted Gabidulin codes as:

Definition 16. ([[46], Def. 4]) Let n, k, l ∈ N with k < n and l ≤ n − k. Choose
the following:

• a hook vector h ∈ {0, . . . , k − 1}l

• a twist vector t ∈ {1, . . . , n − k}l with distinct ti

• η ∈ (Fqm \{0})l .

The set of [k, k, h, η]-twisted linearized polynomials over Fqm is defined as

⎧ ⎫
⎨ k−1 l ⎬
n,k
fi x[i] + ηj fhj x[k−1+tj ] : fi ∈ Fqm .
∑ ∑
Pt,h,η := f= (23)
⎩ ⎭
i=0 j=1

Let α1 , . . . , αn ∈ Fqm be linearly independent over Fq and write α = [α1 . . . . , αn ].

The [α, t, h, η]-twisted Gabidulin code of length n and dimension k is given by
{ }
n,k
Cα,t,h,η [n, k] = [f (α1 ), f (α2 ), . . . , f (αn )] : f ∈ Pt,h,η . (24)

The definition results in the following generator matrix for a twisted Gabidulin code:
 32

α
⎡ ⎤
⎢
⎢ α[1] ⎥
⎥
⎢ .. ⎥
.
⎢ ⎥
⎢ ⎥
α[h1 −1]
⎢ ⎥
⎢ ⎥
⎢ ⎥
[h1 ] [k−1+t1 ] ⎥
⎢
⎢ α + η1 α ⎥
⎢ [h1 +1] ⎥
⎢ α ⎥
GT G = .. ⎥, (25)
⎢ ⎥
⎢
⎢
⎢ . ⎥
⎥
[hl −1]
α
⎢ ⎥
⎢ ⎥
[hl ] [k−1+tl ] ⎥
⎢ ⎥
⎢
⎢ α + ηl α ⎥
⎢
⎢ α[hl +1] ⎥
⎥
⎢
.. ⎥
.
⎢ ⎥
⎣ ⎦
α[k−1]
where h1 < . . . < hl .

Example 7. A twisted Gabidulin code of length 10 and dimension 5 could have

hook vector h = [1, 3] and twist vector t = [2, 4]. The generator matrix would have
the following form: ⎡ ⎤
α
⎢ [1]
⎢ α + η1 α[6] ⎥
⎥

α[2]
⎢ ⎥
GT G = ⎢⎢
⎥,
⎥ (26)
⎢ [3] [8] ⎥
⎣ α + η 2 α ⎦
α[4]
where η1 , η2 ∈ Fqm are some fixed parameters.

Intuitively, the hook vector determines which rows are twisted and the twist vector
dictates the q-power from k to n of the added twist element. The parameter η is the
coefficient of the twist element and it is chosen such that it either belongs to or does
not belong to certain sub-fields of Fqm . The choice of η allows the dimension of the
code to be k, while the elements of the linearized polynomial span a Fq subspace of
dimension n.
This construction was shown in [47] to be MRD and in [46] it was shown to resist
Overbeck’s structural attack. This resistance comes from Overbeck’s Λi operation
(q-sum) not distinguishing it from a random code as easily when the parameters for
the twists are chosen carefully.
The parameter set restriction proposed in [[46], Thm. 4]1 ensures that each distinct
element tj in the twist vector tj ∈ {1, . . . , n − k}l from the code CT G generates a
distinct linearly independent basis element in the q-sum Λi (GT G ). Thus, large
dimension for the q-sum can be consistently achieved with this construction, making
twisted Gabidulin codes resilient to that type of structural attacks.
1
The constraints on ti in Thm. 4 contradict the domain for t set in Def. 4
 33

6.3 Twisted Reed-Solomon Codes

Reed-Solomon codes being a close analogue to Gabidulin codes, it is no surprise that
twisted Reed-Solomon codes have already been considered in the literature [4]. In
fact, their construction was inspired by Sheekey’s class of early twisted Gabidulin
codes [51]. The combination of these two codes then was then used as a template
for the description of the more generalized twisted Gabidulin codes in [47]. This, in
turn, motivated the generalization of the single twist Reed-Solomon codes in [4] to
the multi twist composition [5].
The analogy of the two code families is most evident with the definitions of their
respective polynomials. Whereas a set of twisted linearized polynomials was used
in the rank metric definition, the Hamming metric equivalent uses a type of twisted
polynomials.

Definition 17. ([[5], Def. 1]) Let h, t, η be chosen as in (16), except η ∈ Fnq . The
set of [k, t, h, η]-twisted polynomials is defined as
⎧ ⎫
⎨ k−1 l ⎬
n,k
f i xi + ηj fhj xk−1+tj : fi ∈ Fq .
∑ ∑
Pt,h,η := f= (27)
⎩ ⎭
i=0 j=1

With the help of distinct basis elements α1 , . . . , αn ∈ Fq , we can construct the twisted
Reed-Solomon code as
{ }
n,k
Cα,t,h,η [n, k] = [f (α1 ), f (α2 ), . . . , f (αn )] : f ∈ Pt,h,η , (28)

where k < n and t ≤ n − k.

In general, twisted Reed-Solomon codes are not maximum distance separable,
although certain sub-classes may be constructed as such. They were also shown to
be largely distinct from generalized Reed-Solomon codes [49][4].
For cryptographers, this is yet another intriguing code family. A large sub-
class of MDS Reed-Solomon codes was recently theorized to be out of reach for
certain structural attacks against the McEliece cryptosystem [5]. These attacks
included Schur square distinguishing, the three Wieschebrink attacks and the attack
by Sidelnikov and Shestakov [?][58][53].
Whilst the Sidelnikov-Shestakov attack breaks McEliece implementations with
general Reed-Solomon codes in polynomial time, the distinguisher in that attack
relies on the matrix P in the systematic form of the generator matrix [Ik |P] being
a Cauchy matrix specifically when the code is a generalized Reed-Solomon code
[50]. This criterion is not met with twisted Reed-Solomon codes, which are rarely
equivalent to the general Reed-Solomon codes.
The Schur square distinguishing process is also worth analyzing. For two codes,
the Schur product is the linear span

C1 ⋆ C2 := ⟨c1 ⋆ c2 | c1 ∈ C1 , c2 ∈ C2 ⟩Fq .

Hence, the Schur square is the product C ⋆ C, the dimension of which is the distin-
guishing feature. The two cases for the distinguisher are roughly
 34

{ }
• dim C ⋆ C = min n, 12 k(k + 1) with high probability for a random linear code
C

• dim CT R ⋆ CT R = min {n, 2k − 1}, when k < n2 for a Reed-Solomon code CT R ,

or any shortening at up to 2 positions of CT R [?].

The twisted codes from [5] and their shortenings at up to 2 positions were shown to
always have Schur square dimension n and dimension k > n2 , so this attack fails in
its premise.

6.4 Attack on Twisted Reed-Solomon Codes

Julien Lavauzelle and Julian Renner observed in 2019 that although twisting Reed-
Solomon codes protects them from previously known attacks, they still have enough
structure to make other structural attacks deployed against them viable [30]. The
authors presented an efficient approach, which uses the Schur square of a subfield
subcode of the public code to enable the Sidelnikov-Shestakov attack.
They key vulnerability is that the MDS construction for twisted Reed-Solomon
codes is done over a chain of subfields Fqm0 ⊊ Fqm1 . . . ⊊ Fqml = Fq0 , where mi
are non-negative integers m0 being the smallest, the basis elements α1 , . . . , αn are
distinct for i = 1, . . . , n, so we need q ≥ n and αi are selected
√ from the field Fqm0 [5].
In this MDS construction, n and k are chosen with 2 n + 6 < k ≤ n2 − 2 [30]. The
public code is intersected with the smallest subfield in the chain, Fq , to obtain part
of the structure of a Reed-Solomon code:
{ }
n,k
Cpub ∩ Fnq = [f (α1 ), f (α2 ), . . . , f (αn )] : f ∈ Pt,h,η ∩ Fq [x] . (29)

In the attack shown in [59], Wieschebrink remarks that applying the Schur square to
random subcodes of Reed-Solomon codes outputs a Reed-Solomon code with high
probability. Thus, the Sidelnikov-Shestakov attack works on the Schur square code
of the subfield subcode with high probability.
Letting ĜT RS denote the public generator matrix of a twisted Reed-Solomon code in
the McEliece cryptosystem, the algorithm detailed in Appendix B shows the step-by-
step process of retrieving an alternative valid secret key (S∗ , α∗ , η ∗ ) from ĜT RS . In
the algorithm pseudocode ([[30], Algorithm 1]), the function names SubfieldSubcode,
Square and SidelShest refer to intersecting for the subfield subcode, taking the Schur
square and applying the Sidelnikov-Shestakov attack, respectively.
 35

The function GenSub maps

⎡ ⎤
1 ... 1
⎢
⎢ α1 ... αn ⎥
⎥
⎢
.. .. .. ⎥
. . .
⎢ ⎥
⎢ ⎥
α1h1 −1 . . . αnh1 −1
⎢ ⎥
⎢ ⎥
⎢ ⎥
α1h1 +1 . . . αnh1 +1
⎢ ⎥
⎢ ⎥
[α1 , . . . , αn ] ∈ Fnq ↦→ .. .. ∈ F(k−l)×n .
⎢ ⎥
⎢ ⎥ q
⎢
⎢ . . ⎥
⎥
α1hl −1 . . . αnhl −1
⎢ ⎥
⎢ ⎥
α1hl +1 . . . αnhl +1
⎢ ⎥
⎢ ⎥
⎢ ⎥
⎢ .. .. ⎥
⎢
⎣ . . ⎥
⎦
α1k−1 ... αnk−1

The interpolation in the algorithm maps (a, b) ∈ Fnq × Fnq0 to g ∈ Fnq with the
condition n
gj aj−1
∑
i = bi
j=1

for i = 1, . . . , n. The last function, GTRS, matches the obtained α∗ and η ∗ with the
generator matrix G∗ of suitable Reed-Solomon code [30]. S∗ can be computed such
that S∗ G∗ = ĜT RS . The algorithm runs in polynomial time with O(n4 ) operations
and asserts that the construction of [5] as insecure for at least most practical parameter
sets.

6.5 Analysis of the Same Attack on Twisted Gabidulin Codes

The success of subfield subcodes with exposing the structure in twisted Reed-Solomon
codes begs the question of how a similar attack would fare against a rank based cryp-
tosystem implementing twisted Gabidulin codes. The authors of the attack in [30]
suspect the approach could be used to attack the GPT system with twisted Gabidulin
codes presented in [46] and also conducted some experimental simulations to test
this hypothesis. Julien Lavauzelle and Julian Renner then generously shared their
SageMath [56]2 implementation for an attack combining the subfield subcode part
of the attack in Appendix B with Overbeck’s attack, as described in e.g. Appendix A.

A variation of the GPT cryptosystem is used to implement twisted Gabidulin codes

in [46]. This adaptation makes use of a column permutation matrix P and the public
generatior matrix is computed as:

ĜT G = S[X|GT G ]P, (30)

where ĜT G is the (k × n) generator matrix of a twisted Gabidulin code of rank k,
S is a random (k × k) row scrambling matrix of full rank over Fqm , X is a random
(k × λ) distortion matrix with rank 1 ≤ s ≤ λ and P is a random ((n + λ) × (n + λ))
2
System for Algebra and Geometry Experimentation, v.8.9
 36

column permutation matrix of full rank over Fq . For twisted Gabidulin codes, the
restrictions of the twisted Reed-Solomon system for parameters q ≥ n, n and k do not
apply. However, recall that for twisted Gabidulin codes αi are linearly independent
in addition to being distinct.
From this system, the attack aims to recover an alternate private key (S∗ , α∗ , η ∗ , P∗ )
directly from the twisted public generator matrix ĜT G . Overbeck’s attack then gets
applied to CˆT G ∩ Fq . A successful application of Overbeck’s attack yeilds α∗ and
P∗ , with η ∗ then being obtained via interpolation as in Appendix B and S∗ being
computed such that
S∗ G∗ = (ĜT G P∗−1 )[λ+1:n] ,
where G∗ is the generator matrix of an [α∗ , t, h, η ∗ ]-twisted Gabidulin code and only
the final n − λ coordinates are being considered from ĜT G P∗−1 .
Figure 2 illustrates the structures of generator matrices that are relevant to
the attack. It demonstrates how the generator matrix of a twisted Gabidulin code
incorporates higher q-powers of α without increasing the dimension of the code. It
also highlights how a generator matrix for the subfield subcode is void of these higher
q-powers. In the figure, β is some affine transformation of α.

Figure 2: Structures of generator matrices

Experimental Approach
The proposed parameter sets from [[46], Table 1] were a natural starting point for
experimentation. The attack failed on each of those sets of parameters in the Sage-
Math implementation. To narrow down the problem, the next idea was to look for
parameter sets for which that attack could directly resolve. Lavauzelle and Renner
 37

had discovered that a choice of small λ and an s, such that X has full rank over Fq
were promising research directions [30].

Before fully committing to the analysis of parameters λ and s, some testing was
done to see if the twists, specifically the types of twists to achieve large q-sum
dimension proposed in [[46], Thm. 4], would have some carry over effect into the
subfield subcode. This was done under awareness of the fact that the subfield subcode
structure had already been used to extract adequate structure from the code to
enable Overbeck’s attack for some parameters.
Various choices for the degrees of relative extension fields were also tried out.
These relative extensions are constructed with q m0 replacing the base field degree q
in the code construction phase and q m1 being inserted as the larger extension degree
in place of q m with 1 < m0 < m1 ∈ N. This is still done over the base field Fq and
there is a chain of subfields, i.e. Fq ⊊ Fqm0 ⊊ Fqm1 . The binary field with q = 2 was
used as the base field for all experimentation and the code length was set to n = m0 .

In the search for patterns occurring with λ and s, different parameter choices were
categorized solely on the basis of the attack succeeding. In the successful cases, the
parameters were simply recorded, whereas in the unsuccessful cases the breaking
point of the algorithm and variable values just prior to that point were taken note of.
For parameter sets with large values for n, k, λ only one instance was simulated due
to these simulations being time consuming, while parameter sets with comparatively
small n, k, λ (k ≤ 34) were simulated 10 times each.
The last step was to analyse the patterns in λ and s, especially w.r.t. n and k
and compare the findings to those in the literature.

Experimental Results
As expected, the twists in the code did not prevent or slow down the attack at all.
There was no noticeable change in the running times for the algorithm when number
or structure of twists were varied. Not even when maximal q-sum dimension for
the public code was pursued. Selecting m1 = 2m0 over m1 = 4m0 for the relative
extension fields also had no observable impact.
The feasible choices for λ appeared to range from 1 to some largest value λL
specific to the choice of n and k. Further, the choice of a valid s then depended on
n, k and λ, where an s corresponding to a full Fq rank was always viable. The trend
for suitable s then turned out in consecutive integers down from λ to some minimum
value, which was some function of n, k and λ.
Table 4 shows some sets of parameters, revealed to be broken by experimental
simulation.
 38

Table 4: Experimentally broken parameter sets

k n λL set of s for λL
18 26 3 {3}
21 33 5 {4, 5}
32 48 8 {7, 8}
34 52 9 {7, 8, 9}
46 80 14 {11, 12, 13, 14}
82 140 53 {i ∈ N | 32 ≤ i ≤ 53}

The uniting feature for these parameter sets is that they cause the right kernel of the
public generator matrix to have rank 1, where the right kernel is the set of vectors v
for which ĜT G v = 0. Conversely, for almost every parameter set where the attack did
not succeed, the rank of the right kernel was greater than one. The only exception
to this within the tested parameter sets emerged with λ = 3, s = 2. With parameter
sets having λ > max λ, the subfield subcode structure does not expose the structure
of the public code. This however does greatly narrow down the search space for
potential attackers.

For the cases where λ ≤ λL , corresponding parameter selections have been al-
ready discussed in the literature, as P. Loidreau suggested restricting the parameters
of a distortion matrix X in Gabidulin codes for the GPT system [32]. The intent was
to guarantee a sufficiently high dimension for the right kernel of the public generator
matrix and it was proposed as an early countermeasure in 2010 to Overbeck’s attack
on Gabidulin codes.
Loidreau’s design was addressed only fairly recently, as Horlemann-Trautmann
et. al. showed in 2018 a way to extend Overbeck’s attack further and to focus on
retrieving elements of rank one directly from the code, disregarding the dual code
entirely [27].
In any case, these considerations are no longer specific to twisted codes, and the
simulation results support the claim that subfield subcodes may completely negate
any practical cryptographic advantage from twisted codes, when λ ≤ λL . In addition,
the choice of secure parameters seems to be severely restricted in the λ > λL case.
 39

7 Conclusion
This thesis has covered a diverse array of topics in code-based cryptography, ulti-
mately leading to the description and assessment of twisted codes. Twisted codes
were the driving aspiration for much of the thesis, with the primary goal of having
some meaningful discussion on them in light of the most recent publications. The
topic can be quite intimidating at first, since the concepts build and expand upon
themselves, as is the case in other areas of mathematics correspondingly. Hence,
one of the main contributions of the thesis is the contextual narrative, which leads
the reader all the way from learning the definition for a linear code, to potentially
grasping the essence of structural vulnerabilities in code-based cryptography and
how these challenges are approached. This write-up makes ample use of existing
literature and serves also as a survey to the state-of-the-art research. The practical
experimentation and simulation make for the second main contribution.

As for further research regarding twisted codes, one worthwhile prospect would
be to look into the possibility of masking the subfield subcode structure. This would
immediately reinstate twisted codes as a potentially viable solution for secure com-
munications in the future. Another research direction would be to further analyse the
numerous subfamilies of twisted codes, since they are a broad, recently discovered and
largely unexplored family of codes overall. The fact that the specific constructions
from [46] and [5] are shown to be mostly insecure does not imply the same for other
subfamilies.

Rank metric codes have yet again been reconfirmed as highly susceptible to structural
attacks, even though the episode with twisted codes has returned to more or less same
situation as where it started — with the construction and near complete dismantling
of another supplementary feature to conceal rank code structure. Nevertheless,
continued interest in rank codes is bound to live on, with pressure on one side from
the ever more imminent threat posed by quantum computers and on the other hand,
the unfeasible public key sized of the secure post-quantum alternatives. Besides, the
field of code-based cryptography is a constant back and forth exchange of ideas and
in time it will be due for a novel countermeasure.
 40

References
[1] Gorjan Alagic, Jacob Alperin-Sheriff, Daniel Apon, David Cooper, Quynh Dang,
Yi-Kai Liu, Carl Miller, Dustin Moody, Rene Peralta, et al. Status report on
the first round of the NIST post-quantum cryptography standardization process.
US Department of Commerce, National Institute of Standards and Technology,
2019.

[2] Daniel Augot, Lejla Batina, Daniel J Bernstein, Joppe Bos, Johannes Buchmann,
Wouter Castryck, Orr Dunkelman, Tim Güneysu, Shay Gueron, Andreas Hülsing,
et al. Initial recommendations of long-term secure post-quantum systems.
Available at pqcrypto. eu. org/docs/initial-recommendations. pdf, 2015.

[3] Stephane Beauregard. Circuit for shor’s algorithm using 2n+ 3 qubits. arXiv
preprint quant-ph/0205095, 2002.

[4] P. Beelen, S. Puchinger, and J. Rosenkilde né Nielsen. Twisted reed-solomon

codes. In 2017 IEEE International Symposium on Information Theory (ISIT),
pages 336–340, June 2017.

[5] Peter Beelen, Martin Bossert, Sven Puchinger, and Johan Rosenkilde. Structural
properties of twisted reed-solomon codes with applications to cryptography. In
2018 IEEE International Symposium on Information Theory (ISIT), pages
946–950. IEEE, 2018.

[6] Elwyn Berlekamp, Robert McEliece, and Henk Van Tilborg. On the inherent
intractability of certain coding problems (corresp.). IEEE Transactions on
Information Theory, 24(3):384–386, 1978.

[7] Daniel J Bernstein. Introduction to post-quantum cryptography. In Post-

quantum cryptography, pages 1–14. Springer, 2009.

[8] Daniel J Bernstein, Tung Chou, Tanja Lange, Ingo von Maurich, Rafael Misoczki,
Ruben Niederhagen, Edoardo Persichetti, Christiane Peters, Peter Schwabe,
Nicolas Sendrier, et al. Classic mceliece: conservative code-based cryptography.
NIST submissions, 2019.

[9] Daniel J. Bernstein and Tanja Lange. Post-quantum cryptography-dealing with

the fallout of physics success. IACR Cryptology ePrint Archive, 2017:314, 2017.

[10] Lily Chen, Lily Chen, Stephen Jordan, Yi-Kai Liu, Dustin Moody, Rene Peralta,
Ray Perlner, and Daniel Smith-Tone. Report on post-quantum cryptography.
US Department of Commerce, National Institute of Standards and Technology,
2016.

[11] R. Overbeck D. Engelbert and A. Schmidt. A summary of mceliece-type

cryptosystems and their security. Cryptology ePrint Archive, Report 2006/162,
2006. [Link]
 41

[12] Ph. Delsarte. Bilinear forms over a finite field, with applications to coding
theory. Journal of Combinatorial Theory, Series A, 25(3):226–241, 1978.

[13] E. M. Gabidulin, A. V. Paramonov, and O. V. Tretjakov. Ideals over a

non-commutative ring and their application in cryptology. In Advances in
Cryptology — EUROCRYPT ’91, pages 482–489. Springer Berlin Heidelberg,
1991.

[14] Ernst M. Gabidulin. Theory of codes with maximum rank distance. Problemy
Peredachi Informatsii, 21(1):3–16, 1985.

[15] Ernst M. Gabidulin. Public-key cryptosystems based on linear codes. Citeseer,

1995.

[16] Ernst M Gabidulin. Attacks and counter-attacks on the gpt public key cryp-
tosystem. Designs, Codes and Cryptography, 48(2):171–177, 2008.

[17] Ernst M Gabidulin, Alexei V Ourivski, P Farrell, M Darnell, and B Honary.

Improved gpt public key cryptosystems. Coding, Communications, and Broad-
casting, pages 73–102, 2000.

[18] Ernst M. Gabidulin and Nina I. Pilipchuk. Error and erasure correcting
algorithms for rank codes. Designs, codes and Cryptography, 49(1-3):105–122,
2008.

[19] Philippe Gaborit, Olivier Ruatta, and Julien Schrek. On the complexity of the
rank syndrome decoding problem. IEEE Transactions on Information Theory,
62(2):1006–1019, 2015.

[20] J. Keith Gibson. Severely denting the gabidulin version of the mceliece public
key cryptosystem. Des. Codes Cryptography, 6(1):37–45, July 1995.

[21] J. Keith Gibson. The security of the gabidulin public key cryptosystem. In
Eurocrypt, 1996.

[22] Valerii Denisovich Goppa. A new class of linear correcting codes. Problemy
Peredachi Informatsii, 6(3):24–30, 1970.

[23] Lov K Grover. A fast quantum mechanical algorithm for database search. arXiv
preprint quant-ph/9605043, 1996.

[24] Richard W. Hamming. Error detecting and error correcting codes. The Bell
system technical journal, 29(2):147–160, 1950.

[25] Israel N. Herstein. Topics in algebra. John Wiley & Sons, 2006.

[26] Anna-Lena Horlemann-Trautmann, Kyle Marshall, and Joachim Rosenthal.

Considerations for rank-based cryptosystems. In 2016 IEEE International
Symposium on Information Theory (ISIT), pages 2544–2548. Ieee, 2016.
 42

[27] Anna-Lena Horlemann-Trautmann, Kyle Marshall, and Joachim Rosenthal.

Extension of overbeck’s attack for gabidulin-based cryptosystems. Designs,
Codes and Cryptography, 86(2):319–340, 2018.

[28] Loo-Keng HUA. A theorem on matrices over a sfield and its applications. In
Bulletin of the American Mathematical Society, volume 55, pages 1046–1046.
Amer Mathematical Soc 201 Charles St, Providence, RI 02940-2213, 1949.

[29] Gareth A. Jones and J. Mary Jones. Information and coding theory. Springer
Science & Business Media, 2012.

[30] Julien Lavauzelle and Julian Renner. Cryptanalysis of a system based on twisted
reed-solomon codes. arXiv preprint arXiv:1904.11785, 2019.

[31] Pierre Loidreau. Etude et optimisation de cryptosystèmes à clé publique fondés

sur la théorie des codes correcteurs. PhD thesis, 2001.

[32] Pierre Loidreau. Designing a rank metric based mceliece cryptosystem. In In-
ternational Workshop on Post-Quantum Cryptography, pages 142–152. Springer,
2010.

[33] Robert J. McEliece. A public-key cryptosystem based on algebraic. Coding

Thv, 4244:114–116, 1978.

[34] Marcus Michiel. White paper on mceliece with binary goppa codes. Technical
report, Department of Mathematics and Computer Science, Eindhoven University
of Technology, February 2019.

[35] Stefan M. Moser and Po-Ning Chen. A student’s guide to coding and information
theory. Cambridge University Press, 2012.

[36] Oystein Ore. On a special class of polynomials. Transactions of the American

Mathematical Society, 35(3):559–584, 1933.

[37] Kamil Otal and Ferruh Özbudak. Explicit constructions of some non-gabidulin
linear maximum rank distance codes. Advances in Mathematics of Communica-
tions, 10(3), 2016.

[38] Ayoub Otmani, Hervé Talé Kalachi, and Sélestin Ndjeya. Improved cryptanal-
ysis of rank metric schemes based on gabidulin codes. Designs, Codes and
Cryptography, 86(9):1983–1996, 2018.

[39] Alexei V. Ourivski. Recovering a parent code for subcodes of maximal rank
distance codes. In Proc. of WCC, volume 3, pages 357–363, 2003.

[40] Alexei V. Ourivski and Ernst M. Gabidulin. Column scrambler for the gpt
cryptosystem. Discrete Applied Mathematics, 128(1):207–221, 2003.
 43

[41] Raphael Overbeck. A new structural attack for gpt and variants. In Ed Dawson
and Serge Vaudenay, editors, Progress in Cryptology – Mycrypt 2005, pages
50–63, Berlin, Heidelberg, 2005. Springer Berlin Heidelberg.

[42] Raphael Overbeck. Extending gibson’s attacks on the gpt cryptosystem. In

Coding and Cryptography, pages 178–188. Springer Berlin Heidelberg, 2006.

[43] Raphael Overbeck. Structural attacks for public key cryptosystems based on
gabidulin codes. Journal of cryptology, 21(2):280–301, 2008.

[44] Nicholas Patterson. The algebraic decoding of goppa codes. IEEE Transactions
on Information Theory, 21(2):203–207, 1975.

[45] Eugene Prange. The use of information sets in decoding cyclic codes. IRE
Transactions on Information Theory, 8(5):5–9, 1962.

[46] Sven Puchinger, Julian Renner, and Antonia Wachter-Zeh. Twisted gabidulin
codes in the gpt cryptosystem. arXiv preprint arXiv:1806.10055, 2018.

[47] Sven Puchinger, John Sheekey, et al. Further generalisations of twisted gabidulin
codes. arXiv preprint arXiv:1703.08093, 2017.

[48] Haitham Rashwan, Ernst M Gabidulin, and Bahram Honary. A smart ap-
proach for gpt cryptosystem based on rank codes. In 2010 IEEE International
Symposium on Information Theory, pages 2463–2467. IEEE, 2010.

[49] I. Reed and G. Solomon. Polynomial codes over certain finite fields. Journal of
the Society for Industrial and Applied Mathematics, 8(2):300–304, 1960.

[50] Ron M. Roth and Abraham Lempel. On mds codes via cauchy matrices. IEEE
transactions on information theory, 35(6):1314–1319, 1989.

[51] John Sheekey. A new family of linear maximum rank distance codes. arXiv
preprint arXiv:1504.01581, 2015.

[52] Peter W. Shor. Polynomial-time algorithms for prime factorization and discrete
logarithms on a quantum computer. SIAM Review, 41(2):303–332, 1999.

[53] Vladimir M. Sidelnikov and Sergey O. Shestakov. On insecurity of cryp-

tosystems based on generalized reed-solomon codes. Discrete Mathematics and
Applications, 2(4):439–444, 1992.

[54] Natalia Silberstein, Ankit Singh Rawat, and Sriram Vishwanath. Error resilience
in distributed storage via rank-metric codes. In 2012 50th Annual Allerton
Conference on Communication, Control, and Computing (Allerton), pages 1150–
1157. IEEE, 2012.

[55] Danilo Silva, Frank R Kschischang, and Ralf Koetter. A rank-metric approach
to error control in random network coding. IEEE transactions on information
theory, 54(9):3951–3967, 2008.
 44

[56] W. A. Stein et al. Sage Mathematics Software (Version 8.9). The Sage
Development Team, 2019. [Link]

[57] Antonia Wachter-Zeh. Lecture notes in security in communications and storage,

2017/2018.

[58] Christian Wieschebrink. An attack on a modified niederreiter encryption scheme.

In International Workshop on Public Key Cryptography, pages 14–26. Springer,
2006.

[59] Christian Wieschebrink. Cryptanalysis of the niederreiter public key scheme

based on grs subcodes. In International Workshop on Post-Quantum Cryptog-
raphy, pages 61–72. Springer, 2010.
 45

A Appendix A
Data: Public generator matrix Ĝk
Result: Private keys S∗ and P∗ (row and column scramblers)
initialization;
while Λi (Ĝk ) has full rank do
i ← i + 1;
compute Λi (Ĝk );
end
if Λi (Ĝk )⊥ has not full rank over Fq then
compute column scrambler P∗ , such that first rows of Λi (Ĝk )⊥ P∗⊤ are zero;
else
attack fails;
end
if The last columns of Ĝk P∗−1 generate a Gabidulin code then
use some existing method (e.g. Ourivski [39]) to compute its generator
vector g ∗ and a row scrambler S∗ ;
end
Verify that S∗ and P∗ are part of a valid secret key
Algorithm 1: Overbeck’s Attack [42]
 46

B Appendix B
Data: Public generator matrix ĜT RS
Result: Private key (S∗ , α∗ , η ∗ )
initialization;
Gsub ← SubfieldSubcode(ĜT RS ) ∈ Fq(k−l)×n ;
Gsq ← Square(GSub ) ∈ F(2k−1)×nq ;
′ n
α ← SidelShest(Gsq ) ∈ Fq ;
i ← 1 ∈ N;
while G′ (G⊥ ⊤
sub ) ̸= 0 do
b ←∈ Fq ;
α∗ ← (α1′ − b, . . . , αn′ − b) ∈ Fq ;
G′ ← GenSub(α∗ ) ∈ F(k−l)×n q ;
i ← i + 1;
end
for j ← 1 to l do
i ← 1 ∈ N;
while ghj +1 = 0 do
g ← Interpolate(α′ , (Gpubi,1 , . . . , Gpubi,n )) ∈ Fnq0 ;
i ← i + 1;
end
gk−1+t
ηj∗ ← gh +1j
j

end
G∗T RS ← GTRS(α∗ , η ∗ ) ∈ Fqk×n
0
;
∗ ∗ k×k
S ← GT RS \ĜT RS ∈ Fq0 ;
return (S∗ , α∗ , η ∗ )
Algorithm 2: Attack by Lavauzelle and Renner [[30], Algorithm 1]