Project topics and materials
Get Complete Project Material File(s) Now! »
Code-based cryptography
McEliece encryption scheme
The encryption scheme of McEliece, presented in [McE78], is the first cryptosystem based on error correcting codes. The idea of the McEliece cryptosystem is to use a family F of structured codes for which we know an efficient decoding algorithm. Then the public key will be a random looking generator matrix of a code in F and the trapdoor will be the decoding algorithm for the chosen code. More precisely the McEliece scheme can presented as follows.
Before speaking about the security, we precise what does performing an attack against the McEliece scheme mean. We define two kinds of attack against this scheme: message recovery attacks and key recovery attacks. Message recovery attacks consist in recovering the plaintext m from the knowledge of the cypher text y and the public key (G; t). Once the attack is performed we know the message m but we do not know the private key DC . If we want to recover several messages, the cost will be the cost of the attack on each cypher text. The second kind of attacks, that is the key recovery attacks, consists in recovering an efficient decoding algorithm DC for the code C from the knowledge of a generator matrix G. When we speak about an efficient decoding algorithm we mean that this algorithm works in polynomial time in the parameters n and k of the code. Once the attack is performed, the cost of recovering any message is the cost of the decoding algorithm DC .
In both cases, we say that there exists an attack if there exists an algorithm, which recover the message or the key, in polynomial time in n and k or which can be performed in less than 280 binary operations.
The security of the scheme depends on the choice of the family F and on the hardness of the syndrome decoding problem (see Section 2.2, Problem 1). The syndrome decoding (SD) problem is independent from the choice of F and is related to the security of the message. That is to say, the problem to recover the message m from the cypher text y and the public key G reduces to solve an instance of the SD problem. We will see in details this problem in the following section. The choice of the family F influences the security of the private key. Indeed, for some family F of linear codes there exists an algorithm, working in polynomial time in parameters n and k, which permits to recover a decoder DC from a generator matrix G of a code C . We speak more precisely of the choice of F in Section 2.3.
Information Set Decoding (ISD)
The difficult problem to which refers most of the time code-based cryptosystems is the syndrome decoding problem. It is the case for the McEliece cryptosystem. This problem can be defined as follows.
Problem 1 ((Search) Syndrome Decoding Problem). Let H be a parity check matrix of a random [n; k] code C over Fq. Let t be an integer and s 2 Fnq k be a uniformly random vector, then the Syndrome Decoding Problem is to find a vector e 2 Fn of weight wH (e) t such that He> = s.
The decisional version of this problem was proved NP-complete by Berlekamp, McEliece and van Tilbørd in [BMvT78]. Moreover, this problem is directly related to the decoding problem for a random linear code. Consider a random linear code C over Fq, a parity check matrix H for this code, and denote by t the correction capability of C . Let y := c + e be a vector of Fnq, with c 2 C and e 2 Fnq an error vector with wH (e) t. We want to decode the vector y, that is to recover c 2 C , without knowing a specific decoding algorithm. From the knowledge of the matrix H we can compute the vector s := Hy>. The vector s is called a syndrome. This syndrome depends only on the error vector e. Indeed, we have s := Hy> = Hc> +He> = He>: |{z} =0
If we are able to solve the SD problem for the parameters H, s and t, that is to recover e, then we are able to decode c = y e.
In order to choose parameters for the McEliece scheme we need to have an estimation of the cost of solving the SD problem. To solve the SD problem, the naive approach consists in performing a brute force search on errors vectors with weight t. The method does not provide a good approximation of the real cost of an attack on the message. Indeed, there exists more efficient algorithm to solve this problem. Of course the complexity of these algorithms is not polynomial in the parameters. Except the brute force approach, all algorithms to solve the SD problem are ameliorations of the attack by information set decoding (ISD), introduced by Prange in [Pra62]. This idea is to find a set of positions of the noisy vector which are without errors and such that the sub-matrix of the generator matrix associated to these positions is invertible.
Improvements of this first algorithm exist [Ste88, Dum91, MMT11, BJMM12]. We do not details here any algorithms, some of these methods are well explained in the paper of Peters [Pet10]. Moreover Peters provides a software to compute the best work factor of an ISD attack. To find parameters resistant to ISD algorithms, we use an improve version of this software proposed in [CT16a], called CaWoF (for Caculate Work Factor), which tests all the most efficient variants of the ISD algorithm ([Ste88, Dum91, MMT11, BJMM12]).
Key recovery problem
The complexity of a key recovery attack is more complicated to provide in the general case since it depends on the choice of the family F. As we saw previously, a key recovery attack consists in recovering a decoding algorithm for a code C knowing only a generator matrix of C . Actually the decoder recovery problem for a given family of linear codes reduces to an other problem which is what follows. Consider a family F of linear codes over Fq and G a n k matrix over Fq. The problem consists in finding the structure of the code C 2 F defined by G, that is the secret elements which permit to construct an efficient decoding algorithm for the code C . Depending on the choice of F, this problem can be easy to solve. For instance if the chosen family is not large enough, a brute force attack can solve the decoder recovery problem in less than 280 binary operations. The historical choice made by McEliece in [McE78] was the family of classical Goppa codes (see Definition 1.39) with parameters [1024; 524; 101]. For now, we do not know a efficient algorithm to solve the decoder recovery problem for the family of Goppa codes. That is, for cryptographic parameters, from a generator matrix of a Goppa code we are not able to recover the support and the Goppa polynomial defining the code. That is why we assume that this family is secure for the McEliece scheme and in code-based cryptography in general. The main problem is that the size of keys is large. Since 1978, several families have been proposed for the McEliece scheme, in order to reduce the key size. However, for some proposals the code recovery problem is not so hard. It is the case for Generalized Reed Solomon (GRS) codes (Definition 1.36), since Sildelnikov and Shestakov provide, in [SS92], an algorithm which recovers in polynomial time in the parameters of the code the GRS code from a given generator matrix. For AG codes on a curve with genus 1, there exists two kind of attack. In [FM08], Faure and Minder presented an attack against AG codes over curve of genus 2. They can recover the AG code chosen from its generator matrix. This attack cannot be extend to curve with high genus due to the complexity which is exponential in the genus. In 2014, Couvreur, Márquez-Corbella and Pellikaan presented an attack against AG codes over curve with higher genus [CMCP14]. They do not solve the code recovery problem but solve directly the decoder recovery problem in building a decoder for the chosen AG code from only a generator matrix.
In this thesis, the principal interest for us is the case of alternant codes and subfield subcode of AG (SSAG) codes. For the key security of these two cases the following fact is important.
Fact 1. Let SSAGq(X ; P; G) be an AG code and assume that the curve X is known. It is possible to have a polynomial time decoding algorithm, from the knowledge of the support P and the divisor G.
That is to say, the security of a SSAG code depends on the knowledge of its support an divisor. In this thesis, when we speak about the secret elements of an SSAG code we mean the support and the divisor of this code. In the particular case of alternant codes this also means the support as a vector and the multiplier.
Algebraic cryptanalysis of McEliece schemes using alternant codes
In this section, we present a general framework of attack, called algebraic attack, against the private key of a McEliece scheme using rational SSAG codes, that is alternant codes. In 2010, Faugère, Otmani, Perret and Tillich proposed in [FOPT10] a new approach to study the key security of McEliece schemes using alternant codes. They prove that the secret elements, that is the support and the multiplier of the private key, satisfy a system of polynomial equations. This approach is also well described in the Portzamparc’s thesis [dP15]. We explain here, how this polynomial system is built.
Let C := Ar;q(x; y) be an alternant code over Fq, with a support x and a multiplier y of length n defined over Fqm . From the knowledge of x and y it is possible to decode the code C . That is the security of the private key reduces to the knowledge of the pair (x; y). Let us explain how to build a polynomial system whose solutions are x and y.
Table of contents :
Introduction
Résumé
1 Algebraic geometry codes
1.1 Coding theory
1.2 Introduction to algebraic geometry
1.3 AG codes: definition and properties
2 Code-based cryptography
2.1 McEliece encryption scheme
2.2 Information Set Decoding (ISD)
2.3 Key recovery problem
2.4 Algebraic cryptanalysis of McEliece schemes using alternant codes
3 McEliece scheme using quasi-cyclic alternant codes
3.1 Quasi-cyclic alternant codes
3.2 Structural analysis of the invariant code
3.3 Security reduction to the key security of the invariant code
3.4 Proposition of a scheme: BIG QUAKE
4 A structural attack on a scheme using quasi-dyadic alternant codes
4.1 Presentation of the NIST submission: DAGS
4.2 Schur products and conductors
4.3 Using the QD structure to compute a conductor
4.4 Description of the attack
4.5 Algorithm, work factor and implementation
5 Short McEliece keys from codes on curves with positive genus
5.1 Construction of quasi-cyclic SSAG codes
5.2 Structure of the invariant code
5.3 QC codes from a cyclic cover of the projective line
5.4 The McEliece scheme with QC Hermitian codes
Bibliography
