Cryptanalysis techniques in algebraic code–based
cryptography
Alain Couvreur1,2
1 INRIA
2 LIX, École polytechnique

Nutmic 2019

A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 20191 / 801

History of code–based cryptography

2

Algebraic cryptanalysis in code–based cryptography

3

How to design secure schemes with codes?

A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 20192 / 80Prerequisites on error correcting codes

Prerequisites on error correcting codes
A linear code is a vector subspace C ⊆ Fnq :n is its length;

A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 20193 / 80Prerequisites on error correcting codes

Prerequisites on error correcting codes
A linear code is a vector subspace C ⊆ Fnq :n is its length;k is its dimension as an Fq –vector space;

A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 20193 / 80Prerequisites on error correcting codes

Prerequisites on error correcting codes
A linear code is a vector subspace C ⊆ Fnq :n is its length;k is its dimension as an Fq –vector space;
A t–decoder for C is an algorithm D taking as input x ∈ Fnq andreturning:• c ∈ C such that dH (x, c) 6 t if exists.
• “?” else.

A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 20193 / 80Prerequisites on error correcting codes

Prerequisites on error correcting codes
A linear code is a vector subspace C ⊆ Fnq :n is its length;k is its dimension as an Fq –vector space;
A t–decoder for C is an algorithm D taking as input x ∈ Fnq andreturning:• c ∈ C such that dH (x, c) 6 t if exists.
• “?” else.

Definition 1
The Hamming distance on Fnq is defined by:def

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

A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 20193 / 80Prerequisites on error correcting codes

A classical operation

Definition 2
Let C ⊆ Fnqm be a code. Its subfield subcode is defined by:
C ∩ Fnq .
Very classical operation. Many algebraic codes derive from generalised
Reed–Solomon codes using this operation: Goppa codes, BCH codes,
Srivastava codes, etc...

A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 20194 / 80History of code–based cryptography

1

History of code–based cryptography

2

Algebraic cryptanalysis in code–based cryptography

3

How to design secure schemes with codes?

A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 20195 / 80History of code–based cryptography

It starts with two articles[1] E.R. Berlekamp, R.J. McEliece and H.C.A. Van Tilborg. On theinherent intractability of certain coding problems. IEEE Trans. Inform.
Theory 24(2), 1978.
[2] R.J. McEliece. A public key cryptosystem based on algebraic coding
theory. DSN Progress Report 44; 1978.

A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 20196 / 80History of code–based cryptography

It starts with two articles[1] E.R. Berlekamp, R.J. McEliece and H.C.A. Van Tilborg. On theinherent intractability of certain coding problems. IEEE Trans. Inform.
Theory 24(2), 1978.
[2] R.J. McEliece. A public key cryptosystem based on algebraic coding
theory. DSN Progress Report 44; 1978.
In the article [1]:Theorem 1
The following problem is NP–complete:
Bounded decoding problem. Given C ⊆ Fnq , y ∈ Fnq and t > 0.
Does there exist c ∈ C such thatdH (c, y ) 6 t?
A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 20196 / 80History of code–based cryptography

It starts with two articles[1] E.R. Berlekamp, R.J. McEliece and H.C.A. Van Tilborg. On theinherent intractability of certain coding problems. IEEE Trans. Inform.
Theory 24(2), 1978.
[2] R.J. McEliece. A public key cryptosystem based on algebraic coding
theory. DSN Progress Report 44; 1978.
In the article [2], McEliece proposes a new public key encryption
scheme.

A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 20197 / 80History of code–based cryptography

McEliece presented in the literature

Secret key.
G , a structured k × n matrix whose rows span a code C ;S ∈ GLk ;P ∈ Sn .

Public key. (SG P, t);

Encryption m 7→ mSG P + e for a uniformly random e of weight t;
Decryption
Right multiply by P −1 : mSG P + e 7−→ mSG + eP −1 ;decode to get mS;
right multiply it by S −1 to get m.

A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 20198 / 80History of code–based cryptography

This is what McEliece said!

A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 20199 / 80History of code–based cryptography

This is what McEliece said!

A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 201910 / 80

History of code–based cryptography

But... may be we should present it differently
F denotes a family of codes of length n and dimension k;

S denotes a set “of secrets” with a surjective map C : S −→ F
sending a secret s ∈ S into a code C (s).

To any s ∈ S is associated a decoding algorithm D(s) for C (s)correcting up to t errors.
Secret key s ∈ S;

Public key (G , t), where G denotes a k × n generator matrix of C (s);Encryption m ∈ Fkq 7−→ mG + e where e is a uniformly random word ofweight t.
Decryption Apply D(s) to mG + e to recover m.

A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 201911 / 80

History of code–based cryptography

Example – Generalised Reed Solomon codes

Definition 2 (Generalised Reed–Solomon codes)
Let n, k be positive integers k 6 n. Let x = (x1 , . . . , xn ) ∈ Fnq be a vectornwith distinct entries and y = (y1 , . . . , yn ) ∈ (F×
q) .
def

GRSk (x, y ) = {(y1 f (x1 ), . . . , yn f (xn )) | deg(f ) < k} .
F the set of [n, k] GRS codes;nS = {(x, y ) ∈ Fnq × (F×q ) | ∀i 6= j, xi 6= xj };D(s) is your favorite decoder for GRS, e.g. Berlekamp Welchalgorithm, with t = b n−k
2 c·

A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 201912 / 80

History of code–based cryptography

Example – Alternant codes
Definition 3 (Alternant codes)
Let x = (x1 , . . . , xn ) ∈ Fnqm be a vector with distinct entries andny = (y1 , . . . , yn ) ∈ (F×q m ) . An alternant code of degree r is a code of theform
Ar (x, y ) = GRSr (x, y )⊥ ∩ Fnq

A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 201913 / 80

History of code–based cryptography

Example – Alternant codes
Definition 3 (Alternant codes)
Let x = (x1 , . . . , xn ) ∈ Fnqm be a vector with distinct entries andny = (y1 , . . . , yn ) ∈ (F×q m ) . An alternant code of degree r is a code of theform
Ar (x, y ) = GRSr (x, y )⊥ ∩ Fnq= GRSn−r (x, y ⊥ ) ∩ Fnq

F the set of alternant codes of length n and degree r ;n
S = {(x, y ) ∈ Fnq × (F×q ) | ∀i 6= j, xi 6= xj };D(s) is your favorite decoder for alternant codes, e.g. Berlekamp
Welch algorithm.
A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 201913 / 80

History of code–based cryptography

Example – Alternant codes
Definition 3 (Alternant codes)
Let x = (x1 , . . . , xn ) ∈ Fnqm be a vector with distinct entries andny = (y1 , . . . , yn ) ∈ (F×q m ) . An alternant code of degree r is a code of theform
Ar (x, y ) = GRSr (x, y )⊥ ∩ Fnq= GRSn−r (x, y ⊥ ) ∩ Fnq

F the set of alternant codes of length n and degree r ;n
S = {(x, y ) ∈ Fnq × (F×q ) | ∀i 6= j, xi 6= xj };D(s) is your favorite decoder for alternant codes, e.g. Berlekamp
Welch algorithm.
A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 201913 / 80

History of code–based cryptography

Example – Classical Goppa codes – McEliece (1978)

Definition 4 (Classical Goppa codes)
Let x = (x1 , . . . , xn ) ∈ Fnqm be a vector with distinct entries andg ∈ Fqm [x]<t be a polynomial such that ∀i, g (xi ) 6= 0. The Goppa code
associated to (x, g ) is defined asdef

G (x, g ) = Adeg g (x, g (x)−1 ) ∩ Fnq
where g (x)−1 = (g (x1 )−1 , . . . , g (xn )−1 )S = {(x, g ) | · · · };etc...

A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 201914 / 80

History of code–based cryptography

Example – Classical Goppa codes – McEliece (1978)

Definition 4 (Classical Goppa codes)
Let x = (x1 , . . . , xn ) ∈ Fnqm be a vector with distinct entries andg ∈ Fqm [x]<t be a polynomial such that ∀i, g (xi ) 6= 0. The Goppa code
associated to (x, g ) is defined asdef

G (x, g ) = Adeg g (x, g (x)−1 ) ∩ Fnq
where g (x)−1 = (g (x1 )−1 , . . . , g (xn )−1 )S = {(x, g ) | · · · };etc...

A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 201914 / 80

History of code–based cryptography

Example – MDPC codes
Definition 5 (QC-MDPC codes)
Let n be a positive even integer and f , g ∈ F2 [X ]<n be two polynomials of√
weight in O( n). A [2n, n] QC-MDPC code is the kernel of the sparse
matrix
f0
f1 · · · fn−1
g0
g1 · · · gn−1
 fn−1 f0 · · · fn−2 gn−1 g0 · · · gn−2 


..
..
.. ..
.. ..
.
.
.
.
.
.
F the set of [2n, n] MDPC, codes√
S = {(f , g ) ∈ Fq [x]<n of weight O( n)};D(s) is your favorite decoder for MDPC codes, e.g. Bit Flipping
algorithm.
A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 201915 / 80

History of code–based cryptography

Example – Algebraic geometry codes

Definition 6 (Algebraic geometry codes)
Let X be a smooth projective geometrically connected curve over Fq , G be
a divisor on X and P = (P1 , . . . , Pn ) be a set of Fq –points of X . We definedef

CL (X , P, G ) = {(f (P1 ), . . . , f (Pn )) | f ∈ L(G )}.
F the set of AG codes of length n from X .

S = {(P, G ) ∈ X (Fq )n × DivFq (X ) | ∀i 6= j, Pi 6= Pj };D(s) is your favorite decoder for AG codes, e.g. Error Correcting Pairs
algorithm.

A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 201916 / 80

History of code–based cryptography

History – McEliece 1978

1978 : McEliece’s original proposal based on binary Goppa codes(special case of alternant codes). Public key : 32kB for ≈ 65 bits of
security1 .
2018 : NIST proposals :Classic McEliece, public key 1 to 1.3 MByte for > 256 bits security.
NTS KEM, 319 KBytes for > 128 bits security.

1

With respect to Prange algorithm
A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 201917 / 80

History of code–based cryptography

History – McEliece 1978

1978 : McEliece’s original proposal based on binary Goppa codes(special case of alternant codes). Public key : 32kB for ≈ 65 bits of
security1 .
2018 : NIST proposals :Classic McEliece, public key 1 to 1.3 MByte for > 256 bits security.
NTS KEM, 319 KBytes for > 128 bits security.

During these 40 years many attempts to get shorter keys.

1

With respect to Prange algorithm
A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 201917 / 80

History of code–based cryptography

History – McEliece 1978

1978 : McEliece’s original proposal based on binary Goppa codes(special case of alternant codes). Public key : 32kB for ≈ 65 bits of
security1 .
2018 : NIST proposals :Classic McEliece, public key 1 to 1.3 MByte for > 256 bits security.
NTS KEM, 319 KBytes for > 128 bits security.

During these 40 years many attempts to get shorter keys. How?

1

With respect to Prange algorithm
A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 201917 / 80

History of code–based cryptography

Idea 1 : Reducing the extension degree

GRSk (x, y )

Fqm
m

Fq

GRSk (x, y ) ∩ Fnq

Fact. The larger the m the worse the parameters. But:

A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 201918 / 80

History of code–based cryptography

Idea 1 : Reducing the extension degree

GRSk (x, y )

Fqm
m

Fq

GRSk (x, y ) ∩ Fnq

Fact. The larger the m the worse the parameters. But:
Case m = 1 is broken (Sidelnikov, Shestakov 1992);
Some specific cases of m = 2 and 3 called wild Goppa codes arebroken too:C., Otmani, Tillich, 2014;
Faugère, Perret, de Portzamparc, 2014
A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 201918 / 80

History of code–based cryptography

Idea 2 : Using codes with a non trivial automorphism group

In 2005, Gaborit proposes to use codes with a non trivial automorphismgroup G.
Quasi–cyclic codes (QC–codes) : G = Z/`Z;

Quasi–dyadic codes (QD–codes) : G = (Z/2Z)γ .
Advantage. Permits to reduce the public key size with almost no
incidence on the security

A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 201919 / 80

History of code–based cryptography

Idea 2 : Using codes with a non trivial automorphism group

In 2005, Gaborit proposes to use codes with a non trivial automorphismgroup G.
Quasi–cyclic codes (QC–codes) : G = Z/`Z;

Quasi–dyadic codes (QD–codes) : G = (Z/2Z)γ .
Advantage. Permits to reduce the public key size with almost no
incidence on the security w.r.t. message security attacks.

A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 201919 / 80

History of code–based cryptography

Idea 2 : Using codes with a non trivial automorphism group

In 2005, Gaborit proposes to use codes with a non trivial automorphismgroup G.
Quasi–cyclic codes (QC–codes) : G = Z/`Z;

Quasi–dyadic codes (QD–codes) : G = (Z/2Z)γ .
Advantage. Permits to reduce the public key size with almost no
incidence on the security w.r.t. message security attacks.
But, may affect the security w.r.t. key recovery attacks.

A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 201919 / 80

History of code–based cryptography

Idea 2 : Using codes with a non trivial automorphism group

In 2005, Gaborit proposes to use odes with a non trivial automorphismgroup G.
Caution! Some tempting choices of using large groups lead to key
recovery attacks:
QC–BCH codes: Otmani, Tillich, Dallot (2008);
QC–altenant codes : Faugère, Otmani, Perret, Tillich (2010);
QC and QD–alternant codes : Faugère, Otmani, Perret, Tillich, dePortzamparc (2016).
DAGS (QD–Alternant codes): Barelli, C. (2018).

A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 201920 / 80

History of code–based cryptography

Further constructions from GRS codes

Berger Loidreau, 2001. Subcodes of GRS codes.
Wieschebrink, 2006. Adds random columns in a GRS code’s
generator matrix.
Baldi, Bianchi, Chiaraluce, Rosenthal, Schipani, 2013. Right
multiply the GRS code by a sparse matrix.
Wang’s RLCE system, 2016. Replaces some columns of a GRS’s
generator matrix by linear combinations of GRS and random columns.

A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 201921 / 80

History of code–based cryptography

Other families of codes

Sidelnikov 1994. Binary Reed Muller codes.
Janwa Moreno 1996. Algebraic geometry codes and their subfield
subcodes.
Misoczki, Tillich, Sendrier, Barreto 2012. QC–MDPC codes.

A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 201922 / 80

History of code–based cryptography

Other families of codes

Sidelnikov 1994. Binary Reed Muller codes.
Janwa Moreno 1996. Algebraic geometry codes and their subfield
subcodes.
Misoczki, Tillich, Sendrier, Barreto 2012. QC–MDPC codes.
RemarkNon exhaustive list.

A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 201922 / 80

History of code–based cryptography

Chronology
1978 : McEliece

A. Couvreur

Proposals
Attacks
BrokenPartially Broken

Cryptanalysis in code–based crypto

Nutmic 201923 / 80

History of code–based cryptography

Chronology
1978 : McEliece

Proposals
Attacks
BrokenPartially Broken

1986 : Niederreiter
Suggests GRS codes

A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 201924 / 80

History of code–based cryptography

Chronology
1978 : McEliece

Proposals
Attacks
BrokenPartially Broken

1986 : Niederreiter
Suggests GRS codes
1992 : Sidelnikov Shestakov

A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 201925 / 80

History of code–based cryptography

Chronology
1978 : McEliece

Proposals
Attacks
BrokenPartially Broken

1986 : Niederreiter
Suggests GRS codes
1992 : Sidelnikov Shestakov
1994 : Sidelnikov
Proposes Reed-Muller codes

A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 201926 / 80

History of code–based cryptography

Chronology
1978 : McEliece

Proposals
Attacks
BrokenPartially Broken

1986 : Niederreiter
Suggests GRS codes
1992 : Sidelnikov Shestakov
1994 : Sidelnikov
Proposes Reed-Muller codes
1996 : Janwa, Moreno
Propose AG codes and their subfield subcodes

A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 201927 / 80

History of code–based cryptography

Chronology
1978 : McEliece

Proposals
Attacks
BrokenPartially Broken

1986 : Niederreiter
Suggests GRS codes
1992 : Sidelnikov Shestakov
1994 : Sidelnikov
Proposes Reed-Muller codes
1996 : Janwa, Moreno
Propose AG codes and their subfield subcodes2001 : Berger Loidreau
Propose subcodes of GRS codes

A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 201928 / 80

History of code–based cryptography

Chronology
1978 : McEliece

Proposals
Attacks
BrokenPartially Broken

1986 : Niederreiter
Suggests GRS codes
1992 : Sidelnikov Shestakov
1994 : Sidelnikov
Proposes Reed-Muller codes
1996 : Janwa, Moreno
Propose AG codes and their subfield subcodes2001 : Berger Loidreau
Propose subcodes of GRS codes2005 : Gaborit
Quasi–cyclic BCH codes

A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 201929 / 80

History of code–based cryptography

Chronology
1978 : McEliece
1994 : Sidelnikov
Proposes Reed-Muller codes

Proposals
Attacks
BrokenPartially Broken

1996 : Janwa, Moreno
Propose AG codes and their subfield subcodes2001 : Berger Loidreau
Propose subcodes of GRS codes2005 : Gaborit
Quasi-cyclic subcodes of BCH codes

A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 201930 / 80

History of code–based cryptography

Chronology
1978 : McEliece
1994 : Sidelnikov
Proposes Reed-Muller codes

Proposals
Attacks
BrokenPartially Broken

1996 : Janwa, Moreno
Propose AG codes and their subfield subcodes2001 : Berger Loidreau
Propose subcodes of GRS codes2005 : Gaborit
Quasi-cyclic subcodes of BCH codes2007 : Minder Shokrollahi
Subexponential time attack on RM codes

A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 201931 / 80

History of code–based cryptography

Chronology
1978 : McEliece
1996 : Janwa, Moreno
Propose AG codes
and their subfield subcodes2001 : Berger Loidreau
Propose subcodes of GRS codes

Proposals
Attacks
BrokenPartially Broken

2005 : Gaborit
Quasi-cyclic subcodes of BCH codes

A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 201932 / 80

History of code–based cryptography

Chronology
1978 : McEliece
1996 : Janwa, Moreno
Propose AG codes
and their subfield subcodes2001 : Berger Loidreau
Propose subcodes of GRS codes

Proposals
Attacks
BrokenPartially Broken

2005 : Gaborit
Quasi-cyclic subcodes of BCH codes2008 : Faure Minder, Attack on AG codes for genus ≤ 2

A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 201933 / 80

History of code–based cryptography

Chronology
1978 : McEliece
1996 : Janwa, Moreno... and their subfield subcodes

Proposals
Attacks
BrokenPartially Broken

2001 : Berger Loidreau
Propose subcodes of GRS codes2005 : Gaborit
Quasi-cyclic subcodes of BCH codes2008 : Faure Minder, Attack on AG codes for genus ≤ 2
2008 : Berger, Cayrel, Gaborit, Otmani
Propose QC alternant codes

A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 201934 / 80

History of code–based cryptography

Chronology
1978 : McEliece
1996 : Janwa, Moreno... and their subfield subcodes

Proposals
Attacks
BrokenPartially Broken

2001 : Berger Loidreau
Propose subcodes of GRS codes2005 : Gaborit
Quasi-cyclic subcodes of BCH codes2008 : Berger, Cayrel, Gaborit, Otmani
Propose QC alternant codes2010 : Bernstein, Lange Peters
Propose q–ary “wild” Goppa codes
Otmani, Tillich, Dallot Faugère, Perret, Otmani, Tillich
Attacks on QC-codes

A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 201935 / 80

History of code–based cryptography

Chronology
1978 : McEliece
1996 : Janwa, Moreno... and their subfield subcodes

Proposals
Attacks
BrokenPartially Broken

2001 : Berger Loidreau
Propose subcodes of GRS codes2005 : Gaborit
Quasi-cyclic subcodes of BCH codes2008 : Berger, Cayrel, Gaborit, Otmani
Propose QC alternant codes2010 : Bernstein, Lange Peters
Propose q–ary “wild” Goppa codes
Otmani, Tillich, Dallot Faugère, Perret, Otmani, Tillich
Attacks on QC-codes

A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 201936 / 80

History of code–based cryptography

Chronology
1978 : McEliece
1996 : Janwa, Moreno... and their subfield subcodes

Proposals
Attacks
BrokenPartially Broken

2001 : Berger Loidreau
Propose subcodes of GRS codes2005 : Gaborit
Quasi-cyclic subcodes of BCH codes2008 : Berger, Cayrel, Gaborit, Otmani
Propose QC alternant codes2010 : Bernstein, Lange Peters
Propose q–ary “wild” Goppa codes
Otmani, Tillich, Dallot Faugère, Perret, Otmani, Tillich
Attacks on QC-codes
Wieschebrink’s C ⋆ C attack

A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 201937 / 80

History of code–based cryptography

Chronology
1978 : McEliece
1996 : Janwa, Moreno... and their subfield subcodes

Proposals
Attacks
BrokenPartially Broken

2001 : Berger Loidreau
Propose subcodes of GRS codes2005 : Gaborit
Quasi-cyclic subcodes of BCH codes2008 : Berger, Cayrel, Gaborit, Otmani
Propose QC alternant codes2010 : Bernstein, Lange Peters
Propose q–ary “wild” Goppa codes
Otmani, Tillich, Dallot Faugère, Perret, Otmani, Tillich
Attacks on QC-codes
Wieschebrink’s C ⋆ C attack

A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 201938 / 80

History of code–based cryptography

Chronology
1978 : McEliece
1996 : Janwa, Moreno... and their subfield subcodes

Proposals
Attacks
BrokenPartially Broken

2010 : Bernstein, Lange Peters
Propose q–ary “wild” Goppa codes

A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 201939 / 80

History of code–based cryptography

Chronology
1978 : McEliece
1996 : Janwa, Moreno... and their subfield subcodes

Proposals
Attacks
BrokenPartially Broken

2010 : Bernstein, Lange Peters
Propose q–ary “wild” Goppa codes2011 : Faugère, Gautier, Otmani, Perret, Tillich
Distinguisher for High rate Goppa codes

A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 201940 / 80

History of code–based cryptography

Chronology
1978 : McEliece
1996 : Janwa, Moreno... and their subfield subcodes

Proposals
Attacks
BrokenPartially Broken

2010 : Bernstein, Lange Peters
Propose q–ary “wild” Goppa codes2011 : Faugère, Gautier, Otmani, Perret, Tillich
Distinguisher for High rate Goppa codes2012 : Misoczki, Tillich, Sendrier, Barreto
Propose MDPC codes

A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 201941 / 80

History of code–based cryptography

Chronology
1978 : McEliece
1996 : Janwa, Moreno
AG codesand their subfield subcodes2010 : Bernstein, Lange Peters
Propose q–ary “wild” Goppa codes

Proposals
Attacks
BrokenPartially Broken

2011 : Faugère, Gautier, Otmani, Perret, Tillich
Distinguisher for High rate Goppa codes2012 : Misoczki, Tillich, Sendrier, Barreto
Propose MDPC codes

A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 201942 / 80

History of code–based cryptography

Chronology
1978 : McEliece
1996 : Janwa, Moreno
AG codesand their subfield subcodes2010 : Bernstein, Lange Peters
Propose q–ary “wild” Goppa codes

Proposals
Attacks
BrokenPartially Broken

2011 : Faugère, Gautier, Otmani, Perret, Tillich
Distinguisher for High rate Goppa codes2012 : Misoczki, Tillich, Sendrier, Barreto
Propose MDPC codes
2014 : C., Márquez–Corbella, Pellikaan : attack on AG codes

A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 201943 / 80

History of code–based cryptography

Chronology
1978 : McEliece
1996 : Janwa, Moreno
AG codesand their subfield subcodes2010 : Bernstein, Lange Peters
Propose q–ary “wild” Goppa codes

Proposals
Attacks
BrokenPartially Broken

2011 : Faugère, Gautier, Otmani, Perret, Tillich
Distinguisher for High rate Goppa codes2012 : Misoczki, Tillich, Sendrier, Barreto
Propose MDPC codes
2014 : C., Márquez–Corbella, Pellikaan : attack on AG codes

A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 201944 / 80

History of code–based cryptography

Chronology
1978 : McEliece
1996 : Janwa, Moreno
AG codesand their subfield subcodes2010 : Bernstein, Lange Peters
Propose q–ary “wild” Goppa codes

Proposals
Attacks
BrokenPartially Broken

2011 : Faugère, Gautier, Otmani, Perret, Tillich
Distinguisher for High rate Goppa codes2012 : Misoczki, Tillich, Sendrier, Barreto
Propose MDPC codes
2014 : C., Márquez–Corbella, Pellikaan : attack on AG codes
C., Otmani, Tillich : Goppa codes with m = 2

A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 201945 / 80

History of code–based cryptography

Chronology
1978 : McEliece
1996 : Janwa, Moreno
AG codesand their subfield subcodes2010 : Bernstein, Lange Peters
Propose q–ary “wild” Goppa codes

Proposals
Attacks
BrokenPartially Broken

2011 : Faugère, Gautier, Otmani, Perret, Tillich
Distinguisher for High rate Goppa codes2012 : Misoczki, Tillich, Sendrier, Barreto
Propose MDPC codes
2014 : C., Márquez–Corbella, Pellikaan : attack on AG codes
C., Otmani, Tillich : Goppa codes with m = 2

A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 201946 / 80

History of code–based cryptography

Chronology
1978 : McEliece
1996 : Janwa, Moreno
AG codesand their subfield subcodes2010 : Bernstein, Lange Peters
Propose q–ary “wild” Goppa codes

Proposals
Attacks
BrokenPartially Broken

2011 : Faugère, Gautier, Otmani, Perret, Tillich
Distinguisher for High rate Goppa codes2012 : Misoczki, Tillich, Sendrier, Barreto
Propose MDPC codes
2014 : C., Márquez–Corbella, Pellikaan : attack on AG codes
C., Otmani, Tillich : Goppa codes with m = 2
Faugère, Perret, Portzamparc : Some Goppa codes with m = 2, 3

A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 201947 / 80

History of code–based cryptography

Chronology
1978 : McEliece
1996 : Janwa, Moreno
AG codesand their subfield subcodes2010 : Bernstein, Lange Peters
Propose q–ary “wild” Goppa codes

Proposals
Attacks
BrokenPartially Broken

2011 : Faugère, Gautier, Otmani, Perret, Tillich
Distinguisher for High rate Goppa codes2012 : Misoczki, Tillich, Sendrier, Barreto
Propose MDPC codes
2014 : C., Márquez–Corbella, Pellikaan : attack on AG codes
C., Otmani, Tillich : Goppa codes with m = 2
Faugère, Perret, Portzamparc : Some Goppa codes with m = 2, 3

A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 201948 / 80

History of code–based cryptography

Chronology
1978 : McEliece
1996 : Janwa, Moreno
AG codesand their subfield subcodes2010 : Bernstein, Lange Peters
Propose q–ary “wild” Goppa codes

Proposals
Attacks
BrokenPartially Broken

2011 : Faugère, Gautier, Otmani, Perret, Tillich
Distinguisher for High rate Goppa codes2012 : Misoczki, Tillich, Sendrier, Barreto
Propose MDPC codes
2014 : C., Márquez–Corbella, Pellikaan : attack on AG codes
C., Otmani, Tillich : Goppa codes with m = 2
Faugère, Perret, Portzamparc : Some Goppa codes with m = 2, 3
Faugère, Otmani, Perret, Portzamparc, Tillich
Further attack on QC and QD codes

A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 201949 / 80

History of code–based cryptography

Chronology
1978 : McEliece
1996 : Janwa, Moreno
AG codesand their subfield subcodes2010 : Bernstein, Lange Peters
Propose q–ary “wild” Goppa codes

Proposals
Attacks
BrokenPartially Broken

2011 : Faugère, Gautier, Otmani, Perret, Tillich
Distinguisher for High rate Goppa codes2012 : Misoczki, Tillich, Sendrier, Barreto
Propose MDPC codes
2014 : C., Márquez–Corbella, Pellikaan : attack on AG codes
C., Otmani, Tillich : Goppa codes with m = 2
Faugère, Perret, Portzamparc : Some Goppa codes with m = 2, 3
Faugère, Otmani, Perret, Portzamparc, Tillich
Further attack on QC and QD codes
Nov 2017 : NIST’s call for post quantum crypto

A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 201950 / 80

History of code–based cryptography

Chronology
1978 : McEliece
1996 : Janwa, Moreno
AG codesand their subfield subcodes2010 : Bernstein, Lange Peters
Propose q–ary “wild” Goppa codes

Proposals
Attacks
BrokenPartially Broken

2011 : Faugère, Gautier, Otmani, Perret, Tillich
Distinguisher for High rate Goppa codes2012 : Misoczki, Tillich, Sendrier, Barreto
Propose MDPC codes
2014 : C., Márquez–Corbella, Pellikaan : attack on AG codes
C., Otmani, Tillich : Goppa codes with m = 2
Faugère, Perret, Portzamparc : Some Goppa codes with m = 2, 3
Faugère, Otmani, Perret, Portzamparc, Tillich
Further attack on QC and QD codes
Nov 2017 : NIST’s call for post quantum cryptoetc...
A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 201951 / 80

Algebraic cryptanalysis in code–based cryptography

1

History of code–based cryptography

2

Algebraic cryptanalysis in code–based cryptography

3

How to design secure schemes with codes?

A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 201952 / 80

Algebraic cryptanalysis in code–based cryptography

Theoretical security analysis of McEliece encryption

Security proofs consist in reducing to the Bounded decoding problem
under the following assumption:
Assumption. The uniform distribution on the public [n, k] codesin family F is computationally indistinguishable from the uniform
distribution on the whole family of [n, k] codes.

A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 201953 / 80

Algebraic cryptanalysis in code–based cryptography

Two types of attacks

In algebraic code–based cryptography, there are two major types of attacks:
Message recovery attacks based on generic decoding algorithms.
Exponential time if t = Θ(n).
Key recovery attacks : ad hoc methods to recover s ∈ S such thatthe public key Cpub = C (s).

A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 201954 / 80

Algebraic cryptanalysis in code–based cryptography

Two types of attacks

In algebraic code–based cryptography, there are two major types of attacks:
Message recovery attacks based on generic decoding algorithms.
Exponential time if t = Θ(n).
Key recovery attacks : ad hoc methods to recover s ∈ S such thatthe public key Cpub = C (s).
We focus on key recovery attacks in the present talk.

A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 201954 / 80

Algebraic cryptanalysis in code–based cryptography

Sidelnikov Shestakov, 1992
Efficient key recovery attack on GRS codes.
Idea.
From a generator matrix G of a code GRSk (x, y ),compute two minimum weight codewords whose supports are close,
they correspond to split polynomials with many common roots. The
ratio of these polynomial is a homography. This provides information
on x.

A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 201955 / 80

Algebraic cryptanalysis in code–based cryptography

Sidelnikov Shestakov, 1992
Efficient key recovery attack on GRS codes.
Idea.
From a generator matrix G of a code GRSk (x, y ),compute two minimum weight codewords whose supports are close,
they correspond to split polynomials with many common roots. The
ratio of these polynomial is a homography. This provides information
on x.
Note.
Computing minimum weight codewords is hard but...
is only Gaussian elimination for GRS codes!

A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 201955 / 80

Algebraic cryptanalysis in code–based cryptography

Sidelnikov Shestakov, 1992
Efficient key recovery attack on GRS codes.
Idea.
From a generator matrix G of a code GRSk (x, y ),compute two minimum weight codewords whose supports are close,
they correspond to split polynomials with many common roots. The
ratio of these polynomial is a homography. This provides information
on x.
Note.
Computing minimum weight codewords is hard but...
is only Gaussian elimination for GRS codes!
This is a polynomial time distinguisher!

A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 201955 / 80

Algebraic cryptanalysis in code–based cryptography

Some attacks deriving from Sidelnikov Shestakov

Minder Shokrollahi 2007. Broke Sidelnikov’s proposal based on binary
Reed Muller codes. Subexponential time attack;Faure Minder, Broke AG codes from hyperelliptic curves. The cost of
the attack is exponential in the curve’s genus.

A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 201956 / 80

Algebraic cryptanalysis in code–based cryptography

Some attacks deriving from Sidelnikov Shestakov

Minder Shokrollahi 2007. Broke Sidelnikov’s proposal based on binary
Reed Muller codes. Subexponential time attack;Faure Minder, Broke AG codes from hyperelliptic curves. The cost of
the attack is exponential in the curve’s genus.
In red: due to the cost of computing minimum weight codewords.

A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 201956 / 80

Algebraic cryptanalysis in code–based cryptography

Algebraic attacks by polynomial system solving
Idea. A code Ar (x, y ) code is contained in the kernel of a matrix of the
form:


y1
···
yn
 x1 y1 · · · xn yn H =  ..
.. 
 .
. 
r −1
r
−1
x1 y1 · · · xn yn
Put xi , yi as formal variables Xi , Yi and solve the polynomial system:
H(Xi , Yi ) · t G = 0

A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 201957 / 80

Algebraic cryptanalysis in code–based cryptography

Algebraic attacks by polynomial system solving
Idea. A code Ar (x, y ) code is contained in the kernel of a matrix of the
form:


y1
···
yn
 x1 y1 · · · xn yn H =  ..
.. 
 .
. 
r −1
r
−1
x1 y1 · · · xn yn
Put xi , yi as formal variables Xi , Yi and solve the polynomial system:
H(Xi , Yi ) · t G = 0
For usual McEliece parameters, the resolution of such a polynomial
system is out of reach. But...

A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 201957 / 80

Algebraic cryptanalysis in code–based cryptography

Algebraic attacks by polynomial system solving
Idea. A code Ar (x, y ) code is contained in the kernel of a matrix of the
form:


y1
···
yn
 x1 y1 · · · xn yn H =  ..
.. 
 .
. 
r −1
r
−1
x1 y1 · · · xn yn
Put xi , yi as formal variables Xi , Yi and solve the polynomial system:
H(Xi , Yi ) · t G = 0
For usual McEliece parameters, the resolution of such a polynomial
system is out of reach. But... if you use alternant codes with
automorphisms...
A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 201957 / 80

Algebraic cryptanalysis in code–based cryptography

Algebraic attacks on alternant codes with automorphisms
Given a code C ⊆ Fnq with a group action G, one can define:
The invariant codedef

C G = {x ∈ C | ∀σ ∈ G, σ(x) = x}.

A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 201958 / 80

Algebraic cryptanalysis in code–based cryptography

Algebraic attacks on alternant codes with automorphisms
Given a code C ⊆ Fnq with a group action G, one can define:
The invariant codedef

C G = {x ∈ C | ∀σ ∈ G, σ(x) = x}.
If the action of G is public, then C G is computable in polynomial time.
Moreover,
Theorem 1 (Faugère, Otmani, Perret, Portzamparc, Tillich 2014)r
and for some x G , y G
If C = Ar (x, y ) then C G = Ar 0 (x G , y G ) for r 0 ≈ |G|nof lengths ≈ |G|.

Theorem 2 (Barelli, 2018)
If C = CL (X , P, G ) then C G = CL (X /G, P G , G G ) where |P G | ≈ |P||G| andG
deg G G ≈ deg|G| . (+ This results extends to subfield subcodes).
A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 201958 / 80

Algebraic cryptanalysis in code–based cryptography

Algebraics attacks on the invariant code

The algebraic attack can be performed on the invariant code and iseasier (less variables, equations of smaller degree).
Attacks on quasi–cyclic and quasi–dyadic Goppa/alternant codes,(Faugère, Otmani, Perret, Portzamparc, Tillich 2010, 2014)

Deducing the secret on the original code from the structure of theinvariant code can be done in polynomial time (Barelli, WCC 2017).

A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 201959 / 80

Algebraic cryptanalysis in code–based cryptography?–product and square codes

In Fnq we denote by ? the component wise product:defu ? v = (u1 v1 , . . . , un vn ).
Then, the star product of two codes A , B ⊆ Fnq :def

A ? B = Span{a ? b | a ∈ A , b ∈ B}
def

If A = B, then we denote by A 2 = A ? A .

A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 201960 / 80

Algebraic cryptanalysis in code–based cryptography

The why of ?–product

Algebraic codes are evaluation codes from an algebra
Fq [X ] (GRS, alternant codes),Fq [X1 , . . . , Xn ] (Reed–Muller codes)
Ring OS of regular functions on an open subset of a curve (AG codes
and their subcodes)

A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 201961 / 80

Algebraic cryptanalysis in code–based cryptography

The why of ?–product

Algebraic codes are evaluation codes from an algebra
Fq [X ] (GRS, alternant codes),Fq [X1 , . . . , Xn ] (Reed–Muller codes)
Ring OS of regular functions on an open subset of a curve (AG codes
and their subcodes)
Idea. Import the ring structure at the level of codes to get further
information on the public key.

A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 201961 / 80

Algebraic cryptanalysis in code–based cryptography

A wonderful distinguisher
Theorem 3 (Cascudo, Cramer, Mirandola, Zémor 2013)
Let R be a random [n, k]–code then

 

k +1
2
Prob dim R < min n,−→ 0.
2

A. Couvreur

Cryptanalysis in code–based crypto(n, k → ∞)Nutmic 201962 / 80

Algebraic cryptanalysis in code–based cryptography

A wonderful distinguisher
Theorem 3 (Cascudo, Cramer, Mirandola, Zémor 2013)
Let R be a random [n, k]–code then

 

k +1
2
Prob dim R < min n,−→ 0.
2(n, k → ∞)Theorem 4n
For x, y ∈ Fnq × (F×q) ,GRSk (x, y )2 = GRS2k−1 (x, y ? y ).
RemarkSimilar result for AG codes CL (X , P, G )2 = CL (X , P, 2G ) under someconditions on deg G .
A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 201962 / 80

Algebraic cryptanalysis in code–based cryptography

First use of ? Wieschebrink 2010

On Berger Loidreau system:
Public key C ⊆ GRSk (x, y ) of codimension ` ≈ 5;

Secret key s = (x, y ).

A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 201963 / 80

Algebraic cryptanalysis in code–based cryptography

First use of ? Wieschebrink 2010

On Berger Loidreau system:
Public key C ⊆ GRSk (x, y ) of codimension ` ≈ 5;

Secret key s = (x, y ).
Fact.

C 2 = GRSk (x, y )2 with a high probability.

A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 201963 / 80

Algebraic cryptanalysis in code–based cryptography

First use of ? Wieschebrink 2010

On Berger Loidreau system:
Public key C ⊆ GRSk (x, y ) of codimension ` ≈ 5;

Secret key s = (x, y ).
Fact.

C 2 = GRSk (x, y )2 with a high probability.
Wieschebrink’s attack.
Compute C 2 ;Perform Sidelnikov Shestakov attack on C 2 to recover (x, y ? y ).
Deduce (x, y ).

A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 201963 / 80

Algebraic cryptanalysis in code–based cryptography

Other attacks based on the raw ?–product distinguisher

Wieschebrink’s scheme (C., Gautier, Gaborit, Otmani, Tillich, 2015);
BBCRS scheme (C., Gautier, Otmani, Tillich, 2015);
RLCE scheme (C. Lequesne, Tillich, 2019)

A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 201964 / 80

Algebraic cryptanalysis in code–based cryptography

Distinguisher and filtration attack
Illustrative example on GRS codes. Suppose you know the codes
GRSk (x, y )(Fq [X ]6k−1 )GRSk−1 (x, y )(Fq [X ]6k−2 )A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 201965 / 80

Algebraic cryptanalysis in code–based cryptography

Distinguisher and filtration attack
Illustrative example on GRS codes. Suppose you know the codes
GRSk (x, y )(Fq [X ]6k−1 )GRSk−1 (x, y )(Fq [X ]6k−2 )You’d like to compute
GRSk−2 (x, y )A. Couvreur(Fq [X ]6k−3 )Cryptanalysis in code–based crypto

Nutmic 201965 / 80

Algebraic cryptanalysis in code–based cryptography

Distinguisher and filtration attack
Illustrative example on GRS codes. Suppose you know the codes
GRSk (x, y )(Fq [X ]6k−1 )GRSk−1 (x, y )(Fq [X ]6k−2 )You’d like to compute
GRSk−2 (x, y )(Fq [X ]6k−3 )Then note that
GRSk−2 (x, y ) ? GRSk (x, y ) ⊆ GRSk (x, y )2
Indeed :(k − 3) + (k − 1) = 2(k − 2).

A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 201965 / 80

Algebraic cryptanalysis in code–based cryptography

Distinguisher and filtration attack
GRSk−2 (x, y ) can be computed as the set
def

Cond(GRSk (x, y ), GRSk−1 (x, y )2 ) =z ∈ Fnq | z ? GRSk (x, y ) ⊆ GRSk−1 (x, y )2

A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 201966 / 80

Algebraic cryptanalysis in code–based cryptography

Distinguisher and filtration attack
GRSk−2 (x, y ) can be computed as the set
def

Cond(GRSk (x, y ), GRSk−1 (x, y )2 ) =z ∈ Fnq | z ? GRSk (x, y ) ⊆ GRSk−1 (x, y )2
Then reiterate the process to deduce the filtration
GRSk (x, y ) ⊇ GRSk (x, y ) ⊇ · · · ⊇ GRSr (x, y ) ⊇ · · ·A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 201966 / 80

Algebraic cryptanalysis in code–based cryptography

Distinguisher and filtration attack
GRSk−2 (x, y ) can be computed as the set
def

Cond(GRSk (x, y ), GRSk−1 (x, y )2 ) =z ∈ Fnq | z ? GRSk (x, y ) ⊆ GRSk−1 (x, y )2
Then reiterate the process to deduce the filtration
GRSk (x, y ) ⊇ GRSk (x, y ) ⊇ · · · ⊇ GRSr (x, y ) ⊇ · · ·RemarkThere is no reason to know both GRSk (x, y ) and GRSk−1 (x, y ) but
GRSk−1 (x, y ) can be replaced by a shortening of GRSk (x, y ) at one
position.
A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 201966 / 80

Algebraic cryptanalysis in code–based cryptography

Applications

Alternative attack on GRS codes (C., Gautier, Gaborit, Otmani,
Tillich, 2015);
AG codes and their subcodes (C., Márquez–Corbella, Pellikaan,
2014–17);
Wild Goppa codes for m = 2 (C. Otmani, Tillich, 2014–17);

A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 201967 / 80

Algebraic cryptanalysis in code–based cryptography

Applications

Alternative attack on GRS codes (C., Gautier, Gaborit, Otmani,
Tillich, 2015);
AG codes and their subcodes (C., Márquez–Corbella, Pellikaan,
2014–17);
Wild Goppa codes for m = 2 (C. Otmani, Tillich, 2014–17);
RemarkNo more need to compute minimum weight codewords. Succeeds where
Sidelnikov Shestakov fails!

A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 201967 / 80

How to design secure schemes with codes?

1

History of code–based cryptography

2

Algebraic cryptanalysis in code–based cryptography

3

How to design secure schemes with codes?

A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 201968 / 80

How to design secure schemes with codes?

Algebraic codes

Subfield Subcodes of AG codes

Alternant codes

AG CodesA. Couvreur

GRS codes

Classical
Goppa
Codes

Cryptanalysis in code–based crypto

Nutmic 201969 / 80

How to design secure schemes with codes?

Sidelnikov Shestakov 1992

Subfield Subcodes of AG codes

Alternant codes

AG CodesA. Couvreur

GRS codes

Classical
Goppa
Codes

Cryptanalysis in code–based crypto

Nutmic 201970 / 80

How to design secure schemes with codes?

Faure Minder 2008

Subfield Subcodes of AG codes

Alternant codesg≤2

AG CodesA. Couvreur

GRS codes

Classical
Goppa
Codes

Cryptanalysis in code–based crypto

Nutmic 201971 / 80

How to design secure schemes with codes?

C. Márquez–Corbella, Pellikaan, 2014

Subfield Subcodes of AG codes

Alternant codes

AG CodesA. Couvreur

GRS codes

Classical
Goppa
Codes

Cryptanalysis in code–based crypto

Nutmic 201972 / 80

How to design secure schemes with codes?

C. Otmani, Tillich & Faugère, Perret, Portzamparc 2014

Subfield Subcodes of AG codes

Alternant codes

AG CodesA. Couvreur

GRS codes

Classical
Goppa
Codes

Cryptanalysis in code–based crypto

Nutmic 201973 / 80

How to design secure schemes with codes?

Other point of view : subcodes of GRS codes.

Subcodes of GRS codes

GRS

Alt

(m = 1)(m = 2)

m=3

...

m≫1

...

Decreasing dimension of the subcode

A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 201974 / 80

How to design secure schemes with codes?

Other point of view : subcodes of GRS codes.
What filtration attacks can break

Subcodes of GRS codes

GRS

Alt

(m = 1)(m = 2)

m=3

...

m≫1

...

√
dim ' 2 k

Decreasing dimension of the subcode

A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 201975 / 80

How to design secure schemes with codes?

Other point of view : subcodes of GRS codes.
What filtration attacks can break

Faugère, Otmani, Perret, Tillich distinguisher

Subcodes of GRS codes

GRS

Alt

(m = 1)(m = 2)

m=3

...

m≫1

...

√
dim ' 2 k

Decreasing dimension of the subcode

A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 201976 / 80

How to design secure schemes with codes?

How to evaluate the security of algebraic codes?
Security analysis framework
Sufficiently many codes in the family, even up to permutation(Sendrier’s support splitting algorithm);

A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 201977 / 80

How to design secure schemes with codes?

How to evaluate the security of algebraic codes?
Security analysis framework
Sufficiently many codes in the family, even up to permutation(Sendrier’s support splitting algorithm);
Low weight codewords are hard to compute (avoid,
Sidelnikov–Shestakov like attacks).

A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 201977 / 80

How to design secure schemes with codes?

How to evaluate the security of algebraic codes?
Security analysis framework
Sufficiently many codes in the family, even up to permutation(Sendrier’s support splitting algorithm);
Low weight codewords are hard to compute (avoid,
Sidelnikov–Shestakov like attacks).
No square code distinguisher.
C 2 , (C ⊥ )2 and their shortenings should behave like random codes.

A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 201977 / 80

How to design secure schemes with codes?

How to evaluate the security of algebraic codes?
Security analysis framework
Sufficiently many codes in the family, even up to permutation(Sendrier’s support splitting algorithm);
Low weight codewords are hard to compute (avoid,
Sidelnikov–Shestakov like attacks).
No square code distinguisher.
C 2 , (C ⊥ )2 and their shortenings should behave like random codes.

If you use some automorphis group, check the above properties forboth C and C G .

A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 201977 / 80

How to design secure schemes with codes?

How to evaluate the security of algebraic codes?
Security analysis framework
Sufficiently many codes in the family, even up to permutation(Sendrier’s support splitting algorithm);
Low weight codewords are hard to compute (avoid,
Sidelnikov–Shestakov like attacks).
No square code distinguisher.
C 2 , (C ⊥ )2 and their shortenings should behave like random codes.

If you use some automorphis group, check the above properties forboth C and C G .
How to resist to attacks by algebraic systems solving? Difficult
question...

A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 201977 / 80

How to design secure schemes with codes?

What is still surviving?

Algebraic world

Binary Goppa codes (NIST’s Classic McEliece and
NTS KEM)
Goppa codes for m  2.
Goppa codes with a “small” automorphism group
Subfield subcodes of AG codes

Probabilistic world

A. Couvreur

Quasi–cyclic MDPC codes;

Cryptanalysis in code–based crypto

Nutmic 201978 / 80

How to design secure schemes with codes?

What is still surviving?

Binary Goppa codes (NIST’s Classic McEliece and
NTS KEM)
Goppa codes for m  2.
Goppa codes with a “small” automorphism group
Subfield subcodes of AG codes
Advantages : Short ciphertexts, no decoding failure.

Algebraic world

Probabilistic world

A. Couvreur

Quasi–cyclic MDPC codes;

Cryptanalysis in code–based crypto

Nutmic 201978 / 80

How to design secure schemes with codes?

What is still surviving?

Binary Goppa codes (NIST’s Classic McEliece and
NTS KEM)
Goppa codes for m  2.
Goppa codes with a “small” automorphism group
Subfield subcodes of AG codes
Advantages : Short ciphertexts, no decoding failure.

Algebraic world

Probabilistic world
Quasi–cyclic MDPC codes;
Advantages : short keys, especially designed for
cryptography, somehow simpler security analysis.

A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 201978 / 80

How to design secure schemes with codes?

What is still surviving?

Binary Goppa codes (NIST’s Classic McEliece and
NTS KEM)
Goppa codes for m  2.
Goppa codes with a “small” automorphism group
Subfield subcodes of AG codes
Advantages : Short ciphertexts, no decoding failure.

Algebraic world

Probabilistic world
Quasi–cyclic MDPC codes;
Advantages : short keys, especially designed for
cryptography, somehow simpler security analysis.
Other paradigms HQC, RQC : do not rely on indistinguishability
assumption: promising application of algebraic codes!

A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 201978 / 80

How to design secure schemes with codes?

Thanks for your attention!

A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 201979 / 80

How to design secure schemes with codes?

Questions?

A. Couvreur

Cryptanalysis in code–based crypto

Nutmic 201980 / 80