A Survey on Code-based Cryptography

Violetta Weger1 , Niklas Gassner2 , and Joachim Rosenthal2

1
Department of Electrical and Computer Engineering, Technical University of
Munich, Theresienstrasse 90, 80333 Munich, Germany, [email protected]
2
Institute of Mathematics, University of Zurich, Winterthurerstrasse 190, 8057 Zurich,
arXiv:2201.07119v3 [cs.CR] 24 Feb 2022

Switzerland, {niklas.gassner, rosenthal}@math.uzh.ch

February 25, 2022

Abstract
The improvements on quantum technology are threatening our daily cybersecurity, as
a capable quantum computer can break all currently employed asymmetric cryptosystems.
In preparation for the quantum-era the National Institute of Standards and Technology
(NIST) has initiated a standardization process for public-key encryption (PKE) schemes,
key-encapsulation mechanisms (KEM) and digital signature schemes. With this chapter
we aim at providing a survey on code-based cryptography, focusing on PKEs and signature
schemes. We cover the main frameworks introduced in code-based cryptography and
analyze their security assumptions. We provide the mathematical background in a lecture
notes style, with the intention of reaching a wider audience.

Contents
1 Introduction 2

2 Preliminaries 4
2.1 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2 Algebraic Coding Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.3 Cryptography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.3.1 Public-Key Encryption . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.3.2 Key-Encapsulation Mechanisms . . . . . . . . . . . . . . . . . . . . . . 21
2.3.3 Digital Signature Schemes . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.3.4 Zero-Knowledge Identification Scheme . . . . . . . . . . . . . . . . . . 24
2.3.5 Fiat-Shamir Transform . . . . . . . . . . . . . . . . . . . . . . . . . . 27

3 Code-Based Public-Key Encryption Frameworks 28

3.1 McEliece Framework . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.2 Niederreiter Framework . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.3 Alekhnovich’s Cryptosystems . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.3.1 The First Variant . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.3.2 The Second Variant . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.4 Quasi-Cyclic Scheme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

1
 3.5 GPT Cryptosystem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

4 Code-based Signature Schemes 44

4.1 Hash-and-Sign . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
4.2 Zero-Knowledge Identification Scheme Framework . . . . . . . . . . . . . . . 46

5 Security Analysis 52
5.1 NP-completeness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
5.2 Information Set Decoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
5.2.1 General Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
5.2.2 Overview Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
5.2.3 Techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
5.2.4 Prange’s Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
5.2.5 Stern’s Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
5.2.6 BJMM Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
5.2.7 Generalized Birthday Decoding Algorithms . . . . . . . . . . . . . . . 74
5.2.8 Asymptotic Cost . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
5.2.9 Rank-metric ISD Algorithms . . . . . . . . . . . . . . . . . . . . . . . 77
5.3 Algebraic Attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
5.4 Other Attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82

6 Historical Overview 83

7 Submissions to NIST 87
7.1 Finalists: Classic McEliece, BIKE and HQC . . . . . . . . . . . . . . . . . . . 89
7.1.1 Classic McEliece . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
7.1.2 Proposed Parameters for Classic McEliece . . . . . . . . . . . . . . . . 90
7.1.3 BIKE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
7.1.4 Proposed Parameters for BIKE . . . . . . . . . . . . . . . . . . . . . . 92
7.1.5 HQC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
7.1.6 Proposed Parameters for HQC . . . . . . . . . . . . . . . . . . . . . . 94

1 Introduction
Current public-key cryptosystems are based on the problem of factoring integers or the discrete
logarithm problem on an elliptic curve or over a finite field. While there are no efficient
algorithms known for classical computers to solve these problems efficiently, Shor’s algorithm
allows a quantum computer to solve these problems in polynomial time [201].
As research on quantum computers advances, the cryptographic community is searching
for cryptosystems that will survive attacks on quantum computers. This area of research is
called post-quantum cryptography.
In 2016 the National Institute of Standards and Technology (NIST) has initiated a stan-
dardization process for post-quantum cryptosystems. Such cryptosystems are usually based
on NP-complete problems for two reasons: NP-complete problems are at least as hard as the
hardest problems in NP, but solutions of such problems can be verified efficiently.
The main candidates for post-quantum cryptography are:

• Code-based cryptography (CBC), is based on the NP-complete problem of decoding a

random linear code.

2
 • Lattice-based cryptography, is based on the NP-complete problems of finding the short-
est vector, respectively the closest vector to a given vector in a lattice. For an overview
see [176].

• Multivariate cryptography, is based on the NP-complete problem of solving multivariate

quadratic equations defined over some finite field. For an overview see [92].

• Isogeny-based cryptography, based on finding the isogeny map between two supersin-
gular elliptic curves [131].

For an overview on post-quantum cryptography see [54].

Code-based cryptography usually bases its security on the fact that decoding a random
linear code is an NP-complete problem, which was shown in 1978, by Berlekamp, McEliece
and Van Tilborg in [52]. In the same year, McEliece proposed a cryptosystem [160], in
which one picks a code with underlying algebraic structure that allows efficient decoding
and then disguises this code as a seemingly random linear code. A message gets encoded
as codeword and encrypted by adding an error to the message. With the knowledge of the
algebraic structure of the code, one can recover the initial message, but an adversary faces
the challenge of decoding a random linear code.
The NIST standardization process has now reached the final round, where only one code-
based scheme has been selected as finalist for standardization, namely Classical McEliece [11].
The research in this area is, however, not finished yet, especially with the recent announcement
that NIST will reopen the standardization call for signature schemes, as no satisfactory scheme
has been submitted. And although NIST did not choose any of the rank-metric systems as
finalist, they frequently encourage the research in other metrics.
In this chapter we give an extensive survey on code-based cryptography, explaining the
mathematical background of such systems and the difficulties of proposing secure and at the
same time practical schemes. We cover the main proposals and the approaches to break such
systems. With the recent news, that NIST will reopen the standardization process for digital
signature schemes, we hope to reach different research communities to tackle this new chal-
lenge together.

This chapter is organized as follows. In Section 2 we introduce some basics of algebraic

coding theory as well as the basics of asymmetric cryptography, such as PKEs and signature
schemes. In particular, we aim at introducing all used coding-theoretic objects in Section 2.2
and to describe on a high-level the considered cryptographic schemes in 2.3. This includes
public-key encryption (PKE), key-encapsulation mechanism (KEM) and signature schemes.
In particular, we show how to construct a signature scheme via the Fiat-Shamir transform on
a zero-knowledge identification (ZKID) scheme.
The main focus of this chapter will lay on Section 3 where we introduce the public-key
encryption frameworks by McEliece, Niederreiter, Alekhnovich as well as the quasi-cyclic
scheme and the GPT cryptosystem.
In Section 4 we discuss some code-based signatures, starting with the first construc-
tion method, namely hash-and-sign in Section 4.1 and finishing with some code-based ZKID
schemes in Section 4.2.
In Section 5 we analyze the security of these systems, where we first focus on the decoding
problem of a random linear code: we present the proofs of NP-completeness in Section 5.1
and the best-known solvers for the underlying problems in Section 5.2.

3
 In the second part of the security analysis, namely Section 5.3 we also present some
algebraic attacks, which clearly depend on the chosen secret code. For this section, we focus
on two of the most preferred codes, one being Reed-Solomon codes and the other being their
rank metric analog, Gabidulin codes. Finally, we end the security analysis by shortly reporting
on some other ways of attacking code-based systems, such as side-channel attacks, in Section
5.4.
In Section 6 we provide a historical overview on the main code-based PKE and signature
scheme proposals, stating their differences, in the notion of the given frameworks, and whether
they are broken.
In Section 7 we shortly cover the submissions to the NIST standardization process with a
focus on the finalists in Section 7.1: Classic McEliece, BIKE and HQC.

2 Preliminaries
In order to make this chapter as self-contained as possible, we present here a rather long
preliminary section, which hopefully makes this survey also accessible to non-experts. We
start with the notation used throughout this chapter, followed by the basics of algebraic
coding theory and defining all concepts and codes that will be used or metioned and finally
presenting the basics of the considered schemes on a very high-level and with specific examples.

2.1 Notation
We denote by Fq the finite field with q elements, where q is a prime power and denote by F× q
its multiplicative group, i.e., Fq \ {0}. Throughout this chapter, we denote by bold upper case
or lower case letters matrices, respectively vectors, e.g. x ∈ Fnq and A ∈ Fqk×n . The identity
matrix of size k is denoted by Idk . Sets are denoted by upper case letters and for a set S, we
denote by | S | its cardinality. By GLn (Fq ) we denote the n × n invertible matrices over Fq .
Notation specific to only one part of this chapter will be defined right before their use.

2.2 Algebraic Coding Theory

This section is designed to recall and/or introduce all definitions and coding theoretic objects
required in this chapter. Most proofs will be omitted or left as an exercise. For interested
readers that are completely new to algebraic coding theory we recommend the following books
[193, 51, 214, 155]. We also leave away the references to standard definitions and results, which
can be found in any book on coding theory. For more specific results, we will give a proper
reference.
In classical coding theory one considers the finite field Fq of q elements, where q is a prime
power.
Definition 1 (Linear Code). Let 1 ≤ k ≤ n be integers. Then, an [n, k] linear code C over
Fq is a k-dimensional linear subspace of Fnq .
The parameter n is called the length of the code, the elements in the code are called
codewords and R = k/n is called the rate of the code. In order to measure how far apart two
vectors are, we endow Fq with a metric. Usually, this is the Hamming metric.
Definition 2 (Hamming Metric). Let n be a positive integer. For x ∈ Fnq , the Hamming
weight of x is given by the size of its support, i.e.,
wtH (x) =| {i ∈ {1, . . . , n} | xi 6= 0} | .

4
For x, y ∈ Fnq , the Hamming distance between x and y is given by the number of positions
in which they differ, i.e.,

dH (x, y) =| {i ∈ {1, . . . , n} | xi 6= yi } | .

Note that the Hamming distance is induced from the Hamming weight, that is dH (x, y) =
wtH (x − y). Having defined a metric, one can also consider the minimum distance of a code,
i.e., the smallest distance achieved by its distinct codewords.

Definition 3 (Minimum Distance). Let C be a code over Fq . The minimum Hamming

distance of C is denoted by dH (C) and given by

dH (C) = min{dH (x, y) | x, y ∈ C, x 6= y}.

Exercise 4. Show that for a linear code C, we have

dH (C) = min{wtH (x) | x ∈ C, x 6= 0}.

Exercise 5. A non-linear code C ′ ⊂ Fnq is just defined as a subset of Fnq . Give an example,
where
dH (C ′ ) 6= min{wtH (x) | x ∈ C, x 6= 0}.
We denote by dH (x, C) the minimal distance between x ∈ Fnq and a codeword in C. Let r
be a positive integer. We define the Hamming sphere as all the vectors, which have at most
Hamming weight r, i.e.,

BH (r, n, q) = {x ∈ Fnq | wtH (x) ≤ r}.

Exercise 6. Show that

r  
X n
| BH (r, n, q) |= (q − 1)i .
i
i=0

The minimum distance of a code is an important parameter, since it is connected to the

error correction capacity of the code. We say that a code can correct up to t errors, if for
all x ∈ Fnq with dH (x, C) ≤ t, there exists exactly one y ∈ C, such that dH (x, y) ≤ t. A
decoding algorithm D is an algorithm that is given such a word x ∈ Fnq and returns the closest
codeword, y ∈ C, such that dH (x, y) ≤ t. The most interesting codes for applications are
codes with an efficient decoding algorithm, which clearly not every code possesses.
Exercise 7. Let C be a linear code over
j Fq kof length n and of minimum distance dH . Show
that the code can correct up to t := dH2−1 errors.
One of the most important bounds in coding theory is the Singleton bound, which provides
an upper bound on the minimum distance of a code.

Theorem 8 (Singleton Bound [206]). Let k ≤ n be positive integers and let C be an [n, k]
linear code over Fq . Then,
dH ≤ n − k + 1.

Exercise 9. Prove the Singleton Bound by showing that deleting dH − 1 of the positions is an
injective map.

5
 A code that achieves the Singleton bound is called a maximum distance separable (MDS)
code. MDS codes are of immense interest, since they can correct the maximal amount of
errors for fixed code parameters.
Linear codes allow for an easy representations through their generator matrices, which
have the code as an image.

Definition 10 (Generator Matrix). Let k ≤ n be positive integers and let C be an [n, k]

linear code over Fq . Then, a matrix G ∈ Fqk×n is called a generator matrix of C if
n o
C = xG | x ∈ Fkq ,

that is, the rows of G form a basis of C.

One can also represent the code through a matrix H, which has the code as kernel.

Definition 11 (Parity-Check Matrix). Let k ≤ n be positive integers and let C be an [n, k]

(n−k)×n
linear code over Fq . Then, a matrix H ∈ Fq is called a parity-check matrix of C, if
n o
C = y ∈ Fnq | Hy⊤ = 0 .

For any x ∈ Fnq , we call xH⊤ a syndrome.

Exercise 12. Let k ≤ n be positive integers and let C be an [n, k] linear code over Fq . Let
H be a parity-check matrix of C. Show that C has minimum distance dH if and only if every
dH − 1 columns of H are linearly independent and there exist dH columns, which are linearly
dependent.
For x, y ∈ Fnq let us denote by hx, yi the standard inner product, i.e.,
n
X
hx, yi = xi y i .
i=1

Then, we can define the dual of an [n, k] linear code C over Fq as the orthogonal space of C.

Definition 13 (Dual Code). Let k ≤ n be positive integers and let C be an [n, k] linear code
over Fq . The dual code C ⊥ is an [n, n − k] linear code over Fq , defined as

C ⊥ = {x ∈ Fnq | hx, yi = 0 ∀ y ∈ C}.

Exercise 14. Show that the dual of an MDS code is an MDS code.
For x ∈ Fnq and S ⊆ {1, . . . , n} we denote by xS the vector consisting of the entries of x
indexed by S. While for A ∈ Fqk×n , we denote by AS the matrix consisting of the columns of
A indexed by S. Similarly, we denote by CS the code consisting of the codewords cS .
Observe that an [n, k] linear code can be completely defined by certain sets of k positions.
The following concept characterizes such defining sets.

Definition 15 (Information Set). Let k ≤ n be positive integers and let C be an [n, k] linear
code over Fq . Then, a set I ⊂ {1, . . . , n} of size k is called an information set of C if

| C |=| CI | .

6
Exercise 16. How many information sets can an [n, k] linear code have at most?
Exercise 17. Let C be an [n, k] linear code, I an information set and let G be a generator
matrix G and H a parity-check matrix. Show that GI is an invertible matrix of size k. If
I C := {1, . . . , n} \ I is the complement set of I then HI C is an invertible matrix of size n − k.
Exercise 18. Let C be the code generated by G ∈ F2×4 5 , given as
 
1 3 2 3
G= .
0 4 4 3
Determine all information sets of this code.
Definition 19 (Systematic Form). Let k ≤ n be positive integers and C be an [n, k] linear
code over Fq . Then, for some permutation matrix P and some invertible matrix U the
systematic form of the generator matrix G is


UGP = Idk A ,
k×(n−k)
where A ∈ Fq . Whereas, for some permutation matrix P′ and some invertible matrix
′
U , the systematic form of the parity-check matrix is
U′ HP′ = B Idn−k ,

(n−k)×k
where B ∈ Fq .
Let us denote by VH (r, n, q) the volume of a ball in the Hamming metric, i.e.,
VH (r, n, q) =| BH (r, n, q) | .
The Gilbert-Varshamov bound [110, 217, 196] is one of the most prominent bounds in coding
theory and widely used in code-based cryptography since it provides a sufficient condition for
the existence of linear codes.
Theorem 20 (Gilbert-Varshamov bound, e.g. [193], Theorem 4.4). Let q be a prime power
and let k ≤ n and dH be positive integers, such that
VH (dH − 2, n − 1, q) < q n−k .
Then, there exists a [n, k] linear code over Fq with minimum Hamming distance at least dH .
The better known Gilbert-Varshamov bound is a statement on the maximal size of a code,
that is: let us denote by AL(n, d, q) the maximal size of a code in Fnq having minimum distance
d.
Theorem 21 (Gilbert-Varshamov Bound, e.g. [51], Theorem 13.71). Let q be a prime power
and n, d be positive integers. Then,
qn
AL(n, d, q) ≥ .
VH (d − 1, n, q)
It turns out that random codes attain the asymptotic Gilbert-Varshamov bound with high
probability. This will be an important result for asymptotic analysis of some algorithms. Let
us first give some notation: let 0 ≤ δ ≤ 1 denote the relative minimum distance, i.e., δ = d/n
and let us denote by
1
R(δ) := lim sup logq AL(n, δn, q)
n→∞ n
the asymptotic information rate.

7
Definition 22 (Entropy Function). For a positive integer q ≥ 2 the q-ary entropy function
is defined as follows:
hq : [0, 1] → R,
x → x logq (q − 1) − x logq (x) − (1 − x) logq (1 − x).
Exercise 23. Show that for s ∈ [0, 1 − 1/q] we have that
1. VH (sn, n, q) ≤ q hq (s)n ,
2. VH (sn, n, q) ≥ q hq (s)n−o(n) ,
using Stirling’s formula.
Theorem 24 (The Asymptotic Gilbert-Varshamov Bound, e.g. [193], Theorem 4.10). For
every prime power q and δ ∈ [0, 1 − 1/q] there exists an infinite family C of codes with rate
R(δ) ≥ 1 − hq (δ).
Recall that in complexity theory we write f (n) = Ω(g(n)), if
f (n)
lim sup > 0.
n→∞ g(n)
For example, f (n) = Ω(n) means that f (n) grows at least polynomially in n.
Theorem 25 ([42, 181]). For every prime power q, δ ∈ [0, 1 − 1/q) and 0 < ε < 1 − hq (s)
and sufficiently large positive integer n. The following holds for
k = ⌈(1 − hq (δ) − ε)n⌉ .
If G ∈ Fqk×n is chosen uniformly at random, the linear code C generated by G has rate at least
1 − hq (δ) − ε and relative minimum distance at least δ with probability at least 1 − e−Ω(n) .
Exercise 26. Proof Theorem 25 following these steps:
1. What is the probability for G to have full rank?
2. For each non-zero x ∈ Fkq show that xG is a uniformly random element.

3. Show that the probability that wtH (xG) ≤ δn is at most q (hq (δ)−1)n .
4. Use the union bound over all non-zero x and the choice of k to get the claim.
These results hold also more in general over any finite chain ring and for any additive
weight, see [64].
In order to give a self-contained chapter, we also want to introduce some of the most
prominent codes that are used in code-based cryptography. For this we start with Generalized
Reed-Solomon codes (GRS).
Definition 27 (Generalized Reed-Solomon Code, [188]). Let k ≤ n ≤ q be positive integers.
Let α ∈ Fnq be an n-tuple of distinct elements, i.e., α = (α1 , . . . , αn ) with αi 6= αj , for all
i 6= j ∈ {1, . . . , n}. Let β ∈ Fnq be an n-tuple of nonzero elements, i.e., β = (β1 , . . . , βn ), with
βi 6= 0 for all i ∈ {1, . . . , n}. The Generalized Reed-Solomon code of length n and dimension
k, denoted by GRSn,k (α, β) is defined as

GRSn,k (α, β) = (β1 f (α1 ), . . . , βn f (αn )) f ∈ Fq [x], deg(f ) < k .

8
 In the case where β = (1, . . . , 1), we call the code GRSn,k (α, β) a Reed-Solomon (RS) code
and denote it by RSn,k (α).
Exercise 28. Show that the Vandermonde matrix
 
1 ··· 1
 α1 · · · αn 
 .. .. 
 
 . . 
α1k−1 · · · αnk−1

is a generator matrix of a RS code. Similarly, build a generator matrix of the GRSn,k (α, β)
code.
Exercise 29. Show that GRS codes are MDS codes, i.e.,

dH (GRSn,k (α, β)) = n − k + 1.

Observe that the dual code of a GRS code is again a GRS code.

Proposition 30 (E.g. [193], Proposition 5.2). Let k ≤ n ≤ q be positive integers. Then

GRSn,k (α, β)⊥ = GRSn,n−k (α, γ),

where
n
Y
γi = βi−1 (αi − αj )−1 .
j=1
j6=i

Another important family of codes in code-based cryptography is the family of classical

q-ary Goppa codes.
Let m be a positive integer, n = q m and Fqm be a finite field. Let G ∈ Fqm [x]. Then
define the quotient ring .
Sm = Fqm [x] hGi .

Lemma 31 (E.g. [155], Chapter 12). Let α ∈ Fq be such that G(α) 6= 0. Then (x − α) is
invertible in Sm and
1 G(x) − G(α)
(x − α)−1 = − .
G(α) x−α
Definition 32 (Classical Goppa Code [113, 114, 115]). Let α = (α1 , . . . , αn ) ∈ Fnqm , be such
that αi 6= αj for all i 6= j ∈ {1, . . . , n} and G(αi ) 6= 0 for all i ∈ {1, . . . , n}. Then we can
define the classical q-ary Goppa code as
n
( )
n
X ai
Γ(α, G) = a ∈ Fq = 0 in Sm .
x − αi
i=1

Proposition 33 (E.g. [155], Chapter 12). The Goppa code Γ(α, G) has minimum Hamming
distance dH (Γ(α, G)) ≥ deg(G) + 1 and dimension k ≥ n − m deg(G).

9
 In order to construct a parity-check matrix of a classical Goppa code, let us define β =
(G(α1 )−1 , . . . , G(αn )−1 ). The parity-check matrix of Γ(α, G) is then given by the weighted
Vandermonde matrix  
β1 ··· βn
 β1 α1 · · · βn αn 
H =  .. ..  .
 
 . . 
β1 α1r−1 · · · βn αnr−1
(n−k)×n
Note that H ∈ Fqm , but the code Γ(α, G) is the Fq -kernel of H.
From this construction, we can already see that strong connection between classical Goppa
codes and GRS codes. For this we define subfield subcodes and alternant codes in the follow-
ing.

Definition 34 (Subfield Subcode, e.g. [155], Chapter 7). Let C be an [n, k] linear code over
Fqm . The subfield subcode of C over Fq is then defined as

CFq = C ∩ Fnq .

Proposition 35 (E.g. [155], Chapter 7). Let C be an [n, k] linear code over Fqm with minimum
distance d. Then CFq has dimension ≥ n − m(n − k) and minimum distance ≥ d.

Exercise 36. Prove Proposition 35 using the map

φ : Fnqm → Fnqm ,
(x1 , . . . , xn ) 7→ (xq1 − x1 , . . . , xqn − xn ).

A special case of subfield subcodes are the alternant codes, where one takes subfield
subcodes of GRS codes.

Definition 37 (Alternant Code, e.g. [155], Chapter 12). Let α ∈ Fnqm be pairwise distinct
and β ∈ (F× n
q m ) . Then the alternant code Am,n,k (α, β) is defined as

Am,n,k (α, β) = GRSm,n,k (α, β) ∩ Fnq .

Proposition 38 (E.g. [155], Chapter 12). The alternant code Am,n,k (α, β) has dimension
≥ n − m(n − k) and minimum distance ≥ n − k + 1.

Exercise 39. Prove Proposition 38.

Thus, classical Goppa codes are alternant codes, i.e., subfield subcodes of GRS codes.
Another important family of codes is that of cyclic codes. They can be represented through
only one vector. Let c = (c1 , . . . , cn ) ∈ Fnq , then we denote by σ(c) its cyclic shift, i.e.,

σ(c1 , . . . , cn ) = (cn , c1 , . . . , cn−1 ).

We call a code cyclic, if the cyclic shift of any codeword is also a codeword.

Definition 40 (Cyclic Code, e.g. [193], Chapter 8). Let C be an [n, k] linear code over Fq .
We say that C is cyclic if σ(C) = C.

Proposition 41 (E.g. [193], Example 8.2). Let k ≤ n ≤ q − 1 be positive integers and let
α ∈ Fnq be pairwise distinct. Then RSn,k (α) is a cyclic code.

10
Exercise 42. Prove Proposition 41.
Pn−1
Note that any polynomial c(x) = i=0 ci xi ∈ Fq [x] of degree (at most) n − 1 corresponds
n
naturally to a vector c = (c0 , . . . , cn−1 ) ∈ Fq .

Proposition 43 (E.g. [193], Chapter 8). Cyclic codes over Fq of length n are ideals of
Fq [x]/(xn − 1).

Exercise 44. Prove Proposition 43 using the map

ϕ : Fq [x]/(xn − 1) → Fnq ,
c(x) 7→ (c0 , . . . , cn−1 ).

Since we can see cyclic codes as ideals in Fq [x]/(xn − 1), we can also consider the generator
polynomial of a cyclic code.

Definition 45 (Generator Polynomial). The generator polynomial of a cyclic code C ⊂ Fnq is

the unique monic generator of minimal degree of the corresponding ideal in Fq [x]/(xn − 1).

Proposition 8.1). Let C be a cyclic code over Fq of length n with

Proposition 46 (E.g. [193], P
generator polynomial g(x) = ri=0 gi xi , where r is the degree of g. Then

1. g(x) | xn − 1.

2. C has dimension n − r.
(n−r)×n
3. A generator matrix G ∈ Fq of C is given by
 
g0 · · · gr
G=
 .. .. .

. .
g0 · · · gr

4. Let h(x) be such that g(x)h(x) = xn − 1, then hg(x)i⊥ = hh(x)i.

Exercise 47. Prove Proposition 46.

Exercise 48. How many cyclic codes over F3 of length 4 exist?
Note that the generator matrix in Proposition 46 is in a special form, such a matrix is
called a circulant matrix.
Exercise 49. Give the generator polynomial of RSn,k (α, β).
Exercise 50. Let us consider the code C over F3 generated by
 
1 0 1 0
G= .
0 1 0 1

1. Show that C is cyclic.

2. Find the generator polynomial of C.

3. Find the generator polynomial of C ⊥ .

11
 Another interesting family of codes for cryptography are the low-density parity-check
(LDPC) codes introduced by Gallager [107]. The idea of LDPC codes is to have a parity-check
matrix that is sparse. These codes are usually defined over the binary, although they can
be generalized to arbitrary finite fields [85], for the applications in cryptography the binary
LDPC codes suffice. In order to define LDPC codes we introduce the notation of row-weight,
respectively column-weight of a matrix, which refers to the Hamming weight of each row,
respectively of each column. Thus, a matrix having row-weight w, asks for each row to have
Hamming weight w.
Classically LDPC codes are defined as follows.
Definition 51 ([107]). Let λ, ρ ∈ N. An [n, k] linear code C over F2 is called a (λ, ρ)-regular
(n−k)×n
LDPC code, if there exists a parity-check matrix H ∈ F2 of C which has column-weight
λ and row-weight ρ.
A more common definition for cryptographic applications reads as follows.
Definition 52. Let w ∈ N be a constant. An [n, k] linear code C over F2 is called a w-
(n−k)×n
low-density parity-check code, if there exists a parity-check matrix H ∈ F2 of C having
row-weight w.
Exercise 53. Show that the rate of an (λ, ρ)-regular LDPC code is given by 1 − λ/ρ.
(n−k)×n
For a parity-check matrix H ∈ F2 and a received vector x ∈ Fn2 we call the (n − k)
equations derived from Hx⊤ parity-check equations, i.e.,
n
X
hij xj
j=1

for all i ∈ {1, . . . , n − k}. We say that a parity-check equation is satisfied if

n
X
hij xj = 0,
j=1

and else call it unsatisfied.

LDPC codes are interesting from a coding-theoretic point of view, as they (essentially)
achieve Shannon capacity in a practical way. From a cryptographic stand point, these codes
are interesting as they have no algebraic structure, which might be detected by an attacker,
but nevertheless have an efficient decoding algorithm.
One decoding algorithm dates back to Gallager [107] and is called Bit-Flipping algorithm.
There have been many improvements (e.g. [220, 134, 156])). The algorithm is iterative and
its error correction capability increases with the code length. The idea of the Bit-Flipping
algorithm is that at each iteration the number of unsatisfied parity-check equations associ-
ated to each bit of the received vector is computed. Each bit which has more than b ∈ N
(some threshold parameter) unsatisfied parity-check equations is flipped and the syndrome is
updated accordingly. This process is repeated until either the syndrome becomes 0, or until
a maximal number of iteration M ∈ N is reached. In the later case we have a decoding failure.
The complexity of this algorithm is thus given by O(nwN ), where w is the row-weight of the
parity-check matrix and N is the average number of iterations.
One can also relax the condition on the row-weight of LDPC codes, to get moderate-
density parity-check (MDPC) codes.

12
Definition 54 ([171]). An [n, k] linear code C over F2 is called a moderate-density parity-check
(n−k)×n p
code, if there exists a parity-check matrix H ∈ F2 having row-weight O( n log(n)).

Thus, the only difference to LDPC codes is, that we allow a larger row-weight in the parity-
check matrix. This might however lead to an increase of iterations within the Bit-Flipping
algorithm and decoding failures become increasingly likely.
Finally, we introduce quasi-cyclic codes. For x = (x1 , . . . , xn ) ∈ Fnq and some ℓ ∈
{1, . . . , n} we denote by σℓ (x) its ℓ-cyclic shift, i.e.,

σℓ (x) = (x1+ℓ , . . . , xn+ℓ ),

where the indices i + ℓ should be considered modulo n.

Definition 55 (E.g. [155], Chapter 16). An [n, k] linear code C is a quasi-cyclic (QC) code,
if there exists ℓ ∈ N, such that σℓ (C) = C.

In addition, if n = ℓa, for some a ∈ N, then it is convenient to write the generator matrix
composed into a × a circulant matrices.
We introduce a class of codes, the Reed-Muller codes, introduced in [167] in 1954. They
are, similarly to Reed-Solomon codes, constructed as the evaluation of polynomials. While
Reed-Solomon codes only consider polynomials in one variable, Reed-Muller codes use mul-
tivariate polynomials. For this part we follow [121].
Let p be a prime, q = pn and m, r be positive integers. Denote with Fq [x1 , . . . , xm ]≤r
the Fq -vector space of polynomials in m variables of degree at most r and fix an order
{α1 , α2 , . . . , αqm } of Fm
q .

Definition 56 ([167]). The Reed-Muller code RMq (m, r) over Fq is defined as the image of
the evaluation map
m
ev : Fq [x1 , . . . , xm ]≤r → Fqq ,
f 7→ (f (α1 ), f (α2 ), . . . , f (αqm )).

We will note that there exist efficient decoding algorithms for Reed-Muller codes, the first
efficient decoding algorithm was published in [187].
For the case q = 2, we can compute dimension and minimum distance of RMq (m, r).

Proposition 57 (E.g. [193], Problem 2.19). Let r ≤ m. Then dimF2 (RM2 (m, r)) =
P r m


i=0 i .

Exercise 58. Prove Proposition 57 using the following steps:

1. Consider B = {xi1 xi2 · · · xik | i1 < i2 < . . . < ik , 0 ≤ k ≤ r}. Show that ev(B) spans
RM2 (m, r) as F2 -vector space. (Hint: x2 = x in F2 .)

2. Let f be a polynomial in the linear span of B. We may assume that x1 x2 . . . xs is a

maximum degree term (otherwise change the indices of x1 , x2 , . . . , xm ) and write

f = x1 x2 · · · xs + g(x1 , x2 , . . . , xm ).

Let αs+1 , . . . , αm ∈ F2 . Justify that h(x1 , . . . , xs ) := f (x1 , . . . , xs , αs+1 , . . . , αm ) is a

non-zero polynomial.

13
 3. Show that there exist α1 , . . . , αs ∈ F2 such that h(α1 , . . . , αs ) 6= 0. (Hint: if h does not
have a constant term, write h(x1 , . . . , xs ) = xi1 · · · xik + k(x1 , . . . , xs ), where xi1 · · · xik
is a term of minimal degree.)

4. Deduce that the evaluation map restricted to the linear span of B, ev|hBi , is injective
and conclude the proof of Proposition 57.

Proposition 59 (E.g. [193], Problem 2.19). Let r ≤ m. The minimum distance of RM2 (m, r)
is 2m−r .

Proof. Let a(x1 , . . . , xm ) = x1 · · · xr . Note that f (α1 , . . . , αm ) is non-zero if and only if

α1 = α2 = . . . = αr = 1. There are 2m−r choices of vectors (1, . . . , 1, αr+1 , . . . , αm ) ∈ Fm
2 , so
ev(f ) is a codeword of weight 2 m−r , implying that the minimum distance is at most 2 m−r .
Let B = {xi1 xi2 · · · xik | i1 < i2 < . . . < ik , 0 ≤ k ≤ r}. We have seen in Exercise 58 that
ev(hBi) is a basis of RM2 (m, r). Let f (x1 , . . . , xm ) ∈ hBi be a non-zero polynomial, we may
assume that x1 x2 · · · xs is a term of f of maximum degree. Write

f = x1 x2 · · · xs + g(x1 , x2 , . . . , xm ).

Then
h(x1 , . . . , xs ) := f (x1 , . . . , xs , αs+1 , . . . , αm )
is a non-zero polynomial for all αs+1 , . . . , αm ∈ F2 , and there exist α1 , . . . , αs ∈ F2 such that
h(α1 , . . . , αs ) 6= 0 (see Exercise 58). There are 2m−s choices of αs+1 , . . . , αm , so ev(h) has
weight at least 2m−s ≥ 2m−r .

We also want to introduce the following two methods to get a new code from an old code:
puncturing and shortening. When we puncture a code we essentially delete all coordinates
indexed by a certain set in all codewords, while shortening can be regarded as the puncturing
of a special subcode.

Definition 60. Let C be an [n, k] linear code over Fq and let T ⊆ {1, . . . , n} be a set of size
t. Then, we define the punctured code C T in T as follows

C T = {(ci )i6∈T | c ∈ C}.

Let us define C(T ) to be the subcode containing all codewords which are 0 in T , that is

C(T ) = {c ∈ C | ct = 0 ∀t ∈ T }.

Then, we define the shortened code CT in T to be

CT = C(T )T .

Clearly the punctured code C T has now length n − t. What happens to its dimension?
Exercise 61. Show that if t < d the minimum distance of C, then C T has dimension k.
Shortening and puncturing of a code are heavily connected through the dual code:

Theorem 62 (E.g. [193], Problem 2.14). Let C be a linear [n, k] code over Fq with dual code
C ⊥ . Let T ⊆ {1, . . . , n} be a set of size t. Then

1. (C ⊥ )T = (C T )⊥ ,

14
 2. (C ⊥ )T = (CT )⊥ .

Example 63. Let us consider the binary code generated by

 
1 0 0 1 1 0
G = 0 1 0 0 1 1 ,
0 0 1 1 1 1

and T = {4, 5}. Then, the punctured code C T has generator matrix
 
1 0 0 0
GT = 0 1 0 1 .
0 0 1 1

Note that C(T ) = {(1, 0, 1, 0, 0, 1), (0, 0, 0, 0, 0, 0)}, thus the generator matrix of CT is given
by

GT = 1 0 1 1 .
Exercise 64. Show that Theorem 62 holds for this example.
We say that two codes C1 and C2 are permutation equivalent, if there exists a permutation
of indices, which transforms C1 into C2 , that is there exists σ ∈ Sn , such that σ(C1 ) = C2 .
Concatenated codes were first introduced by Forney [99], and use the basic idea of a double
encoding process through two codes.

Definition 65 ([99]). Let C1 be an [n1 , k1 ] linear code of minimum distance d1 over Fq ,

called inner code and C2 be an [n2 , k2 ] linear code of minimum distance d2 over Fqk1 , called
outer code. Then, the concatenated code C = C2 ◦ C1 is an [n1 n2 , k1 k2 ] linear code over Fq of
minimum distance at least d1 d2 .

The codewords of C are built as follows: for any u ∈ Fkqk21 and encode u using a generator
matrix G2 of C2 , receiving the codeword ((uG2 )1 , . . . , (uG2 )n2 ). Let us denote for a ∈ Fqk1
by a the corresponding vector in Fkq 1 having fixed a basis. As a next step we represent the
entries of each codeword as a vector in Fkq 1 and encode them using a generator matrix G1 of
C1 . Then, the codewords of C are of the form

((uG2 )1 G1 , . . . , (uG2 )n2 G1 ).

Until now, we have considered classical coding theory, where the finite field is endowed
with the Hamming metric. However, there exist many more metrics, for example the rank
metric. In the following we introduce rank-metric codes, for which we follow the notation of
[116]. Let us denote by Fqn×m the n × m matrices over Fq .

Definition 66 ([90, 194, 100]). [Rank Metric] Let A, B ∈ Fqn×m. The rank weight of A is
given by the rank of A, i.e., wtR (A) = rk(A) and the rank distance between A and B is given
by
dR (A, B) = rk(A − B).

Using this metric on Fqn×m we can define the matrix rank-metric codes.

Definition 67 (Matrix Rank-Metric Codes, [90, 194, 100]). An Fq -linear subspace of Fqn×m
is called a matrix rank-metric code.

15
 A special class of matrix rank-metric codes are the vector rank-metric codes.
Definition 68 (Vector Rank Metric, [90, 194, 100]). Let x, y ∈ Fnqm . The rank weight of x is
defined as the dimension of the Fq -vector space generated by its entries, i.e.,


wtR (x) = dimFq hx1 , . . . , xn iFq

and the rank distance between x and y is given by

dR (x, y) = wtR (x − y).

While in the Hamming metric the support of x ∈ Fnqm is defined as the indices of non-zero
entries of x, i.e.,
suppH (x) = {i ∈ {1, . . . , n} | xi 6= 0},
the support in the rank metric is defined as the Fq -vector space generated by its entries, i.e.,

suppR (x) = hx1 , . . . , xn iFq .

With this metric we can define the vector rank-metric codes.

Definition 69 (Vector Rank-Metric Codes, [90, 194, 100]). An Fqm -linear subspace of Fnqm
is a vector rank-metric code.
While every vector rank-metric code is a matrix-rank metric code, the opposite is not
true. Let B = {b1 , . . . , bm } be a basis of Fqm over Fq , then for every x ∈ Fqm , there exist
x(j) ∈ Fq for j ∈ {1, . . . , m} such that we can write
m
X
x= bj x(j) .
j=1

Thus for a vector x = (x1 , . . . , xn ) ∈ Fnqm , we can define B(x) ∈ Fqn×m having entries B(x)i,j =
(j)
xi . With this we can define for a vector rank-metric code C ⊂ Fnqm the matrix rank-vector
code
B(C) = {B(c) | c ∈ C}.
Proposition 70 (E.g. [116], Proposition 1.5). Let C ⊂ Fnqm be a vector rank-metric code of
dimension k. Then B(C) has dimension mk over Fq .
Exercise 71. Prove Proposition 70.
Similarly to before for the rank metric we can define the minimum distance of a code.
Let C ⊂ Fqn×m be a matrix rank-metric code. Then C has minimum rank distance

dR (C) = min{wtR (A) | A ∈ C, A 6= 0}.

The same works as well for vector rank-metric codes: let C ⊂ Fnqm be a vector rank-metric
code. Then C has minimum rank distance

dR (C) = min{wtR (c) | c ∈ C, c 6= 0}.

Exercise 72. Let {0} =6 C ⊂ Fnqm be a vector rank-metric code with minimum rank distance
dR (C) and let B be a basis of Fqm over Fq . Show that

dR (C) = dR (B(C)).

16
 With the minimum rank distance we can also state a Singleton bound:

Theorem 73 (Matrix Rank-Metric Singleton Bound, [90], Theorem 5.4). Let C ⊂ Fqn×m be
a matrix rank-metric code of dimension dimFq (C) = k with minimum rank distance dR (C).
Then
k ≤ max{n, m}(min{n, m} − dR (C) + 1).

Codes achieving this bound are called Matrix Maximum Rank Distance (Matrix MRD)
codes.

Theorem 74 (Vector Rank-Metric Singleton Bound, [100], Lemma 1). Let C ⊂ Fnqm be a
vector rank-metric code of dimension dimFqm (C) = k with minimum rank distance dR (C).
Then
k ≤ n − dR (C) + 1.

Codes achieving these bounds are called Vector Maximum Rank Distance (Vector MRD)
codes.
Note that MDS codes have density 1 for q going to infinity, and due to the MDS conjecture,
we assume they have density 0 for n going to infinity. Similar results hold also for the rank
metric: vector MRD codes are dense for q going to infinity by [168] and since dR (C) is bounded
by m, have density 0 for n going to infinity. It was shown in [119] that matrix MRD codes
are sparse for all parameter sets as the field grows, with only very few exceptions. Unlike in
the Hamming metric, we know that vector MRD codes exist for any set of parameters, by the
seminal work of Delsarte [90] and Gabidulin [100]. The code presented within these papers
is usually referred to as (classical) Gabidulin code. In order to introduce these codes let us
first recall the basics of q-polynomials.
A q-polynomial or linearized polynomial f of q-degree d over Fqm is a polynomial of the
form
d
i
X
f (x) = f i xq .
i=0

Let us denote by Pℓ the q-polynomials of q-degree up to ℓ over Fqm .

The classical Gabidulin code can now be defined in a similar fashion as the Reed-Solomon
code, i.e., as evaluation code.

Definition 75 (Classical Gabidulin Code, [90, 100]). Let g1 , . . . , gn ∈ Fqm be linearly inde-
pendent over Fq and let k ≤ n ≤ m. The classical Gabidulin code C ⊂ Fnqm of dimension k is
defined as
C = {(f (g1 ), . . . , f (gn )) | f ∈ Pk−1 }.

Exercise 76. Show that classical Gabidulin codes are vector MRD codes, by taking a non-
zero codeword c = (f (g1 ), . . . , f (gn )) and considering the Fq -dimension of the kernel of the
q-polynomial f .
In order to introduce the generalized Gabidulin codes, we first have to define the rank
analog of the Vandermonde matrix.

Definition 77 (Moore Matrix, [166]). Let (v1 , . . . , vn ) ∈ Fnqm . We denote the by

Ms,k (v1 , . . . , vn ) ∈ Fqk×n

m

17
the s-Moore matrix:
v1 ··· vn
 
[s] [s]
 v1 ··· vn 
Ms,k (v1 , . . . , vn ) =  .. .. ,
 
 . . 
[s(k−1)] [s(k−1)]
v1 · · · vn

where [i] = q i .
Definition 78 (Generalized Gabidulin Code, [139]). Let g1 , . . . , gn ∈ Fqm be linearly inde-
pendent over Fq and let s be coprime to m. The generalized Gabidulin code C ⊂ Fnqm of
dimension k is defined as the rowspan of Ms,k (g1 , . . . , gs ).
For s = 1, we can see that this coincides with the classical Gabidulin codes, which have
the generator matrix
g1 ··· gn
 
 g1q · · · gnq 
M1,k (g1 , . . . , gn ) =  .. .. .
 
 . . 
k−1 k−1
g1q · · · gnq
Since the Moore matrix can be seen as a rank analog of a Vandermonde matrix, a gen-
eralized Gabidulin code can be seen as a rank analog of a generalized Reed-Solomon code.
In fact, as generalized Reed-Solomon codes are MDS codes, generalized Gabidulin codes are
vector MRD codes.
Theorem 79 ([139]). The generalized Gabidulin code C ⊂ Fnqm of dimension k is a vector
MRD code.
In addition, as in the Hamming metric we have nice duality results.
Proposition 80 ([139]). Let C ⊂ Fnqm be a k dimensional generalized Gabidulin code, then
C ⊥ ⊂ Fnqm is a n − k dimensional generalized Gabidulin code.
This duality result holds also more in general; for all vector MRD codes.
Proposition 81 ([139]). Let C ⊂ Fnqm be a k-dimensional vector MRD code, then C ⊥ ⊂ Fnqm
is a (n − k)-dimensional vector MRD code.
The classical Gabidulin code has been the first rank-metric code introduced into code-
based cryptography in [101], which is known as the GPT system. Other classes of rank-metric
codes that are used in code-based cryptography are the rank analogues of LDPC and MDPC
codes. Instead of asking for a low (respectively moderate) number of non-zero entries within
each row of the parity-check matrix, one now has to consider the Fq -subspace generated by
the coefficients of the parity-check matrix.
(n−k)×n
Definition 82 (Low Rank Parity-Check Code (LRPC), [102]). Let H ∈ Fqm be a full
rank matrix, such that its coefficients hi,j generate an Fq -subspace F of small dimension d,

F = h(hi,j )i,j iFq .

The code C ⊂ Fnqm having parity-check matrix H is called a low rank parity-check (LRPC)
code of dual weight d and support F .

18
2.3 Cryptography
As coding theory is the art of reliable communication, this goes hand in hand with cryptogra-
phy, the art of secure communication. In cryptography we differ between two main branches,
symmetric cryptography and asymmetric cryptography.
In symmetric cryptography there are the two parties that want to communicate with each
other and prior to communication have exchanged some key, that will enable them a secure
communication. Such secret key exchange might be performed using protocols such as the
Diffie-Hellman key exchange [91], which itself lies in the realm of asymmetric cryptography.
More mathematically involved is the branch of asymmetric cryptography, where the two
parties do not share the same key. In this survey we will focus on two main subjects of
asymmetric cryptography, that were also promoted by the NIST standardization call [74],
namely public-key encryption (PKE) schemes and digital signature schemes.
Many of these cryptographic schemes seem very abstract when discussed in generality. To
get a grasp of the many definitions and concepts, we will also provide some easy examples.
First of all, let us recall the definition of a hash function. A hash function is a function that
compresses the input value to a fixed length. In addition, we want that it is computationally
hard to reverse a hash function and also to find a different input giving the same hash value.
In this chapter, we denote a publicly known hash function by H.

2.3.1 Public-Key Encryption

Let us start with public-key encryption (PKE) schemes. A PKE consists of three steps:
1. key generation,
2. encryption,
3. decryption.
The main idea is that one party, usually called Alice, constructs a secret key S and a connected
public key P. The public key, as the name suggests, is made publicly known, while the secret
key is kept private.
This allows an other party, usually called Bob, to use the public key to encrypt a message
m by applying the public key, gaining the so called cipher c.
The cipher is now sent through the insecure channel to Alice, who can use her secret key
S to decrypt the cipher and recover the message m.
An adversary, usually called Eve, can only see the cipher c and the public key P. In order
for a public-key encryption scheme to be considered secure, it should be infeasible for Eve to
recover from c and P the message m. This also implies that the public key should not reveal
the secret key.
What exactly does infeasible mean, however? This is the topic of security. For a cryp-
tographic scheme, we define its security level to be the average number of binary operations
needed for an adversary to break the cryptosystem, that means either to recover the message
(called message recovery) or the secret key (called key recovery).
Usual security levels are 280 , 2128 , 2256 or even 2512 , meaning for example that an adversary
is expected to need at least 280 binary operations in order to reveal the message. These are
referred to as 80 bit, 128 bit, 256 bit, or 512 bit security levels.
Apart from the security of a PKE, one is also interested in the performance, including how
fast the PKE can be executed and how much storage the keys require. Important parameters
of a public-key encryption are

19
 Table 1: Public-Key Encryption

ALICE BOB

KEY GENERATION
Construct a secret key S
Construct a connected public key P
P
−→
ENCRYPTION
Choose a message m
Encrypt the message c = P(m)
c
←−
−
DECRYPTION
Decrypt the cipher m = S(c)

• the public key size,

• the secret key size,
• the ciphertext size,
• the decryption time.
These values are considered to be the performance of the public-key encryption. With ’size’
we intend the bits that have to be sent or stored for this key, respectively for the cipher.
Clearly, one prefers small sizes and a fast decryption.
As an example for a PKE, we can choose one of the most currently used schemes, namely
RSA [192].
Example 83 (RSA).
1. Key Generation: Alice chooses two distinct primes p, q and computes n = pq and
ϕ(n) = (p − 1)(q − 1). She chooses a natural number e < ϕ(n), which is coprime to
ϕ(n). The public key is P = (n, e) and the secret key is S = (p, q).
2. Encryption: Bob chooses a message m and encrypts it by computing

c = me mod n.

3. Decryption: Alice can decrypt the cipher by first computing d and b such that

de + bϕ(n) = 1.

Since  −b
cd = (me )d = m1−bϕ(n) = m mϕ(n) = m1−b = m,
she can recover the message m.

20
 Eve sees n but there is no feasible algorithm to compute p and q.
Exercise 84. Assume that Alice has chosen p and q to have 100 digits. How large is the public
key size?
√
Exercise 85. Assume that the fastest known algorithm to factor n into p and q costs n binary
operations. In order to reach a security level of 280 binary operations, how large should Alice
choose p and q?
Exercise 86. To give you also a feeling for cryptanalysis; why should we always choose two
distinct primes? Or in other words; how can you attack RSA if p = q?

2.3.2 Key-Encapsulation Mechanisms

A key-encapsulation mechanism (KEM) is a way to transmit a key for symmetric cryptography
using an asymmetric cryptosystem.
Public-key systems are often not optimal to transmit longer messages. Instead, the two
parties often use a public-key system to share a random m, usually a number or vector. Then
both parties use an agreed-on function, called key derivation function, to calculate a key M
from m.
The function is usually chosen to be a one-way function, meaning that computing back
M with only the knowledge of the function and m is not computationally feasible. With this
key, the parties can then encrypt their message.
Most KEM schemes are based on Shoup’s idea [202]. In Table 2 we give an outline, in
which we assume that a public-key system is given. For this, let H denote a hash function.
As mentioned before, it is often the case that instead of directly encrypting the key M ,
a random m is encrypted. From this m, both parties can generate a key using the agreed-on
key derivation function.
Example 87. For an example of a KEM we again consider RSA.

1. Key Generation: Alice choose two distinct primes p, q and computes n = pq and
ϕ(n) = (p − 1)(q − 1). Alice also chooses a positive integer e < ϕ(n), which is coprime
to ϕ(n). The public key is given by P = (n, e) and the private key is given by (p, q).

2. Encryption: Bob chooses a random message m and computes its hash M = H(m). He
then performs the usual steps of RSA, that is: he encrypts c = me mod n and sends
this to Alice.

3. Decryption: Alice can compute d = e−1 mod ϕ(n) and computes cd = m mod n.
Also Alice can now compute the shared key M = H(m).

2.3.3 Digital Signature Schemes

Digital Signature schemes aim at giving a guarantee of the legitimate origin to an object,
such as a digital message, exactly as signing a letter to prove that the sender of this letter is
really you.
In this process we speak of authentication, meaning that a receiver of the message can
(with some probability) be sure that the sender is legit, and of integrity, meaning that the
message has not been altered.
A digital signature scheme again consists of three steps:

1. key generation,

21
 Table 2: Key-Encapsulation Scheme

ALICE BOB

KEY GENERATION
Generate a secret key S
Construct a connected public key P
P
−→
ENCRYPTION
Choose a random message m
Generate a key M = H(m)
Use the public key P to encrypt m as
cipher c
c
←−
−
DECRYPTION
Using the secret key S, decrypt c to get m
compute H(m) = M
COMMUNICATION
The parties may now communicate with each
other since they both possess a key to encrypt
and decrypt messages

2. signing,

3. verification.

In digital signature schemes we consider two parties, one is the prover, that has to prove his
identity to the second party called verifier, that in turn, verifies the identity of the prover.
As a first step, the prover constructs a secret key S, which he keeps private and a public
key P, which is made public. The prover then chooses a message m, and creates a signature
s using his secret key S and the message m, getting a signed message (m, s).
The verifier can easily read the message m, but wants to be sure that the sender really
is the prover. Thus, he uses the public key P and the knowledge of the message m on the
signature s to get authentication.
The security of a digital signature scheme introduces a new person, the impersonator. An
impersonator, tries to cheat the verifier and acts as a prover, however without the knowledge
of the secret key S. An impersonator wins, if a verifier has verified a forged signature. This
comes with a certain probability, called cheating probability or soundness error. In order to
ensure integrity a digital signature should always involve a secret key as well as the message
itself.
Clearly, the secret key should still be infeasible to recover from the publicly known private
key, thus one still has the usual adversary, called Eve, and a security level, as in a public-key
encryption scheme.

22
 Table 3: Digital Signature Scheme

PROVER VERIFIER

KEY GENERATION
Construct a secret key S
Construct a connected public key P
P
−→
SIGNING
Choose a message m
Construct a signature s from S and m
m,s
−−→
VERIFICATION
Verify the signature s using P and m

The performance of a digital signature scheme consists of

• the communication cost, that is the total number of bits, that have been exchanged
within the process,

• the signature size,

• the public key size,

• the secret key size,

• the verification time.

An easy example for a signature scheme is given by turning the RSA public-key encryption
protocol into a signature scheme.
Example 88 (RSA Signature Scheme).

1. Key Generation: Alice chooses two distinct primes p, q and computes n = pq and
ϕ(n) = (p − 1)(q − 1). She chooses a natural number e < ϕ(n), which is coprime to
ϕ(n). She computes d and b such that

de + bϕ(n) = 1.

The public key is P = (n, e) and the secret key is S = (p, q, d).

2. Signing: Alice chooses a message m and signs it by computing

s = md mod n.

She then sends m, s to Bob.

23
 3. Verification: Bob can verify the signature s by checking if

se = m mod n.

Exercise 89. How would an impersonator forge a signature provided that the impersonator
does not care about the content of the message m?

2.3.4 Zero-Knowledge Identification Scheme

Since digital signature schemes can be constructed using the Fiat-Shamir transform [1] on
zero-knowledge identification (ZKID) schemes, we will also introduce the concept of ZKID
and then of the transform itself.
The process and notation for a ZKID scheme are similar to that of a digital signature
scheme. We have two parties, a prover and a verifier. Different to a digital signature scheme,
the prover does not want to prove his identity to the verifier, but rather convince the verifier
of his knowledge of a secret object, without revealing said object.
A ZKID scheme consists of two stages: key generation and verification. The verification
process can consist of several communication steps between the verifier and the prover, in
particular will we be interested in the following scheme:
1. The prover prepares two commitments c0 , c1 , and sends them to the verifier.
2. The verifier randomly picks a challenge b ∈ {0, 1}, and sends it to the prover.
3. The prover provides a response rb that only allows to verify cb .

4. The verifier checks the validity of cb , usually by recovering cb using rb and the public
key.
A ZKID scheme has three important attributes:
1. Zero-knowledge: this means that no information about the secret is revealed during the
process.
2. Completeness: meaning that an honest prover will always get accepted.
3. Soundness: for this, we want that an impersonator has only a small cheating probability
to get accepted.
Again, for the performance of the scheme, we have
• the communication cost,
• the secret key,
• the public key size,

• the verification time.

In order to achieve an acceptable cheating probability, the protocols are often repeated
several times and only if each instance was verified will the prover be accepted. This technique
is known as compression technique and was first introduced in [2]. It is also possible to reduce
the overall communication cost using this technique. We will thus, explain this method in
detail.

24
 Table 4: ZKID Scheme

PROVER VERIFIER

KEY GENERATION
Construct a secret key S
Construct a connected public key P
P
−→
VERIFICATION
Construct commitments c0 , c1
c0 ,c1
−−−→
Choose b ∈ {0, 1}
b
←−
−
Construct response rb
r
b
−→
Verify cb using rb

Before the first round, the prover generates the commitments for all the N rounds, that
cib
is for i ∈ {1, . . . , N } and b ∈ {0, 1}. The prover then sends the hash value

c = H c10 , c11 , . . . , cN N


0 , c1

to the verifier.
In the i-th round, after receiving the challenge b, the prover sets its response rb such that
the verifier can compute cib , and additionally includes ci1−b .
At the end of each round, the verifier uses rb to compute cib , and stores it together with
ci1−b .
After the final round N , the verifier is able to check validity of the initial commitment c,
by computing the hash of all the stored cib .
This way, one hash is sent at the beginning of the protocol, and only one hash (instead
of two) is transmitted in each round and thus, the number of exchanged hash values reduces
from 2N to N + 1.
An easy example is again provided using the hardness of integer factorization, namely the
Feige-Fiat-Shamir protocol [97].
Example 90 (Feige-Fiat-Shamir).

1. Key Generation: The prover chooses two distinct primes p, q and computes n = pq
and some positive integer k. The prover chooses s1 , . . . , sk coprime to n. The prover
now computes
vi ≡ s−2
i mod n.
The public key is given by P = (n, v1 , . . . , vk ). The secret key is given by S =
(p, q, s1 , . . . , sk ).

25
 Figure 1: Compression Technique for N Rounds

PROVER VERIFIER
Generate cib , for i ∈ {1, . . . , N } and b ∈
{0, 1}
Set c = H c10 , c11 , . . . , cN N


0 , c1
c
−→
←−−−−−−−−−−−−−−−−−−−−−−−−
Repeat single round for N times
−−−−−−−−−−−−−−−−−−−−−−−−−→
Check validity of c

GENERIC i-th ROUND

←−−−−−−−−−−−−−−−−−−−−−−
Exchange additional messages
−−−−−−−−−−−−−−−−−−−−−−−→
Choose b ∈ {0, 1}
b
←−
−
Construct response rb
rb , ci1−b
−−−−−→
Store ci1−b , compute and store cib

2. Verification: The prover chooses a random integer c and a random sign σ ∈ {−1, 1}
and computes
x ≡ σc2 mod n
and sends this to the verifier. The verifier chooses the challenge b = (b1 , . . . , bk ) ∈ Fk2
and sends b to the prover. The prover then computes the response
Y
r≡c sj mod n
bj =1

and sends r to the verifier. The verifier can now check whether
Y
x ≡ ±r 2 vj mod n.
bj =1

Eve, the impersonator, can see the public vi but she does not know the si . She can pick
a random r and b = (b1 , . . . , bk ) ∈ Fk2 . She then computes
Y
x ≡ r2 vj mod n
bj =1

and sends x to the verifier. The verifier will then challenge her with his b′ , but Eve simply
returns her r. If Eve has correctly chosen b = b′ , she will be verified.
Exercise 91. What is the cheating probability of this scheme? If you repeat this process t
times before accepting the prover, what is now your cheating probability?
Exercise 92. Let us assume that k = 10. How many times should you repeat this process in
order to reach a cheating probability of at least 2128 ?

26
2.3.5 Fiat-Shamir Transform
The Fiat-Shamir transform allows us to build a signature scheme from a zero-knowledge
identification scheme. To avoid the communication with the verifier that randomly picks a
challenge, the challenge is replaced with the seemingly random hash of the commitment and
message.
The following table follows the general description of the Fiat-Shamir transform from
[1]. We assume that we are given a zero-knowledge identification scheme and a public hash
function H.
Table 5: Fiat-Shamir Transform

PROVER VERIFIER

KEY GENERATION
Given the public key P and the secret key S
of some ZKID and a message m
Choose a commitment c
Compute a = H(m, c)
Compute a response r to the challenge a
The signature is the pair s = (a, r)
m,s
−−→
VERIFICATION
Use the response r and the public key P
to construct the commitment c
Check if H(m, c) = a

Using the Fiat-Shamir transform we can turn the Feige-Fiat-Shamir ZKID into a signature
scheme.
Example 93 (Fiat-Shamir digital signature scheme).

1. Key Generation: Let H be a publicly known hash function. The prover chooses
a positive integer k and two distinct primes p, q and computes n = pq. The prover
chooses s1 , . . . , sk integers coprime to n and computes vi ≡ s−2 i mod n for all i ∈
{1, . . . , k}. The secret key is given by S = (p, q, s1 , . . . , sk ) and the public key is given
by (n, v1 , . . . , vk ).

2. Verification: the prover chooses randomly c1 , . . . , ct < n and computes xi ≡ c2i mod n
for all i ∈ {1, . . . , t}. In order to bypass the communication with the verifier from before,
the prover computes the first kt bits of

H(m, x1 , . . . , xt ) = (a1,1 , . . . , at,k ) = a.

Q
The prover now computes ri ≡ ci sj mod n for all i ∈ {1, . . . , t} and sends
aij =1

27
 (m, a, r1 , . . . , rt ) to the verifier. The verifier computes
Y
zi ≡ ri2 vj mod n
ai,j =1

for all i ∈ {1, . . . , t} and checks if

H(m, z1 , . . . , zt ) = a.

3 Code-Based Public-Key Encryption Frameworks

Code-based cryptography and in particular code-based PKEs first came up with the seminal
work of Robert J. McEliece in 1978 [160]. The main idea of code-based cryptography is to
base the security of the cryptosystem on the hardness of decoding a random linear code.
Since this problem is NP-hard, code-based cryptography is considered to be on of the most
promising candidates for post-quantum cryptography.
In a nutshell, code-based cryptosystems work as follows: the private key is given by a
linear code C, which can efficiently correct t errors. The public key is C ′ a disguised version
of the linear code, which should not reveal the secret code, in fact, should behave randomly.
While anyone with C ′ , the publicly known code, can encode their message and possibly
add some intentional errors, an attacker would only see a random code and in order to recover
the message would need to decode it.
The constructor of the secret code however, can transform the encoded message to a
codeword of C, which is efficiently decodable.
The first code-based cryptosystem by McEliece uses the generator matrix G as a rep-
resentation of the secret code and in order to disguise the generator matrix, one computes
G′ = SGP, where S is an invertible matrix, thus only changing the basis of the code, and P
is a permutation matrix, thus giving a permutation equivalent code. In the encryption step
the message is then encoded through G′ and an intentional error vector e is added.
An equivalent [151] cryptosystem was proposed by Niederreiter in [170], where one uses
the parity-check matrix H, and the disguised parity-check matrix H′ = SHP, instead of the
generator matrix and the cipher is given by the syndrome of an error vector, i.e., s = H′ e⊤ .
The code-based system proposed by Alekhnovich uses the initial idea of McEliece, but
twists the disguising of the code, by adding a row to the parity-check matrix, which is a
erroneous codeword, thus making the error vector the main part of the secret key. The
idea of Alekhnovich, which is not considered practical has been the starting point of a new
framework, the quasi-cyclic scheme. Finally, the McEliece framework has also been introduced
for the rank metric by Gabidulin, Paramonov and Tretjakov and is usually denoted by the
GPT system.
Clearly, all of these cryptosystems (except for Alekhnovich’s, which uses a random code)
have been originally proposed for a specific code. In the following we will introduce the idea
behind the systems as frameworks, thus without considering a specific code.

3.1 McEliece Framework

Although McEliece originally proposed in [160] to use a binary Goppa code as secret code,
one usually denotes by the McEliece framework the following. Alice, the constructor of the
system, chooses an [n, k] linear code C over Fq , which can efficiently decode t errors through
the decoding algorithm D. Instead of publishing a generator matrix G of this code, which

28
would then reveal to everyone the algebraic structure of C and especially how to decode,
one hides G through some scrambling: we compute G′ = SGP, for some invertible matrix
S ∈ GLk (Fq ) and an n × n permutation matrix P. Hoping that the new matrix G′ and the
code it generates C ′ seem random (although C ′ is permutation equivalent to C), Alice then
publishes this disguised matrix G′ and the error correction capacity t of C.
Bob who wants to send a message m ∈ Fkq to Alice can then use the public generator
matrix G′ to encode his message, i.e., mG′ , and then adds a random error vector e ∈ Fnq of
Hamming weight up to t to it, i.e., the cipher is given by c = mG′ + e.
An eavesdropper, Eve, only knows G′ , t and the cipher c. In order to break the cryptosys-
tem and to reveal the message m, she would need to decode C ′ , which seems random to her.
Thus, she is facing an NP-complete problem and the best known solvers have an exponential
cost.
However, Alice can revers the disguising by computing cP−1 , which results in a codeword
of C added to some error vector of weight up to t. That is

cP−1 = mSG + eP−1 .

Through the decoding algorithm D Alice gets mS and thus by multiplying with S−1 , she
recovers the message m.

Table 6: McEliece Framework

ALICE BOB

KEY GENERATION
Choose a linear code C ⊆ Fnq of dimension k
and error correction capacity t. Let G be a
k × n generator matrix of C.
Choose randomly S ∈ GLk (Fq ) and an n × n
permutation matrix P. Compute G′ = SGP.
The public key is given by P = (t, G′ ) and
S = (G, S, P)
P
−→
ENCRYPTION
Choose a message m ∈ Fkq and a random
error vector e ∈ Fnq of weight at most t
Encrypt the message c = mG′ + e
c
←−
−
DECRYPTION
Decrypt the cipher, by decoding cP−1 =
mSG + eP−1 to get mS, and finally recover
the message as m = (mS)S−1

Since this is the key part of this survey, we will provide a toy example explained in full
detail.

29
Example 94. Let C be the [7, 4] binary Hamming code, which can efficiently correct 1 error.
We take as 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

We choose S ∈ GL4 (F2 ) to be  

0 1 1 1
 
1 0 1 1
 
S= 
1 0 1 0
 
 
0 0 1 1
and the permutation matrix P to be
 
0 1 0 0 0 0 0
 
0 0 0 1 0 0 0
 
 
0 0 0 0 0 1 0
 
 
P = 1 0 0 0 0 0 0 .
 
 
0 0 0 0 1 0 0
 
 
0 0 1 0 0 0 0
 
 
0 0 0 0 0 0 1

We thus compute  
1 0 0 1 0 1 1
 
1 1 1 0 0 1 0
 
′
G =
 
0 1 0 0 1 1 1

 
1 0 0 1 1 0 0
and publish (G′ , 1), since t = 1. The message we want to send is m = (1, 0, 1, 1) ∈ F42 and
thus we compute
mG′ = (0, 1, 0, 1, 0, 1, 0).
Now, we choose an error vector e ∈ F72 of Hamming weight 1, e.g.,
e = (1, 0, 0, 0, 0, 0, 0).
Thus, the cipher is given by
c = (1, 1, 0, 1, 0, 1, 0).
The constructor, who possesses P can compute
cP−1 = cP⊤ = (1, 1, 1, 1, 0, 0, 0).

30
We can now use the decoding algorithm of Hamming codes to recover mS = (1, 1, 1, 0) and
by multiplying with  
0 1 0 1
 
1 0 0 1
 
−1
S =  
0 1 1 1

 
0 1 1 0
we recover the message m = (1, 0, 1, 1).
In this toy example, an attacker which sees G′ , t, c has two possibilities:

1. recover the message directly,

2. recover the secret key.

The first type of attack could work as follows:

1. We bring G′ into a row-reduced form, that is for G′ = [A | B] we compute A−1 G′ ,

giving  
1 0 0 0 1 1 0
 
0 1 0 0 1 1 1
 
G= .
0 0 1 0 0 1 1
 
 
0 0 0 1 1 0 1

With G = [Id4 | C] we can also compute the parity-check matrix as H = [C⊤ | Id3 ],
that is  
1 1 0 1 1 0 0
 
H = 1 1 1 0 0 1 0 .
 
 
0 1 1 1 0 0 1

2. We can now compute the syndrome of c through H, i.e.,

⊤
s = cH = (1, 1, 0).
⊤
Note, that this is also the syndrome of the error vector e, i.e., eH = s. Since there is
only one entry of e that is non-zero, we must have that the syndrome s is equal to the
column hi where ei 6= 0. And in fact, s = h1 , thus we have found

e = (1, 0, 0, 0, 0, 0, 0)

and
c − e = mG′ = (0, 1, 0, 1, 0, 1, 0).
Note, that the moment we know the error vector, we can use linear algebra to recover
the message. Since this is a toy example, we will also execute this step.

31
 3. Denote by m = mA, then

(0, 1, 0, 1, 0, 1, 0) = mG′ = mAA−1 G′ = mG.

Since G = [Id4 | C], we have that

mG = (m, mC).

Hence, we can directly read off that m = (0, 1, 0, 1) and by multiplying with A−1 , we
recover m = (1, 0, 1, 1).
The second type of attack, namely a key-recovery attack, is in nature more algebraic. Know-
ing, that the secret code is a [7, 4] binary code that can correct one error, the suspicion that
the secret code is a Hamming code is natural. If not, one could proceed as follows.
1. We choose a set I ⊂ {1, . . . , n} of size k, which is a possible information set. Let us
denote by G′I the matrix consisting of the columns of G′ indexed by I.

2. We compute (G′I )−1 G′ to get an identity matrix in the columns indexed by I.

3. Choose the permutation matrix P′ which brings the identity matrix in the columns
indexed by I to the first k positions.
With this, if one chose I = {4, 2, 6, 3} (the order matters here only for the permutation
matrix) we recover G and will now finally be able to read off the secret code and thus also
know its decoding algorithm. With this, we can compute from G and G′ the matrices S and
P.
Although this example for the McEliece framework is clearly using a code that should not
be used in practice, it shows in a few easy steps the main ideas of the attacks. For example,
the minimum distance of a code should be large enough, since else an easy search for the
error vector will reveal the message, and also the public code parameters should not reveal
anything on the structure of the secret code, meaning that there should be many codes having
such parameters.
These two different kind of attacks aim at solving two different problems the security of
the McEliece system is based upon:
1. decoding the erroneous codeword, assuming that the code is random, should be hard,

2. the public code, which is permutation equivalent to the secret code, should not reveal
the algebraic structure of the secret code.
Only if both of these points are fulfilled is the security of the cryptosystem guaranteed.
We will see more on this in Section 5.

3.2 Niederreiter Framework

The Niederreiter framework [170] uses the parity-check matrix instead of the generator matrix,
resulting in an equivalently secure system [151]. Niederreiter originally proposed to use GRS
codes as secret codes, however, we will consider with the Niederreiter framework the more
general scheme.
Alice again chooses an [n, k] linear code C over Fq which can efficiently decode up to t
errors. She then scrambles a parity-check matrix H of C by computing H′ = SHP, for some

32
invertible matrix S ∈ GLn−k (Fq ) and an n × n permutation matrix P. She publishes the
seemingly random parity-check matrix H′ together with the error correction capacity t.
Bob can then encrypt a message m ∈ Fnq of Hamming weight up to t, simply by computing
the syndrome of m through the parity-check matrix H′ , i.e., the cipher is given by c = mH′⊤ .
While Eve would only have access to H′ , which looks random to her, t and c, she faces
an NP-hard problem and can only apply exponential time algorithms in order to recover m.
Alice, on the other hand, can recover the message by computing S−1 c, which results in a
syndrome of her code C, which she knows how to decode. That is

S−1 c⊤ = HPm⊤ ,
where Pm⊤ still has Hamming weight up to t. Thus, she recovers Pm⊤ and by multiplication
with P−1 , she recovers the message m.

Table 7: Niederreiter Framework

ALICE BOB

KEY GENERATION
Choose a linear code C ⊆ Fnq of dimension k
that can efficiently correct t errors. Let H be
a (n − k) × n parity-check matrix of C
Choose randomly S ∈ GLn−k (Fq ) and an n×n
permutation matrix P. Compute H′ = SHP
The public key is given by P = (t, H′ )
P
−→
ENCRYPTION
Choose a message m ∈ Fnq of weight at
most t
Encrypt the message c⊤ = H′ m⊤
c
←−
−
DECRYPTION
Decrypt the cipher by decoding S−1 c⊤ =
HPm⊤ to get Pm⊤ , and finally recover the
message as m⊤ = P−1 (Pm⊤ )

We provide the same toy example for the Niederreiter framework.

Example 95. This time, we start with a parity-check matrix H of the [7, 4] binary Hamming
code, given by  
1 1 0 1 1 0 0
 
H = 1 0 1 1 0 1 0 .
 
 
0 1 1 1 0 0 1

33
We choose as invertible matrix S ∈ G3 (F2 ) the following
 
1 1 0
 
S = 0 1 1
 
 
0 0 1
and as permutation matrix we choose
 
0 0 1 0 0 0 0
 
0 0 0 0 1 0 0
 
 
1 0 0 0 0 0 0
 
 
P = 0 0 0 0 0 0 1 .
 
 
0 1 0 0 0 0 0
 
 
0 0 0 1 0 0 0
 
 
0 0 0 0 0 1 0
With this, we compute
 
0 0 1 1 1 1 0
 
H′ = SHP = 0 1 1 1 0 0 1 .
 
 
1 0 0 1 0 1 1

The public key is given by H′ and t = 1. Assume that we want to send the message m =
(0, 0, 1, 0, 0, 0, 0) ∈ F72 . For this, we compute the cipher as the syndrome of m through H′ ,
i.e.,
c = m(H′ )⊤ = (1, 1, 0)
and send it to the constructor.
The constructor which knows S and P first computes
S−1 c⊤ = HPm⊤ = (0, 1, 0)⊤ ,
and then uses the decoding algorithm of the Hamming code to get
mP⊤ = (0, 0, 0, 0, 0, 1, 0).
Finally multiplying this with P−1 we get the message m = (0, 0, 1, 0, 0, 0, 0).
The security is clearly equivalent to that of Example 94, due to the duality of G and H
and the attacks form Example 94 work here as well.

3.3 Alekhnovich’s Cryptosystems

Alekhnovich’s cryptosystem [12] marks the first code-based cryptosystem with a security
proof, i.e., it relies solely on the decoding problem. This seminal work lays the foundations of
modern code-based cryptography, where researchers try to construct code-based cryptosys-
tems with a provable reduction to the problem of decoding a random linear code.
There are two variants to this cryptosystem, both are relying on the following hard prob-
lem:

34
Problem 96. Given a code C, distinguish a random vector from an erroneous codeword of C.
Note that variations of these cryptosystem are used in [5, 15]. For the following description
of the two variants we rely on the survey [229] and for more details we also refer to [229].

3.3.1 The First Variant

The idea is not to keep the parity-check matrix or generator matrix of the code hidden, but a
random error vector. Thus, a random matrix A is chosen and to this one adds the row xA+e,
thus an erroneous codeword of the code generated by A is added resulting in the augmented
matrix H. Let us consider C to be Ker(H), that is the code having H as parity-check matrix.
One then publishes G, a generator matrix of C.
In this variant one only encrypts a single bit. One either sends as cipher an erroneous
codeword of C ⊥ or a random vector, depending if 0 or 1 was encrypted. Finally, using the
secret error vector e, one can compute the standard inner product of the cipher and e and
will recover the message, with some decryption failure.
More in detail, if the cipher was given by aG + e′ , for a random a ∈ F2n−k and a random
error vector e′ ∈ Fn2 of weight t, then

he, aG + e′ i = he, aGi + he, e′ i.

⊥ ′
√ he, aGi = 0, since ′e ∈ C by construction. In addition, since wtH (e) = wtH (e ) =
Note that
t = o( n), we have that he, e i = 0 with high probability. If the cipher was given by a random
vector c ∈ Fn2 instead, then with probability 1/2 we get he, ci = 1.
Thus, there is a decryption failure in the case m = 1 of probability 1/2. In order to get
a reliable system one can encrypt the message multiple times. A systematic description of
Alekhnovich’s First Variant can be found in Table 8.
We give an example of the first variant.
Example 97. Let  
1 1 0 0 0 0
 
1 0 1 0 0 0
 
A= .
0 0 0 1 1 0
 
 
0 0 0 1 0 1
We choose m = (0, 1, 0, 1), e = (1, 0, 0, 0, 0, 0) and compute

mA + e = (0, 0, 1, 1, 0, 1).

If we append this to the matrix A, we get the matrix

 
1 1 0 0 0 0
 
1 0 1 0 0 0
 
 
H = 0 0 0 1 1 0 .
 
 
0 0 0 1 0 1
 
 
0 0 1 1 0 1

35
 Table 8: Alekhnovich First Variant

ALICE BOB

KEY GENERATION
√
Let t ∈ o( n) and choose a random matrix
k×n
A ∈ F2
Let e ∈ Fn2 be a random vector of weight t and
let x ∈ Fk2 be a random vector
Compute y = xA + e and H⊤ = (A⊤ , y⊤ )
Let C = ker(H) and choose a generator matrix
(n−k)×n
G ∈ F2 of C
The public key is given by P = (G, t) and the
secret key is S = e
P
−→
ENCRYPTION
Choose a message m ∈ F2
If m = 0: choose a ∈ F2n−k and e′ ∈ Fn2
of weight t at random, send c = aG + e′
If m = 1: choose a random vector c ∈ Fn2
c
←−
−
DECRYPTION
Decrypt the cipher, by computing b = he, ci.
If m = 0: b = 0 with high probability
If m = 1: b = 1 with probability 1/2

The dual code C of H has a generator matrix

 
G= 0 0 0 1 1 1 .

We encrypt 0 as
c0 = (0, 0, 0, 1, 1, 1) + (0, 1, 0, 0, 0, 0) = (0, 1, 0, 1, 1, 1),
and 1 as random vector
c1 = (1, 0, 1, 0, 0, 1).
To decrypt the cipher c, we compute he, ci. If we receive c0 , we compute that he, c0 i = 0.
If we receive c1 , we see that he, c1 i = 1.

3.3.2 The Second Variant

In this variant one generalizes the idea of the first variant and construct directly a matrix M
in which every row is an erroneous codeword.

36
 n/2×n n×n/2
This is achieved by choosing at random A ∈ F2 , X ∈ F2 and E ∈ F2n×n having
row weight t. Then one computes the matrix M = XA + E.
Let C0 be a binary code of length n, that can correct codewords transmitted through a
binary symmetric channel (BSC) with transition probability t2 /n. Let us consider
ϕ : Fn2 → Fn2 ,
x 7→ Mx.
Define
C1 = ϕ−1 (C0 ) = {x ∈ Fn2 | ϕ(x) ∈ C0 },
C2 = Ker(A) and finally C = C1 ∩C2 . Let G ∈ F2k×n be a generator matrix of C. This generator
matrix is made public, while the error vectors in E are kept secret.
k/2 k/2
To encrypt a message m ∈ F2 we first append a random vector r ∈ F2 to get x =
(m, r) ∈ Fk2 and then compute
c = xG + e,
for some random error vector e ∈ Fn2 of weight t.
To decrypt we now compute
y⊤ = Ec⊤ = E(xG + e)⊤
= E(xG)⊤ + Ee⊤
= XA(xG)⊤ + E(xG)⊤ + Ee⊤
= M(xG)⊤ + Ee⊤ ,
where we have used that Aa⊤ = 0 for all a ∈ C, in particular also for xG. Note that
z⊤ = M(xG)⊤ ∈ C0 , since C ⊆ C1 and ϕ(C1 ) = C0 . Finally, every row ei of E has weight t
and thus, hei , ei = 1 with probability at most t2 /n. Thus, the decoding algorithm of C0 on y
gives z with high probability. Finally, we can solve the linear system
xG = ϕ−1 (z)
to get x and the first k/2 bits reveal the message m.

3.4 Quasi-Cyclic Scheme

The quasi-cyclic scheme is inspired by the scheme of Alekhnovich, introduced in [8] and used
in [5]. Similarly to Alekhnovich’s schemes, it is a probabilistic approach to encryption schemes
and does not hide the initial code, which needs to be efficiently decodable. The message gets
encrypted as codeword to which an error, too large to decode, gets added. With the knowledge
of the private key parts of this error can be cancelled out resulting (with high probability) in a
vector which can be decoded to recover the message. We present the scheme in the Hamming
metric, but note that the scheme can also be adapted to the rank metric.
Let n be a positive integer, p be a prime and R = Fp [x]/(xn − 1). We identify an element
Pn−1 i n
a = i=0 ai x ∈ R with the vector a = (a0 , a1 , . . . , an−1 ) ∈ Fp and vice versa. Thus,
whenever we write a ∈ R has Hamming weight w, we refer to the Hamming weight of its
corresponding vector in Fnp , i.e.,
n−1
!
X
wtH (a) = wtH ai xi = wtH (a0 , . . . , an−1 ) = wtH (a).
i=0
The quasi-cyclic framework uses two types of codes:

37
 Table 9: Alekhnovich Second Variant

ALICE BOB

KEY GENERATION
n/2×n
Choose random matrices A ∈ F2 ,X ∈
n×n/2 n×n
F2 and E ∈ F2 of row weight t
Set M = XA + E ∈ GLn (F2 )
Let C0 be a binary code of length n that
can efficiently correct codewords transmitted
through a BSC of transition probability t2 /n
Let ϕ be the map x 7→ Mx
Let C = ϕ−1 (C0 ) ∩ Ker(A)
Let G ∈ F2k×n be a generator matrix of C
The public key is given by P = (G, t) and
S=E
P
−→
ENCRYPTION
k/2
Choose a message m ∈ F2 and choose
k/2
randomly r ∈ F2 and e ∈ Fn2 of weight
t
Compute x = (m, r) ∈ Fk2 and
c = xG + e
c
←−
−
DECRYPTION
Decrypt the cipher, by computing y⊤ =
Ec⊤ = z⊤ + Ee⊤
and use the decoding algorithm of C0 on y to
get z
Recover x from the linear system xG =
ϕ−1 (z) and thus m

1. An [n, k] linear code C over Fp , which can efficiently decode δ errors. A generator matrix
G ∈ Fpk×n is made public.
2. A
 random double circulant [2n, n] code presented through a parity-check matrix H =
Idn | diag(h) , which does not require to be efficiently decodable and is also made
public.
√
Let w, wr and we be positive integers all in the range of n/2. These are publicly known
parameters.
The cryptosystem then proceeds as follows. Alice chooses a random h ∈ R with corre-
sponding h ∈ Fnp and an [n, k] linear code C over Fp , that can efficiently correct t errors and

38
chooses a generator matrix G of C.

Table 10: Quasi-Cyclic Scheme

ALICE BOB

KEY GENERATION
Choose an [n, k] linear code C over Fp , which
can efficiently decode t errors with
generator matrix G ∈ Fpk×n and choose h ∈ R
Choose (y, z) ∈ R2 such that wtH (y) =
wtH (z) = w, compute s = y + hz
The public key is P = (G, h, s, we , wr ) and the
secret key is S = (y, z)
P
−→
ENCRYPTION
Choose a message m ∈ Fkp
Choose e ∈ R such that wtH (e) = we
Choose (r1 , r2 ) ∈ R2 such that
wtH (r1 ) = wtH (r2 ) = wr
Compute u = r1 + hr2
Compute v = mG + sr2 + e
The cipher is c = (u, v)
c
←−
−
DECRYPTION
Compute c′ = v − uz and use the decoding
algorithm of C to recover m

Alice then also chooses two elements y, z ∈ R, corresponding to the vector y, z both of
Hamming weight w.
She publishes the generator matrix G, the random element h and s = y + hz, while x and
y are kept secret and can clearly not be recovered from s and h.
Bob, who wants to send a message m ∈ Fkp to Alice, can choose e ∈ R corresponding to
the vector e ∈ Fnp of Hamming weight we and two elements r1 , r2 ∈ R, with corresponding
vectors r1 , r2 both of Hamming weight wr . He then computes u = r1 +hr2 with corresponding
vector u and
v = mG + sr2 + e,
where s ∈ Fnp is the vector corresponding to the public s. The cipher is then given by
c = (u, v).
The message m is thus encoded through the public G and an error vector sr2 + e is added,
where both r2 and e were randomly chosen by Bob. The only control Alice has on the error
vector is in s. This knowledge and also the additional information of Bob on r2 provided

39
through the vector u will allow Alice to decrypt the cipher.
In fact, Alice can use the decoding algorithm of C on v − uz, since

v − uz = mG + sr2 + e − (r1 + hr2 )z

= mG + (y + hz)r2 + e − r1 z − hr2 z
= mG + (yr2 − r1 z + e).
It follows that the decryption succeeds if wtH (yr2 − r1 z + e) ≤ t. Note that parameter sets
should be chosen such that this happens with high probability, but clearly the framework
does have a decoding failure rate (DFR).
Remark 98. The reason why we can make the generator matrix of the efficiently decodable
code public, lies in the random choice of h, which determines the parity-check matrix H and
in the fact that the error added to the codeword has a weight larger than the error correction
capacity of the public code. In fact, u and s are two syndromes through H of a vector with
given weight, as u = (r1 , r2 )H⊤ and s = (y, z)H⊤ . In order to recover (r1 , r2 ) or (y, z), an
attacker would need to solve the NP-hard syndrome decoding problem. In addition, since
wtH (sr2 + e) > t even with the knowledge of G and v an attacker can not uniquely determine
the message m.
Since the algebraic code, which is efficiently decodable, is publicly known, the security of
this framework is different to that of the McEliece framework and the Niederreiter framework,
as it does not rely on the indistinguishability of the code.
Remark 99. However, we want to stress the fact, that the SDP is NP-hard for a completely
random code. The code with the double circulant parity-check matrix H is in fact not
completely random, and thus the question arises, if also this new problem lies in the complexity
class of NP-hard problems.
Example 100. We choose R = F2 [x]/(x7 + 1) and as code the binary repetition code of length
7, which can correct up to 3 errors. The generator matrix G is given by
 
G= 1 1 1 1 1 1 1 ,

and codewords with more ones than zeroes are decoded to (1, 1, 1, 1, 1, 1, 1), everything else
to (0, 0, 0, 0, 0, 0, 0). Further, we choose
h = 1 + x + x2 ∈ R,
and w = wr = we = 1. We pick y = 1, z = x3 , both in R of weight w = 1, and compute
s = y + hz = 1 + x3 + x4 + x5 .
The public key is then given by
P = (G, h, s, we , wr ),
the secret key is the pair
S = (y, z) = (1, x3 ).
For this example, the message is m = (1) ∈ F12 . We also pick e = x ∈ R of weight we = 1
and r1 = r2 = x2 both in R of weight wr = 1. We can then compute
u = r1 + hr2 = x3 + x4 ,

40
hence u = (0, 0, 0, 1, 1, 0, 0), and since sr2 = 1 + x2 + x5 + x6 of weight 5 > t we get

v = mG + sr2 + e
= (1, 1, 1, 1, 1, 1, 1) + (1, 0, 1, 0, 0, 1, 1) + (0, 1, 0, 0, 0, 0, 0)
= (0, 0, 0, 1, 1, 0, 0).

We can then send the cipher

c = (u, v) = ((0, 0, 0, 1, 1, 0, 0), (0, 0, 0, 1, 1, 0, 0)).

To decrypt the cipher, we compute with the knowledge of the secret key S = (y, z) = (1, x3 )
that uz = 1 + x6 and compute

v − uz = (0, 0, 0, 1, 1, 0, 0) − (1, 0, 0, 0, 0, 0, 1)
= (1, 0, 0, 1, 1, 0, 1),

which gets decoded to to the codeword (1, 1, 1, 1, 1, 1, 1), from which we recover the message
m = (1).
Exercise 101. Repeat this example with the fixed public parameters G = (1, 1, 1, 1, 1, 1, 1),
h = 1 + x + x2 , s = 1 + x3 + x4 + x5 , we = wr = 1 and the secret key S = (1, x3 ), but now
Bob chooses e = x4 , r1 = 1, r2 = x. Is the decryption successful in this case?

3.5 GPT Cryptosystem

The Gabidulin-Paramonov-Tretjakov (GPT) cryptosystem was introduced in [101] and is
based on rank-metric codes. As usual, we pick an Fq -basis of Fqm and use this to identify
elements of Fqm with vectors in Fm q . The system we present is not following the original
proposal, which was broken [175], but an adapted formulation, and as before we present the
system as a framework, i.e., without choosing a family of codes for the secret code.
The GPT system proceeds as follows. Alice chooses an [n, k] linear rank-metric code C
over Fqm with error correction capacity t and generator matrix G. For some positive integer λ,
she then chooses S ∈ GLk (Fqm ), P ∈ GLn+λ (Fq ) and X ∈ Fqk×λ
m of rank s ≤ λ. She publishes
the scrambles matrix G′ = S[X | G]P and the target weight t.
Bob can then encrypt his message m ∈ Fkqm , by computing

c = mG′ + e,

for some randomly chosen error vector e ∈ Fqn+λ

m with wtR (e) = t.
To decrypt, Alice can compute

cP−1 = mS[X | G] + eP−1 .

Since wtR (eP−1 ) = t, she can apply the decoding algorithm of the code C to the last n
positions of cP−1 to recover mS and thus also m. A systematic description of the GPT
system can be found in Table 11.
This framework is closely related to the McEliece framework, as the algebraic code which
can be efficiently decoded has to be kept secret and the matrix P acts as an isometry. In fact,
while for the Hamming metric P is chosen a permutation matrix, which fixes the Hamming
weight of a vector, in the rank metric we choose P to be a full rank matrix over Fq , which
thus fixes the rank weight of a vector over Fqm .

41
 Table 11: GPT Cryptosystem

ALICE BOB

KEY GENERATION
Choose a generator matrix G ∈ Fqk×n m of a
rank-metric code of rank distance d = 2t + 1
and a positive integer λ
Choose S ∈ GLk (Fqm ), P ∈ GLn+λ (Fq )
Choose a matrix X ∈ Fqk×λ
m of rank s ≤ λ and
compute G′ = S[X | G]P.
The public key is P = (G′ , t) and the secret
key is S = (G, S, X, P)
P
−→
ENCRYPTION
Choose e ∈ Fn+λ
qm with wtR (e) ≤ t
Encrypt m ∈ Fkqm as c = mG′ + e
c
←−
−
DECRYPTION
Compute c′ = cP−1 and apply the decoding
algorithm to the last n positions to recover
m′ = mS
Compute m = m′ S−1

Exercise 102. Establish the Niederreiter version of the GPT system using the parity-check
matrix.
Example 103. We give an example for n = 4, m = 5, k = 2 and s = λ = 1. We identify
F32 = F2 [x]/(x5 + x2 + 1) and consider the Gabidulin code with generator matrix
 
1 x x2 x3
G= ,
1 x2 x4 x3 + x

which can correct up to 1 error. We further need a S ∈ GL2 (F32 ) and a P ∈ GL5 (F2 ) and X
of rank s ≤ λ = 1, so we take  
1 x
S= ,
0 1

42
and for simplicity  
0 0 1 0 0
 
1 0 0 0 0
 
 
P = 0 1 0 0 0 ,
 
 
0 0 0 0 1
 
 
0 0 0 1 0
and  
1
X= 
x2 + 1
We compute that
 
x+1 x3 +x x3 +x+1 x4 + x3 + x2 1
G′ = S[X | G]P =  .
1 x2 x2 +1 x3 +x x4

The public key is the pair

P = (G′ , 1),
the secret key is
P = (G, S, X, P).
We want to encrypt the message

m = (x + 1, x2 + 1).

We choose the error vector

e = (x3 + 1, 0, x3 + 1, x3 + 1, 0),

and compute

c = mG′ + e = (x3 + 1, x3 + x, x2 + 1, x3 + x2 + x + 1, x4 + x3 + 1).

To decrypt c, we compute

c′ = cP−1 = (x2 + 1, x3 + 1, x3 + x, x4 + x3 + 1, x3 + x2 + x + 1),

and use the decoding algorithm of Gabidulin codes to get

mS = (x + 1, x + 1),

and by multiplying with  

1 x
S−1 = 
0 1
we recover m.

43
4 Code-based Signature Schemes
We give two approaches of building a code-based signature, one is following the hash-and-
sign approach of the CFS scheme [76], which can also be adapted to the rank metric and the
second one is through code-based ZKID schemes, which can be turned into signature schemes
via the Fiat-Shamir transform.
The first approach has a crucial drawback as the signing requires to be repeated expo-
nentially many times in order to find a decodable syndrome, while signatures have size linear
in the security parameter. Also the second approach still fails to provide a practical solution
due to large signature sizes. The question on how to get a secure and practical code-based
signature scheme is thus still open.

4.1 Hash-and-Sign
In this section we will present two signature schemes, which are not constructed through a
ZKID and the Fiat-Shamir transform, but rather rely on the idea of hash-and-sign, namely
the CFS scheme [76], which is in fact the first code-based signature scheme, and RankSign
[19].
We present the CFS scheme as framework in Table 12. Note that the CFS scheme uses an
error correcting code to sign a message. To this end, one needs to find an error vector with
restricted weight, which corresponds to an arbitrary syndrome. However, not every vector
can be expressed as a syndrome of an error vector of weight t ≤ d−1
2 , since there are no perfect
codes. Thus, the authors of [76] propose the use of the only family of codes, which is suitable
for such an approach, namely high rate Goppa codes. In fact, high rate Goppa codes provide
the existence of such error vectors for a non-negligible proportion of syndromes.
Unfortunately, the use of high rate Goppa codes is not safe, due to the distinguisher in
[95]. Note that this distinguisher does not break the CFS scheme in general, as it only proves
that one of the two problems to which the security of the CFS scheme reduces can be solved
in polynomial time.
(n−k)×n
In the key generation process, one chooses a parity-check matrix H ∈ F2 of a binary
code that can efficiently correct t errors. One then hides the parity-check matrix as in the
Niederreiter framework, by choosing an n × n permutation matrix P and S ∈ GLn−k (F2 ) and
computing H′ = SHP. The public key is then given by P = (H′ , t) and the secret key by
S = (S, H, P).
In the signing process, given a message m, one first chooses randomly mi ∈ F2n−k and
uses the decoding algorithm of C to find e, such that wtH (e) ≤ t and
eH⊤ = S−1 H(m, H′ , mi )
if possible. The signature is then given by s = (mi , eP).
In the verification, the verifier checks that wtH (eP) ≤ t and if
ePH′⊤ = H(m, H′ , mi ).
Recall that H is a publicly known hash function.
Exercise 104. Show that ePH′⊤ = H(m, H′ , mi ).
Remark 105. The signing time is inversely related to the proportion of vectors, which are
syndromes of error vectors of weight t ≤ d−1
2 and this proportion scales badly with the error
correction capacity of the code.

44
 Table 12: CFS

PROVER VERIFIER

KEY GENERATION
(n−k)×n
Choose a parity-check matrix H ∈ F2
of C, with error correction capacity t
Choose an n × n permutation matrix P and
S ∈ GLn−k (F2 )
Compute H′ = SHP. The public key is then
given by P = (H′ , t)
and the secret key by S = (S, H, P)
P
−→
SIGNING
Given a message m, choose mi ∈ F2n−k
Use the decoding algorithm of C to find e, with
wtH (e) ≤ t and eH⊤ = S−1 H(m, H′ , mi )
Sign as s = (mi , eP)
m,s
−−→
VERIFICATION
Check if wtH (eP) ≤ t and if
ePH′⊤ = H(m, H′ , mi ).

RankSign [19] is another code-based signature scheme based on the hash-and-sign ap-
proach, where the authors propose to use augmented LRPC codes over an extension field Fqm
and introduce a mixture of erasures and errors, which can be efficiently decoded.
In the key generation process, instead of hiding the parity-check matrix H of the LRPC
code over Fqm using BHQ, where B ∈ GLn−k (Fqm ) and Q ∈ GLn (Fq ), we first add some
(n−k)×t′
random columns to H : Let A ∈ GLn−k (Fqm ), P ∈ GLn+t (Fq ) and R ∈ Fqm . Typically
one sets t′ = t, but one could also use other choices. Then, one hides H by computing
H′ = A(R | H)P.
While H′ and some integer ℓ are publicly known, the secret key is given by R, H, A, P.
In the signing process, one first chooses randomly ẽ ∈ Ftqm and hashes a message m and a
seed, denoted by seed ∈ {0, 1}ℓ and hash function H, to get m′ = H(m | seed) ∈ Fqn−k m . Then

one sets a syndrome s = m (A ) − ẽR and tries to syndrome decode this syndrome s′
′ ′ −1 ⊤ ⊤

using H. If one succeeds, that is, there exists a e′ ∈ Fnqm of rank weight r = t + r ′ and such
that e′ H⊤ = s′ , then one defines

e = (ẽ | e′ )(P⊤ )−1

and sets the signature

s = (e, seed).

45
 Table 13: RankSign

PROVER VERIFIER

KEY GENERATION
Choose A ∈ GLn−k (Fqm ), P ∈ GLn+t (Fq ),
(n−k)×t′
Choose r, ℓ ∈ N, R ∈ Fqm
(n−k)×n
Choose H ∈ Fqm a parity-check matrix
of a LRPC code
Compute H′ = A(R | H)P
The keys are given by S = (A, P, R, H),
and P = (H′ , ℓ, r)
P
−→
SIGNING
Choose ẽ ∈ Ftqm and a message m
Choose seed ∈ {0, 2}ℓ
Compute m′ = H(m | seed)
Set s′ = m′ (A−1 )⊤ − ẽR⊤
Find e′ , such that wtR (e′ ) = r and e′ H⊤ = s′
m,s
Set e = (ẽ | e′ )(P⊤ )−1 and s = (e, seed) −−→
VERIFICATION
Check if wtR (e) = r and if
eH′⊤ = H(m, seed)

If not, this process needs to be repeated until one succeeds.

In the verification, the verifier checks that wtR (e) = r = t + r ′ , and if

eH′⊤ = m′ = H(m | seed).

Recall that H is a publicly known hash function.

Exercise 106. Show that eH′⊤ = m′ .
We want to note here that this signature scheme was later attacked in [88].

4.2 Zero-Knowledge Identification Scheme Framework

As described in Section 2.3.5, digital signature schemes can be constructed from a ZKID
scheme using the Fiat-Shamir transform [1]. In this section, we present two famous ZKID
schemes for this purpose, namely the scheme by Cayrel, Véron and El Yousif Alaoui (CVE)
[71] and scheme by Aguilar, Gaborit and Schrek (AGS) [2].
The CVE scheme [71] is an improvement of Stern’s [209] and Véron’s [218] identification
schemes, which are both based on the hardness of decoding a random binary code [52]. The

46
CVE scheme relies on non-binary codes over a large finite field. With this choice, the cheating
q
probability for a single round is reduced from 2/3 of Stern’s 3-pass scheme to 2(q−1) by using
a 5-pass scheme based on codes over Fq .
The idea of the scheme is the following; the secret key is given by a random error vector
of weight t and the public key is a parity-check matrix together with the syndrome of this
error vector. The challenges are requesting either a response that shows that the error vector
has indeed weight t or a response that shows that the error vector solves the parity-check
equations.
The scheme is of large interest, as it uses an actual random linear code, which is possible
since no decoding process is required. The security of this scheme thus fully relies on the
hardness of decoding a random linear code and not on the indistinguishability of a secret
code.
n
Let σ be a permutation of {1, . . . , n} and for v ∈ F×q and a ∈ Fnq we denote by

σv (a) = σ(v) ⋆ σ(a),

where ⋆ denotes the component-wise product. Recall that H denotes a publicly known hash
function.
We now show how the communication cost of this scheme is derived, following the rea-
soning of [28].
In order to represent a vector of length n and Hamming weight t over Fq , we can either
use the full vector, which requires n ⌈log2 (q)⌉ bits, or just consider its support, together with
the ordered non-zero entries, resulting in


t ⌈log2 (n)⌉ + ⌈log2 (q − 1)⌉

bits. Thus the most convenient choice for a given set of parameters n, t and q is


ψ(n, q, t) = min{n ⌈log2 (q)⌉ , t ⌈log2 (n)⌉ + ⌈log2 (q − 1)⌉ }.

Since random objects, such as the monomial transformation, are completely determined by
the seed for the pseudorandom generator, they can also be compactly represented as such,
whose length is denoted by lSeed . Also the length of the hash values will be denoted by lH .
Using the compression technique for N rounds of the protocol we get the following average
communication cost:
 
ψ(n, q, t) + lSeed
lH + N ⌈log2 (q − 1)⌉ + n ⌈log2 (q)⌉ + 1 + lH + .
2

For the maximal communication cost, we take the maximum size of the response, and thus
we obtain
 
lH + N ⌈log2 (q − 1)⌉ + n ⌈log2 (q)⌉ + 1 + lH + max{ψ(n, q, t) , lSeed } .

Let us fix t = ⌊dH /2⌋, for dH denoting the minimum distance of the Gilbert-Varshamov
bound. The authors of [71] have used the analysis due to Peters [178] to estimate the infor-
mation set decoding complexity, and have proposed two parameters sets:

- q = 256, n = 128, k = 64, t = 49, for 87-bits security, having a communication cost of
3.472 kB;

47
 Table 14: CVE Scheme

PROVER VERIFIER

KEY GENERATION
Choose the parameters q, n, k, t and a hash
function H
Choose e ∈ BH (t, n, q) and a parity-check ma-
trix
(n−k)×n
H ∈ Fq . Compute the syndrome
s = eH ∈ ⊤
Fqn−k .
P
The public key is given by P = (H, s, t) −→
VERIFICATION
n
Choose u ∈ Fnq , a permutation σ, v ∈ (F×
q )


Set c0 = H σ, v, uH⊤


Set c1 = H σv (u), σv (e)
c0 ,c1
−−−→
Choose z ∈ F×
q
z
←−
−
Set y = σv (u + ze)
y
−→
Choose b ∈ {0, 1}
b
←−
−
If b = 0, set r = (σ, v)
If b = 1, set r = σv (e)
r
−→
If b = 0, accept if

c0 = H σ, v, σv−1 (y)H⊤ − zs
or
If b = 1, accept if wtH (σv (e)) = t and

c1 = H y − zσv (e), σv (e)

- q = 256, n = 208, k = 104, t = 78, for 128-bits security, having a communication cost
of 43.263 kB.

Exercise 107. Show the zero-knowledge property and the completeness property for the CVE
scheme.
An easy attempt for an impersonator would be to guess the challenge b before sending
the commitments.
Thus, the strategy if we guess b = 0, would be to choose an error vector e′ , which satisfies

48
the parity-check equations, that is
s = e′ H ⊤ ,
and to forget about the weight condition. This can easily be achieved using linear algebra.
We denote by s0 the strategy for b = 0, which in detail requires to choose randomly u′ , σ ′ and
v′ according to the scheme and to send the commitments c′0 = H(σ ′ , v′ , u′ H⊤ ) and a random
c′1 . When the impersonator received a z ∈ F× ′
q , the impersonator now computes y according
′
to the cheating error vector e , i.e.,

y′ = σv′ ′ (u′ + ze′ ).

The impersonator wins, if the verifier now asks for b = 0, since the verifier will check
−1
c′0 = H(σ ′ , v′ , σv′ ′ (y′ )H⊤ − zs)
−1
= H(σ ′ , v′ , σv′ ′ (σv′ ′ (u′ + ze′ ))H⊤ − zs)
= H(σ ′ , v′ , (u′ + ze′ )H⊤ − zs)
= H(σ ′ , v′ , u′ H⊤ + ze′ H⊤ − zs)
= H(σ ′ , v′ , u′ H⊤ + zs − zs).

If the verifier asks for b = 1, the impersonator looses.

Whereas the strategy if we guess b = 1, would be to choose an error vector e′ , which has the
correct weight, i.e., wtH (e′ ) = t, but does not satisfy the parity-check equations. We denote by
s1 the strategy for b = 1, which in detail requires to choose randomly u′ , σ ′ and v′ according
to the scheme and to send the commitments: a random c′0 and c′1 = H(σv′ ′ (u′ ), σv′ ′ (e′ )).
When the impersonator received a z ∈ F× ′
q , the impersonator now computes y according to
′
the cheating error vector e , i.e.,
y′ = σv′ ′ (u′ + ze′ ).
The impersonator wins, if the verifier now asks for b = 1, since the verifier will check if
wtH (σv′ ′ (e′ )) = t and

c′1 = H(y′ − zσv′ ′ (e′ ), σv′ ′ (e′ ))

= H(σv′ ′ (u′ + ze′ ) − zσv′ ′ (e′ ), σv′ ′ (e′ ))
= H(σv′ ′ (u′ ) + σv′ ′ (ze′ ) − zσv′ ′ (e′ ), σv′ ′ (e′ )).

If the verifier asks for b = 0, the impersonator looses.

With this easy strategy, one would get a cheating probability of 1/2, which just corresponds
to choosing the challenge b correctly. However, by also guessing z correctly one can improve
the above strategy.
q
Proposition 108. The cheating probability of the CVE scheme is 2(q−1) .

Proof. We modify the easy strategies si , following [71]:

Let us denote by s′0 the improved strategy on s0 , which works as follows: recall that
′
e is chosen such that the parity-check equations are satisfied but not the weight condition.
Instead of randomly choosing the commitment c′1 , we choose a z ′ ∈ F× q and a second cheating
error vector ẽ of weight t, we compute a ỹ = σv′ ′ (u′ + z ′ e′ ) with this guess and compute

c′1 = H(ỹ − z ′ ẽ, ẽ).

49
When we receive a z from the verifier, we check if we made the correct choice, that is: if
z = z ′ , we send the pre-computed ỹ, and if z 6= z ′ we compute y′ = σv′ ′ (u′ + ze′ ). If the
verifier asks for b = 0, we use the usual strategy of s0 and will get accepted, as before. If the
verifier asks for b = 1, we send as answer ẽ. If we have guessed correctly and z = z ′ , we will
get accepted also in this case as
˜ − zẽ, ẽ)
c′1 = H(by

by definition.
Let us denote by s′1 the improved strategy on s1 , which works as follows: recall that e′
is chosen having the correct weight. Instead of randomly choosing the commitment c′0 , we
choose a z ′ ∈ F× ′ ′ ′ ′
q and compute a ỹ = σv′ (u + z e ) with this guess and compute

c′0 = H(σ ′ , v′ , u′ H⊤ + z ′ (e′ H⊤ − s)).

When we receive a z from the verifier, we check if we made the correct choice, that is: if
z = z ′ , we send the pre-computed ỹ, and if z 6= z ′ we compute y′ = σv′ ′ (u′ + ze′ ). If the
verifier asks for b = 1, we use the usual strategy of s1 and will get accepted. If the verifier
asks for b = 0, we send as answer (σ ′ , v′ ). If we have guessed correctly and z = z ′ , we will get
accepted also in this case as
−1
c′0 = H(σ ′ , v′ , σv′ ′ (y′ )H⊤ − zs)
−1
= H(σ ′ , v′ , σv′ ′ (σv′ ′ (u′ + z ′ e′ ))H⊤ − zs)
= H(σ ′ , v′ , (u′ + z ′ e′ )H⊤ − zs)
= H(σ ′ , v′ , u′ H⊤ + z ′ e′ H⊤ − zs)
= H(σ ′ , v′ , u′ H⊤ + z ′ s − zs).

Thus, the probability that an impersonator following the strategy s′i will get accepted is
given by
1 1 1 q
P (b = i) + P (b = 1 − i) · P (z = z ′ ) = + · = ,
2 2 q−1 2(q − 1)
which concludes this proof.

The second ZKID scheme we want to present is the scheme by Aguilar, Gaborit and Schrek
[2], which we will denote by AGS. This scheme is constructed upon quasi-cyclic codes over
F2 . Let us consider a vector a ∈ Fjk
2 divided into j blocks of k entries each, that is,
 
(1) (1) (j) (j)
a = a1 , . . . , ak , . . . , a1 , . . . , ak .

(k)
We use ρi to denote a function that performs a block-wise cyclic shift of a by i positions,
i.e.,  
(k) (1) (1) (j) (j)
ρi (a) = a1−i mod k , . . . , ak−i mod k , . . . , a1−i mod k , . . . , ak−i mod k .

The cheating probability of this scheme asymptotically tends to 12 .

The idea is similar to that of the CVE scheme, but working with the generator matrix
instead.

50
 Table 15: AGS Scheme

PROVER VERIFIER

KEY GENERATION
Choose the parameters n, k, t and a hash func-
tion Hash
Choose m ∈ Fk2 and e ∈ BH (t, n, 2) and a
generator matrix
G ∈ F2k×n . Compute the erroneous codeword
c = mG + e ∈ Fn2
P
The public key is given by P = (G, c, t) −→
VERIFICATION
Choose u ∈ Fk2 , a permutation σ


Set c0 = H σ


Set c1 = H σ(uG)
c0 ,c1
−−−→
Choose z ∈ {1, . . . , k}
z
←−
−
(k)

Set c2 = H σ(uG + ρz (e))
c
2
−→
Choose b ∈ {0, 1}
b
←−
−
(k)
If b = 0, set r = (σ, u + ρz (m))
(k)
If b = 1, set r = (σ(uG), σ(ρz (e)))
r
−→


If b = 0, accept if c0 = H σ and
(k) (k)

c2 = H (u + ρz (m))G + ρz (c)
(k)
If b = 1, accept if wtH (ρz (e)) =
t and
c1 = H σ(uG) and
(k)

c2 = H σ(uG) + σ(ρz (e))

The secret key consists of a message and an error vector, while the public key consists of
an erroneous codeword and the generator matrix. The challenges either require the proof of
the error vector having the correct weight or of the knowledge of the message.
When performing N rounds, the average communication cost is
 
lSeed + k + n + ψ(n, t, 2)
lH + N ⌈log2 (k)⌉ + 1 + 2lH + ,
2

51
while the maximum communication cost is
 
lH + N ⌈log2 (k)⌉ + 1 + 2lH + max{lSeed + k , n + ψ(n, t, 2)} .

In [2], three parameters sets are proposed:

- n = 698, k = 349, t = 70, for 81-bits security, having a communication cost of 2.565 kB;

- n = 1094, k = 547, t = 109, for 128-bits security, having a communication cost of 28.232
kB.

Exercise 109. Show the zero-knowledge property and completeness for the AGS scheme.
We remark that one interesting property of these code-based ZKID schemes is that one
does not require a code with an efficient decoding algorithm. Which stands in contrast to
the requirements for many of the code-based public-key encryption schemes. Thus, choosing
a random code the security of such schemes is much closer related to the actual NP-hard
problem of decoding a random linear code.
Clearly, using any of the two code-based ZKID schemes presented above and the Fiat-
Shamir transform one immediately gets a signature scheme.

5 Security Analysis
In the security analysis of a cryptographic scheme we make a difference between two main
attack approaches:

1. structural attacks,

2. non-structural attacks.

A structural attack aims at exploiting the algebraic structure of the cryptographic system.
Whereas a non-structural attack tries to combinatorically recover the message or the secret
key without exploiting any algebraic structure.
For example the security of the McEliece and Niederreiter type of cryptosystems rely on
two assumptions. The first one being

The public code is not distinguishable from a random code.

A structural attack would usually aim at exactly this assumption, and try to recover the secret
code, if the scrambled public version of it does not behave randomly. Clearly, structural or
algebraic attacks heavily depend on the chosen secret codes for the cryptosystem, if the system
depends on an algebraic code that is efficiently decodable, and is not attacking the presented
frameworks in general.
Assuming that this first assumption is met however, the security of most code-based
cryptosystems relies also on this second assumption

Decoding a random linear code is hard/ infeasible.

A non-structural attack on the McEliece cryptosystem would thus assume that the public
code is in fact random, and rather try to decode this random code nevertheless.

52
 In general we also speak of attacks in terms of: key-recovery attacks, where an attacker
tries to recover the secret key (usually structural attacks), and message-recovery attacks,
where an attacker directly tries to decrypt the cipher without first recovering the secret key.
Thus, in the following we will first focus on the non-structural attacks, which in code-
based cryptography usually aim at decoding a random linear code. We want to note here
that there are also other hard problems in coding theory (e.g. [41, 224, 48]). For example the
code-equivalence problem [179, 200, 77] was already considered for cryptographic applications
in [59].

5.1 NP-completeness
As discussed in the security analysis, code-based cryptography is traditionally based on the
hardness of decoding a random linear code.
Problem 110. Decoding Problem (DP) Let Fq be a finite field and k ≤ n be positive
integers. Given G ∈ Fqk×n , c ∈ Fnq and t ∈ N, is there a vector x ∈ Fkq and e ∈ Fnq of weight
less than or equal to t such that c = xG + e?
Note that the DP formulated through the generator matrix is equivalent to the syndrome
decoding problem, which is formulated through the parity-check matrix.
Problem 111. Syndrome Decoding Problem (SDP) Let Fq be a finite field and k ≤ n
(n−k)×n
be positive integers. Given H ∈ Fq , s ∈ Fqn−k and t ∈ N, is there a vector e ∈ Fnq such
that wtH (e) ≤ t and eH⊤ = s?
Berlekamp, McEliece and van Tilborg famously proved in [52] the NP-completeness of the
syndrome decoding problem for the case of binary linear codes equipped with the Hamming
metric. In [41], Barg generalized this proof to an arbitrary finite field. Finally, the NP-
hardness proof has been generalized to arbitrary finite rings endowed with an additive weight
in [223], thus including famous metrics such as the homogeneous and the Lee metric.
In this section we provide the proof of NP-completeness for the SDP as in [41].

In order to understand this proof, we first give a small introduction to complexity theory.
Let P denote a problem. In order to estimate how hard it is to solve P we have two main
complexity classes.
Definition 112. P denotes the class of problems that can be solved by a deterministic Turing
machine in polynomial time.
The concept of deterministic and non-deterministic Turing machines will exceed the scope
of this chapter, just note that ”can be solved by a deterministic Turing machine in polynomial
time” is the same as our usual ”can be solved in polynomial time”.
Example 113. Given a list S of n integers and an integer k, determine whether there is an
integer s ∈ S such that s > k? Clearly, this can be answered by going through the list and
checking for each element whether it is greater than k, thus it has running time at most n
and this problem is in P.
Definition 114. NP denotes the class of problems that can be solved by a non-deterministic
Turing machine in polynomial time.
Thus, in contrary to the popular belief that NP stands for non-polynomial time, it actually
stands for non-deterministic polynomial time. The difference is important: all problems in P
live inside NP!

53
 To understand NP better, we might use the equivalent definition: A problem P is in NP
if and only if one can check that a candidate is a solution to P in polynomial time.
The example from before is thus also clearly in NP, since if given a candidate a, we can
check in polynomial time whether a ∈ S and whether a > k.
There are, however, interesting problems which are in NP, but we do not know whether
they are in P. Let us change the previous example a bit.

P Given a list S of n integers and an integer k, is there a set of integers T ⊆ S,

Example 115.
such that t = k? Since there are exponentially many subsets of S, there is no known
t∈T
algorithm to solve this problem in polynomial time and thus, we do not know whether it lives
P if given a candidate T , we can check in polynomial time if all t ∈ T are also in S
in P. But,
and if t = k, which clearly places this problem inside NP.
t∈T
The most important complexity class, for us, will be that of NP-hard problems. In order
to define this class, we first have to define polynomial-time reductions.
A polynomial-time reduction from R to P follows the following steps:
1. take any instance I of R,

2. transform I to an instance I ′ of P in polynomial time,

3. assume that (using an oracle) you can solve P in the instance I ′ in polynomial time,
getting the solution s′ ,

4. transform the solution s′ in polynomial time to get a solution s of the problem R in the
input I.
The existence of a polynomial-time reduction from R to P, informally speaking, means that
if we can solve P, we can also solve R and thus solving P is at least as hard as solving R.
Definition 116. P is NP-hard if for every problem R in NP, there exists a polynomial-time
reduction from R to P.
Informally speaking this class contains all problems which are at least as hard as the
hardest problems in NP.
Example 117. One of the most famous examples for an NP-hard problem is the subsetP sum
problem: given a set of integers S, is there a non-empty subset T ⊆ S, such that t = 0?
t∈T
We want to remark here, that NP-hardness is only defined for decisional problems, that
are problems of the form ”decide whether there exists..” and not for computational/search
problems, that are problems of the form ”find a solution..”. However, considering for example
the SDP, in its decisional version, it asks whether there exists error vector e with certain con-
ditions. If one could solve the computational problem, that is to actually find such an error
vector e in polynomial time, then one would also be able to answer the decisional problem in
polynomial time. Thus, not being very rigorous, we call also the computational SDP NP-hard.

In order to prove that a problem P is NP-hard, fortunately we do not have to give a

polynomial-time reduction to every problem in NP: there are already problems which are
known to be NP-hard, thus it is enough to give a polynomial-time reduction from an NP-
hard problem to P.
Finally, NP-completeness denotes the intersection of NP-hardness and NP.

54
Definition 118. A problem P is NP-complete, if it is NP-hard and in NP.
Note that the SDP is clearly in NP: given a candidate vector e we can check in polynomial
time if wtH (e) ≤ t and if eH⊤ = s. Thus, we are only left with showing the NP-hardness of the
SDP through a polynomial-time reduction. For this, we choose the 3-dimensional matching
(3DM) problem, which is a well-known NP-hard problem.
Problem 119. 3-Dimensional Matching (3DM) Problem
Let T be a finite set and U ⊆ T × T × T . Given U, T , decide if there exists a set W ⊆ U such
that | W |=| T | and no two elements of W agree in any coordinate.
Proposition 120. The SDP is NP-complete.
For the proof of Proposition 120 we follow closely [223].
Proof. We prove the NP-completeness by a polynomial-time reduction from the 3DM problem.
For this, we start with a random instance of 3DM with T of size t, and U ⊆ T × T × T of
size u. Let us denote the elements in T = {b1 , . . . , bt } and in U = {a1 , . . . , au }. From this we
build the matrix H⊤ ∈ Fu×3t
q , as follows:
• for j ∈ {1, . . . , t}, we set hi,j = 1 if ai [1] = bj and hi,j = 0 else,
• for j ∈ {t + 1, . . . , 2t}, we set hi,j = 1 if ai [2] = bj and hi,j = 0 else,
• for j ∈ {2t + 1, . . . , 3t}, we set hi,j = 1 if ai [3] = bj and hi,j = 0 else.
With this construction, we have that each row of H⊤ corresponds to an element in U , and
has weight 3. Let us set the syndrome s as the all-one vector of length 3t. Assume that we
can solve the SDP on the instances H, s and t in polynomial time. Let us consider two cases.
Case 1: First, assume that the SDP solver returns as answer ‘yes’, i.e., there exists an
e ∈ Fuq , of weight less than or equal to t and such that eH⊤ = s.
• We first observe that we must have wtH (e) =| Supp(e) |= t. For this note that each
row of H⊤ adds at most 3 non-zero entries to s. Therefore, we need to add at least t
rows to get s, i.e., | Supp(e) |≥ t and hence wtH (e) ≥ t. As we also have wtH (e) ≤ t
by hypothesis, this implies that wtH (e) =| Supp(e) |= t.
• Secondly, we observe that the weight t solution must be a binary vector. For this we
note that the matrix H⊤ has binary entries and has constant row weight three, and since
| Supp(e) |= t, the supports of the t rows of H⊤ that sum up to the all-one vector have
to be disjoint. Therefore, we get that the j-th equation from the system of equations
eH⊤ = s is of the form ei hi,j = 1 for some i ∈ Supp(e). Since hi,j = 1, we have ei = 1.
Recall from above that the rows of H⊤ correspond to the elements of U . The t rows corre-
sponding to the support of e are now a solution W to the 3DM problem. This follows from
the fact that the t rows have disjoint supports and add up to the all-one vector, which implies
that each element of T appears exactly once in each coordinate of the elements of W .
Case 2: Now assume that the SDP solver returns as answer ‘no’, i.e., there exists no e ∈ Fuq
of weight at most t such that eH⊤ = s. This response is now also the correct response for the
3DM problem. In fact, if there exists W ⊆ U of size t such that all coordinates of its elements
are distinct, then t rows of H⊤ should add up to the all one vector, which in turn means the
existence of a vector e ∈ {0, 1}u of weight t such that eH⊤ = s.
Thus, if such a polynomial time solver exists, we can also solve the 3DM problem in
polynomial time.

55
Example 121. Let us consider T = {A, B, C, D} and

U = {(D, A, B), (C, B, A), (D, A, B), (B, C, D), (C, D, A), (A, D, A), (A, B, C)}.

Then the above construction would yield

 
0 0 0 1 1 0 0 0 0 1 0 0
 
 0 0 1 0 0 1 0 0 1 0 0 0 
 
 
 0 0 0 1 1 0 0 0 0 1 0 0 
 
 
⊤
H = 0 1 0 0 0 0 1 0 0 0 0 1 .
 
 
 0 0 1 0 0 0 0 1 1 0 0 0 
 
 
 1 0 0 0 0 0 0 1 1 0 0 0 
 
 
1 0 0 0 0 1 0 0 0 0 1 0

A solution to eH⊤ = (1, . . . , 1) would be e = (1, 0, 0, 1, 1, 0, 1) which corresponds to

W = {(D, A, B), (B, C, D), (C, D, A), (A, B, C)}.

Notice that the very same construction is used also in the problem of finding codewords
with given weight.
Problem 122. Given Weight Codeword Problem (GWCP)
(n−k)×n
Let Fq be a finite field and k ≤ n be positive integers. Given H ∈ Fq and w ∈ N, is
there a vector c ∈ Fnq such that wtH (c) = w and cH⊤ = 0n−k ?
Proposition 123. The GWCP is NP-complete.
Proof. We again prove the NP-completeness by a reduction from the 3DM problem. To this
end, we start with a random instance of 3DM, i.e., T of size t, and U ⊆ T × T × T of size
u. Let us denote the elements in T = {b1 , . . . , bt } and in U = {a1 , . . . , au }. At this point, we
⊤
build the matrix H ∈ Fu×3t
q , like in the proof of Proposition 120.
(3tu+3t+u)×(3tu+3t)
Then we construct H⊤ ∈ Fq in the following way.
 
⊤
H Idu · · · Idu
 
− Id3t 0 ··· 0 
 
 
⊤
H = 0 − Idu 0 ,
 
 .. ..
 
.

 . 
 
0 0 − Idu

where we have repeated the size-u identity matrix 3t times in the first row. Let us set
w = 3t2 + 4tM and assume that we can solve the GWCP on the instance given by H, w in
polynomial time. Let us again consider two cases.
Case 1: In the first case the GWCP solver returns as answer ‘yes’, since there exists a
c ∈ R3tu+3t+u , of weight equal to w, such that cH⊤ = 03tu+3t . Let us write this c as

c = (c, c0 , c1 , . . . , c3t ),

56
where c ∈ Ru , c0 ∈ R3t and ci ∈ Ru for all i ∈ {1, . . . , 3t}. Then, cH⊤ = 03tu+3t gives the
equations
⊤
cH − c0 = 0,
c − c1 = 0,
..
.
c − c3t = 0.
⊤
Hence, we have that wtH (cH ) = wtH (c0 ) and

wtH (c) = wtH (c1 ) = · · · = wtH (c3t ).

Due to the coordinatewise additivity of the weight, we have that

⊤
wtH (c) = wtH (cH ) + (3t + 1)wtH (c).
⊤ ⊤
Since wtH (cH ) ≤ 3t, we have that wtH (cH ) and wtH (c) are uniquely determined as the
remainder and the quotient, respectively, of the division of wtH (c) by 3t + 1. In particular,
⊤
if wtH (c) = 3t2 + 4t, then we must have wtH (c) = t and wtH (cH ) = 3t. Hence, the first u
parts of the found solution c, i.e., c, give a matching for the 3DM in a similar way as in the
⊤
proof of Proposition 120. For this we first observe that cH is a full support vector and it
⊤
plays the role of the syndrome, i.e., cH = (x1 , . . . , x3t ), where xi ∈ F×
q . Now, using the same
argument as in the proof of Proposition 120, we note that c has exactly t non-zero entries,
which corresponds to a solution of 3DM.
Case 2: If the solver returns as answer ‘no’, this is also the correct answer for the 3DM
problem. In fact, if there exists a W ⊆ U of size t, such that all coordinates of its elements
⊤
are distinct, then t rows of H should add up to the all one vector, which in turn means the
⊤
existence of a e ∈ {0, 1}u of support size t such that xeH = (x, . . . , x) =: c0 for any x ∈ F× q .
And thus, with c = xe a solution c to the GWCP with the instances constructed as above
should exist.
Thus, if such a polynomial time solver for the GWCP exists, we can also solve the 3DM
problem in polynomial time.

We remark that the bounded version of this problem, i.e., deciding if a codeword c with
wtH c ≤ w exists, can be solved by applying the solver of Problem 122 at most w many times.
The computational versions of Problems 122 and 111 are at least as hard as their deci-
sional counterparts. Trivially, any operative procedure that returns a vector with the desired
properties (when it exists) can be used as a direct solver for the above problems.
We have seen that the SDP in the Hamming metric over any finite field (actually also over
any finite ring with unity) is NP-complete. The situation is different for the SDP in the rank
metric. In [106] the authors provided a randomized reduction to an NP-hard problem, which
is not the same as a deterministic reduction. Thus, the following remains an open problem:
Open Problem 124. Is the rank-metric SDP NP-hard?
Note that the problem on which the McEliece system is based upon is not exactly equiv-
alent to the SDP. In the McEliece system the parameter t is usually bounded by the error
correction capacity of the chosen code. Whereas in the SDP, the parameter t can be chosen
to be any positive integer. Thus, we are in a more restricted regime than in the SDP.

57
Problem 125 (Bounded SDP). Let Fq be a finite field and k ≤ n be positive integers. Given
(n−k)×n
H ∈ Fq , s ∈ Fqn−k and d ∈ N, such that every set of d − 1 columns of H is linearly
independent and w = d−1 n ⊤
 
2 , is there a vector e ∈ Fq such that wtH (e) ≤ w and eH = s?
This problem is conjectured to be NP-hard [41] and in [216] it is observed that this problem
is not likely to be in NP, since already verifying that d − 1 columns are linearly independent
is NP-hard.
There have been attempts [129] to transform the McEliece system in such a way that the
underlying problem is closer or even exactly equivalent to the SDP, the actual NP-complete
problem. This proposal has been attacked shortly after in [143]. However, using a different
framework than the McEliece system, this is actually possible, for example by using the
quasi-cyclic framework.
We also want to remark here, that the following generalization of the GWCP, i.e., Problem
122, is also NP-complete [216]:
(n−k)×n
Problem 126. Let Fq be a finite field and k ≤ n be positive integers. Given H ∈ Fq
and w ∈ N, is there a vector c ∈ Fnq such that wtH (c) ≤ w and cH⊤ = 0n−k ?
In [216] this problem was called the minimum distance problem, since if one could solve
the above problem, then by running such solver on w ∈ {1, . . . , n} until an affirmative answer
is found, this would return the minimum distance of a code.
However, this does not mean that finding the minimum distance of a random code is
NP-complete. In fact, with the above problem one can prove the NP-hardness of finding the
minimum distance, but it is unlikely to be in NP, since in order to check whether a candidate
solution d really is the minimum distance of the code, one would need to go through (almost)
all codewords.

5.2 Information Set Decoding

In this section we cover the main approach to solve the SDP, namely information set decoding
(ISD) algorithms. For this we will follow closely [222].
In the McEliece and the Niederreiter framework the secret code is usually endowed with
a particular algebraic structure to guarantee the existence of an efficient decoding algorithm
and is then hidden from the public to appear as a random code. In different frameworks, such
as the quasi-cyclic framework, the secret is actually purely the error vector and the algebraic
code is made public. In both cases an adversary has to solve the NP-complete problem of
decoding a random linear code.

An adversary would hence use the best generic decoding algorithm for random linear
codes. Two main methods are known until today for decoding random linear codes: ISD and
the generalized birthday algorithm (GBA). ISD algorithms are more efficient if the decoding
problem has only a small number of solutions, whereas GBA is more efficient when there are
many solutions. Also other ideas such as statistical decoding [9], gradient decoding [22] and
supercode decoding [40] have been proposed but fail to outperform ISD algorithms.

ISD algorithms are an important aspect of code-based cryptography since they predict
the key size achieving a given security level. ISD algorithms should not be considered as
attacks in the classical sense, as they are not breaking a code-based cryptosystem, instead
they determine the choice of parameters for a given security level.

58
 Due to the duality of the decoding problem and the SDP also ISD algorithms can be for-
mulated through the generator matrix or the parity-check matrix. Throughout this survey,
we will stick to the parity-check matrix formulation.

The first ISD algorithm was proposed in 1962 by Prange [182] and interestingly, all im-
provements display the same structure: choose an information set, use Gaussian elimination
to bring the parity-check matrix in a standard form, assuming a certain weight distribution
on the error vector, we can go through smaller parts of the error vector and check if the
parity-check equations are satisfied. The assumed weight distribution of the error vector thus
constitutes the main part of an ISD algorithm.
In an ISD algorithm we fix a weight distribution and go through all information sets to
find an error vector of this weight distribution. This is in contrast to ’brute-force attacks’
where one fixes an information set and goes through all weight distributions of the error
vector. In fact, due to this, ISD algorithms are in general not deterministic, since there are
instances for which there exists no information set where the error vector has the sought after
weight distribution. Clearly, a brute-force algorithm requires much more binary operations
than an ISD algorithm, thus, in practice we only consider ISD algorithms.

ISD algorithms were originally proposed for the Hamming metric, but have also been
translated to the rank metric, which we cover in Section 5.2.9. Recently, ISD algorithms
have also been proposed for other metrics, such as the Lee metric in [126, 223, 89] and the
sum-rank metric [184]. To propose an ISD algorithm in a new metric is always the first step
to introduce this new metric to code-based cryptography.

For this section we will need to recall some notation: let S ⊆ {1, . . . , n} be a set of
size s, then for a vector x ∈ Fnq we denote by xS the vector of length s consisting of the
entries of x indexed by S. Whereas, for a matrix A ∈ Fqk×n , we denote by AS the matrix
consisting of the columns of A indexed by S. For a set S we denote by S C its complement.
For S ⊆ {1, . . . , n} of size s we denote by Fnq (S) the vectors in Fnq having support in S. The
projection of x ∈ Fnq (S) to Fsq is then canonical and denoted by πS (x). On the other hand,
we denote by σS (x) the canonical embedding of a vector x ∈ Fsq to Fnq (S).

5.2.1 General Algorithm

(n−k)×n
We are given a parity-check matrix H ∈ Fq of a code C, a positive integer t and a
syndrome s ∈ Fq , such that there exists a vector e ∈ Fnq of Hamming weight less than or
n−k

equal to t with syndrome s, i.e., eH⊤ = s. The aim of the algorithm is to find such a vector
e.

1. Find an information set I ⊂ {1, . . . , n} of size k for C.

2. Bring H into the systematic form corresponding to I, i.e., find an invertible matrix
(n−k)×(n−k) (n−k)×k
U ∈ Fq , such that (UH)I = A, for some A ∈ Fq and (UH)I C = Idn−k .
3. Go through all error vectors e ∈ Fnq having the assumed weight distribution (and in
particular having Hamming weight t).
4. Check if the parity-check equations, i.e., eH⊤ U⊤ = sU⊤ are satisfied.
5. If they are satisfied, output e, if not start over with a new choice of I.

59
 Since the iteration above has to be repeated several times, the cost of such algorithm is
given by the cost of one iteration times the number of required iterations.
Clearly, the average number of iterations required is given as the reciprocal of the success
probability of one iteration and this probability is completely determined by the assumed
weight distribution.

5.2.2 Overview Algorithms

The first ISD algorithm was proposed in 1962 by Prange [182] and is sometimes referred to
as plain ISD. In this algorithm Prange makes use of an information set of a code, that in
fact contains all the necessary information to decode, in a clever way. For this we have to
assume that there is an information set where the error vector has weight 0 (thus all t errors
are outside of this information set). One now only has to bring the parity-check matrix into
systematic form according to this information set, which has a polynomial cost, this is called
an iteration of the algorithm. However, one has to find such an information set first. This is
done by trial and error, which results in a large number of iterations. Indeed, the assumption
that no errors happen in the information set is not very likely and thus the success probability
of one iteration is very low.
All the improvements that have been suggested to Prange’s simplest form of ISD (see for
example [65, 67, 66, 93, 138, 149, 215]) assume a more likely weight distribution of the error
vector, which results in a higher cost of one iteration but give overall a smaller cost, since less
iterations have to be performed.
The improvements split into two directions: the first direction is following the idea of Lee
and Brickell [146] where they ask for v errors in the information set and t − v outside. The
second direction is Dumer’s approach [93], which is asking for v errors in k + ℓ bits, which are
containing an information set, and t − v in the remaining n − k − ℓ bits. Clearly, the second
direction includes the first direction by setting ℓ = 0.
Following the first direction, Leon [149] generalizes Lee-Brickell’s algorithm by introducing
a set of size ℓ outside the information set called zero-window, where no errors happen. In
1988, Stern [208] adapted the algorithm by Leon and proposed to partition the information
set into two sets and ask for v errors in each part and t − 2v errors outside the information
set (and outside the zero-window). In 2010, with the rise of code-based cryptography over a
general finite field Fq , Peters generalized these algorithms to Fq .
In 2011, Bernstein, Lange and Peters proposed the ball-collision algorithm [57], where they
reintroduce errors in the zero-window. In fact, they partition the zero-window into two sets
and ask for w errors in both and hence for t − 2v − 2w errors outside. This algorithm and its
speed-up techniques were then generalized to Fq by Interlando, Khathuria, Rohrer, Rosenthal
and Weger in [128]. In 2016, Hirose [123] generalized the nearest neighbor algorithm over Fq
and applied it to the generalized Stern algorithm.
An illustration of these algorithms is given in Figure 2, where we assume for simplicity
that the information set is in the first k positions and the zero-window is in the adjacent ℓ
positions.

The second direction has resulted in many improvements, for example in 2009 Finiasz and
Sendrier [98] have built two intersecting subsets of the k +ℓ bits, which contain an information
set, and ask for v disjoint errors in both sets and t−2v in the remaining n−k−ℓ bits. Niebuhr,

60
Figure 2: Overview of algorithms following the splitting of Lee-Brickell, adapted from [57].

Persichetti, Cayrel, Bulygin and Buchmann [169] in 2010 improved the performance of ISD
algorithms over Fq based on the idea of Finiasz and Sendrier.
In 2011, May, Meurer and Thomae [158] proposed the use of the representation technique
introduced by Howgrave-Graham and Joux [127] for the subset sum problem. Further im-
provements have been proposed by Becker, Joux, May and Meurer [44] in 2012 by introducing
overlapping supports. We will refer to this algorithm as BJMM. In 2015, May-Ozerov [159]
used the nearest neighbor algorithm to improve BJMM and finally in 2017, the nearest neigh-
bor algorithm over Fq was applied to the generalized BJMM algorithm by Gueye, Klamti and
Hirose [120].
These new approaches do not use set partitions of the support but rather a sum partition
of the weight. An illustration of these algorithms is given in Figure 3, where we again assume
that the k + ℓ bits containing an information set are in the beginning. The overlapping sets
are denoted by X1 and X2 and their intersection of size 2α(k + ℓ) is in blue. The amount of
errors within the intersection is denoted by δ.

A very introductory reading on ISD algorithms is in the thesis of Weger [222], which we
also follow closely and for binary ISD algorithms, a very informative reading is the thesis of
Meurer [161].

It is important to remark (see [161]) that the BJMM algorithm, even if having the smallest
complexity until today, comes with a different cost: memory. In order to achieve a complexity
of 128 bits, BJMM needs about 109 terabytes of memory. In fact, Meurer observed that if one
restricts the memory to 240 (which is a reasonable restriction), BJMM and the ball-collision
algorithm are performing almost the same.

What is the possible impact on the cost of ISD algorithms when using a capable quantum
computer? In [53] the authors expect that quantum computers result in a square
√ root speed up
for ISD algorithms, since Grover’s search algorithm [117, 118] needs only O( N ) operations
to find an element in a set of size N , instead of O(N ) many. Thus, intuitively, the search
of an information set will become faster and thus the number of iterations needed in an ISD
algorithm will decrease.

61
 Figure 3: Overview of algorithms following the splitting of Dumer.

Since all the improvements upon Prange’s algorithm were only focusing on decreasing
this number of iterations, the speed up for these algorithms will be smaller, than for the
original algorithm by Prange. Hence the authors predict that on a capable quantum computer
Prange’s algorithm will result as the fastest.

5.2.3 Techniques
In the following we introduce some speed-up techniques for ISD algorithms, mostly introduced
in [57] over F2 and later generalized to Fq in [128].

First of all, we want to fix the cost that we consider throughout this chapter of one
addition and one multiplication over Fq , i.e., we assume that one addition over Fq costs
⌈log2 (q)⌉ binary operations and one multiplication costs ⌈log2 (q)⌉2 binary operations. The
cost of the multiplication is clearly not using the fastest algorithm known but will be good
enough for our purposes. Also for the cost of multiplying two matrices we will always stick
to a broad estimate given by school book long multiplication,
 i.e., multiplying AB, where
A ∈ Fqk×n and B ∈ Fqn×r will cost nkr ⌈log2 (q)⌉ + ⌈log2 (q)⌉2 binary operations.

Number of Iterations One of the main parts in the cost of an information set decoding
algorithm is the average number of iterations needed. This number depends on the success
probability of one iteration. In turn, the success probability is completely given by the
assumed weight distribution of the error vector. Since in one iteration we consider a fixed
information set, the success probability of an iteration is given by the fraction of how many
vectors there are with the assumed weight distribution, divided by how many vectors there
are in general with the target weight t.
Example 127. For example, we are looking for e ∈ Fnq of Hamming weight t, and we assume
that the error vector has no errors inside
an information set I, and thus all t errors appear
in I C of size n − k. Since there are n−k t
t (q − 1) many vectors having support of size t in a
set of size n − k and the total number of vectors of support t in a set of size n is given by

62
 n

t (q − 1)t , we have that the success probability of one iteration is given by
  −1
n−k n
,
t t
and hence the number of iterations needed on average is given by

n − k −1 n
   
.
t t

Early Abort In some of the algorithms we have to perform a computation and the algo-
rithm only proceeds if the result of this computation satisfies a certain condition. In our case,
the condition is that the weight of the resulting vector does not exceed a target weight.
We thus compute one entry of the result and check the weight of this entry, before pro-
ceeding to the next entry. As soon as the weight of the partially computed vector is above
the target weight, we can stop the computation, hence the name early abort.
Example 128. To provide an example also for this technique, assume that we have to compute
xA, for x ∈ Fkq of Hamming weight t and A ∈ Fqk×n . Usually computing xA would cost
 
nt ⌈log2 (q)⌉2 + ⌈log2 (q)⌉ binary operations.
However, assuming our algorithm only proceeds if wtH (xA) = w, we can use the method
of early abort, i.e., computing one entry of the resulting vector and checking its weight
simultaneously. For this we assume that the resulting vector is uniformly distributed. Since
we are over Fq , the probability that an entry adds to the weight of the full vector is given
by q−1 q
q . Hence we can expect that after computing q−1 w entries the resulting vector should
q
have reached the weight w, and after computing q−1 (w + 1) entries we should have exceeded
the target
 weight w and can abort.
 Since computing only one entry of the resulting vector
2
costs t ⌈log2 (q)⌉ + ⌈log2 (q)⌉ binary operations, the cost of this step is given by

q  
(w + 1)t ⌈log2 (q)⌉2 + ⌈log2 (q)⌉
q−1
binary operations, instead of
 
nt ⌈log2 (q)⌉2 + ⌈log2 (q)⌉ .
q
Clearly, this is a speed up, whenever q−1 (w + 1) < n.

Number of Collisions In some algorithms we want to check if a certain condition is verified

and only then we would proceed. This condition depends on two vectors x and y living in
some sets. S, respectively T . Hence the algorithm would go through all the vectors x ∈ S
and then through all the vectors y ∈ T in their respective sets and check if the condition
is satisfied for a fixed pair (x, y). If this is the case, such a pair is called a collision. The
subsequent steps of the algorithm would be performed on all the collisions, thus multiplying
the cost of these steps with the size of the set of all (x, y), i.e., | S || T |.
Instead, we can compute the average number of collisions we can expect on average.
Example 129. Let us also give an example for this technique; assume that we only proceed
whenever
x + y = s,

63
for a fixed s ∈ Fkq and for all x ∈ Fkq of Hamming weight v and all y ∈ Fkq of Hamming weight
w. To verify this condition we have to go through all possible x and y, thus costing
  
k k
(q − 1)v+w min{k, v + w} log2 (q)
v w
binary operations. As a subsequent step one would compute for all such (x, y) the vector
Ax − By, for some fixed A ∈ Fqn×k and B ∈ Fqn×k . Usually one would do this for all elements
in S = {(x, y) | x, y ∈ Fkq , wtH (x) = v, wtH (y) = w}, giving this step a cost of
  
k k
(q − 1)v+w min{k, v + w}n log2 (q) + log2 (q)2 .


v w
However, we only have to perform the subsequent steps as many times as on average we
expect a collision, i.e., a pair (x, y) such that x + y = s. Assuming a uniform distribution,
this amount is given by
k k v+w



v w (q − 1)
  
|S| k k
= < (q − 1)v+w−n .
qn qn v w
Thus computing Ax − By for all (x, y) ∈ S costs on average
  
k k
(q − 1)v+w−n min{k, v + w}n log2 (q) + log2 (q)2


v w
binary operations, which is clearly less than the previous cost.

Intermediate Sums In some algorithms we have to do a certain computation for all vectors
in a certain set. The idea of intermediate sums is to do this computation in the easiest case
and to use the resulting vector to compute the results for harder cases. This will become
clear with an example.
Example 130. Let A ∈ F2k×n and assume that we want to compute xA for all x ∈ Fk2 of
Hamming weight t. This would usually cost
 
k
nt
t
binary operations.
Using the concept of intermediate sums helps to speed up this computation: we first
compute xA for all x ∈ Fk2 of Hamming weight 1, thus just outputting the rows of A which
is for free. As a next step, we compute xA for all x ∈ Fk2 of Hamming weight 2, which is the
same as adding two rows of A and hence costs k2 n binary operations. As a next step, we

compute xA for all x ∈ Fk2 of Hamming weight 3. This is the same as adding one
row of A
to one of the already computed vectors from the previous step, thus this costs k3 n binary
operations. If we proceed in this way, until we compute xA for all x ∈ Fk2 of Hamming weight
t, this step costs
nL(k, t)
binary operations, where
t  
X k
L(k, t) = .
i
i=2

64
This is a speed up to the previous cost, since
t        
X k k k k
n =n + ··· + < nt .
i 2 t t
i=2

When generalizing this result to Fq , to compute xA for all x ∈ Fkq of Hamming weight
1, does not come for free anymore. Instead we have to compute A · λ for all λ ∈ F× q which
2
costs kn ⌈log2 (q)⌉ binary operations. Further, if we want to compute xA for all x ∈ Fkq of
Hamming weight 2, we have to add two multiples of rows of A. While there are still k2 many

rows, we now have (q − 1)2 multiples. Thus, this step costs k2 (q − 1)2 n ⌈log2 (q)⌉ binary

operations. Proceeding in this way, the cost of computing xA for all x ∈ Fkq of Hamming
weight t, is given by
Lq (k, t)n ⌈log2 (q)⌉ + kn ⌈log2 (q)⌉2
binary operations, where
t  
X k
Lq (k, t) = (q − 1)i .
i
i=2
Which is clearly less than the previous cost of
 
k  
(q − 1)t nt ⌈log2 (q)⌉2 + ⌈log2 (q)⌉
t

binary operations.

5.2.4 Prange’s Algorithm

In Prange’s algorithm we assume that there exists an information set I that is disjoint to the
support of the error vector Supp(e), i.e.,

I ∩ Supp(e) = ∅.

Of course, such an assumption comes with a probability whose reciprocal defines how many
iterations are needed on average, if the algorithm ends. Note that Prange’s algorithm is not
deterministic, i.e., there are instances which Prange’s algorithm can not solve. For an easy
example, one can just take an instance where wtH (e) = t > n − k =| I C |. For a more elabo-
rate example, which also allows unique decoding, assume that we have a parity-check matrix,
which is such that each information set includes the first position. Then an error vector with
non-zero entry in the first position could never be found through Prange’s algorithm.

To illustrate the algorithm, let us assume that the information set is I = {1, . . . , k}, and
(n−k)×n
let us denote by J = I C . To bring the parity-check matrix H ∈ Fq into systematic
(n−k)×(n−k)
form, we multiply by an invertible matrix U ∈ Fq . Since we assume that no errors
occur in the information set, we have that e = (0k , eJ ) with wtH (eJ ) = t. We are in the
following situation:
 
  A ⊤
eH⊤ U⊤ = 0k eJ   = sU⊤ ,
Idn−k

65
 (n−k)×k
for A ∈ Fq .
It follows that eJ = sU⊤ and hence we are only left with checking the weight of sU⊤ .
We will now give the algorithm of Prange in its full generality, i.e., we are not restricting
to the choice of I and J that we made before for simplicity.

Algorithm 1 Prange’s Algorithm over Fq in the Hamming metric

(n−k)×n
Input: H ∈ Fq , s ∈ Fqn−k , t ∈ N.
Output: e ∈ Fnq with eH⊤ = s and wtH (e) = t.

1: Choose an information set I ⊂ {1, ..., n} of size k and define J = I C .

(n−k)×(n−k)
2: Compute U ∈ Fq , such that

(UH)I = A and (UH)J = Idn−k ,

(n−k)×k
where A ∈ Fq .
3: ′
Compute s = sU . ⊤

4: if wtH (s′ ) = t then

5: Return e such that eI = 0k and eJ = s′ .
6: Start over with Step 1 and a new selection of I.

Theorem 131. Prange’s algorithm over Fq requires on average

 −1  
n−k n  
(n − k)2 (n + 1) ⌈log2 (q)⌉ + ⌈log2 (q)⌉2
t t

binary operations.

Proof. One iteration of Algorithm 1 only consists in bringing H into systematic form and to
apply the same row
 operations
 on the syndrome; thus, the cost can be assumed equal to that
⊤
of computing U H s , i.e.,

(n − k)2 (n + 1)(⌈log2 (q)⌉ + ⌈log2 (q)⌉2 )

binary operations.
The success probability is given by having chosen the correct weight distribution of e. In
this case, we require that no errors happen in the chosen information set, hence the probability
is given by
  −1
n−k n
.
t t
Then, the estimated overall cost of Prange’s ISD algorithm over Fq is given as in the
claim.

Let us consider an example for Prange’s algorithm.

66
Example 132. Over F5 , we are given
 
3 2 1 4 3 0 4 4 3 4
 
2 3 4 0 1 2 3 2 4 2
 
 
3 0 3 1 4 0 2 2 0 0
 
H= ,
2 3 0 2 3 1 4 4 3 0
 
 
0 2 3 0 2 0 3 4 2 4
 
 
2 3 4 0 2 2 0 0 1 2

s = (2, 4, 0, 2, 0, 4) and t = 2. We start by choosing an information set, since I1 = {1, 2, 3, 4}

is not an information set, our first choice might be I2 = {1, 2, 3, 5}. As a next step we compute
U to get H into systematic form. For this information set we have that
 
3 4 1 1 0 0 0 0 0 0
 
0 3 3 0 4 1 0 0 0 0
 
 
4 4 2 0 4 0 1 0 0 0
 
U2 H =  .
1 4 4 0 3 0 0 1 0 0
 
 
2 0 2 0 2 0 0 0 1 0
 
 
0 1 3 0 1 0 0 0 0 1

We apply the same on the syndrome, getting

s′2 = sU⊤
2 = (3, 2, 4, 3, 4, 1),

which is now unfortunately not of Hamming weight 2. Thus, we have to choose another infor-
mation set. This procedure repeats until the chosen information set succeeds. For example
for I = {7, 8, 9, 10}. In fact, if we now compute the systematic form we get
 
1 0 0 0 0 0 4 0 0 4
 
0 1 0 0 0 0 1 1 0 3
 
 
0 0 1 0 0 0 4 2 1 1
 
UH =   
0 0 0 1 0 0 0 4 4 0

 
0 0 0 0 1 0 2 3 2 0
 
 
0 0 0 0 0 1 2 4 4 3

and s′ = sU⊤ = (2, 0, 0, 4, 0, 0), which has Hamming weight 2. Thus,

e = (s′ , 0) = (2, 0, 0, 4, 0, 0, 0, 0, 0, 0).

5.2.5 Stern’s Algorithm

Stern’s algorithm [208] is one of the most used ISD algorithms, as it is considered one of the
fastest algorithms on a classical computer. In this algorithm we use the idea of Lee-Brickell

67
and allow errors inside the information set and in addition we partition the information set
into two sets and ask for v errors in both of them. Further, we also use the idea of Leon [149]
to have a zero-window of size ℓ outside the information set, where no errors happen.
Stern’s algorithm is given in Algorithm 2. But first we explain the algorithm and illustrate
it.
The steps are the usual: we first choose an information set and then bring the parity-check
matrix into systematic form according to this information set. We partition the information
set into two sets and define the sets S and T , where S takes care of all vectors living in one
partition and T takes care of all vectors living in the other partition. We can now check
whether two of such fixed vectors give us the wanted error vector.
To illustrate the algorithm, we assume that the information set is I = {1, . . . , k} and
that the zero-window is Z = {k + 1, . . . , k + ℓ}. Further, let us define J = (I ∪ Z)C =
{k + ℓ + 1, . . . , n}. We again denote by U the matrix that brings the parity-check matrix into
systematic form and write the error vector partitioned into the information set part I, the
zero-window part Z and the remaining part J, as e = (eI , 0ℓ , eJ ), with wtH (eI ) = 2v and
wtH (eJ ) = t − 2v. Thus, we get the following:
 
A ⊤ B⊤
    
⊤ ⊤ ⊤
eH U = eI 0ℓ eJ  Idℓ 0ℓ×(n−k−ℓ) = s1 s2 = sU ,
 

 
0(n−k−ℓ)×ℓ Idn−k−ℓ

(n−k−ℓ)×k
where A ∈ Fqℓ×k and B ∈ Fq .
From this we get the following two conditions

eI A⊤ = s1 , (5.1)
eI B⊤ + eJ = s2 . (5.2)

We partition the information set I into the sets X and Y , for the sake of simplicity, assume
that k is even and m = k/2. Assume that X = {1, . . . , m} and Y = {m + 1, . . . , k}. Hence,
we can write eI = (eX , eY ), and Condition (5.1) becomes

σX (eX )A⊤ = s1 − σY (eY )A⊤ . (5.3)

Observe that the σX is needed, as eX has length m but we want to multiply it to A⊤ ∈

Fqk×ℓ .In the algorithm we will not use the embedding σX but rather Fkq (X), thus eX will
have length k, but only support in X.
In the algorithm, we define a set S that contains all vectors of the form σX (eX )A⊤ , i.e.,
of the left side of (5.3) and a set T that contains all vectors of the form s1 − σY (eY )A⊤ , i.e.,
of the right side of (5.3). Whenever a vector in S and a vector in T coincide, we call such a
pair a collision.
For each collision we define eJ such that Condition (5.2) is satisfied, i.e.,

eJ = s2 − eI B⊤

and if the weight of eJ is the remaining t − 2v, we have found the sought-after error vector.
We now give the algorithm of Stern in its full generality, i.e., we are not restricting to the
choice of I, J and Z, that we made before for illustrating the algorithm.

68
Algorithm 2 Stern’s Algorithm over Fq in the Hamming metric

(n−k)×n
Input: H ∈ Fq , s ∈ Fqn−k , t ∈ N, k = m1 + m2 , ℓ < n − k and v < min{m1 , m2 , ⌊ 2t ⌋}.
Output: e ∈ Fnq with eH⊤ = s and wtH (e) = t.

1: Choose an information set I ⊂ {1, ..., n} of size k and choose a zero-window Z ⊂ I C of

size ℓ, and define J = (I ∪ Z)C .
2: Partition I into X of size m1 and Y of size m2 = k − m1 .
(n−k)×(n−k)
3: Compute U ∈ Fq , such that
     
A Idℓ 0ℓ×(n−k−ℓ)
(UH)I =   , (UH)Z =   and (UH)J =  ,
B 0(n−k−ℓ)×ℓ Idn−k−ℓ

(n−k−ℓ)×k
where A ∈ Fqℓ×k and B ∈ Fq .
 
4: Compute sU⊤ = s1 s2 , where s1 ∈ Fℓq and s2 ∈ Fn−k−ℓ
q .
5: Compute the set S

S = {(eX A⊤ , eX ) | eX ∈ Fkq (X), wtH (eX ) = v}.

6: Compute the set T

T = {(s1 − eY A⊤ , eY ) | eY ∈ Fkq (Y ), wtH (eY ) = v}.

7: for (a, eX ) ∈ S do
8: for (a, eY ) ∈ T do
9: if wtH (s2 − (eX + eY )B⊤ ) = t − 2v then
10: Return e such that eI = eX + eY , eZ = 0ℓ and eJ = s2 − (eX + eY )B⊤ .
11: Start over with Step 1 and a new selection of I.

Theorem 133. Stern’s algorithm over Fq requires on average

m1 −1 m2 −1 n − k − ℓ −1 n
       

v v t − 2v t
  
· (n − k)2 (n + 1) ⌈log2 (q)⌉ + ⌈log2 (q)⌉2 + (m1 + m2 )ℓ ⌈log2 (q)⌉2
   
m2 v
+ ℓ Lq (m1 , v) + Lq (m2 , v) + (q − 1) ⌈log2 (q)⌉
v
m1 m2 2v



v (q − 1)
 
q
+ v min n − k − ℓ, (t − 2v + 1)
qℓ q−1
 
· 2v ⌈log2 (q)⌉2 + ⌈log2 (q)⌉

binary operations.

Proof. As in Prange’s algorithm, as a first step we bring H into systematic form and apply

69
the same row operations on the syndrome; a broad estimate for the cost is given by
 
(n − k)2 (n + 1) ⌈log2 (q)⌉ + ⌈log2 (q)⌉2

binary operations.
To compute the set S, we can use the technique of intermediate sums. We want to compute
eX A⊤ for all eX ∈ Fkq (X) of Hamming weight v. Using intermediate sums, this costs

Lq (m1 , v)ℓ ⌈log2 (q)⌉ + m1 ℓ ⌈log2 (q)⌉2

binary operations.
Similarly, we can build set T : we want to compute s1 − eY A⊤ , for all eY ∈ Fkq (Y ) of
Hamming weight v. Using intermediate sums, this costs
 
2 m2
Lq (m2 , v)ℓ ⌈log2 (q)⌉ + m2 ℓ ⌈log2 (q)⌉ + (q − 1)v ℓ ⌈log2 (q)⌉
v

binary operations. Note, that the Lq (m2 , v)ℓ ⌈log2 (q)⌉ + m2 ℓ ⌈log2 (q)⌉2 part comes from
m2

⊤
computing eY A , whereas the v (q − 1)v ℓ ⌈log2 (q)⌉ part comes from subtracting from each
of the vectors eY A⊤ the vector s1 .
In the remaining steps we go through all (a, eX ) ∈ S and all (a, eY ) ∈ T , thus usually the
cost of these steps should be multiplied by the size of S × T . However, since the algorithm
first checks for a collision, we can use instead of | S || T | the number of collisions we expect
on average. More precisely: since S consists of all eX ∈ Fkq (X) of Hamming weight v, S
is of size mv1 (q − 1)v and similarly T is of size mv2 (q − 1)v . The resulting vectors eX A⊤ ,

respectively, s1 − eY A⊤ live in Fℓq , and we assume that they are uniformly distributed. Hence,
we have to check on average
m1
m2
2v
v v (q − 1)
qℓ
many collisions. For each collision we have to compute s2 − (eX + eY )B⊤ . Since the algorithm
only proceeds if the weight of s2 − (eX + eY )B⊤ is t − 2v, we can use the concept of early
abort. Computing one entry of the vector s2 − (eX + eY )B⊤ costs
 
2v ⌈log2 (q)⌉2 + ⌈log2 (q)⌉

binary operations. Thus, we get that this step costs on average

q  
(t − 2v + 1)2v ⌈log2 (q)⌉2 + ⌈log2 (q)⌉
q−1
binary operations.
Finally, the success probability is given by having chosen the correct weight distribution
of e; this is exactly the same as over F2 and given by
    −1
m1 m2 n−k−ℓ n
.
v v t − 2v t

Thus, we can conclude.

70
 Note that we usually set in Stern’s algorithm the parameter m1 = ⌊ k2 ⌋. Hence assuming
that k is even we get a nicer formula for the cost, being

−2 
n − k − ℓ −1 n 
   
k/2 
⌈log2 (q)⌉ + ⌈log2 (q)⌉2
v t − 2v t
 2   !
k/2 q
· (n − k)2 (n + 1) + (q − 1)2v−ℓ min n − k − ℓ, (t − 2v + 1) 2v
v q−1
    
k/2
+ kℓ ⌈log2 (q)⌉2 + ℓ 2Lq (k/2, v) + (q − 1)v ⌈log2 (q)⌉
v
binary operations.

5.2.6 BJMM Algorithm

In what follows we cover the BJMM algorithm proposed in [44], this is considered to be the
fastest algorithm over the binary, for this reason we will stick to the binary case also for this
paragraph.
In the previous ISD algorithms one always represented the entries of the error vector as
0 = 0 + 0 and 1 = 1 + 0 = 0 + 1, that is one was looking for a set partition of the support.
The novel idea of the algorithm is to use also the other representations, i.e., 0 = 0 + 0 = 1 + 1.
Thus, the search space for the smaller error vector parts become larger but the probability to
find the correct error becomes larger as well.
The idea of the BJMM algorithm is to write a vector e of some length n and weight v as
e = e1 + e2 , where e1 and e2 are both of length n and of weight v/2 + ε, thus we are asking
for an overlap in ε positions, which will cancel out.
The first part of all algorithms, which belong to the second direction of improvements,
is to perform a partial Gaussian elimination (PGE) step, that is for some positive integer
(n−k)×(n−k)
ℓ ≤ n − k one wants to find an invertible matrix U ∈ F2 , such that (after some
permutation of the columns)  
Idn−k−ℓ A
UH =  ,
0 B
(n−k−ℓ)×(k+ℓ) ℓ×(k+ℓ)
where A ∈ F2 and B ∈ F2 . Hence we are looking for e = (e1 , e2 ), with
e1 ∈ Fn−k−ℓ
2 of weight t − v and e 2 ∈ F k+ℓ
2 , of weight v. For the parity-check equations, we
also split the new syndrome sU = (s1 , s2 ) with s1 ∈ Fn−k−ℓ
⊤
2 and s2 ∈ Fℓ2 , that is we want to
solve     
Idn−k−ℓ A e⊤ s⊤
UHe⊤ =   1  =  1 .
0 B e⊤
2 s⊤
2

The parity-check equations can thus be written as

e⊤ ⊤ ⊤
1 + Ae2 = s1 ,
Be⊤ ⊤
2 = s2 .

The idea of the algorithms using PGE is to solve now the second equation, i.e., to search for
e2 of length k + ℓ and weight v such that e2 B⊤ = s2 and then to define e1 = s1 − e2 A⊤ and
to check if this has then the remaining weight t − v.

71
 Note that this is now a smaller instance of a syndrome decoding problem, for which we
want to find a list of solutions. The success probability of such a splitting of e is then given
be
k + ℓ n − k − ℓ n −1
   
.
v t−v t
An important part of such algorithms is how to merge two lists of parts of the error vector
together. For this we consider two lists L1 , L2 , a positive integer u < k, which denotes the
number of positions on which one merges, a target vector t ∈ Fu2 and a target weight w. For
a vector x, let us denote by x|u the vector consisting of the first u entries of x.

Algorithm 3 Merge

Input: The input lists L1 , L2 , the positive integers 0 < u < k and 0 ≤ v ≤ n, the matrix
k×(k+ℓ)
B ∈ F2 and the target t ∈ Fu2 .
Output: L = L1 ⊲⊳ L2 .

1: Lexicographically sort L1 and L2 according to (Bx⊤ i )|u , respectively (Byj )|u +t for xi ∈ L1
and yj ∈ L2 .
2: for (xi , yj ) ∈ L1 × L2 with (Bx⊤ ⊤
i )|u = (Byj )|u + t do
3: if wtH (xi + yj ) = w then
4: L = L ∪ {xi + yj }.
5: Return L.

Lemma 134. The average cost of the merge algorithm (Algorithm 3) is given by
(L1 + L2 )u(k + ℓ) + L1 log(L1 )
+L2 log2 (L2 ) + (k + ℓ) L1 · L2 2−u ,

where Li = |Li | for i = 1, 2.

Exercise 135. Prove Lemma 134.
The algorithm will use this merging process three times.
For the internal parameter v (which can be optimized), we also choose the positive integers
ε1 , ε2 (also up to optimization), and define
v1 = v/2 + ε1 ,
v2 = v1 /2 + ε2 .
We start with creating the two base lists B1 and B2 , which depend on a partition P1 , P2 of
{1, . . . , k + ℓ}, of same size, i.e., k+ℓ
2 :

Bi = {x ∈ F2k+ℓ (Pi ) | wtH (x) = v2 /2}.

These lists have size B = (k+ℓ)/2

v2 /2
.
(1) (1) (1) (2) (2)
We now choose t1 ∈ Fu2 1 , which determines t2 = (s2 )|u1 +t1 . We also choose t1 , t3 ∈
Fu2 2 , which define
(2) (1) (2)
t2 = (t1 )|u2 + t1 ,
(2) (1) (2)
t2 = (t2 )|u2 + t3 .

72
 (2)
Then, for a positive integer u2 and the four target vectors ti , for i ∈ {1, . . . , 4} we
(2)
perform the first four merges using Algorithm 3 to get Li = B1 ⊲⊳ B2 on u2 positions,
(2) (2)
weight v2 and target vector ti for i ∈ {1, . . . , 4}. The lists Li are expected to be of size
L2 = k+ℓ −u2 .


v2 2
With the four new lists we then perform another two merges yielding
(1) (2) (2)
Li = L2i−1 ⊲⊳ L2i
(1)
on u1 positions, with weight v1 and target vectors ti for i ∈ {1, 2}. These lists are expected
to be of size L1 = k+ℓ

−u
v1 2
1.

As a last step we then merge the two new lists to get the final list
(1) (1)
L = L1 ⊲⊳ L2

on ℓ positions,

−ℓ with weight v and target vector s2 . The final list is expected to be of size
L = k+ℓ
v 2 .
One important aspect of such algorithms is the following
We have to make sure that at least one representation of the solution lives in each list.
This can either be done by employing the probability of this happening in the success proba-
bility, thus increasing the number of iterations or by choosing u, the number of positions on
which one merges in such a way that we can expect that at least one representation lives in
the lists.
(1) (1)
In [44] the authors chose the second option: observe that the number of tuples (e1 , e2 ) ∈
(1) (1)
L1 × L2 that represent a single solution e2 ∈ L is given by
  
v k+ℓ−v
U1 = .
v/2 ε1
(1)
Hence choosing u1 = log2 (U1 ) ensures that L ≥ 1. Similarly, since we also represent ei as
(2) (2) (1)
sum of two overlapping vectors (e2i−1 , e2i ), we have that for each ei we have approximately
  
v1 k + ℓ − v1
U2 =
v1 /2 ε2
many representations. Thus, we can choose u2 = log2 (U2 ).
Proposition 136. Algorithm 4 has an average cost of

n n − k − ℓ −1 k + ℓ −1 
    
· (n − k − ℓ)2 (n + 1)
t t−v v
+ 4(2Bu2 (k + ℓ) + 2B log(B) + (k + ℓ)B 2 2−u2 )
+ 2(2L2 u1 (k + ℓ) + 2L2 log(L2 ) + (k + ℓ)L22 2−u1 )
+ (2L1 ℓ(k + ℓ) + 2L1 log(L1 ) + (k + ℓ)L21 2−ℓ )
  
k + ℓ −ℓ
+ 2 2(t − v + 1)v
v
binary operations.

73
Algorithm 4 BJMM

(n−k)×n
Input: 0 ≤ ℓ ≤ n − k, 0 ≤ u2 ≤ u1 ≤ ℓ, ε1 , ε2 , t, v < t, H ∈ F2 and s ∈ F2n−k .
Output: e ∈ Fn2 with wtH (e) = t and He⊤ = s⊤ .

1: Choose an n × n permutation matrix P.

(n−k)×(n−k)
2: Find U ∈ F2 , such that
 
Idn−k−ℓ A
UHP =  ,
0 B

(n−k−ℓ)×(k+ℓ) ℓ×(k+ℓ)
where A ∈ F2   and B ∈ F2 .
s⊤
3: Compute Us⊤ =  1 , where s1 ∈ Fn−k−ℓ
2 , s2 ∈ Fℓ2 .
s⊤
2
4: Choose partitions P1 , P2 of {1, . . . , k + ℓ} of size (k + ℓ)/2.
5: Set n o
Bj = x ∈ F2k+ℓ (Pj ) | wtH (x) = v2 /2

for j ∈ {1, 2}.

(1) u (1) (1)
6: Choose t1 ∈ F2 1 , set t2 = (s2 )|u1 + t1
(2) (2) (2) (1) (2) (2) (1) (2)
7: Choose t1 , t3 ∈ Fu2 2 , set t2 = (t1 )|u2 + t1 and t4 = (t2 )|u2 + t3
8: for i ∈ {1, . . . , 4} do
(2)
9: Compute Li = B1 ⊲⊳ B1 using Algorithm 3 on u2 positions to get weight v2 and
(2)
target vectors ti .
10: for i ∈ {1, 2} do
(1) (2) (2)
11: Compute Li = L2i−1 ⊲⊳ L2i using Algorithm 3 on u1 positions to get weight v1 and
(1)
target vectors ti .
(1) (1)
12: Compute L = L1 ⊲⊳ L2 using Algorithm 3 on ℓ positions to get weight v and target
vector s2 .
13: for e2 ∈ L do
14: if wtH (s1 − e2 A⊤ ) = t − v then
15: Set e = (e1 , e2 ).
16: Return Pe.
17: Else start over at step 1.

5.2.7 Generalized Birthday Decoding Algorithms

(n−k)×n
In the syndrome decoding problem (SDP) we are given a parity-check matrix H ∈ Fq ,
a syndrome s ∈ Fqn−k and a weight t ∈ N and want to find an error vector e ∈ Fnq , such that
s = eH⊤ and wtH (e) = t.
The first step of a generalized birthday algorithm (GBA) decoder is the partial Gaussian
elimination step, i.e., for some positive integer ℓ ≤ n − k we bring the parity-check matrix

74
into the form  
Idn−k−ℓ A
H′ =  ,
0 B
up to permutation of columns. We recall from the BJMM algorithm, that this leaves us with
solving the smaller SDP instance: find e2 ∈ Fqk+ℓ of Hamming weight v ≤ t, such that

e2 B⊤ = s2 ,
ℓ×(k+ℓ)
for s2 ∈ Fℓq and B ∈ Fq .
This second step is usually performed using Wagner’s algorithm on a levels.
By abuse of notation, we write for the rest eB⊤ = s, instead of e2 B⊤ = s2 . In a Lee-
Brickell approach, one would now go through all possible e ∈ Fqk+ℓ of weight v and check if
they satisfy the parity-check equations. The idea of GBA is to split the vector e further. Let
us start with GBA on one level, that is
e = (e1 , e2 )
 
(k+ℓ)/2
with ei ∈ Fq of weight v/2, for i ∈ {1, 2}. Hence we define B = B1 B2 , with
ℓ×(k+ℓ)/2
Bi ∈ Fq , for i ∈ {1, 2} and split the syndrome s = s1 + s2 . We hence want that
e1 B⊤
1 + e B⊤ = s = s + s . For this we define two lists
2 2 1 2

L1 = {(e1 , e1 B⊤ (k+ℓ)/2
1 − s1 ) | e1 ∈ Fq , wtH (e1 ) = v/2},
L2 = {(e2 , e2 B⊤ (k+ℓ)/2
2 − s2 ) | e2 ∈ Fq , wtH (e2 ) = v/2}.
We are then looking for an element ((e1 , x1 ), (e2 , x2 )) ∈ L1 × L2 , such that x1 + x2 = 0, which
will then imply that e1 B⊤ ⊤
1 + e2 B2 = s = s1 + s2 .
This idea can be generalized to a levels, thus splitting
(1) (1)
e = (e1 , . . . , e2a ),
(1) (k+ℓ)/2a
where ei ∈ Fq of weight v/(2a ) and writing
 
B = B1 · · · B2a ,

ℓ×(k+ℓ)/2a
where Bi ∈ Fq and splitting s = s1 + · · · + s2a . For this we will need the merging
positions 0 ≤ u1 ≤ · · · ≤ ua = ℓ. One first constructs the base lists
(1) (1) (1) (1) a (1)
Lj = {(ej , ej B⊤
j − sj ) | ej ∈ F(k+ℓ)/2
q , wtH (ej ) = v/2a },
for j ∈ {1, . . . , 2a } and then performs a merges: in the i-th merge we are given a parameter
0 ≤ ui ≤ v and we want to merge
(i+1) (i) (i)
Lj = L2j−1 ⊲⊳ui L2j .
For this let us define the merge L = L1 ⊲⊳u L2 first formally. Given Li = {(ei , xi )}, for
i ∈ {1, 2} and u
L1 ⊲⊳u L2 = {((e1 , e2 ), x1 + x2 ) | x1 + x2 =u 0},
where a =u b, denotes that a and b are equal on the first u positions. The merging process
follows the following algorithm

75
 1. Lexicographically order the elements (ei , xi ) ∈ Li for i ∈ {1, 2} according to the first u
positions,
2. Search for a collision, i.e., x1 +x2 =u 0 and if found insert the corresponding ((e1 , e2 ), x1 +
x2 ) in L.
The general idea of GBA is that we will not use the probability that we can split e into
(e1 , . . . , e2a ) each having weight v/2a , but rather we want that the merging process of will
produce a solution with high probability. The average size of L is given by
| L1 || L2 |
L =| L1 ⊲⊳u L2 |= ,
qu
and thus, whenever L ≥ 1 we can be assured that this algorithm returns (on average) a
solution e.
This is only possible for large weights v. If we are in this case, there exists a further
(1)
improvement on the algorithm, where one does not take the whole lists Li but only 2b many
2b
such elements, and thus the algorithm works as long as 2qu ≥ 1.
Stern’s ISD algorithm is a special case of Wagner’s algorithm on one level, where ℓ = 0
and s1 = 0. However, in Stern’s algorithm one employs the probability of splitting the error
vector into (e1 , e2 ), rather than asking for
| L1 || L2 |
≥ 1.
qℓ
The idea of GBA or more precisely of Wagner’s approach was used in famous ISD papers
such as BJMM and MMT, where 3 levels turned out to be an optimal choice.

5.2.8 Asymptotic Cost

An important aspect of ISD algorithms (apart from the cost) is their asymptotic cost. The
idea of the asymptotic cost is that we are interested in the exponent e(R, q) such that for
large n the cost of the algorithm is given by q (e(R,q)+o(1))n . This is crucial in order to compare
different algorithms.
We consider codes of large length n, and consider the dimension and the error correction
capacity as functions in n, i.e., k, t : N → N. For these we define
lim t(n)/n = T,
n→∞
lim k(n)/n = R.
n→∞

If c(n, k, t, q) denotes the cost of an algorithm, for example Prange’s algorithm, then we are
now interested in
1
C(q, R, T ) = lim logq (c(n, k, t, q)).
n→∞ n
For this we often use Stirlings formula, that is
 
1 α + o(1)n
lim logq = α logq (α) − β logq (β) − (α − β) logq (α − β).
n→∞ n β + o(1)n
One of the most important aspects in computing the asymptotic cost, is that random
codes attain the asymptotic Gilbert-Varshamov bound with high probability, thus we are
allowed to choose a relative minimum distance δ such that R = 1 − hq (δ).

76
Example 137. The asymptotic cost of Prange’s algorithm is easily computed as
  !
n − k −1 n

1
lim logq =
n→∞ n t t
− (1 − T ) logq (1 − T ) − (1 − R) logq (1 − R) + (1 − R − T ) logq (1 − R − T ).
Exercise 138. Prove that the asymptotic cost of Prange is equal to
Hq (T ) − (1 − R)Hq (T /(1 − R)).
For the more sophisticated algorithms such as Stern and BJMM, we will also have internal
parameters, such as ℓ, v, which will be chosen optimal, i.e., giving the smallest cost.
Note that we assume half-distance decoding, i.e., T = δ/2, thus C(q, R, δ/2) = e(R, q)
and then compute the largest value of e(R⋆ , q) by taking
R⋆ = argmax0<R<1 e(R, q).
With the asymptotic cost, we can now compare different ISD algorithms. For this, we
will restrict ourselves to the binary case, since we presented the BJMM algorithm only over
the binary. In the following table BJMM refers to the algorithm presented in [44], MMT to
[158], BCD to the algorithm from [57] and Stern and Prange refer to the algorithms of [208],
respectively [182].

Algorithm e(R∗ , 2)
BJMM 0.1019
MMT 0.115
BCD 0.1163
Stern 0.1166
Prange 0.1208

Table 16: Asymptotic cost of different ISD algorithms over the binary

5.2.9 Rank-metric ISD Algorithms

Finally, we want to conclude this section on ISD algorithms explaining the idea of rank-metric
ISD algorithms.
For this we first recall that the Hamming support of an error vector e ∈ Fnqm is defined as
suppH (e) = {i ∈ {1, . . . , n} | ei 6= 0}.
The Hamming weight of e is then given by the size of the Hamming support, i.e.,
wtH (e) =| suppH (e) |≤ n.
If we would want to go through all error vectors of a given Hamming weight t, there are
 
n
(q m − 1)t
t

77
many choices. This concept changes when we move to the rank-metric. The rank support of
an error vector e ∈ Fnqm is usually defined as the Fq -vector space spanned by the entries of e :

suppR (e) = he1 , . . . , en iFq .

The rank weight of e is then defined as the Fq -dimension of the rank support, i.e.,

wtR (e) = dimFq (suppR (e)).

If we want to go through all vectors of a given rank weight t, there are

t−1 m
q − qi
 
m Y
= ∼ q (m−t)t
t q qt − qi
i=0

many choices. Thus, it is quite clear, that to look for an error vector in the rank metric poses
a more costly problem than its Hamming metric counterpart.
We wrote that this is usually the rank support that is considered, since there also exists a
different notion. For this let us recall the associated matrix of e ∈ Fnqm . Let Γ = {γ1 , . . . , γm }
be a basis of Fqm over Fq . For e ∈ Fnqm we can define the associated matrix Γ(e) ∈ Fqn×m as
m
X
ei = Γi,j γj .
j=1

That is we extend e⊤ according to the chosen basis into a matrix and we again have that

wtR (e) = rk(Γ(e)),

which is independent of the choice of basis.

Example 139. Let us consider e = (1, α) ∈ F28 , where F8 = F2 [α]/(α3 + α + 1). Then
 
1 0 0
Γ(e) =  .
0 1 0

Using the associated matrix, we have two definitions of a rank support:

1. If m ≤ n, we define the rank support the same way as before, that is

supp(e) = rowsp(Γ(e)) ⊆ Fm
q .
m 
In this case we again have t q vector spaces to go through.

2. If n ≤ m, we define the rank support however differently:

supp(e) = colsp(Γ(e)) ⊆ Fnq .

n
In this case we have t q many vector spaces.

78
 In the following we give only the ideas of the combinatorial and algebraic algorithms to
solve the rank SDP. First observe that we can write e = βE, where β = (β1 , . . . , βt ) is a basis
of the support of the error vector e and E ∈ Ft×nq .
The first proposed rank ISD algorithm [72] performs a basis enumeration. That is, we
want to enumerate all possible choices for β. Since if we know β, then solving βEH⊤ = s has
quadratic complexity. This attack has approximately a complexity of q tm operations.
The second proposed rank ISD algorithm [174] enumerates all possible matrices E in-
stead, resulting in a cost of approximately q (t−1)(k+1) operations. These approaches are called
combinatorial attacks, as they solve the rank SDP through enumerations.
The algebraic approach aims at translating the notion of the rank metric into an algebraic
setting. For example via linearized polynomials: in [104] and [21] it was observed that for
e ∈ Fnqm there exists a linearized polynomial of q-degree t of the form
t
i
X
f x) = f i xq
i=0

annihilating the error vector, i.e., f (ei ) = 0 for all i ∈ {1, . . . , n}. This algorithm works well
for small choices of t, giving an approximate cost [104] of
(k+1)m
 
O (n − k)3 q t⌈ n ⌉−n .

It is important to note that very recently, i.e., in 2020, a new benchmark for the complexity
of the rank SDP has been achieved by the paper [37], which solves the rank SDP using the
well studied MinRank problem from multivariate cryptography. This might be one of the
major reasons why NIST did not choose to finalize any of the code-based cryptosystem based
on the rank metric, although they were achieving much lower public key sizes; this area of
code-based cryptography needs further research before we can deem it secure.

5.3 Algebraic Attacks

In this section, we present some techniques which are used for algebraic attacks on certain
code-based cryptosystems. Most famously, is the square code attack, which is in general a
distinguisher attack. Distinguishers a priori want to show that the public code is in fact not
behaving randomly but like an algebraically structured code. Distinguishers can then further
imply a strategy on how to recover the structure of the secret code, e.g. the evaluation points
of a GRS code, or be used directly in a message recovery.
Definition 140. Let v = (v1 , . . . , vn ), w = (w1 , . . . , wn ) ∈ Fnq be two vectors. The Schur
product v ∗ w of v and w is the coordinatewise product of v and w, i.e.,

v ∗ w := (v1 w1 , . . . , vn wn ).

With this definition we can also define the Schur product of two linear codes.
Definition 141. Let C1 , C2 ⊂ Fnq be two linear codes. The Schur product of C1 and C2 is
defined as the Fq -span generated by the Schur product of all combinations of elements, i.e.,

C1 ∗ C2 := h{c1 ∗ c2 | c1 ∈ C1 , c2 ∈ C2 }i ⊂ Fnq .

For a linear code C ⊂ Fnq , we call C ∗ C the square code of C and denote it with C (2) .

79
 Clearly for any code C ⊆ Fnq of dimension k, we have that
 
(2) k(k + 1)
dim(C ) ≤ min ,n .
2
However, for codes which have a lot of algebraic structure, this square code dimension
might be much smaller.
Proposition 142. Let k ≤ n ≤ q be positive integers. Then,

dim(GRSn,k (α, β)) = min{2k − 1, n}.

Exercise 143. Prove Proposition 142.

Whereas for a random linear code of dimension k, the expected dimension of its square
code is typically quadratic in the dimension k:
Theorem 144 ([68, Theorem 2.3]). For a random linear code C over Fq of dimension k and
length n, we have with high probability that
  
(2) k+1
dim(C ) = min ,n .
2
This clearly provides a distinguisher between random codes and algebraically structured
codes. Let us list some of the codes, which suffer from such a distinguisher

1. GRS codes: Proposition 142,

2. low-codimensional subcodes of GRS codes: [225],
3. Reed-Muller codes: [63],
4. Polar codes: [38],
5. some Goppa codes: [83],
6. high rate alternant codes: [95],
7. algebraic geometry codes [82, 81].

Note, that square code attacks often need to be performed on a modified version of the
public code, for example
1. the sum of two GRS codes: [78, 84],
2. GRS codes with additional random entries: [80],
3. expanded GRS codes: [79].
McEliece proposed to use classical binary Goppa codes as secret codes in [160], and no al-
gebraic attack on this system has been developed. Thus, they are considered to be reasonably
secure and were chosen as the finalists for the NIST standardization process [11].
Recall that Goppa codes are heavily connected to GRS codes: let us consider a GRS code
over Fqm and some 1 ≤ λ ≤ m. The code C which contains all codewords of the GRS code
living in a fixed λ-dimensional Fq -vector subspace of Fqm is called a subspace subcode of a
GRS code.

80
 • If we choose λ = m we get a GRS code, which provides very low key sizes for the
McEliece cryptosystem due to their large error correction capacity and only considering
ISD attacks. They are however insecure due to the square code attack.

• If we choose λ = 1 we get a Goppa code, which suffers from very large key sizes due
to their small correction capacity, but they are deemed to be secure against algebraic
attacks.

The proposal [135] and also [49] propose to use a different λ in the McEliece system,
trying to find a balance between the two extreme points and profiting from both advantages:
smaller key sizes than Goppa codes would provide and thwarting the vulnerability of GRS
codes. But also this suggestion has been attacked for λ ≥ m/2 by the square code attack in
[79]:

Let us summarize this in Table 17.

dim C (2)


Code C
n o
Random Code min k(k+1)
2 , n (with high probability)
RS Code min{2k − 1, n}
n o
k(k+1) mr
Binary Goppa Codes min 2 − 2 (2r log2 (r) − r − 1) , n
[n, k = n − mr] (with high probability)
min O(mk2 ), n

Expanded GRS Code
[mn, mk] (with high probability)

Table 17: Square code dimension of different codes

Note that for the rank-metric based cryptosystems a similar distinguisher exists for the
rank analogues of the Reed-Solomon codes, namely the Gabidulin codes: these attacks all
stem from the original attack of Overbeck [175] on the proposal [101] to use Gabidulin codes
in the GPT framework, but also includes the attack of [125] on its generalization [152, 186].
They main tool here is that instead of taking the square code, one performs the Frobenius
map on the code.
Let us consider an extension field Fqm of the base field Fq . We denote by [i] the ith
Frobenius power, q i . The Frobenius map can be applied to a matrix or a vector by doing so
coordinatewise, i.e., for a matrix M ∈ Fqk×n
m with entries (mj,ℓ ) we denote by M[i] the matrix
[i]
with entries (mj,ℓ ).

81
Definition 145. Let M ∈ Fqk×n
m and ℓ ∈ N, then we define the operator Λℓ as

(ℓ+1)k×n
Λℓ : Fqk×n
m → Fq m ,
 
M
 
 [1] 
M ,
M 7→ Λℓ (M) = 
 ..  .

 . 
 
M[ℓ]

The Frobenius attack now considers the rowspan of this new matrix.

Proposition 146 ([175]). , Lemma 5.1 If M is the generator matrix of an [n, k] Gabidulin
code and ℓ ≤ n − k − 1, then the subvector space spanned by the rows of Λℓ (M) is an [n, k + ℓ]
Gabidulin code.

Note that this is similar to Proposition 142, where one shows that the square code of a
GRS code is again a GRS code. And as the square code dimension of a GRS code is 2k − 1,
in this case the dimension of the rowspace of the Frobenius of a Gabidulin code is k + ℓ.
However, for a random code C, the Frobenius of this code should have dimension of order
kℓ.

Theorem 147 ([153]). Let M ∈ Fqk×n

m be a random matrix of full column rank over Fq . Then
Λℓ (M) has rank
min{(ℓ + 1)k, n},
with probability at least 1 − 4q −m .

The Frobenius map can thus distinguish between a Gabidulin code and a random code.

5.4 Other Attacks

We want to note here, that there exist also several other attacks on code-based cryptosystems,
such as: side-channel attacks and chosen-ciphertext attacks. Since these attacks are less
mathematically involved, we will just quickly cover them and refer interested readers to [69].
Side-channel attacks try to get information from the implementation of the cryptosystem,
which includes timing information, power consumption and many more. Thus, side-channel
attacks complement the algebraic and non-structural attacks we have discussed before by
considering also the physical security of the cryptosystem.
There have been many side-channel attacks on the McEliece cryptosystem (see for example
[211, 24, 210, 73, 191]) which aim for example at the timing/reaction attacks based on the
error weight or recover the error weight using a simple power analysis on the syndrome
computation.
Note that recently the information gained through side-channel attacks was used in ISD
algorithms in [124].
Another line of attacks is the chosen-ciphertext attack (CCA): in a chosen-ciphertext
attack we consider the scenario in which the attacker has the ability to choose ciphertexts ci
and to view their corresponding decryptions, i.e., the messages mi . In this scenario we might
speak of an oracle that is querried with ciphertexts. The aim of the attacker is to gain the
secret key or to get as much information as possible on the attacked system. In an adaptive

82
chosen-ciphertext attack (CCA2) the attacker wants to distinguish a target ciphertext without
consulting the oracle on this target. Thus, the attacker may query the oracle on many
ciphertext but the target one. This means that the new ciphertexts are created based on
responses (being the corresponding messages) received previously.
In this context we also speak of ciphertext indistinguishability, meaning that an attacker
can not distinguish ciphertexts based on the message they encrypt. We have two main
definitions:

1. Indistinguishability under chosen-plaintext attack (IND-CPA),

2. Indistinguishability under adaptive chosen-ciphertext attack (IND-CCA2).

These are usually defined over a game, which is played between an attacker and a chal-
lenger, where we assume that we have a public-key encryption scheme with a secret key S and
a publicly known public key P. For IND-CPA, the attacker and the challenger are playing
the following game.

1. The attacker sends two distinct messages m1 , m2 to the challenger.

2. The challenger selects one of the messages mi and sends the challenge ci , which is the
encrypted message mi .

3. The attacker tries to guess i.

We say that a system is IND-CPA secure if an attacker has only a negligible advantage over
randomly guessing i.
For IND-CCA2, the attacker and the challenger are playing the following game.

1. The attacker sends two distinct messages m1 , m2 to the challenger.

2. The challenger selects one of the messages mi and sends the challenge ci , which is the
encrypted message mi .

3. The attacker may query a decryption oracle on any cipher but the target cipher ci .

4. The attacker tries to guess i.

We say that a system is IND-CCA2 secure if an attacker has only a negligible advantage over
randomly guessing i.
Note that in [137] the authors gave conversions of the McEliece system to achieve CCA2
security.

6 Historical Overview
There have been many proposals especially for the McEliece framework. We will here only
list a small choice of them, which we hope represent well the major difficulties in proposing
new code-based cryptosystems.
McEliece proposed to use binary Goppa codes for his framework, and while the initially
proposed parameters are now broken with information set decoding [55], algebraic attacks are
only known for specific parameter sets of Goppa codes [83, 95]. In fact, for most parameter
sets, there is no algebraic property of binary Goppa codes known which distinguishes them
from a random code. The drawback of binary Goppa codes, however, is that they can only

83
correct a small amount of errors, leading to large generator matrices for cryptosystems to
reach a fixed security level, resulting in large key sizes.
Other proposals have tried to avoid this problem by using other classes of algebraic codes.
Several proposals are based on GRS codes, since these codes have the largest possible error
correction capability, but were ultimately broken: Sidelnikov-Shestakov proposed an attack
[205] which recovers parameters for the Niederreiter scheme [170], where GRS codes were
originally proposed.
Attempts to avoid this weakness [50, 29, 31, 33, 61, 136, 170, 135, 45] were often unsuc-
cessful, as GRS codes can be distinguished from random codes with the help of the square
code [225, 78, 84, 79, 145], since the square code of a GRS code has a very low dimension.
Other proposals have been made using non-binary Goppa codes [56], algebraic geometry
codes [130], LDPC and MDPC codes [32, 164, 163], Reed-Muller codes [204] and convolutional
codes [154], but most of them were unsuccessful in hiding the structure of the private code
[82, 83, 140, 162, 173].

The first rank-metric code based cryptosystem called GPT was proposed in 1991 by
Gabidulin, Paramonov and Tretjakov [101]. The authors suggest the use of Gabidulin codes,
which can be seen as the rank-metric analog of GRS codes. Similar to the distinugisher on
GRS codes, namely the square code attack, also Gabidulin codes suffer from a distinguisher
by Overbeck [175] using the Frobenius map.
The GPT system was then generalized in [186], but still suffers from an extended Frobenius
distinguisher [125]. Since this proposal some authors have tried to fix this security issue by
tweaking the Gabidulin code [47, 185].

A different cryptosystem, which relies its security on the hardness of polynomial recon-
struction was proposed in [23] and has been attacked in [75]. Since this cryptosystem is
different to the usual McEliece framework, we denote it in the following as Augot-Finiasz
(AF).
Faure and Loidreau [96] proposed a rank-metric analog of the AF system, thus relying
the security on the hardness of reconstructing p–polynomials. Also this proposal has been
subject to algebraic attacks [103] and to repair attempts [219, 190, 189, 144] which have been
broken in [62]. Note that the AF system can be broken through list decoding of RS codes and
in the same manner, the Faure-Loidreau system can be broken via list decoding of Gabidulin
codes.

Next, we want to list some of the most important proposals for code-based signature
schemes. The first code-based signature scheme was proposed in 2001 by Courtois, Finiasz
and Sendrier (CFS) [76]. Again this can be considered as a framework, but the code suggested
by the authors was a high rate Goppa code, for which, unfortunately, exists a distinguisher
[95].
Another way to approach this problem, is to relax the weight condition on the error vector.
This idea has been followed in [30] where low-density generator matrices were proposed, in
[112], where convolutional codes were suggested and in [147], where they use Reed-Muller
codes. The proposals [30, 112] have been attacked in [180, 165] respectively.
Also notable are the signature schemes in [132, 133, 43, 105], which can at most be
considered as one-time signatures due to the attack in [70, 172].
In [122] the authors propose binary (u | u + v) codes in a signature scheme and the
security relies on the problem of finding a closest codeword. However, the hull of such a code

84
 Code proposed in attack

Goppa [160, 11]

Wild Goppa [56] [83]
Interleaved Goppa [94]
GRS [170] [205]
Twisted RS [45] [145]
low-codimensional subcodes of GRS [50] [225]
Sum of GRS [29, 136] [78]
Expanded GRS [135] [79]
Subspace Subcodes of GRS [49] [79]
GRS and random columns [221, 224] [80]
(U | U + V ) RS [157]
Reed-Muller [204] [63, 162]
Polar [203] [38]
Algebraic geometry [130] [82, 81]
LDPC [32, 164] [173]
MDPC [163] [173]
Convolutional [154] [140]
Ordinary concatenated [198] [199]
Generalized concatenated [183]

Table 18: Proposals for the McEliece Framework

Code proposed in attack

Gabidulin [101, 186] [175, 125]

Subspace subcodes of Gabidulin [47]
Twisted Gabidulin [185]

Table 19: Proposals for the GPT framework

is typically much larger than for a random linear code of the same length and dimension.
Thus, this proposal has been attacked in [86]. This problem has later been solved by the
authors of Wave [87], by using generalized (u | u + v) codes over the ternary and basing

85
 Code proposed in attack

GRS (list decoding) [23] [75]

Gabidulin (list decoding) [96] [103]
Interleaved Gabidulin [219, 190, 189] [62]
Gabidulin [144] [62]

Table 20: Proposals for the AF framework

the security on the farthest codeword problem. In addition, Wave provides a proof of the
preimage sampleable property (first introduced in [109]), which thwarts all attacks trying to
exploit the knowledge of signatures.
In [207] the authors propose a code-based signature scheme from the Lyubashevsky frame-
work, which was then broken in [14].
Also the code-equivalence problem has been used for a code-based signature scheme in
[59], which was attacked in [58].
A one-time signature scheme from quasi-cyclic codes has been proposed in [177]. Also this
proposal has been attacked in [197].
The signature scheme RaCoSS [195] submitted to NIST standardization process is similar
to the hash-and-sign approach of CFS but depending on some Bernoulli distributed vector.
This proposal has been broken (either see [226] or the comment section on the NIST website1 ).
Finally, the signature scheme pqsigRM [147] is an adaption of the broken CFS scheme
[76], where the authors propose the use of Reed-Muller codes instead of Goppa codes, this
proposal has also been cryptanalyzed2 .

In the rank metric, one of the most notable signature schemes is that of RankSign [19],
which has been attacked in [88].
Other rank-metric signature schemes include Durandal [18], which is in the Lyubashevsky
framework and MURAVE [142].

Due to the Fiat-Shamir transform, we also include code-based ZKID schemes here, al-
though the proposals until now all suffer from large signature sizes. The ZKID schemes
usually use random codes, thus we will often not specify a particular proposed code.
The first code-based ZKID was proposed by Stern in 1993 [209] and recently after also by
Véron [218]. In this survey we have covered two improvements on their idea, namely CVE
[71] and AGS [2].
In a recent paper [28] the authors propose to use restricted error vectors in CVE, which
leads to smaller signature sizes.
Another approach to reduce the signature sizes is the quasi-cyclic version of Stern’s ZKID,
proposed in [60].
Also rank-metric ZKID schemes have been proposed in the recent paper [46], with the
aim of turning it into a fully fledged rank-metric signature scheme.
1
https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/round-1/official-comments/Ra
2
https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/round-1/official-comments/pq

86
7 Submissions to NIST
In 2016 the National Institute of Standards and Technology (NIST) started a competition to
establish post-quantum cryptographic standards for public-key cryptography and signature
schemes. Initially, 82 proposals were submitted of which 69 could participate in the first
round. 19 of these submissions were based on coding theory.
In 2020, the third round was announced. Of the initial candidates, 9 public-key systems
and 6 signature schemes still remain in this round. Three of the 9 public-key cryptosystems
are code-based, one of them being Classic McEliece [11], a Niederreiter-based adaption of the
initial McEliece cryptosystem.
The other two candidates put effort on avoiding the drawback of large public-key sizes.
BIKE [15] achieves this by combining circulant matrices with MDPC codes, whereas HQC
[5] is a proposal based on the quasi-cyclic scheme, which does not require using the algebraic
structure of the error-correcting code.
In this section, we will study these candidates in depth, for this we provide tables sum-
marizing the submissions that were eliminated in round 1, round 2 and finally the finalists of
round 3.

Table 21 contains all public-key encryption and key-encapsulation mechanism candidates,

which were eliminated in round one. All candidates use the Hamming metric (HM) or the
rank metric (RM). Key sizes will be given in kilobytes, pk denotes the public key and sk the
secret key.
Due to space limitations, we will sometimes abbreviate the McEliece framework with MF,
the Niederreiter framework with NF, the framework of Alekhnovich by AF, the quasi-cyclic
framework by QCF and finally a Diffie-Hellman approach by DH.
In addition to acronyms that were already introduced, we also abbreviate quasi-cyclic
(QC), Ideal Code (IC) and double-circulant (DC).
The given key sizes are for the parameter sets that were proposed for 128 bits of security
(however, some proposals contained multiple suggestions for parameter sets for this security
level).
All data is taken from the supporting documentations of the NIST proposals BIG QUAKE
[35], DAGS [34], Edon-K [111], LAKE [16], LEDAkem [25], LEDApkc [26], Lepton [228],
LOCKER [17], McNie [108], Ouroboros-R [7], QC-MDPC KEM [227], Ramstake [212] and
RLCE-KEM [221].

The reason for the drop out of BIG QUAKE was mainly discussed at CBC 20193 , and is
due to the large key sizes of the proposal, as it is ”still worse than completely unstructured
lattice KEM.” The reason for Lepton’s drop out, is a security issue that can be found in the
comment section of the NIST website4 .

3
https://drive.google.com/file/d/1nruEobwdeJbtwouJssbjZCK0WQiBN7rW/view
4
urlhttps://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/round-
1/official-comments/Lepton-official-comment.pdf

87
 Candidate Framework Code Metric Pk Size Reason for Drop Out
BIG QUAKE NF QC Goppa HM 25 − 103 large key sizes
DAGS MF dyadic GS HM 8.1 broken [39]
Edon K MF binary Goppa HM 2.6 broken [150]
LAKE NF IC, DC, LRPC RM 0.4 merged (ROLLO)
LEDAkem NF QC LDPC HM 3.5 − 6.4 merged (LedAcrypt)
LEDApkc MF QC LDPC HM 3.5 − 6.4 merged (LedAcrypt)
Lepton AF BCH HM 1.0 cryptanalysis
LOCKER NF IC, DC, LRPC RM 0.7 merged (ROLLO)
McNie MF/NF QC LRPC RM 0.3 − 0.5 broken [20] [141]
Ouroboros-R QCF DC LRPC RM 1.2 merged (ROLLO)
QC-MDPC KEM MF QC MDPC HM 1.2 − 2.6 N/A
Ramstake DH RS HM 26.4 broken [213]
RLCE-KEM MF GRS HM 118 − 188 broken [80]

Table 21: Code-based PKE/KEM submissions to NIST, eliminated in round 1

In Table 22 we list all code-based signature schemes that were eliminated during round
one, which in every case was due to cryptanalysis.
The table contains their signature sizes, public key sizes, secret key sizes (all in kilobytes)
and the recommended number of rounds necessary to ensure verification with a very high
probability.
For this a security level of 128-bit is fixed in the respective scheme. The signature size
of pqsigRM is taken from [148], all other data is taken from the supporting documentations
pqsigRM [147], RaCoSS [195] and RankSign [19].

Candidate Signature Size Pk Size Sk Size Rounds

pqsigRM 0.5 262 138 100
RaCoSS 0.3 169 100 100
RankSign 1.4 − 1.5 10 1.4 − 1.5 N/A

Table 22: Code-based signature submissions to NIST, eliminated in round 1

Table 23 contains all PKE/KEM candidates that were eliminated during round two. There
are no code-based signature schemes that made it to round two or further.
All data is taken from the supporting documentations of LEDAcrypt [27], NTS-KEM [10],

88
ROLLO [3] and RQC [6].

Candidate Framework Code Metric Pk Size Reason for Drop Out

LEDAcrypt McE/N QC LDPC HM 1.4 − 2.7 broken [13]
NTS-KEM Niederreiter binary Goppa HM 319 merged (Classic McE)
ROLLO Niederreiter IC, LRPC RM 0.7 cryptanalysis [36]
RQC Quasi-Cyclic IC, Gabidulin RM 1.8 N/A

Table 23: Code-based PKE/KEM submissions to NIST, eliminated in round 2

Finally, there are three candidates that made it to the final round, round three. Classic
McEliece, as main candidate, and BIKE and HQC as alternative candidates.
As before, the public key (pk) size is given in kilobytes, data is taken from the proposed
parameters for the 128-bit security level.

Candidate Framework Code Metric pk size

Classic McEliece Niederreiter binary Goppa Hamming 14
BIKE Niederreiter MDPC Hamming 1.5
HQC Quasi-Cyclic decodable code of choice, QC Hamming 2.2

Table 24: Final round code-based PKE submissions to NIST

7.1 Finalists: Classic McEliece, BIKE and HQC

In this section, we present the three code-based round 3 proposals Classic McEliece, BIKE
and HQC. For each one, we give a mathematical description and the proposed parameters.

7.1.1 Classic McEliece

The NIST submission Classic McEliece uses the Niederreiter framework (Section 3.2) with
binary Goppa codes (Definition 32) as secret codes. This subsection is based on the round 3
submission [11].
Let us start with the description of the scheme. Let m be a positive integer, q = 2m ,
n ≤ q and t ≥ 2 be positive integers such that mt < n and set k = n − mt.
Further, pick a monic irreducible polynomial f (z) ∈ F2 [z] of degree m and identify Fq
with F2 [z]/f (z). Note that under this identification, every element in F2m can be written as

u0 + u1 z + . . . + um−1 z m−1

for a unique vector (u0 , u1 , . . . , um−1 ) ∈ Fm

2 .
With these preliminaries set, we can describe the public-key encryption scheme:

89
 • Key Generation:

1. Generate a random monic irreducible polynomial g(x) ∈ Fq [x] of degree t and n

random distinct elements α1 , . . . , αn ∈ Fq .
2. Compute a parity-check matrix H̃ = {h̃ij }ij of the binary Gopppa code with
parameters (g, α1 , . . . , αn ) by computing h̃ij = αi−1
j /g(αj ).

3. Apply an invertible matrix to H̃ and permute the columns of this matrix to get a
matrix in systematic form H = (Idn−k |T).
Denote with (α′1 , . . . , α′n ) the n-tuple obtained by applying the same permutation
to (α1 , . . . , αn ).
Note that (Idn−k |T) is a parity-check matrix of the Goppa code defined by (g, α′1 , . . . , α′n ).

• Private Key: The private key is the (n + 1)-tuple Γ′ = (g, α′1 , . . . , α′n ).

• Public Key: The public key is the (n − k) × (n − k) matrix T and the number t.

• Encryption: Encode the message as weight t vector e ∈ Fn2 and compute

c0 = He⊤ ∈ F2n−k .

• Decryption: Extend c0 to v = (c⊤ n ′

0 , 0, . . . , 0) ∈ F2 . The parameters Γ of the private
key define a Goppa code, so we can use a decoding algorithm for Goppa codes to find
a codeword c with distance ≤ t to v (if it exists).
We then recover e as e = v + c and check that it indeed satisfies He⊤ = c0 and is of
weight t.

Remark 148. The decryption works for the following reason: we have that H = (Idn−k |T), so

Hv⊤ = Idn−k c0 = c0 .

Thus, it follows that

H(v + e)⊤ = 0,
and c = v + e is a codeword of the Goppa code defined by Γ′ .
Since this code has minimum distance at least 2t + 1, we get that v + e is also the unique
codeword of distance up to t from v, so we may recover the error vector as e = v + c.

7.1.2 Proposed Parameters for Classic McEliece

We give an overview of the proposed parameter sets, input and output sizes for the expected
security levels. Level 1 corresponds to 128 bits, level 3 corresponds to 192 bits and level 5
corresponds to 256 bits of security. The key sizes and ciphertext size are given in bytes.
The Classic McEliece submission is considered the main candidate for standardization
by NIST. It is clearly based on the original proposal of McEliece [160] and thus a rather
conservative choice by NIST. The main advantage of Classic McEliece is thus its well studied
security, as there are no known algebraic attacks on the original proposal of McEliece since
1978, but it still suffers from the same disadvantage, i.e., the large size of its public keys.

90
 Parameter set m n t Public key Private key Ciphertext Security level
mceliece348864 12 3488 64 261120 6492 128 1
mceliece460896 13 4608 96 524160 13608 188 3
mceliece6688128 13 6688 128 1044992 13932 240 5
mceliece6960119 13 6960 119 1047319 13948 226 5
mceliece8192128 13 8192 128 1357824 14120 240 5

Table 25: Parameters for Classic McEliece

7.1.3 BIKE
The NIST submission Bit Flipping Key Encapsulation (BIKE) combines circulant matrices
with the idea of moderate density parity-check matrices (Definition 54). The usage of circulant
matrices keeps key sizes small while using moderate density parity-check matrices allows
efficient decoding with a Bit-Flipping algorithm. We follow the NIST round 3 submission [15]
and give a ring-theoretic description of the system. Note however that BIKE can also be fully
described with matrices.
Let r be prime number such that 2 is primitive modulo r, i.e., 2 generates the multiplicative
group Z/rZ× . The parameter r denotes the block size, √ from which we obtain the code length
n = 2r. We √ further pick an even row weight w ≈ n such that w/2 is odd and an error
weight t ≈ n.
We then set R := F2 [x]/(xr − 1). Any element a ∈ R can be represented as polynomials
of degree less or equal than r − 1 and can uniquely be written as linear combination of the
form
Xr−1
a= λi x i ,
i=0

where λi ∈ F2 for all i ∈ {0, 1, . . . , r − 1}. This gives us a natural notion of the weight of a,
which we denote with wt(a), i.e.,

wt(a) = |{i ∈ {0, 1, . . . , r − 1} | λi 6= 0}|.

Remark 149. The choice of r ensures that the irreducible factors of xr − 1 are x − 1 and
xr−1 + xr−2 + · · · + 1 (see Exercise 152). As a consequence of this, an element a ∈ R is
invertible if and only if wt(a) is odd and wt(a) 6= r.

• Key Generation: Pick a pair (h0 , h1 ) ∈ R2 such that wt(h0 ) = wt(h1 ) = w/2. Then
compute h = h1 h−1
0 ∈ R.

• Private Key: The private key is the pair (h0 , h1 ).

• Public Key: The public key is the element h ∈ R and the integer t.

• Encryption: The message gets encoded as error (e0 , e1 ) ∈ R2 such that wt(e0 ) +
wt(e1 ) = t and then encrypted as s = e0 + e1 h.

91
 • Decryption: We compute sh0 = e0 h0 + e1 h1 . Since h0 and h1 are of moderate density,
this can be decoded efficiently with a Bit-Flipping algorithm to recover the pair (e0 , e1 ).

Remark 150. The difficulty of attacking BIKE lies in finding an element h̃ ∈ R of at most
moderately high weight, such that hh̃ is also of at most moderately high weight.
Pr−1
Remark 151. BIKE can also be described with matrices: for a = i=0 ai xi ∈ R and b =
Pr−1 i
i=0 bi x , we are considering the code with parity-check matrix
 
a0 a1 · · · ar−2 ar−1 b0 b1 · · · br−2 br−1
 
 ar−1 a0 · · · ar−3 ar−2 br−1 b0 · · · br−3 br−2 
 
 . .. .. .. .. .. 
 
H =  .. . . . . .  .
 
 
 a2 a3 · · · a0 a1 b2 b3 · · · b0 b1 
 
a1 a2 · · · ar−1 a0 b1 b2 · · · br−1 b0
Pr−1 Pr−1
In this case, the errors e0 = i=0 e0,i xi and e1 = i=0 e1,i xi may be viewed as vectors

ẽj = (ej,0 , ej,r−1 , ej,r−2 , . . . , ej,1 )

for all j ∈ {1, 2}. We then compute syndromes by

H(ẽ1 | ẽ2 )⊤ .

Exercise 152. Let r be a prime such that 2 generates Z/rZ× . Show that the irreducible
factors of xr − 1 ∈ F2 [x] are x − 1 and xr−1 + xr−2 + · · · 1. You may use the following steps:
1. Let p(x) be a monic irreducible factor of xr−1 + xr−2 + · · · + 1 and α a root of p(x) in
the algebraic closure. Show that r is the smallest positive integer such that αr = 1.
 n
2. Justify that the roots of p(x) are the elements of the set α(2 ) | n ∈ N≥1 .
 n
3. Show that α(2 ) | n ∈ N≥1 contains exactly r − 1 elements and conclude that p(x) =
xr−1 + xr−2 + · · · + 1.

7.1.4 Proposed Parameters for BIKE

We now present the proposed parameters for three levels of security, where again level 1 is
128 bits of security, level 3 is 192 bits, and level 5 is 256 bits of security. We also include an
estimate for the decoding failure rate (DFR) and key and ciphertext sizes in bytes.
It can be seen that BIKE has a small public key size, which is a big advantage over the
other systems.

7.1.5 HQC
The submission Hamming Quasi-Cyclic (HQC) is based on the quasi-cyclic framework (see
Section 3.4) and uses a combination of a decodable code of choice and circulant matrices.
The third round proposal suggests to use concatenated Reed-Muller and Reed-Solomon codes
(Definitions 65, 56, 27), in the initial NIST submission [4, Section 1.6] a tensor product code
of a BCH and a repetition code was proposed. An important feature of HQC is the fact that

92
 Security r w t Private key Public key Ciphertext DFR
Level 1 12323 142 134 281 1541 1573 2−128
Level 3 24659 206 199 419 3083 3115 2−192
Level 5 40973 274 264 580 5122 5154 2−256

Table 26: Parameters for BIKE

the used codes are not secret. We follow the NIST submission [5] for the detailed description.

Let n be such that (xn − 1)/(x − 1) is irreducible over F2 . We pick a positive integer
k < n and an [n, k] linear code C with an efficient decoding algorithm, whose error correcting
capacity
√ is given by t. We are further given error weights w, wr and we , all in the range of
n n
2 . We set R := F2 [x]/(x − 1). Recall that any element a ∈ R can be written as

a = λn−1 xn−1 + λn−2 xn−2 + . . . + λ0

for unique λ0 , λ1 , . . . , λn−1 ∈ F2 . For such an element we denote its Hamming weight as

wtH (a) = |{i ∈ {0, 1, . . . , n − 1} | λi 6= 0}|.

n
Pn−1alsoi that we can identify a vector a = (a0 , a1 , . . . , an−1 ) ∈ F2 with the element a =
Note
i=0 ai x ∈ R and vice versa. In the following description any bold letter, e.g. u, refers to
the associated vector in Fn2 of an element in R, e.g. u ∈ R.

• Key Generation: Given the parameters (n, k, t, w, we , wr ), choose a generator matrix

G of the code C and generate a random h ∈ R.

• Private Key: The private key is a randomly generated pair (y, z) ∈ R2 such that
wtH (y) = wtH (z) = w.

• Public Key: We compute s = y + hz ∈ R. The public key is given by (G, h, s, t).

• Encryption: We randomly generate an element e ∈ R such that wt(e) = we and a pair

(r1 , r2 ) ∈ R2 such that wtH (r1 ) = wtH (r2 ) = wr .
Let m ∈ Fk2 be the message, which gets encrypted as the pair c = (u, v) ∈ R2 , where
u = r1 + hr2 and v = mG + sr2 + e.

• Decryption: As mentioned in the quasi-cyclic framework, we compute that

v − uz = mG + (yr2 − r1 z + e).

The term yr2 − r1 z + e has Hamming weight ≤ t with high probability (this follows
non-trivially from the choice of the parameters). If this is the case, we can use the
decoding algorithm of C to recover the message m.

93
 Security n w wr = we Public key Private key Ciphertext DFR
Level 1 17669 66 75 2249 40 4481 2−128
Level 3 35851 100 114 4522 40 9026 2−192
Level 5 57637 131 149 7245 40 14469 2−256

Table 27: Parameters for HQC

7.1.6 Proposed Parameters for HQC

The following table contains the proposed parameters for HQC together with an upper es-
timate on the decoding failure rate (DFR) and ciphertext size and key sizes. The key and
ciphertext sizes are given in bytes and as before, security levels 1,3 and 5 correspond to
128-bit, 192-bit and 256-bit security respectively.
The advantages of HQC are its efficient implementation and its small key sizes. However,
HQC suffers from a low encryption rate.

Acknowledgement
The authors would like to thank Jean-Pierre Tillich, Nicolas Sendrier and Thomas Debris-
Alazard for fruitful discussions. The first author is supported by the Swiss National Science
Foundation grant number 195290.
The second and third author are supported by armasuisse Science and Technology (Project
Nr.: CYD C-2020010).

References
[1] M. Abdalla, J. H. An, M. Bellare, and C. Namprempre. From identification to signa-
tures via the Fiat-Shamir transform: Minimizing assumptions for security and forward-
security. In L. R. Knudsen, editor, Advances in Cryptology — EUROCRYPT 2002,
pages 418–433, Berlin, Heidelberg, 2002. Springer Berlin Heidelberg.

[2] C. Aguilar, P. Gaborit, and J. Schrek. A new zero-knowledge code based identification
scheme with reduced communication. In 2011 IEEE Information Theory Workshop,
pages 648–652. IEEE, 2011.

[3] C. Aguilar Melchor, N. Aragon, M. Bardet, S. Bettaieb, L. Bidoux, O. Blazy, J.-C.

Deneuville, P. Gaborit, A. Hauteville, A. Otmani, O. Ruatta, J.-P. Tillich, and G. Zémor.
ROLLO- Rank-Ouroboros, LAKE & LOCKER. NIST PQC Call for Proposals, 2020.
Round 2 Submission.

[4] C. Aguilar Melchor, N. Aragon, S. Bettaieb, L. Bidoux, O. Blazy, J.-C. Deneuville,

P. Gaborit, E. Persichetti, and G. Zémor. Hamming Quasi-Cyclic (HQC). NIST PQC
Call for Proposals, 2017. Round 1 Submission.

[5] C. Aguilar Melchor, N. Aragon, S. Bettaieb, L. Bidoux, O. Blazy, J. Bos, J.-C.

Deneuville, A. Dion, P. Gaborit, J. Lacan, E. Persichetti, J.-M. Robert, P. Véron, and

94
 G. Zémor. Hamming Quasi-Cyclic (HQC). NIST PQC Call for Proposals, 2020. Round
3 Submission.

[6] C. Aguilar Melchor, N. Aragon, S. Bettaieb, L. Bidoux, O. Blazy, M. Bros, A. Couvreur,

J.-C. Deneuville, P. Gaborit, A. Hauteville, and G. Zémor. Rank Quasi-Cyclic (RQC).
NIST PQC Call for Proposals, 2020. Round 2 Submission.

[7] C. Aguilar Melchor, N. Aragon, S. Bettaieb, L. Bidoux, O. Blazy, J.-C. Deneuville,

P. Gaborit, A. Hauteville, and G. Zémor. Ouroboros-R. NIST PQC Call for Proposals,
2017. Round 1 Submission.

[8] C. Aguilar-Melchor, O. Blazy, J.-C. Deneuville, P. Gaborit, and G. Zémor. Efficient

encryption from random quasi-cyclic codes. IEEE Transactions on Information Theory,
64(5):3927–3943, 2018.

[9] A. Al Jabri. A statistical decoding algorithm for general linear block codes. In IMA
International Conference on Cryptography and Coding, pages 1–8. Springer, 2001.

[10] M. Albrecht, C. Cid, K. G. Paterson, C. J. Tjhai, and M. Tomlinson. NTS-KEM -

Second round submission. NIST PQC Call for Proposals, 2019. Round 2 Submission.

[11] M. R. Albrecht, D. J. Bernstein, T. Chou, C. Cid, J. Gilcher, T. Lange, V. Maram,

I. von Maurich, R. Misoczki, R. Niederhagen, K. G. Paterson, E. Persichetti, C. Peters,
P. Schwabe, N. Sendrier, J. Szefer, C. J. Tjhai, M. Tomlinson, and W. Wang. Classic
McEliece: Conservative Code-Based Cryptography. NIST PQC Call for Proposals, 2020.
Round 3 Submission.

[12] M. Alekhnovich. More on average case vs approximation complexity. In 44th Annual

IEEE Symposium on Foundations of Computer Science, 2003. Proceedings., pages 298–
307, 2003.

[13] D. Apon, R. Perlner, A. Robinson, and P. Santini. Cryptanalysis of LEDAcrypt. Cryp-

tology ePrint Archive, Report 2020/455, 2020. https://ia.cr/2020/455.

[14] N. Aragon, M. Baldi, J.-C. Deneuville, K. Khathuria, E. Persichetti, and P. Santini.

Cryptanalysis of a code-based full-time signature. Designs, Codes and Cryptography,
89(9):2097–2112, 2021.

[15] N. Aragon, P. S. Barreto, S. Bettaieb, L. Bidoux, O. Blazy, J.-C. Deneuville, P. Ga-

borit, S. Ghosh, S. Gueron, T. Güneysu, C. A. Melchor, R. Misoczki, E. Persichetti,
N. Sendrier, J.-P. tillich, V. Vasseur, and G. Zémor. BIKE: Bit Flipping Key Encapsu-
lation. NIST PQC Call for Proposals, 2020. Round 3 Submission.

[16] N. Aragon, O. Blazy, J.-C. Deneuville, P. Gaborit, A. Hauteville, O. Ruatta, J.-P. Tillich,
and G. Zémor. LAKE - Low rAnk parity check codes Key Exchange. NIST PQC Call
for Proposals, 2017. Round 1 Submission.

[17] N. Aragon, O. Blazy, J.-C. Deneuville, P. Gaborit, A. Hauteville, O. Ruatta, J.-P. Tillich,
and G. Zémor. LOCKER - LOw rank parity Check codes EncRyption. NIST PQC Call
for Proposals, 2017. Round 1 Submission.

95
[18] N. Aragon, O. Blazy, P. Gaborit, A. Hauteville, and G. Zémor. Durandal: a rank
metric based signature scheme. In Annual International Conference on the Theory and
Applications of Cryptographic Techniques, pages 728–758. Springer, 2019.
[19] N. Aragon, P. Gaborit, A. Hauteville, O. Ruatta, and G. Zémor. RankSign - a signature
proposal for the NIST’s call. NIST PQC Call for Proposals, 2017. Round 1 Submission.
[20] N. Aragon, P. Gaborit, A. Hauteville, and J.-P. Tillich. Improvement of generic attacks
on the rank syndrome decoding problem. 2017.
[21] N. Aragon, P. Gaborit, A. Hauteville, and J.-P. Tillich. A new algorithm for solv-
ing the rank syndrome decoding problem. In 2018 IEEE International Symposium on
Information Theory (ISIT), pages 2421–2425. IEEE, 2018.
[22] A. Ashikhmin and A. Barg. Minimal vectors in linear codes. IEEE Transactions on
Information Theory, 44(5):2010–2017, 1998.
[23] D. Augot and M. Finiasz. A public key encryption scheme based on the polynomial
reconstruction problem. In International Conference on the Theory and Applications of
Cryptographic Techniques, pages 229–240. Springer, 2003.
[24] R. Avanzi, S. Hoerder, D. Page, and M. Tunstall. Side-channel attacks on the McEliece
and Niederreiter public-key cryptosystems. Journal of Cryptographic Engineering,
1(4):271–281, 2011.
[25] M. Baldi, A. Barenghi, F. Chiaraluce, G. Pelosi, and P. Santini. LEDAkem (low dEnsity
coDe-bAsed key encapsulation mechanism). NIST PQC Call for Proposals, 2017. Round
1 Submission.
[26] M. Baldi, A. Barenghi, F. Chiaraluce, G. Pelosi, and P. Santini. LEDApkc (low dEnsity
coDe-bAsed public-key cryptosystem. NIST PQC Call for Proposals, 2017. Round 1
Submission.
[27] M. Baldi, A. Barenghi, F. Chiaraluce, G. Pelosi, and P. Santini. LEDAcrypt: Low-
dEnsity parity-check coDe-bAsed cryptographic systems - version 3.0. NIST PQC Call
for Proposals, 2020. Round 2 Submission.
[28] M. Baldi, M. Battaglioni, F. Chiaraluce, A.-L. Horlemann-Trautmann, E. Persichetti,
P. Santini, and V. Weger. A new path to code-based signatures via identification schemes
with restricted errors. arXiv preprint arXiv:2008.06403, 2020.
[29] M. Baldi, M. Bianchi, F. Chiaraluce, J. Rosenthal, and D. Schipani. A variant of the
McEliece cryptosystem with increased public key security. In Proceedings of the Seventh
International Workshop on Coding and Cryptography, number 7, pages 173–182. HAL-
Inria, 2011.
[30] M. Baldi, M. Bianchi, F. Chiaraluce, J. Rosenthal, and D. Schipani. Using LDGM
codes and sparse syndromes to achieve digital signatures. In International Workshop on
Post-Quantum Cryptography, pages 1–15. Springer, 2013.
[31] M. Baldi, M. Bianchi, F. Chiaraluce, J. J. Rosenthal, D. Mose, et al. Method and
apparatus for public-key cryptography based on error correcting codes, Nov. 17 2015.
US Patent 9,191,199.

96
[32] M. Baldi, M. Bodrato, and F. Chiaraluce. A new analysis of the McEliece cryptosystem
based on QC-LDPC codes. In International Conference on Security and Cryptography
for Networks, pages 246–262. Springer, 2008.

[33] M. Baldi, F. Chiaraluce, J. Rosenthal, P. Santini, and D. Schipani. Security of gener-

alised Reed–Solomon code-based cryptosystems. IET Information Security, 13(4):404–
410, 2019.

[34] G. Banegas, P. S. L. M. Barreto, B. O. Boidje, P.-L. Cayrel, G. N. Dione, K. Gaj,

C. T. Gueye, R. Haeussler, J. B. Klamti, O. N’diaye, D. T. Nguyen, E. Persichetti, and
J. E. Ricardini. DAGS: Key Encapsulation from Dyadic GS Codes. NIST PQC Call for
Proposals, 2017. Round 1 Submission.

[35] M. Bardet, É. Barelli, O. Blazy, R. Canto-Torres, A. Couvreur, P. Gaborit, O. Ay-

oub, N. Sendrier, and J.-P. Tillich. BIG QUAKE: BInary Goppa QUAsi-cyclic Key
Encapsulation. NIST PQC Call for Proposals, 2017. Round 1 Submission.

[36] M. Bardet, P. Briaud, M. Bros, P. Gaborit, V. Neiger, O. Ruatta, and J. Tillich. An

algebraic attack on rank metric code-based cryptosystems. CoRR, abs/1910.00810, 2019.

[37] M. Bardet, M. Bros, D. Cabarcas, P. Gaborit, R. Perlner, D. Smith-Tone, J.-P. Tillich,

and J. Verbel. Improvements of algebraic attacks for solving the rank decoding and
MinRank problems. In International Conference on the Theory and Application of Cryp-
tology and Information Security, pages 507–536. Springer, 2020.

[38] V. Druagoi, V. Beiu, D. Bucerzan. Vulnerabilities of the McEliece variants based on

polar codes. In International Conference on Security for Information Technology and
Communications, pages 376–390, Springer, 2018.

[39] É. Barelli and A. Couvreur. An efficient structural attack on NIST submission DAGS.
In T. Peyrin and S. Galbraith, editors, Advances in Cryptology – ASIACRYPT 2018,
pages 93–118, Cham, 2018. Springer International Publishing.

[40] A. Barg, E. Krouk, and H. C. van Tilborg. On the complexity of minimum distance
decoding of long linear codes. IEEE Transactions on Information Theory, 45(5):1392–
1405, 1999.

[41] S. Barg. Some new NP-complete coding problems. Problemy Peredachi Informatsii,
30(3):23–28, 1994.

[42] S. Barg and G. .D. Forney. Random codes: Minimum distances and error exponents.
IEEE Transactions on Information Theory, 48(9): 2568-2573, 2002.

[43] P. S. Barreto, R. Misoczki, and M. A. Simplicio Jr. One-time signature scheme from
syndrome decoding over generic error-correcting codes. Journal of Systems and Software,
84(2):198–204, 2011.

[44] A. Becker, A. Joux, A. May, and A. Meurer. Decoding random binary linear codes
in 2n/20 : How 1 + 1 = 0 improves information set decoding. In Annual international
conference on the theory and applications of cryptographic techniques, pages 520–536.
Springer, 2012.

97
[45] P. Beelen, M. Bossert, S. Puchinger, and J. 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.
[46] E. Bellini, F. Caullery,P. Gaborit, M. Manzano and V. Mateu. Improved Veron identifi-
cation and signature schemes in the rank metric. In 2019 IEEE International Symposium
on Information Theory (ISIT), pages 1872–1876. IEEE, 2019.
[47] T. P. Berger, P. Gaborit, and O. Ruatta. Gabidulin matrix codes and their application
to small ciphertext size cryptosystems. In International Conference on Cryptology in
India, pages 247–266. Springer, 2017.
[48] T. P. Berger, C. T. Gueye, and J. B. Klamti. A NP-complete problem in coding theory
with application to code based cryptography. In International Conference on Codes,
Cryptology, and Information Security, pages 230–237. Springer, 2017.
[49] T. P. Berger, C. T. Gueye, and J. B. Klamti. Generalized subspace subcodes with
application in cryptology. IEEE Transactions on Information Theory, 65(8):4641–4657,
2019.
[50] T. P. Berger and P. Loidreau. How to mask the structure of codes for a cryptographic
use. Designs, Codes and Cryptography, 35:63–79, 2005.
[51] E. Berlekamp. Algebraic coding theory. World Scientific, 2015.
[52] E. Berlekamp, R. McEliece, and H. Van Tilborg. On the inherent intractability of certain
coding problems. IEEE Transactions on Information Theory, 24(3):384–386, 1978.
[53] D. J. Bernstein. Grover vs. McEliece. In International Workshop on Post-Quantum
Cryptography, pages 73–80. Springer, 2010.
[54] D. J. Bernstein, J. Buchmann, and E. Dahmen. Post-Quantum Cryptography. Springer-
Verlag, Berlin-Heidleberg, 2009.
[55] D. J. Bernstein, T. Lange, and C. Peters. Attacking and defending the McEliece cryp-
tosystem. In International Workshop on Post-Quantum Cryptography, pages 31–46.
Springer, 2008.
[56] D. J. Bernstein, T. Lange, and C. Peters. Wild McEliece. In International Workshop
on Selected Areas in Cryptography, pages 143–158. Springer, 2010.
[57] D. J. Bernstein, T. Lange, and C. Peters. Smaller decoding exponents: ball-collision
decoding. In Annual Cryptology Conference, pages 743–760. Springer, 2011.
[58] W. Beullens. Not enough LESS: An improved algorithm for solving code equivalence
problems over Fq . In International Conference on Selected Areas in Cryptography, pages
387–403. Springer, 2020.
[59] J.-F. Biasse, G. Micheli, E. Persichetti, and P. Santini. LESS is more: Code-based
signatures without syndromes. In International Conference on Cryptology in Africa,
pages 45–65. Springer, 2020.
[60] L. Bidoux, P. Gaborit, and N. Sendrier. Quasi-cyclic Stern proof of knowledge. arXiv
preprint arXiv:2110.05005, 2021.

98
[61] J. Bolkema, H. Gluesing-Luerssen, C. A. Kelley, K. E. Lauter, B. Malmskog, and
J. Rosenthal. Variations of the McEliece cryptosystem. In Algebraic geometry for coding
theory and cryptography, pages 129–150. Springer, 2017.
[62] M. Bombar and A. Couvreur. Decoding supercodes of Gabidulin codes and applications
to cryptanalysis. arXiv preprint arXiv:2103.02700, 2021.
[63] M. A. Borodin and I. V. Chizhov. Effective attack on the McEliece cryptosystem based
on Reed-Muller codes. Discrete Mathematics and Applications, 24(5):273–280, 2014.
[64] E. Byrne, A.-L. Horlemann, K. Khathuria, and V. Weger. Density of free modules over
finite chain rings. arXiv preprint arXiv:2106.09403, 2021.
[65] A. Canteaut and H. Chabanne. A further improvement of the work factor in an attempt
at breaking McEliece’s cryptosystem. PhD thesis, INRIA, 1994.
[66] A. Canteaut and F. Chabaud. A new algorithm for finding minimum-weight words in a
linear code: Application to McEliece’s cryptosystem and to narrow-sense BCH codes of
length 511. IEEE Transactions on Information Theory, 44(1):367–378, 1998.
[67] A. Canteaut and N. Sendrier. Cryptanalysis of the original McEliece cryptosystem. In
International conference on the theory and application of cryptology and information
security, pages 187–199. Springer, 1998.
[68] I. Cascudo, R. Cramer, D. Mirandola, and G. Zémor. Squares of random linear codes.
IEEE Transactions on Information Theory, 61(3):1159–1173, 2015.
[69] P.-L. Cayrel, C. T. Gueye, O. Ndiaye, and R. Niebuhr. Critical attacks in code-based
cryptography. International Journal of Information and Coding Theory, 3(2):158–176,
2015.
[70] P.-L. Cayrel, A. Otmani, and D. Vergnaud. On Kabatianskii-Krouk-Smeets signatures.
In International Workshop on the Arithmetic of Finite Fields, pages 237–251. Springer,
2007.
[71] P.-L. Cayrel, P. Véron, and S. M. E. Y. Alaoui. A zero-knowledge identification scheme
based on the q-ary syndrome decoding problem. In International Workshop on Selected
Areas in Cryptography, pages 171–186. Springer, 2010.
[72] F. Chabaud and J. Stern. The cryptographic security of the syndrome decoding problem
for rank distance codes. In International Conference on the Theory and Application of
Cryptology and Information Security, pages 368–381. Springer, 1996.
[73] C. Chen, T. Eisenbarth, I. Von Maurich, and R. Steinwandt. Differential power analysis
of a McEliece cryptosystem. In International Conference on Applied Cryptography and
Network Security, pages 538–556. Springer, 2015.
[74] L. Chen, L. Chen, S. Jordan, Y.-K. Liu, D. Moody, R. Peralta, R. Perlner, and D. Smith-
Tone. Report on post-quantum cryptography, volume 12. US Department of Commerce,
National Institute of Standards and Technology, 2016.
[75] J.-S. Coron. Cryptanalysis of a public-key encryption scheme based on the polynomial
reconstruction problem. In International Workshop on Public Key Cryptography, pages
14–27. Springer, 2004.

99
[76] N. T. Courtois, M. Finiasz, and N. Sendrier. How to achieve a McEliece-based dig-
ital signature scheme. In International Conference on the Theory and Application of
Cryptology and Information Security, pages 157–174. Springer, 2001.
[77] A. Couvreur, T. Debris-Alazard, and P. Gaborit. On the hardness of code equivalence
problems in rank metric. arXiv preprint arXiv:2011.04611, 2020.
[78] A. Couvreur, P. Gaborit, V. Gauthier-Umaña, A. Otmani, and J.-P. Tillich.
Distinguisher-based attacks on public-key cryptosystems using Reed–Solomon codes.
Designs, Codes and Cryptography, 73(2):641–666, 2014.
[79] A. Couvreur and M. Lequesne. On the security of subspace subcodes of Reed–Solomon
codes for public key encryption. IEEE Transactions on Information Theory, 2021.
[80] A. Couvreur, M. Lequesne, and J.-P. Tillich. Recovering short secret keys of RLCE in
polynomial time. In International Conference on Post-Quantum Cryptography, pages
133–152. Springer, 2019.
[81] A. Couvreur, I. Márquez-Corbella, and R. Pellikaan. A polynomial time attack against
algebraic geometry code based public key cryptosystems. In 2014 IEEE International
Symposium on Information Theory, pages 1446–1450. IEEE, 2014.
[82] A. Couvreur, I. Márquez-Corbella, and R. Pellikaan. Cryptanalysis of McEliece cryp-
tosystem based on algebraic geometry codes and their subcodes. IEEE Transactions on
Information Theory, 63(8):5404–5418, 2017.
[83] A. Couvreur, A. Otmani, and J.-P. Tillich. Polynomial time attack on wild McEliece
over quadratic extensions. IEEE Transactions on Information Theory, 63(1):404–427,
2016.
[84] A. Couvreur, A. Otmani, J.-P. Tillich, and V. Gauthier-Umana. A polynomial-time
attack on the BBCRS scheme. In IACR International Workshop on Public Key Cryp-
tography, pages 175–193. Springer, 2015.
[85] M. C. Davey and D. J. MacKay. Reliable communication over channels with insertions,
deletions, and substitutions. IEEE Transactions on Information Theory, 47(2):687–698,
2001.
[86] T. Debris-Alazard, N. Sendrier, and J.-P. Tillich. The problem with the SURF scheme.
arXiv preprint arXiv:1706.08065, 2017.
[87] T. Debris-Alazard, N. Sendrier, and J.-P. Tillich. Wave: A new family of trapdoor one-
way preimage sampleable functions based on codes. In International Conference on the
Theory and Application of Cryptology and Information Security, pages 21–51. Springer,
2019.
[88] T. Debris-Alazard and J.-P. Tillich. Two attacks on rank metric code-based schemes:
RankSign and an IBE scheme. In International Conference on the Theory and Applica-
tion of Cryptology and Information Security, pages 62–92. Springer, 2018.
[89] A. Chailloux, T. Debris-Alazard and S. Etinski. Classical and Quantum algorithms
for generic Syndrome Decoding problems and applications to the Lee metric. In arXiv
preprint arXiv:2104.12810, 2021.

100
[90] P. Delsarte. Bilinear forms over a finite field, with applications to coding theory. Journal
of combinatorial theory, Series A, 25(3):226–241, 1978.

[91] W. Diffie and M. Hellman. New directions in cryptography. IEEE transactions on

Information Theory, 22(6):644–654, 1976.

[92] J. Ding, J. E. Gower, and D. S. Schmidt. Multivariate public key cryptosystems, vol-
ume 25. Springer Science & Business Media, 2006.

[93] I. I. Dumer. Two decoding algorithms for linear codes. Problemy Peredachi Informatsii,
25(1):24–32, 1989.

[94] M. Elleuch, A. Wachter-Zeh, and A. Zeh. A public-key cryptosystem from interleaved

Goppa codes. arXiv preprint arXiv:1809.03024, 2018.

[95] J.-C. Faugère, V. Gauthier-Umaña, A. Otmani, L. Perret, and J.-P. Tillich. A dis-
tinguisher for high-rate McEliece cryptosystems. IEEE Transactions on Information
Theory, 59(10):6830–6844, 2013.

[96] C. Faure and P. Loidreau. A new public-key cryptosystem based on the problem of
reconstructing p–polynomials. In International Workshop on Coding and Cryptography,
pages 304–315. Springer, 2005.

[97] U. Feige, A. Fiat, and A. Shamir. Zero-knowledge proofs of identity. Journal of cryp-
tology, 1(2):77–94, 1988.

[98] M. Finiasz and N. Sendrier. Security bounds for the design of code-based cryptosys-
tems. In International Conference on the Theory and Application of Cryptology and
Information Security, pages 88–105. Springer, 2009.

[99] G. D. Forney. Concatenated codes. 1965.

[100] E. M. Gabidulin. Theory of codes with maximum rank distance. Problemy peredachi
informatsii, 21(1):3–16, 1985.

[101] E. M. Gabidulin, A. Paramonov, and O. Tretjakov. Ideals over a non-commutative ring

and their application in cryptology. In Workshop on the Theory and Application of of
Cryptographic Techniques, pages 482–489. Springer, 1991.

[102] P. Gaborit, G. Murat, O. Ruatta and G. Zémor. Low rank parity check codes and their
application to cryptography. Proceedings of the Workshop on Coding and Cryptography
WCC, 2013.

[103] P. Gaborit, A. Otmani, and H. T. Kalachi. Polynomial-time key recovery attack on the
Faure–Loidreau scheme based on Gabidulin codes. Designs, Codes and Cryptography,
86(7):1391–1403, 2018.

[104] P. Gaborit, O. Ruatta, and J. Schrek. On the complexity of the rank syndrome decoding
problem. IEEE Transactions on Information Theory, 62(2):1006–1019, 2015.

[105] P. Gaborit and J. Schrek. Efficient code-based one-time signature from automorphism
groups with syndrome compatibility. In 2012 IEEE International Symposium on Infor-
mation Theory Proceedings, pages 1982–1986. IEEE, 2012.

101
[106] P. Gaborit and G. Zémor. On the hardness of the decoding and the minimum distance
problems for rank codes. IEEE Transactions on Information Theory, 62(12):7245–7252,
2016.
[107] R. Gallager. Low-density parity-check codes. IRE Transactions on information theory,
8(1):21–28, 1962.
[108] L. Galvez, J.-L. Kim, M. J. Kim, Y.-S. Kim, and N. Lee. McNie: Compact McEliece-
Niederreiter Cryptosystem. NIST PQC Call for Proposals, 2017. Round 1 Submission.
[109] C. Gentry, C. Peikert, and V. Vaikuntanathan. Trapdoors for hard lattices and new
cryptographic constructions. In Proceedings of the fortieth annual ACM symposium on
Theory of computing, pages 197-206, 2008.
[110] E. Gilbert. A comparison of signalling alphabets. The Bell system technical journal,
31(3): 504-522, 1952.
[111] D. Gligoroski and K. Gjøsteen. Post-quantum Key Encapsulation Mechanism Edon-K.
NIST PQC Call for Proposals, 2017. Round 1 Submission.
[112] D. Gligoroski, S. Samardjiska, H. Jacobsen, and S. Bezzateev. McEliece in the world of
Escher. IACR Cryptol. ePrint Arch., 2014:360, 2014.
[113] V. Goppa. A new class of linear correcting codes. Problemy Peredachi Informatsii, 6(3):
24-30, 1970.
[114] V. Goppa. A Rational Representation of Codes and (L, g)-Codes. Problemy Peredachi
Informatsii, 7(3): 41-49, 1971.
[115] V. Goppa. Binary symmetric channel capacity is attained with irreducible codes. Prob-
lems of Information Transmission, 10: 89-90, 1974.
[116] E. Gorla. Rank-metric codes. arXiv preprint arXiv:1902.02650, 2019.
[117] L. K. Grover. A fast quantum mechanical algorithm for database search. In Proceedings
of the twenty-eighth annual ACM symposium on Theory of computing, pages 212–219,
1996.
[118] L. K. Grover. Quantum mechanics helps in searching for a needle in a haystack. Physical
review letters, 79(2):325, 1997.
[119] A. Gruica and A. Ravagnani. Common complements of linear subspaces and the sparse-
ness of MRD codes. arXiv preprint arXiv:2011.02993, 2020.
[120] C. T. Gueye, J. B. Klamti, and S. Hirose. Generalization of BJMM-ISD using May-
Ozerov nearest neighbor algorithm over an arbitrary finite field Fq . In International
Conference on Codes, Cryptology, and Information Security, pages 96–109. Springer,
2017.
[121] V. Guruswami and E. Blais. Introduction to Coding Theory, Notes 6: Reed-Solomon,
BCH, Reed-Muller, and concatenated codes. February 2010. Lecture Notes.
[122] A. Herzberg and D. Naor. Surf ‘N’Sign: Client signatures on web documents. IBM
Systems Journal, 37(1):61–71, 1998.

102
[123] S. Hirose. May-Ozerov algorithm for nearest-neighbor problem over Fq and its applica-
tion to information set decoding. In International Conference for Information Technol-
ogy and Communications, pages 115–126. Springer, 2016.

[124] A.-L. Horlemann, S. Puchinger, J. Renner, T. Schamberger, and A. Wachter-Zeh.

Information-set decoding with hints. Technical report, Cryptology ePrint Archive, Re-
port 2021/279. https://eprint. iacr. org/2021/279, 2021.

[125] A.-L. Horlemann-Trautmann, K. Marshall, and J. Rosenthal. Extension of Overbeck’s

attack for Gabidulin-based cryptosystems. Designs, Codes and Cryptography, 86(2):319–
340, 2018.

[126] A. L. Horlemann-Trautmann, V. Weger. Information set decoding in the Lee metric

with applications to cryptography. In Advances in Mathematics of Communications,
15(4): 677-699, 2021.

[127] N. Howgrave-Graham and A. Joux. New generic algorithms for hard knapsacks. In An-
nual International Conference on the Theory and Applications of Cryptographic Tech-
niques, pages 235–256. Springer, 2010.

[128] C. Interlando, K. Khathuria, N. Rohrer, J. Rosenthal, and V. Weger. Generalization of

the ball-collision algorithm. Journal of Algebra Combinatorics Discrete Structures and
Applications, 7(2):195–207, 2020.

[129] F. Ivanov, G. Kabatiansky, E. Krouk, and N. Rumenko. A new code-based cryptosys-

tem. In Code-Based Cryptography Workshop, pages 41–49. Springer, 2020.

[130] H. Janwa and O. Moreno. McEliece public key cryptosystems using algebraic-geometric
codes. Designs, Codes and Cryptography, 8(3):293–307, 1996.

[131] D. Jao and L. De Feo. Towards quantum-resistant cryptosystems from supersingular

elliptic curve isogenies. In International Workshop on Post-Quantum Cryptography,
pages 19–34. Springer, 2011.

[132] G. Kabatianskii, E. Krouk, and B. Smeets. A digital signature scheme based on random
error-correcting codes. In IMA International Conference on Cryptography and Coding,
pages 161–167. Springer, 1997.

[133] G. Kabatiansky, E. Krouk, and S. Semenov. Error correcting coding and security for
data networks: analysis of the superchannel concept. John Wiley & Sons, 2005.

[134] H. Kamabe and S. Kobota. Simple improvements of bit-flipping decoding. In 2010

The 12th International Conference on Advanced Communication Technology (ICACT),
volume 1, pages 113–118. IEEE, 2010.

[135] K. Khathuria, J. Rosenthal, and V. Weger. Encryption scheme based on expanded

Reed-Solomon codes. Advances in Mathematics of Communications, 15(2):207, 2021.

[136] K. Khaturia, J. Rosenthal, and V. Weger. Weight two masking of the Reed-Solomon
structure in conjunction with list decoding. Proceedings of 23rd International Symposium
on MathematicalTheory of Networks and Systems, pages 309—-314, 2018.

103
[137] K. Kobara and H. Imai. Semantically secure McEliece public-key cryptosystems-
conversions for McEliece PKC. In International Workshop on Public Key Cryptography,
pages 19–35. Springer, 2001.

[138] E. A. Kruk. Decoding complexity bound for linear block codes. Problemy Peredachi
Informatsii, 25(3):103–107, 1989.

[139] A. Kshevetskiy and E. Gabidulin. The new construction of rank codes. In Proceedings.
International Symposium on Information Theory, 2005. ISIT 2005., pages 2105–2108.
IEEE, 2005.

[140] G. Landais and J.-P. Tillich. An efficient attack of a McEliece cryptosystem variant
based on convolutional codes. In International Workshop on Post-Quantum Cryptogra-
phy, pages 102–117. Springer, 2013.

[141] T. S. C. Lau and C. H. Tan. Key recovery attack on McNie based on low rank parity
check codes and its reparation. In A. Inomata and K. Yasuda, editors, Advances in
Information and Computer Security, pages 19–34, Cham, 2018. Springer International
Publishing.

[142] T. S. C. Lau and C. H. Tan. MURAVE: A new rank code-based signature with multiple
rank verification. In Code-Based Cryptography Workshop, pages 94–116. Springer, 2020.

[143] T. S. C. Lau and C. H. Tan. Polynomial-time plaintext recovery attacks on the IKKR
code-based cryptosystems. Advances in Mathematics of Communications, 2021.

[144] J. Lavauzelle, P. Loidreau, and B.-D. Pham. RAMESSES, a rank metric encryption
scheme with short keys. arXiv preprint arXiv:1911.13119, 2019.

[145] J. Lavauzelle and J. Renner. Cryptanalysis of a system based on twisted Reed–Solomon

codes. Designs, Codes and Cryptography, 88(7):1285–1300, 2020.

[146] P. J. Lee and E. F. Brickell. An observation on the security of McEliece’s public-

key cryptosystem. In Workshop on the Theory and Application of of Cryptographic
Techniques, pages 275–280. Springer, 1988.

[147] W. Lee, Y.-S. Kim, Y.-W. Lee, and J.-S. No. pqsigRM - Post quantum signature scheme
based on modified Reed-Muller code. NIST PQC Call for Proposals, 2017. Round 1
Submission.

[148] Y. Lee, W. Lee, Y. S. Kim, and J.-S. No. Modified pqsigRM: RM Code-Based Signature
Scheme. IEEE Access, 8:177506–177518, 2020.

[149] J. S. Leon. A probabilistic algorithm for computing minimum weights of large error-
correcting codes. IEEE Transactions on Information Theory, 34(5):1354–1359, 1988.

[150] M. Lequesne and J. Tillich. Attack on the Edon-K key encapsulation mechanism. CoRR,
abs/1802.06157, 2018.

[151] Y. X. Li, R. H. Deng, and X. M. Wang. On the Equivalence of McEliece’s and Niederre-
iter’s Public-Key Cryptosystems. IEEE Transactions on Information Theory, 40(1):271–
273, 1994.

104
[152] P. Loidreau. Designing a rank metric based McEliece cryptosystem. In International
Workshop on Post-Quantum Cryptography, pages 142–152. Springer, 2010.

[153] P. Loidreau and R. Overbeck. Decoding rank errors beyond the error-correcting capa-
bility. In ACCT 2010, Tenth international workshop on Algebraic and Combinatorial
Coding Theory, 2006.

[154] C. Löndahl and T. Johansson. A new version of McEliece PKC based on convolutional
codes. In International Conference on Information and Communications Security, pages
461–470. Springer, 2012.

[155] F. J. MacWilliams and N. J. A. Sloane. The theory of error correcting codes. Elsevier,
Volume 16, 1977.

[156] T. Magloire, N. Ngatched, M. Bossert, A. Fahrner, and F. Takawira. Two bit-flipping

decoding algorithms for low-density parity-check codes. IEEE transactions on commu-
nications, 57(3):591–596, 2009.

[157] I. Márquez-Corbella and J.-P. Tillich. Using Reed-Solomon codes in the (u|u + v) con-
struction and an application to cryptography. In 2016 IEEE International Symposium
on Information Theory (ISIT), pages 930–934. IEEE, 2016.

[158] A. May, A. Meurer, and E. Thomae. Decoding random linear codes in ˜≀(20.054n ). In
International Conference on the Theory and Application of Cryptology and Information
Security, pages 107–124. Springer, 2011.

[159] A. May and I. Ozerov. On computing nearest neighbors with applications to decoding of
binary linear codes. In Annual International Conference on the Theory and Applications
of Cryptographic Techniques, pages 203–228. Springer, 2015.

[160] R. J. McEliece. A public-key cryptosystem based On algebraic coding theory. Deep

Space Network Progress Report, 44:114–116, Jan. 1978.

[161] A. Meurer. A coding-theoretic approach to cryptanalysis. PhD thesis, Ruhr-Universität

Bochum, 2012.

[162] L. Minder and A. Shokrollahi. Cryptanalysis of the Sidelnikov cryptosystem. In Annual

International Conference on the Theory and Applications of Cryptographic Techniques,
pages 347–360. Springer, 2007.

[163] R. Misoczki, J.-P. Tillich, N. Sendrier, and P. S. Barreto. MDPC-McEliece: New

McEliece variants from moderate density parity-check codes. In 2013 IEEE international
symposium on information theory, pages 2069–2073. IEEE, 2013.

[164] C. Monico, J. Rosenthal, and A. Shokrollahi. Using low density parity check codes in
the McEliece cryptosystem. In Proceedings of the 2000 IEEE International Symposium
on Information Theory, page 214, Sorrento, Italy, 2000.

[165] D. Moody and R. Perlner. Vulnerabilities of “McEliece in the world of Escher”. In

Post-Quantum Cryptography, pages 104–117. Springer, 2016.

[166] E. Moore. A two-fold generalization of Fermat’s theorem. Bulletin of the American

Mathematical Society, 2(7): 189-199, 1896.

105
[167] D. E. Muller. Application of Boolean algebra to switching circuit design and to error
detection. Transactions of the I.R.E. Professional Group on Electronic Computers, EC-
3(3):6–12, 1954.
[168] A. Neri, A.-L. Horlemann-Trautmann, T. Randrianarisoa, and J. Rosenthal. On the
genericity of maximum rank distance and Gabidulin codes. Designs, Codes and Cryp-
tography, 86(2):341–363, 2018.
[169] R. Niebuhr, E. Persichetti, P.-L. Cayrel, S. Bulygin, and J. Buchmann. On lower bounds
for information set decoding over Fq and on the effect of partial knowledge. International
journal of information and Coding Theory, 4(1):47–78, 2017.
[170] H. Niederreiter. Knapsack-type cryptosystems and algebraic coding theory. Problems
of Control and Information Theory 15, 1(6):159–166, 1986.
[171] S. Ouzan and Y. Be’ery. Moderate-density parity-check codes. arXiv preprint
arXiv:0911.3262, 2009.
[172] A. Otmani and J.-P. Tillich. An efficient attack on all concrete KKS proposals. In
International Workshop on Post-Quantum Cryptography, pages 98–116. Springer, 2011.
[173] A. Otmani, J.-P. Tillich, and L. Dallot. Cryptanalysis of two McEliece cryptosystems
based on quasi-cyclic codes. Mathematics in Computer Science, 3(2):129–140, 2010.
[174] A. V. Ourivski and T. Johansson. New technique for decoding codes in the rank metric
and its cryptography applications. Problems of Information Transmission, 38(3):237–
246, 2002.
[175] R. Overbeck. Structural attacks for public key cryptosystems based on Gabidulin codes.
Journal of cryptology, 21(2):280–301, 2008.
[176] C. Peikert. A decade of lattice cryptography. Cryptology ePrint Archive, 2015.
[177] E. Persichetti. Efficient one-time signatures from quasi-cyclic codes: A full treatment.
Cryptography, 2(4):30, 2018.
[178] C. Peters. Information-set decoding for linear codes over Fq . In International Workshop
on Post-Quantum Cryptography, pages 81–94. Springer, 2010.
[179] E. Petrank and R. M. Roth. Is code equivalence easy to decide? IEEE Transactions
on Information Theory, 43(5):1602–1604, 1997.
[180] A. Phesso and J.-P. Tillich. An efficient attack on a code-based signature scheme. In
Post-Quantum Cryptography, pages 86–103. Springer, 2016.
[181] J. Pierce. Limit distribution of the minimum distance of random linear codes. IEEE
Transactions on Information Theory, 13(4): 595-599, 1967.
[182] E. Prange. The use of information sets in decoding cyclic codes. IRE Transactions on
Information Theory, 8(5):5–9, 1962.
[183] S. Puchinger, S. Müelich, K. Ishak, and M. Bossert. Code-based cryptosystems using
generalized concatenated codes. In Special Sessions in Applications of Computer Algebra,
pages 397–423. Springer, 2015.

106
[184] S. Puchinger, J. Renner, and J. Rosenkilde. Generic decoding in the sum-rank metric.
In 2020 IEEE International Symposium on Information Theory (ISIT), pages 54-59,
2020.

[185] S. Puchinger, J. Renner, and A. Wachter-Zeh. Twisted Gabidulin codes in the GPT
cryptosystem. arXiv preprint arXiv:1806.10055, 2018.

[186] H. Rashwan, E. M. Gabidulin, and B. Honary. A smart approach for GPT cryptosystem
based on rank codes. In 2010 IEEE International Symposium on Information Theory,
pages 2463–2467. IEEE, 2010.

[187] I. Reed. A class of multiple-error-correcting codes and the decoding scheme. Transac-
tions of the IRE Professional Group on Information Theory, 4(4):38–49, 1954.

[188] 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.

[189] J. Renner, S. Puchinger, and A. Wachter-Zeh. Interleaving Loidreau’s rank-metric

cryptosystem. In 2019 XVI International Symposium” Problems of Redundancy in In-
formation and Control Systems”(REDUNDANCY), pages 127–132. IEEE, 2019.

[190] J. Renner, S. Puchinger, and A. Wachter-Zeh. LIGA: a cryptosystem based on the

hardness of rank-metric list and interleaved decoding. Designs, Codes and Cryptography,
89(6):1279–1319, 2021.

[191] T. Richmond, M. Petrvalsky, and M. Drutarovsky. A side-channel attack against the

secret permutation on an embedded McEliece cryptosystem. In 3rd Workshop on Trust-
worthy Manufacturing and Utilization of Secure Devices-TRUDEVICE, 2015.

[192] R. L. Rivest, A. Shamir, and L. Adleman. A method for obtaining digital signatures
and public-key cryptosystems. Communications of the ACM, 21(2):120–126, 1978.

[193] R. M. Roth. Introduction to coding theory. IET Communications, 47, 2006.

[194] R. Roth. Maximum-rank array codes and their application to crisscross error correction.
IEEE transactions on Information Theory, 37(2):328–336, 1991.

[195] P. S. Roy, R. Xu, K. Fukushima, S. Kiyomoto, K. Morozov, and T. Takagi. Supporting

Documentation of RaCoSS (Random Code-based Signature Scheme). NIST PQC Call
for Proposals, 2017. Round 1 Submission.

[196] G. Sacks. Multiple error correction by means of parity checks. IRE transactions on
information theory, 4(4): 145-147, 1958.

[197] P. Santini, M. Baldi, and F. Chiaraluce. Cryptanalysis of a one-time code-based dig-

ital signature scheme. In 2019 IEEE International Symposium on Information Theory
(ISIT), pages 2594–2598. IEEE, 2019.

[198] N. Sendrier. On the structure of randomly permuted concatenated code. PhD thesis,
INRIA, 1995.

[199] N. Sendrier. On the concatenated structure of a linear code. Applicable Algebra in

Engineering, Communication and Computing, 9(3):221–242, 1998.

107
[200] N. Sendrier and D. E. Simos. The hardness of code equivalence over Fq and its ap-
plication to code-based cryptography. In International Workshop on Post-Quantum
Cryptography, pages 203–216. Springer, 2013.

[201] P. Shor. Algorithms for quantum computation: discrete logarithms and factoring. In
Proceedings 35th Annual Symposium on Foundations of Computer Science, pages 124–
134, 1994.

[202] V. Shoup. A proposal for an ISO standard for public key encryption. In IACR e-Print
Archive, 2001.

[203] S. R. Shrestha and Y.-S. Kim. New McEliece cryptosystem based on polar codes as
a candidate for post-quantum cryptography. In 2014 14th International Symposium on
Communications and Information Technologies (ISCIT), pages 368–372. IEEE, 2014.

[204] V. M. Sidelnikov. A public-key cryptosystem based on binary Reed-Muller codes. Dis-

crete Mathematics and Applications, 4(3):191–208, 1994.

[205] V. M. Sidel’nikov and S. O. Shestakov. On an encoding system constructed on the basis

of generalized Reed–Solomon codes. Diskretnaya Matematika, 4(3):57–63, 1992.

[206] R. Singleton. Maximum distance q-nary codes. IEEE Transactions on Information

Theory, 10(2): 116-118, 1964.

[207] Y. Song, X. Huang, Y. Mu, W. Wu, and H. Wang. A code-based signature scheme from
the Lyubashevsky framework. Theoretical Computer Science, 835:15–30, 2020.

[208] J. Stern. A method for finding codewords of small weight. In International Colloquium
on Coding Theory and Applications, pages 106–113. Springer, 1988.

[209] J. Stern. A new identification scheme based on syndrome decoding. In Annual Inter-
national Cryptology Conference, pages 13–21. Springer, 1993.

[210] F. Strenzke. A timing attack against the secret permutation in the McEliece PKC. In
International Workshop on Post-Quantum Cryptography, pages 95–107. Springer, 2010.

[211] F. Strenzke, E. Tews, H. G. Molter, R. Overbeck, and A. Shoufan. Side channels in

the McEliece PKC. In International Workshop on Post-Quantum Cryptography, pages
216–229. Springer, 2008.

[212] A. Szepieniec. Ramstake - KEM Proposal for NIST PQC Project. NIST PQC Call for
Proposals, 2017. Round 1 Submission.

[213] M. Tiepelt and J.-P. D’Anvers. Exploiting decryption failures in Mersenne number
cryptosystems. pages 45–54, 2020.

[214] J. H. Van Lint. Introduction to coding theory. Springer Science & Business Media,
Volume 86, 2012.

[215] J. van Tilburg. On the McEliece public-key cryptosystem. In Conference on the Theory
and Application of Cryptography, pages 119–131. Springer, 1988.

108
[216] A. Vardy. Algorithmic complexity in coding theory and the minimum distance problem.
In Proceedings of the twenty-ninth annual ACM symposium on Theory of computing,
pages 92–109, 1997.

[217] R. Varshamov. Estimate of the number of signals in error correcting codes. Docklady
Akad. Nauk, SSSR, 117: 739-741, 1957.

[218] P. Véron. Improved Identification Schemes Based on Error-Correcting Codes. In Ap-

plicable Algebra in Engineering, Communication and Computing, 8(1), 1997.

[219] A. Wachter-Zeh, S. Puchinger, and J. Renner. Repairing the Faure-Loidreau public-key

cryptosystem. In 2018 IEEE International Symposium on Information Theory (ISIT),
pages 2426–2430. IEEE, 2018.

[220] T. Wadayama, K. Nakamura, M. Yagita, Y. Funahashi, S. Usami, and I. Takumi.

Gradient descent bit flipping algorithms for decoding LDPC codes. In 2008 International
Symposium on Information Theory and Its Applications, pages 1–6. IEEE, 2008.

[221] Y. Wang. RLCE Key Encapsulation Mechanism (RLCE-KEM) Specification. NIST

PQC Call for Proposals, 2017. Round 1 Submission.

[222] V. Weger. Information Set Decoding in the Lee Metric and the Local to Global Principle
for Densities. PhD thesis, University of Zurich, 2020.

[223] V. Weger, K. Khathuria, A.-L. Horlemann, M. Battaglioni, P. Santini, and E. Per-

sichetti. On the hardness of the Lee syndrome decoding problem. arXiv preprint
arXiv:2002.12785, 2020.

[224] C. Wieschebrink. Two NP-complete problems in coding theory with an application

in code based cryptography. In 2006 IEEE International Symposium on Information
Theory, pages 1733–1737. IEEE, 2006.

[225] C. Wieschebrink. Cryptanalysis of the Niederreiter public key scheme based on GRS
subcodes. volume 6061, pages 61–72, 05 2010.

[226] K. Xagawa. Practical attack on RaCoSS-r. 2018.

[227] A. Yamada, E. Eaton, K. Kalach, P. Lafrance, and A. Parent. QC-MDPC KEM: A

Key Encapsulation Mechanism Based on the QC-MDPC McEliece Encryption Scheme.
NIST PQC Call for Proposals, 2017. Round 1 Submission.

[228] Y. Yu and J. Zhang. Lepton: Key Encapsulation Mechanisms from a variant of Learning
Parity with Noise. NIST PQC Call for Proposals, 2017. Round 1 Submission.

[229] G. Zémor. Notes on Alekhnovich’s cryptosystems. 2016.

109