Jean-Charles Faugère
email: jean-charles.faugere@inria.fr

Valérie Gauthier-Umaña

Ayoub Otmani
email: ayoub.otmani@univ-rouen.fr

Ludovic Perret
email: ludovic.perret@lip6.fr

Jean-Pierre Tillich
email: jean-pierre.tillich@inria.fr

J.-C Faugère

J.-P Tillich

A Distinguisher for High Rate McEliece Cryptosystems

Keywords: McEliece cryptosystem, CFS signature, Algebraic cryptanalysis, Goppa Code Distinguishing problem

The Goppa Code Distinguishing (GD) problem consists in distinguishing the matrix of a Goppa code from a random matrix. The hardness of this problem is an assumption to prove the security of code-based cryptographic primitives such as McEliece's cryptosystem. Up to now, it is widely believed that the GD problem is a hard decision problem. We present the first method allowing to distinguish alternant and Goppa codes over any field. Our technique can solve the GD problem in polynomial-time provided that the codes have sufficiently large rates. The key ingredient is an algebraic characterization of the key-recovery problem. The idea is to consider the rank of a linear system which is obtained by linearizing a particular polynomial system describing a key-recovery attack. Experimentally it appears that this dimension depends on the type of code. Explicit formulas derived from extensive experimentations for the rank are provided for "generic" random, alternant, and Goppa codes over any alphabet. Finally, we give theoretical explanations of these formulas in the case of random codes, alternant codes over any field of characteristic two and binary Goppa codes.

I. INTRODUCTION

T HIS paper investigates the difficulty of the Goppa Code Distinguishing (GD) problem which first appeared in [1]. This is a decision problem that aims at recognizing a generator matrix of a binary Goppa code from a randomly drawn binary matrix. Up to now, it is assumed that no polynomial time algorithm exists that distinguishes a generator matrix of a Goppa code from a randomly picked generator matrix.

The main motivation for introducing the GD problem is to formally relate the problem of decoding a random linear code to the security of the McEliece public-key cryptosytem [START_REF] Mceliece | A Public-Key System Based on Algebraic Coding Theory[END_REF]. Since its apparition, this cryptosystem has withstood many attacks and after more than thirty years now, it still belongs to the very few unbroken public key cryptosystems. This situation substantiates the claim that inverting the encryption function, and in particular recovering the private key from public data, is intractable. The classical methods for inverting the McEliece encryption function without finding a trapdoor all resort to the use of the best general decoding algorithms [START_REF] Lee | An observation on the security of McEliece's public-key cryptosystem[END_REF]- [START_REF] Becker | Decoding random binary linear codes in 2 n/20 : How 1 + 1 = 0 improves information set decoding[END_REF]. All these algorithms, whose time complexity is exponential (in the length), attempt to solve the long-standing problem of decoding random linear code [START_REF] Berlekamp | On the inherent intractability of certain coding problems[END_REF]. They also assume (implicitly or explicitly) that there does not exist an algorithm that is able to decode more efficiently McEliece public keys. Note that if ever such an algorithm exists, it would permit to solve the GD problem.

On the other hand, no significant breakthrough has been observed with respect to the problem of recovering the private key [START_REF] Gibson | Equivalent Goppa codes and trapdoors to McElieces public key cryptosystem[END_REF], [START_REF] Loidreau | Weak keys in the McEliece public-key cryptosystem[END_REF]. This has led to state that the generator matrix of a binary Goppa code does not disclose any visible structure that an attacker could exploit. This is strengthened by the fact that Goppa codes share many characteristics with random codes. For instance they asymptotically meet the Gilbert-Varshamov bound. They also have a trivial permutation group, etc. Hence, the hardness of the GD problem has become a classical belief, and as a consequence, a de facto assumption to prove the semantic security in the standard model (IND-CPA in [START_REF] Nojima | Semantic security for the McEliece cryptosystem without random oracles[END_REF] and IND-CCA2 in [START_REF] Dowsley | A CCA2 secure public key encryption scheme based on the McEliece assumptions in the standard model[END_REF]), and the security in the random oracle model against existential forgery [START_REF] Courtois | How to achieve a McEliece-based digital signature scheme[END_REF], [START_REF] Dallot | Towards a concrete security proof of Courtois, Finiasz and Sendrier signature scheme[END_REF] of the signature scheme [START_REF] Courtois | How to achieve a McEliece-based digital signature scheme[END_REF].

We present a deterministic polynomial-time distinguisher for codes whose rate is close to 1. This includes in particular codes encountered with the signature scheme CFS [START_REF] Courtois | How to achieve a McEliece-based digital signature scheme[END_REF], [START_REF] Finiasz | Security bounds for the design of code-based cryptosystems[END_REF]. However, we emphasize that our method can distinguish codes also used in McEliece's encryption scheme. For instance, the binary Goppa code obtained with m = 13 and r = 19 corresponding to a 90-bit security McEliece public key is distinguishable. More precisely, when the length of the code goes to infinity an asymptotic formula can be derived for the smallest rate R crit for which we can distinguish a q-random code from a q-ary alternant or Goppa code (Theorem 3). For a given q and assuming that the length is q m then when m tends to infinity, we have: R crit = 1 -2 m log q q m log m 1 + o [START_REF] Courtois | How to achieve a McEliece-based digital signature scheme[END_REF] .

where all logarithms are taken to base 2.

Our distinguisher is based on the algebraic attack developped against compact variants of McEliece [START_REF] Faugère | Algebraic cryptanalysis of McEliece variants with compact keys[END_REF]. In this approach, the key-recovery problem is transformed into the one of solving an algebraic system. By using a linearization technique, we are able to derive a linear system whose rank is different from what one would expect in the random case. More precisely, we observe experimentally that this defect in the rank is directly related to the type of codes. We provide explicit formulas for "generic" random, alternant, and Goppa codes over any alphabet. We performed extensive experiments to confirm that the formulas are accurate. Eventually, we prove the formula in the random case and give explanations in the case of alternant codes over any field of characteristic two and binary Goppa codes. However, the existence of our distinguisher does not undermine the security of primitives based on Goppa codes, but basically, it proves that the GD assumption is false for some parameters, and consequently should be used with great care as an assumption for a security reduction.

The paper is organized as follows. In Section III, we introduce the algebraic system that any McEliece cryptosystem must satisfy. In Section IV, we construct a linear system deduced from this algebraic system. This defines an algebraic distinguisher. We then provide explicit formulas that predicts the behavior of the distinguisher coming from experimentations. In Section VI, we give a proof of its typical behavior in the random case. In Section VII and Section VIII, we give explanations of the formulas for alternant and binary Goppa codes. Lastly, we conclude over the cryptographic implications the distinguisher induces and we deduce an asymptotic formula for the smallest rate for which we can distinguish a random code from an alternant code or a Goppa code.

II. CODE-BASED PUBLIC-KEY CRYPTOGRAPHY

The general problem of decoding random linear codes is a potential candidate for building public-key cryptographic primitives such as an encryption scheme. McEliece in [START_REF] Mceliece | A Public-Key System Based on Algebraic Coding Theory[END_REF] was the first to use this problem in public-key cryptography. The general idea is to start from a family of codes equipped with a polynomial-time decoding algorithm. The fundamental concept of this proposal is to consider two equivalent representations of a code: one should facilitate the decoding, whereas from the other one, the decoding should be infeasible. Although his design principle is general, he explicitly advocated to use binary Goppa codes [START_REF] Goppa | A new class of linear correcting codes[END_REF].

A. Coding theory background

Code-based public-key cryptography focuses on linear codes that have a polynomial time decoding algorithm. We recall that a q-ary (linear) code C over the finite field F q of q elements defined by a k × n matrix G (with k n) whose entries belong to F q is the vector space spanned by its rows i.e.,

C def = uG | u ∈ F k q .
The length of C is n and its rate is the ratio R def = k/n. The role of decoding algorithms is to correct errors of prescribed weight. We say that a decoding algorithm corrects r errors if it recovers u from the knowledge of uG + e for all possible e ∈ F n q of weight at most r. One famous family of codes is the one of binary Goppa codes. It belongs to the more general class of alternant codes ([20, Chap. 12, p. 365]). The main well-known feature of an alternant code is the possibility of being decoded in polynomial time. It is more convenient to describe this class through a parity-check matrix over an extension field F q m of F q over which the code is defined. We recall that a parity-check matrix H of a q-ary code C is defined as a matrix such that:

C def = c ∈ F n q | Hc T = 0 .
where the symbol T means the transpose operation. For q-ary alternant codes of length n q m , there exists a parity-check matrix with a very special form related to rectangular Vandermonde matrices:

V r (x, y) def =      y 1 • • • y n y 1 x 1 • • • y n x n . . . . . . y 1 x r-1 1 • • • y n x r-1 n      where x = (x 1 , . . . , x n ) and y = (y 1 , . . . , y n ) are in F n q m .
Definition 1 (Alternant code): A q-ary alternant code of order r associated to x = (x 1 , . . . , x n ) ∈ F n q m where all x i 's are distinct and y = (y 1 , . . . , y n ) ∈ F * q m n denoted by A r (x, y) is c ∈ F n q | V r (x, y)c T = 0 . It is well-known that the dimension k of an alternant codes of degree r satisfies k n -rm. Moreover, a key feature about them is the following property.

Proposition 1: An alternant codes of degree r can decode in polynomial time all errors of weight at most r 2 whenever there exists a parity-check matrix in the form V r (x * , y * ) for some vectors x * and y * . Definition 2 (Goppa codes): A q-ary Goppa code G (x, Γ) associated to a polynomial Γ(z) def = r i=0 γ i x i of degree r over F q m and an n-tuple x = (x 1 , . . . , x n ) of distinct elements of F q m satisfying Γ(x i ) = 0 for all i, 1 i n, is the q-ary alternant code A r (x, y) of order r with y i = Γ(x i ) -1 . Naturally Goppa codes, viewed as alternant codes, inherit a decoding algorithm that corrects up to r 2 errors. But in the case of binary Goppa codes, it is possible to correct twice as many errors. The starting point is the following result given in [20, p. 341].

Theorem 1: A binary Goppa code G (x, Γ) associated to a Goppa polynomial Γ(z) of degree r without multiple roots is equal to the alternant code A 2r (x, y) with

y i = Γ(x i ) -2 .
Corollary 1 ( [START_REF] Patterson | The algebraic decoding of Goppa codes[END_REF]): There exists a polynomial time algorithm decoding all errors of weight at most r for any Goppa code G (x, Γ) where Γ(z) is of degree r and has no multiple roots. It is worthwhile recalling that the only requirement for decoding a binary Goppa G is either to know x and Γ(z) or to know two vectors x * and y * such that:

G = A 2r (x * , y * ). (1)

B. McEliece cryptosystem

We briefly recall here the general principle of McEliece's encryption scheme.

Secret key: the triplet (S, G s , P) of matrices defined over a finite field F q over q elements, with q being a power of two, that is q = 2 s . G s is a full rank matrix of size k × n, with k < n, S is of size k × k and is invertible. P is a permutation matrix of size n × n. The generator matrix G s is chosen in such a way that its associated linear code has a decoding algorithm which corrects in polynomial time r errors.

Public key: the matrix G = SG s P.

Encryption: A plaintext u ∈ F k
q is encrypted by choosing a random vector e in F n q of weight at most r. The corresponding ciphertext is c = uG + e.

Decryption: c ′ = cP -1 is computed from the ciphertext c. Notice that c ′ = (uSG s P + e)P -1 = uSG s + eP -1 and that eP -1 is of Hamming weight at most r. Therefore the aforementioned decoding algorithm can recover in polynomial time uS and therefore the plaintext u by multiplication by S -1 .

C. CFS signatures

Another important code-based cryptographic primitive is the CFS signature scheme [START_REF] Courtois | How to achieve a McEliece-based digital signature scheme[END_REF]. A user whose public key is G and who wishes to sign a message x ∈ F k 2 has to compute a string u such that the Hamming weight of x -uG is at most r. Anyone (a verifier) can publicly check the validity of a signature. Unfortunately, this approach can only provide signatures for messages x that are within distance r from a codeword uG. The CFS scheme prompts to modify the message by appending a counter incremented until the decoding algorithm can find such a signature. The efficiency of this scheme heavily depends on the number of trials. With a binary Goppa codes of length n = 2 m and and dimension k = n -mr, the number of trials is of order r!. So one has to choose a very small r and therefore to take a very large n in order to be secure. The code rate is then equal to 2 m -rm 2 m = 1 -mr 2 m which is quite close to 1 for large n (that is for large values of 2 m ) and moderate values of r. For instance, a 80-bit security CFS scheme requires to take n = 2 21 and r = 10 whereas the McEliece cryptosystem for the same security needs to choose n = 2 11 and r = 32 ([17]). Thus one major difference between the McEliece cryptosystem and the CFS scheme lies in the choice of the parameters.

D. Goppa Code Distinguishing Problem

The minimum requirement for an encryption function is that it should be infeasible from a given ciphertext c and public data 1 like the public key pk, ciphertexts, etc. to recover the corresponding plaintext x. This issue is directly linked to the following computational problem.

Definition 3 (McEliece Problem):

Let G be a generator matrix of a binary Goppa code of length n 2 m and dimension k = n -rm where m and t are positive integers. Let x be a vector from F k 2 m and let e be a vector from F n 2 m of weight t. Finally, we set c def = xG + e. Then the McEliece Problem asks to find x and e only from G and c. One obvious way of solving this problem consists in devising a method that recovers the private key. But, it is also possible to recover a plaintext from a specific ciphertext without resorting to a key-recovery attack. In particular, an attacker against the McEliece scheme would find the plaintext by applying general decoding methods like [START_REF] Mceliece | A Public-Key System Based on Algebraic Coding Theory[END_REF]- [START_REF] Becker | Decoding random binary linear codes in 2 n/20 : How 1 + 1 = 0 improves information set decoding[END_REF], [START_REF] Van Tilburg | On the McEliece public-key cryptosystem[END_REF]- [START_REF] Canteaut | Cryptanalysis of the original McEliece cryptosystem[END_REF] on the public matrix G. Such attacks are called decoding attacks.

The only known methods that aim to solve the McEliece problem are based either on an exhaustive search of the private key or on applying very general decoding methods. Both approaches run in exponential time on some of the parameters. But this situation is a still unsatisfactory because there is no certitude that there does not exist a better way to solve it.

A classical stance is to claim that binary Goppa codes look like random linear codes. It amounts to say that there does not exist a polynomial-time computable quantity which behaves differently depending on whether the code is a Goppa or a random code. Currently, it is an open problem to establish a formal proof that would substantiate the claim that a binary Goppa code is indistinguishable from a random code.

This assumption is attractive because it enables to rely on the hardness of decoding a random linear code to prove the security of the McEliece function. This reasoning does make sense because binary Goppa codes share several common aspects2 with a randomly picked linear code. Furthermore, all the general decoding algorithms do not exploit the information, even partially, that a matrix describes a 'hidden" Goppa code. Based on this, the authors of [START_REF] Courtois | How to achieve a McEliece-based digital signature scheme[END_REF] defined the Goppa code distinguishing problem. Before formalizing this problem, we introduce some notation. For any integers n and k such that k n. We denote by Goppa(n, k) the set of k × n generator matrices of binary Goppa codes. Similarly, Random(n, k) is the set of binary k × n random generator matrices.

Definition 4 (Goppa Code Distinguishing (GD) Problem): A distinguisher D is an algorithm that takes as input a matrix G and returns a bit. D solves the GD problem if it wins the following game:

• b ← {0, 1} • If b = 0 then G ← Goppa(n, k) else G ← Random(n, k) • If D(G) = b then D wins else D loses. Definition 5: The advantage Adv GD (D) of a GD distinguisher D is defined by Adv GD (D) def =: Pr[D(G) = 1 : G ← Goppa(n, k)] -Pr[D(G) = 1 : G ← Random(n, k)] ,
where Pr[D(G) = 1 : G ← Goppa(n, k)] is the probability that D outputs 1 when G is a random binary generator matrix of a Goppa code, and Pr[D(G) = 1 : G ← Random(n, k)] is defined similarly for a binary random matrix.

Definition 6: A function ε(k) is negligible if for any integer a > 0, there exists an integer k a > 0 such that:

∀k k a , ε(k) < 1 k a .
The interest of negligible function is to keep a probability of an event negligible even after polynomially many tries. We are now able to state an important assumption 3 .

Assumption 1 ( [START_REF] Courtois | How to achieve a McEliece-based digital signature scheme[END_REF]): Adv GD (D) is negligible for any polynomial-time algorithm D that solves the GD problem. Until our recent work in [START_REF] Faugère | Distinguisher for high rate McEliece cryptosystems[END_REF] and this paper, the only known algorithm that solves the GD problem enumerates binary Goppa codes and tests the code equivalence thanks to the Support Splitting algorithm [START_REF] Sendrier | Finding the permutation between equivalent linear codes: The support splitting algorithm[END_REF]. This approach runs in time O n r-1 mr for binary Goppa codes of degree r and length n with m log 2 n and r = 1 m (1 -R)n where R is the code rate.

E. Semantically Secure Conversions

The fundamental issue when dealing with cryptographic primitives is to prove its security. Several approaches are possible. The most natural one is to show that the primitive resists to the best known attacks. However, this does not guarantee that there will not appear one day a better attack that renders the primitive insecure. The methodology of security proof by reduction appeared to remedy this question by linking a security notion that a cryptographic primitive should verify to an algorithmic problem widely considered as hard. The approach is similar to the one that proves the NP-Completeness of a given problem. Such a "security proof" proves that if an attacker exists then it can be used as a subroutine to solve a hard problem. In other words, such an attacker has little chances to exist. These simple facts prompt to design conversions that would lead to an IND-CCA secure encryption scheme. The first article to propose such a conversion for the McEliece cryptosystem is [START_REF] Kobara | Semantically secure McEliece public-key cryptosystems-conversions for McEliece PKC[END_REF] which proposes a conversion resulting into an IND-CCA2 in the Random Oracle Model under the assumption that the problem of decoding random linear codes is difficult. This work was then followed by [START_REF] Nojima | Semantic security for the McEliece cryptosystem without random oracles[END_REF] which proposes another modification while providing an IND-CPA secure encryption scheme in the standard model 4 under the assumptions that both decoding random linear codes and distinguishing Goppa codes are difficult problems. Finally, under the same assumptions, [START_REF] Dowsley | A CCA2 secure public key encryption scheme based on the McEliece assumptions in the standard model[END_REF] proposed (a modified) McEliece cryptosystem that is IND-CCA2 in the standard model.

III. ALGEBRAIC CRYPTANALYSIS OF MCELIECE-LIKE CRYPTOSYSTEMS

The McEliece cryptosystem relies on binary Goppa codes which belong to the class of alternant codes. We are now able to construct an algebraic system as explained in [START_REF] Faugère | Algebraic cryptanalysis of McEliece variants with compact keys[END_REF] for a key-recovey. This algebraic system will be the main ingredient for building a distinguisher. We assume that the public matrix is a k × n generator matrix G where by assumption k = n -rm. We know that the knowledge of a matrix V r (x * , y * ) for some vectors x * and y * allows to efficiently decode the public code defined by G. Furthermore, from the definition of G, we also know that:

V r (x * , y * )G T = 0.
Let X 1 , . . . , X n and Y 1 , . . . , Y n be 2n variables corresponding to the x * i 's and the y * i 's. Observe that such x * i 's and y * i 's are a particular solution [START_REF] Faugère | Algebraic cryptanalysis of McEliece variants with compact keys[END_REF] of the following polynomial system:

g i,1 Y 1 X j 1 + • • • + g i,n Y n X j n = 0 | 1 i k and 0 j r -1 (2)
where the g i,j 's are the entries of the known matrix G.

Clearly, solving this system would lead to a possibly equivalent private key. For compact variants [START_REF] Berger | Reducing key length of the McEliece cryptosystem[END_REF], [START_REF] Misoczki | Compact McEliece keys from Goppa codes[END_REF] of [START_REF] Mceliece | A Public-Key System Based on Algebraic Coding Theory[END_REF], additional structures permit to drastically reduce the number of variables allowing to solve (2) for a large set of parameters in polynomialtime using dedicated Gröbner bases techniques [START_REF] Faugère | Algebraic cryptanalysis of McEliece variants with compact keys[END_REF]. But the general case is currently a major open question. However, we describe a simple way for partially solving (2). It basically consists in deriving a linear system from the polynomial system (2). Note that this operation is actually the first step performed during the computation of Gröbner bases algorithms such as by F4 or F5 [START_REF] Faugère | A new efficient algorithm for computing gröbner bases (f4)[END_REF], [START_REF]A new efficient algorithm for computing gröbner bases without reduction to zero : F5[END_REF]. From now on, we will always assume that q = 2 s with s 1.We can assume that G = (g ij ) with 1 i k and 1 j n is in reduced row echelon form over its k first positions:

G = (I k | P)
where P = (p ij ) for 1 i k and k + 1 j n is the submatrix of G formed by its last n -k = mr columns. Next, for any i ∈ {1, . . . , k} and e ∈ {0, . . . , r -1}, we can rewrite (2) as

Y i X e i = n j=k+1 p i,j Y j X e j . (3)
In particular, it follows that for all i in {1, . . . , k}:

                     Y i = n j=k+1 p i,j Y j Y i X i = n j=k+1 p i,j Y j X j Y i X 2 i = n j=k+1 p i,j Y j X 2 j .
Then, thanks to the trivial identity Y

i (Y i X 2 i ) = (Y i X i ) 2
for all i in {1, . . . , k}, we get:

n j=k+1 p i,j Y j n j=k+1 p i,j Y j X 2 j =   n j=k+1 p i,j Y j X j   2 .
It is possible to reorder this to obtain:

n-1 j=k+1 n j ′ >j p i,j p i,j ′ Y j Y j ′ X 2 j ′ + Y j ′ Y j X 2 j = 0.
We thus obtain a linear system L P of k equations involving mr

2 variables Z jj ′ def = Y j Y j ′ X 2 j ′ + Y j ′ Y j X 2 j L P def =                    n-1 j=k+1 n j ′ >j p 1,j p i,j ′ Z jj ′ = 0 . . . n-1 j=k+1 n j ′ >j p k,j p i,j ′ Z jj ′ = 0 (4)
Definition 7: For any integer r 1 and m 1, the number of variables mr 2 in the linear system L P as defined in ( 4) is denoted by N and its rank by rank(L P ). We denote by Ker(L P ) the kernel of L P and its dimension as a F q -vector space is denoted by D.

Let us recall that Ker(L P ) is necessarily a F q -vector space since the linear system (4) have coefficients in F q but the solutions of ( 2) are sought in the extension field F q m . Furthermore, we obviously have:

D = N -rank(L P ).
Hence, in order to recover the solutions of (2), it is necessary that rank(L P ) is almost equal to the number of variables N = mr 2 . For a random system, this is likely to happen when the number k of equations in ( 4) is greater than the number of unknowns, that is to say: k N.

It appears experimentally that D is amazingly large even in the case where k N . It even depends on whether or not the code with generator matrix G is chosen as a (generic) alternant code or as a Goppa code. Interestingly enough, when G is chosen at random, rank(L P ) is equal to min {k, N } with very high probability. In particular, the dimension of the solution space is typically 0 when k is larger than the number of variables N as one would expect. This will be proved in Section VI. Although this defect in the rank is an obstacle to break the McEliece cryptosystem, it can be used to distinguish the public generator of a structured code from a random code.

IV. A DISTINGUISHER OF ALTERNANT AND GOPPA CODES

We consider three cases: when the p ij 's are chosen uniformly and independently at random in F q then we denote by D random the dimension of Ker(L P ). When G is chosen as a generator matrix of a random alternant (resp. Goppa) code of degree r, we denote it by D alternant (resp. D Goppa ). We carried out intensive computations with Magma [START_REF] Bosma | The Magma algebra system I: The user language[END_REF] by randomly generating alternant and Goppa codes over the field F q with q ∈ {2, 4, 8, 16, 32} for r in the range {3, . . . , 50} and several values of m. Furthermore, in our probabilistic model, a random alternant code is obtained by picking uniformly and independently at random two vectors (x 1 , . . . , x n ) and (y 1 , . . . , y n ) from (F q m ) n such that the x i 's are all different and the y i 's are all nonzero. A random Goppa code is obtained by taking a random vector (x 1 , . . . , x n ) in (F q m ) n with all the x i 's different and a random irreducible polynomial Γ(z) = i γ i z i of degree r. Our experiments have revealed that the dimension of Ker(L P ) is predictable and follows formulas.

Experimental Fact 1 (Alternant Case): As long as

N -D alternant < k,
then with high probability, D alternant is equal to T alternant where:

T alternant def = 1 2 m(r -1) (2e + 1)r -2 q e+1 -1 q -1 (5)
where e def = log q (r -1) .

Experimental Fact 2 (Goppa Case): As long as

N -D Goppa < k,
then with high probability, D Goppa is equal to T Goppa where:

T Goppa def =        1 2 m(r -1)(r -2) = T alternant for r < q -1, 1 2 mr (2e + 1)r -2q e + 2q e-1 -1 for r q -1, (6)
with e being the unique integer such that:

(q -1) 2 q e-2 < r (q -1) 2 q e-1 .

V. EXPERIMENTAL RESULTS

We gathered in Table II-XI in the appendix some samples of the results obtained through intensive computations with the Magma system [START_REF] Bosma | The Magma algebra system I: The user language[END_REF]. We randomly generated alternant and Goppa codes over the field F q with q ∈ {2, 4, 8, 16, 32} for values of r in the range {3, . . . , 50} and several m. The Goppa codes are generated by means of an irreducible Γ(z) of degree r and hence Γ(z) has no multiple roots. In particular, we can apply Theorem 1 in the binary case. We compare the dimensions of the solution space against the dimension D random of the system derived from a random linear code. Table II and Table III give figures for the binary case with m = 14. We can check that D random is equal to 0 for r ∈ {3, . . . , 12} and D random = N -k as expected. We remark that D alternant is different from D random whenever r 15, and D Goppa is different from D random as long as r 25. Finally we observe that our formulas for T alternant fit as long as k N -D alternant which correspond to r 15. This is also the case for binary Goppa codes since we have T Goppa = D Goppa as long as k N -D Goppa i.e., r 25. We also give in Table X and Table XI the examples we obtained for q = 4 and m = 6 to check that the arguments also apply. We also compare binary Goppa codes and random linear codes for m = 15 in Table IV-VI and m = 16 in Table VII-IX. We see that D random and D Goppa are different for r 33 when m = 15 and for m = 16 they are different even beyond our range of experiment (r 50).

VI. RANDOM CASE

The purpose of this section is to study the behavior of D random , namely the dimension of Ker(L P ) as F q -vector space when the entries of the matrix P are drawn independently from the uniform distribution over F q . In this case, we can show that:

Theorem 2: Assume that N k and that the entries of P are drawn independently from the uniform distribution over F q . Then for any function ω(x) tending to infinity as x goes to infinity, we have

prob D random mrω(mr) = o(1),
as mr goes to infinity. Notice that if we choose ω(x) = log(x) for instance, then asymptotically the dimension D random of the solution space is with very large probability smaller than mr log(mr). When m and r are of the same order (which is generally chosen in practice) this quantity is smaller than D alternant or D Goppa which are of the form Ω(mr 2 ).

The main ingredient for proving Theorem 2 consists in analyzing a certain (partial) Gaussian elimination process on the matrix:

M def = p ij p ij ′ 1 i k k+1 j<j ′ n .
We can see the matrix M in block form, each block consists of the matrix:

B j = p i,k+j p i,k+j ′ 1 i k 1 j<j ′ n-k .
Each block B j is of size k × (rm -j). Notice that in B j , the rows for which p i,k+j = 0 consist only of zeros. To start the Gaussian elimination process with B 1 , we will therefore choose rm -1 rows for which p i,k+1 = 0. This gives a square matrix M 1 . We perform Gaussian elimination on M by adding rows involved in M 1 to put the first block B 1 in standard form. We continue this process with B 2 by picking now rm -2 rows which have not been chosen before and which correspond to p i,k+2 = 0. This yields a square submatrix M 2 of size rm -2 and we continue this process until we reach the last block. The key observation is that:

rank(M ) rank(M 1 ) + • • • + rank(M rm-1 ).
A rough analysis of this process yields Theorem 2. The important point is that what happens for different blocks are independent processes and it corresponds to looking at different rows of the matrix P . We give all the previous results that we need in order to prove Theorem 2.

It will be convenient to assume that the columns of M are ordered lexicographically. The index of the first column is (j, j ′ ) = (k + 1, k + 2), the second one is (j, j ′ ) = (k + 1, k + 3), while the last one is (j, j ′ ) = (n -1, n). The matrices M i 's which are involved in the Gaussian elimination process mentioned above are defined inductively as follows. Let E 1 be the subset of {1, . . . , k} of indices s such that p s,k+1 = 0. Let F 1 be the subset of E 1 formed by its first rm -1 elements (if these elements exist). Now , we set

M 1 def = (p s,k+1 p s,j ) s∈F1 k+1<j n . (7)
Let r 1 be the rank of M 1 . To simplify the discussion, we assume that: 1) F 1 = {1, 2, . . . , rm -1}, 2) the submatrix N 1 of M 1 formed by its first r 1 rows and columns is of full rank.

Note that we can always assume this by performing suitable row and column permutations. In other words M has the following block structure:

M = N 1 B 1 A 1 C 1 .
We denote:

M (1) def = N -1 1 O -A 1 N -1 1 I M,
where O is a matrix of size r 1 × (k -r 1 ) with only zero entries and I is the identity matrix of size k -r 1 . Notice that M (1) takes the block form:

M (1) = I B ′ 1 O C ′ 1 .
This is basically performing Gaussian elimination on M in order to have the first r 1 columns in standard form. We then define inductively the E i , F i , M i , M (i) and N i as follows:

E i def = s | 1 s k, p s,k+i = 0 \ i-1 u=1 F i-u , F i def = the first rm -i elements of E i .
M i is the submatrix of M (i-1) obtained from the rows in F i and the columns associated to the indices of the form (k + i, j ′ ) where j ′ ranges from k + i + 1 to n. M (i) is obtained from M (i-1) by first choosing a square submatrix N i of M i of full rank and with the same rank as M i and then by performing Gaussian elimination on the rows in order to put the columns of M (i-1) involved in N i in standard form (i.e., the submatrix of M (i-1) corresponding to N i becomes the identity matrix while the other entries in the columns involved in N i become zero). It is clear that the whole process leading to M (rm-1) amounts to perform (partial) Gaussian elimination to M . Hence: Lemma 1: When |E i | rm -i, for all i ∈ {1, . . . , rm -1}, we have:

rank(M ) rm-1 i=1 rank(M i ).
Another observation is that M i is equal to the sum of the submatrix (p s,k+i p s,j ) s∈Fi k+i<j n of M and a certain matrix which is some function on the entries p t,k+i p t,j where t belongs to F 1 ∪ . . . F i-1 and j ranges over {k + i + 1, n}. Since by definition of F i , p s,k+i is different from 0 for s in F i . In addition, the rank of M i does not change by multiplying each row of index s by p -1 s,k+i . Then, it turns out that the rank of M i is equal to the rank of a matrix which is the sum of the matrix (p s,j ) s∈Fi k+i<j n

, another matrix depending on the p t,k+i p t,j 's (where t ranges over F 1 ∪ . . . F i-1 ) and the p s,k+1 's with s ∈ F i . This proves that: Lemma 2: Assume that |E i | rm -i for all i ∈ {1, . . . , rm -1}. Then, the random variables rank(M i ) are independent and rank(M i ) is distributed as the rank of a square matrix of size rm -i with entries drawn independently from the uniform distribution on F q . Another essential ingredient for proving Theorem 2 is the following well known lemma (see for instance [START_REF] Cooper | On the distribution of rank of a random matrix over a finite field[END_REF]

[Theorem 1])

Lemma 3: There exist two positive constants A and B depending on q such that the probability p(s, ℓ) that a random ℓ × ℓ matrix over F q is of rank ℓ -s (where the coefficients are drawn independently from each other from the uniform distribution on F q ) satisfies A q s 2 p(s, ℓ) B q s 2 .

This enables to control the exponential moments of the defect of a random matrix. For a square matrix M of size ℓ × ℓ, we define the defect d(M ) by d(M ) def = ℓrank(M ). Lemma 4: If M is random square matrix whose entries are drawn independently from the uniform distribution over F q , then there exists some constant K such that for every λ > 0,

E q λd(M) Kq λ 2
4 , E(.) denoting the expectation. Proof: By using Lemma 3, we obtain:

E q λd(M ) ∞ d=0 q λd B q d 2 B ∞ d=0 q λd-d 2 .
Observe that the maximum of the function d → q λd-d 2 is reached for d 0 = λ 2 and is equal to q λ 2 4 . Then, we can write the sum above as:

∞ d=0 q λd-d 2 = d d0 q λd-d 2 + d>d0 q λd-d 2
Finally, we notice that:

q λ(d+1)-(d+1) 2 q λd-d 2 q λ(d0+1)-(d0+1) 2 q λd0-d 2 0 = 1 q for d > d 0 , q λ(d-1)-(d-1) 2 q λd-d 2 q λ(d0-1)-(d0-1) 2 q λd0-d 2 0 = 1 q for d d 0 .
This leads to:

∞ d=0 q λd-d 2 d d0 q d-⌊d0⌋ q λ 2 4 + d>d0 q ⌈d0⌉-d q λ 2 4 = O q λ 2 4
.

We can use now the previous lemma together with Lemma 1 and Lemma 2 to derive the following lemma. Lemma 5: Assuming that |E i | rm -i for all i ∈ {1, . . . , t}, we get:

prob t i=1 d(M i ) u K t q -u 2 t
where K is the constant appearing in Lemma 4.

Proof: Let D def = t i=1 d(M i ). Using Markov's inequality: prob(D u) E(q λD ) q λu (8)
for some well chosen λ > 0. The exponential moment appearing at the numerator is upper-bounded with the help of the previous lemma and by using the independence of the random variables q λd(Mi) , i.e.,:

E(q λD ) = E q λ t i=1 d(Mi) = t i=1 E q λd(Mi) K t q tλ 2 4 . (9)
Using now [START_REF] May | Decoding random linear codes in Õ(2 0.054n )[END_REF] in [START_REF]Smaller decoding exponents: Ball-collision decoding[END_REF], we obtain prob(D αt) K t q tλ 2 4

q λu = K t q tλ 2 4 -λu .

We choose λ = 2u t to minimize this upper-bound, leading to:

prob(D u) K t q -u 2 t .
The last ingredient for proving Theorem 2 is a bound on the probability that E i is too small to construct F i . Lemma 6:

Let u i def = mr 2 -(2rm-i)(i-1)
2 and F be the event "|F j | = rm -j for j ∈ {1, . . . , i -1}" then

prob (|E i | < rm -i | F ) e -2 ( q-1 q u i -rm-i+1 ) 2 u i
.

Proof: When all the sets F j are of size rm -j for j in {1, . . . , i -1}, it remains

N - i-1 j=1 (rm -j) = N - (2rm -i)(i -1) 2 = u i
rows which can be picked up for E i . Let S t be the sum of t Bernoulli variables of parameter q-1 q . We obviously have prob

(|E i | < rm -i | F ) = prob(S ui < rm -i).
It remains to use the Hoeffding inequality on the binomial tails to finish the proof. We are ready now to prove Theorem 2:

Proof of Theorem 2: Let u = ⌈ mrω(mr))⌉. We observe now that if all E j 's are of size at least rm-j for j ∈ {1, . . . , u}, we can write

D = N -rank(M ) N - rm-u i=1 rank(M i ) (by Lemma 1) = rm-1 i=1 (rm -i) - rm-u i=1 rank(M i ) = rm-u i=1 d(M i ) + rm-1 i=rm-u+1 (rm -i) = rm-u i=1 d(M i ) + u(u -1) 2 < rm-u i=1 d(M i ) + mrω(mr) 2 .
From this we deduce that prob D random mrω(mr) prob(A ∪ B)

prob(A) + prob(B)
where A is the event "

rm-u i=1 d(M i ) mrω(mr)
2 " and B is the event "for at least one E j with j ∈ {1, . . . , rm -u} we have |E j | < rm -j". We use now Lemma 5 to prove that prob(A) = o(1) as rm goes to infinity. We finish the proof by noticing that the probability of the complementary set of B satisfies Lemma 6).

prob( B) = prob rm-u i=1 |E i | rm -i = rm-u i=1 prob (|E i | rm -i | F ) = 1 -o(1) (by

VII. ALTERNANT CASE

The goal of this section is to explain the value of the dimension D alternant of Ker(L P ) for q-ary alternant codes of degree r. We shall see that this dimension will be obtained by first identifying a F q m -basis of Ker(L P ) when viewed as a linear system with coefficients in F q m . To set up the linear system L P as defined in (4), we have used the trivial identity

Y i Y i X 2 i = (Y i X i ) 2 . The fundamental remark is that we can use any identity Y i X a i Y i X b i = Y i X c i Y i X d i with a, b, c, d ∈ {0, 1, . . . , r -1} such that a + b = c + d.
Such identities lead to the same algebraic system L P :

(j,j ′ )∈J pi,jp i,j ′ YjX a j Y j ′ X b j ′ + Y j ′ X a j ′ YjX b j + YjX c j Y j ′ X d j ′ + Y j ′ X c j ′ YjX d j = 0 (10)
where by definition

J def = (j, j ′ ) ∈ N × N | k + 1 j < j ′ n . (11)
Consequently, the fact that there are many different ways of combining the equations of the algebraic system together yielding the same linearized system L P explains why the dimension Ker(L P ) is large. Indeed, if a non-trivial solution of X 1 , . . . , X n , Y 1 , . . . , Y n exists then all the expressions of the form

Y j X a j Y j ′ X b j ′ + Y j ′ X a j ′ Y j X b j + Y j X c j Y j ′ X d j ′ + Y j ′ X c j ′ Y j X d j
for all (j, j ′ ) ∈ J, and for all a, b, c, d ∈ {0, 1, . . . , r -1} such that a + b = c + d lead to a solution of the linear system L P .

In what follows, we exhibit further elements of Ker(L P ). To this end, we use the automorphisms x -→ x q ℓ where ℓ is in {0, . . . , m -1}. Indeed, we can also consider the identity:

(Y i X a i ) q ℓ ′ (Y i X b i ) q ℓ = (Y i X c i ) q ℓ ′ (Y i X d i ) q ℓ (12)
for any integers a, b, c, d, ℓ and ℓ ′ such that:

aq ℓ ′ + bq ℓ = cq ℓ ′ + dq ℓ .
We get again the linear system L P . However, assuming that ℓ ′ ℓ, solutions obtained from such equations are exactly those coming from the identity:

Y i X a i Y q ℓ-ℓ ′ i X bq ℓ-ℓ ′ i = Y i X c i Y q ℓ-ℓ ′ i X dq ℓ-ℓ ′ i . (13)
We can focus on vectors that satisfy equations obtained with 0 a, b, c, d < r, 0 ℓ < m and a + q ℓ b = c + q ℓ d i.e., the equations obtained from:

Y i X a i (Y i X b i ) q ℓ = Y i X c i (Y i X d i ) q ℓ .
We now try to determine the number of linearly independent solutions induced by such identities.

Definition 8: Let a, b, c and d be integers in {0, . . . , r -1} and an integer ℓ in {0, . . . , m -1} such that a + q ℓ b = c + q ℓ d. We define U a,b,c,d,ℓ = U a,b,c,d,ℓ j,j ′ (j,j ′ )∈J with

U a,b,c,d,ℓ j,j ′ def = Y j X a j Y q ℓ j ′ X q ℓ b j ′ + Y j X c j Y q ℓ j ′ X q ℓ d j ′ .
In the same way, we set U a,b,c,d,ℓ = U a,b,c,d,ℓ j,j ′ (j,j ′ )∈J

where

U a,b,c,d,ℓ j,j ′ def = Y j ′ X a j ′ Y q ℓ j X q ℓ b j + Y j ′ X c j ′ Y q ℓ j X q ℓ d j .
Finally, we define Z a,b,c,d,ℓ = Z a,b,c,d,ℓ j,j ′ (j,j ′ )∈J such that:

Z a,b,c,d,ℓ j,j ′ def = U a,b,c,d,ℓ j,j ′ + U a,b,c,d,ℓ j,j ′ .
The linear system L P rewrites then as:

k+1 j<j ′ n p i,j p i,j ′ Z a,b,c,d,ℓ j,j ′ = 0.
By construction, there exists relations occurring between some Z a,b,c,d,ℓ 's. For instance we always have Z a,b,a,b,ℓ = 0 for any integers a, b and ℓ. We also have other basic relations: Lemma 7: Let integers a, b, c, d, e, f be in {0, . . . , r -1}, and an integer ℓ be in {0, . . . , m -1} such that a + q ℓ b = c + q ℓ d. We have:

Z a,b,c,d,ℓ + Z c,d,e,f,ℓ = Z a,b,e,f,ℓ .

Without loss of generality, we can assume that d > b and let us set δ = d -b. Moreover, as we have a + q ℓ b = c + q ℓ d, it implies that a = c + q ℓ δ. Thus, any vector Z a,b,c,d,ℓ is uniquely described by the tuple (b, c, δ, ℓ) by setting d = b + δ and a = c + q ℓ δ provided that 1 δ r -1 -b and 0 c + q ℓ δ r -1.

The next proposition shows that some vectors Z c+q ℓ δ,b,c,b+δ,ℓ can be expressed as a linear combination of vectors defined with δ = 1.

Proposition 2: Let ℓ, δ, b and c be integers such that ℓ 0, δ

1, 1 b + δ r -1 and 1 c + q ℓ δ r -1. For all 1 i δ, we set b i def = b + i -1 and c i def = c + q ℓ (δ -i). We have Z c+q ℓ δ,b,c,b+δ,ℓ = δ i=1 Z ci+q ℓ ,bi,ci,bi+1,ℓ . ( 15
)
Proof: When δ = 1, the equality ( 15) is obviously verified. We now assume that δ 2. Let b * def = b + 1, δ * def = δ -1 and c * def = c + q ℓ δ * . Then c * is the integer such that c * + q ℓ = c + q ℓ δ, one can see that c + q ℓ δ * = c + q ℓ (δ -1) = c * . By Lemma 7 we have:

Z c * +q ℓ ,b,c * ,b+1,ℓ + Z c+q ℓ δ * ,b * ,c,b * +δ * ,ℓ = Z c * +q ℓ ,b,c,b * +δ * ,ℓ = Z c+q ℓ δ,b,c,b+δ,ℓ .
This means that

Z c+q ℓ δ,b,c,b+δ,ℓ = Z c * +q ℓ ,b,c * ,b+1,ℓ + Z c+q ℓ δ * ,b * ,c,b * +δ * ,ℓ .
The proof follows by induction.

Remark 1: Note that if we have t 0 a, b, c, d < r, 0 ℓ < m be such that a + q ℓ b = c + q ℓ d then we also have 0 ℓ ⌊log q (r -1)⌋.

From Proposition 2, we can deduce that the set of vectors Z c+q ℓ δ,b,c,b+δ,ℓ obtained with tuples (δ, b, c, ℓ) such that δ = 1 form a spanning set. Actually, we can characterize more precisely this set.

Definition 9: Let B r be the set of nonzero vectors Z c+q ℓ ,b,c,b+1,ℓ | b, c, ℓ . We then have:

B r = Z c+1,b,c,b+1,0 | 0 b < c r -2 Z c+q ℓ ,b,c,b+1,ℓ | 0 b r -2, 1 ℓ ⌊log q (r -1)⌋, 0 c r -1 -q ℓ
We are now in position to conclude for the alternant case. Proposition 3: Let r be an integer such that r 3 and let us denote by |B r | the cardinality of B r . Then:

T alternant = m|B r |.
Proof: Let us set e def = ⌊log q (r -1)⌋. Then the number of elements in B r is given by the number of tuples (b, c, ℓ). Therefore we get:

|B r | = 1 2 (r -1)(r -2) + e ℓ=1 r-2 b=0 (r -q ℓ ) = 1 2 (r -1) r -2 + 2er -2 e ℓ=1 q ℓ = 1 2 (r -1) (2e + 1)r -2 e ℓ=0 q ℓ = 1 m T alternant .
Proposition 3 gives an explanation of the value of D alternant . Indeed, it shows that B r is a F q m -basis that provides a F q -basis of Ker(L P ) by the following heuristic. Heuristic 1: Consider a certain decomposition of the elements of F q m in a F q basis. Let π i : F q m → F q be the function giving the i-th coordinate in this decomposition with 1 i m. By extension we denote for z = (z j ) 1 j n ∈ (F q m ) n by π i (z) the vector (π i (z j )) 1 j n ∈ F n q . Then, for any j such that 1 j n and for random choices of x j 's and y j 's, the set π i (Z) | 1 i m and Z ∈ B r forms a basis of Ker(L P ).

In the next section, we will investigate binary Goppa codes. Note that for q-ary Goppa codes of degree r < q -1 we observed that T alternant = T Goppa . In this case, it is easy to see that (5) simplifies to:

1 2 m(r -1)(r -2) def = T Goppa .
This is due to the fact that e = 0 when r < q -1. We leave as an open question the proof that q-ary Goppa codes of degree r < q -1 behave for our distinguisher as alternant codes. We focus now on the classical case -in code-based cryptography -of binary Goppa codes.

VIII. BINARY GOPPA CASE

The goal of this section is to identify a basis of Ker(L P ) for binary Goppa codes of degree r. We assume therefore that q = 2. In that special case, the theoretical expression T Goppa (Experimental Fact 2) has a simpler expression.

Proposition 4: Let e = ⌈log 2 r⌉ + 1. When q = 2, Equation ( 6) can be simplified to

T Goppa = 1 2 mr (2e + 1)r -2 e -1 .
Theorem 1 shows that a binary Goppa code of degree r can be regarded as a binary alternant code of degree 2r. This seems to indicate that we should have D Goppa (r) = T alternant (2r). This is not the case though. It turns out that D Goppa (r) is significantly smaller than this. In our experiments, we have found out that the vectors of B 2r still form a generating set for Ker(L P ). Unfortunately, they are not independent anymore. Our goal is therefore to identify the additional dependencies occuring in B 2r . We will see that many of them come from F 2 m -relations induced by the Goppa polynomial Γ(z). Recall that by definition Y i = Γ(X i ) -2 . This fact will allow to derive two types of linear dependencies. The first type of linear relations is rather natural, whilst the second type is more subtle.

A. Goppa Polynomials: First Linear Dependencies

We will derive the first linear dependencies by means of the Goppa polynomial Γ(X). Proposition 5: Let t, ℓ and c be integers such that 0 t r -2, 1 ℓ ⌊log 2 (2r -1)⌋ and 0 c 2r -2 ℓ -1. We also set c * def = c + 2 ℓ-1 . It holds that :

r b=0 γ 2 ℓ b Z c+2 ℓ ,t+b,c,t+b+1,ℓ = Z c * +2 ℓ-1 ,2t,c * ,2t+1,ℓ-1 + Z c+2 ℓ-1 ,2t+1,c,2t+2,ℓ-1 . ( 16
)
Proof: Let ℓ, δ, b and c be integers such that ℓ 0, δ 1, 1 b + δ r -1, 1 c + 2 ℓ δ r -1. Let also d = b + δ and a = c + 2 ℓ δ. We can write that for any (j, j ′ ) in J notation being as in [START_REF] Berlekamp | On the inherent intractability of certain coding problems[END_REF] :

U a,b,c,d,ℓ j,j ′ = U c+2 ℓ δ,b,c,b+δ,ℓ j,j ′ = Y j Y 2 ℓ j ′ X a j X 2 ℓ b j ′ + X c j X 2 ℓ d j ′ = Y j Y 2 ℓ j ′ X 2 ℓ b j ′ X a j + X c j X 2 ℓ δ j ′ = Y j Y 2 ℓ j ′ X 2 ℓ b j ′ X c j X 2 ℓ δ j + X 2 ℓ δ j ′ = X δ j + X δ j ′ 2 ℓ Y j X c j Y j ′ X b j ′ 2 ℓ
.

In the same way, we can prove that for all (j, j ′ ) in J:

U c+2 ℓ δ,b,c,b+δ,ℓ j,j ′ = X δ j + X δ j ′ 2 ℓ Y j ′ X c j ′ Y j X b j 2 ℓ
.

Observe now that:

Y j X c j Y j ′ X t+b j ′ 2 ℓ = Y j X c j Y 2 ℓ-1 j ′ X 2 ℓ t j ′ Y j ′ X 2b j ′ 2 ℓ-1 . Let γ b be the coefficient of z b in Γ(z), that is Γ(z) = r b=0 γ b z b . Since Y j ′ Γ(X j ′ ) 2 = 1, we have Y j ′ r b=0 γ 2 b X 2b j ′ = 1. This implies that r b=0 γ 2 b Y 2 j ′ X 2(b+t) j ′ = Y j ′ X 2t j ′ and then: r b=0 γ 2 ℓ b Y j X c j Y j ′ X t+b j ′ 2 ℓ = Y j X c j Y j ′ X 2t j ′ 2 ℓ-1
.

Therefore, we get:

r b=0 γ 2 ℓ b U c+2 ℓ δ,t+b,c,t+b+δ,ℓ = U c ′ +2 ℓ ′ δ ′ ,b ′ ,c ′ ,b ′ +δ ′ ,ℓ ′ (17)
with

ℓ ′ = ℓ -1, δ ′ = 2δ, b ′ = 2t, and c ′ = c. Since c ′ + 2 ℓ ′ δ ′ = c + 2 ℓ δ and c + 2 ℓ δ 2r -1 we have c ′ + 2 ℓ ′ δ ′ 2r -1.
Moreover, we require b ′ + δ ′ 2r -1 which means 2(t + δ) 2r -1. This last inequality implies t + δ r -1.

Similarly, we can prove:

r b=0 γ 2 ℓ b U c+2 ℓ δ,t+b,c,t+b+δ,ℓ = U c ′ +2 ℓ ′ δ ′ ,b ′ ,c ′ ,b ′ +δ ′ ,ℓ ′ .
We are now in position to conclude the proof. Thanks to the previous results:

r b=0 γ 2 ℓ b Z c+2 ℓ ,t+b,c,t+b+1,ℓ = Z c+2 ℓ ,2t,c,2(t+1),ℓ-1
Moreover by Proposition 2, we also have:

Z c+2 ℓ ,2t,c,2(t+1),ℓ-1 = Z c * +2 ℓ-1 ,2t,c * ,2t+1,ℓ-1 + Z c+2 ℓ-1 ,2t+1,c,2t+2,ℓ-1
where by definition c * is equal to c + 2 ℓ-1 . As a consequence, B 2r can not be a basis of Ker(L P ). We count the number of linear dependencies predicted by Proposition 5. Proposition 6: Let N L be the number of equations of the form (16) and let us set u def = ⌊log 2 (2r -1)⌋. Then, the following equality holds:

N L = 2(r -1) (ru + 1 -2 u ) .
Proof: Each equation is defined by a triple (t, c, ℓ). As 0 t r -2, 1 ℓ u and 0 c 2r -2 ℓ -1. Thus:

N L = r-2 t=0 u ℓ=1 (2r -2 ℓ ).

B. Goppa Polynomials: Additional Linear Dependencies

It turns out that there are still other dependencies. To see this, we define the vector Q a,b,c,d,ℓ def = Z a,b,c,d,ℓ j,j ′ 2 (j,j ′ )∈J

. It immediately follows that:

Q a,b,c,d,ℓ j,j ′ = U a,b,c,d,ℓ j,j ′ 2 + U a,b,c,d,ℓ j,j ′ 2 .
We exhibit new linear dependencies between some elements of B 2r and the vectors Q a,b,c,d,ℓ j,j ′ . Proposition 7: For any integers b 0, t 0, δ 1 and ℓ such that 0 ℓ ⌊log 2 (2r -1)⌋ -1, b + δ ≤ 2r -1 and t + 2 ℓ δ r -1, we have

Z 2t+2 ℓ+1 δ,b,2t,b+δ,ℓ+1 = r c=0 γ 2 c Q c+2 ℓ δ,b,t+c,b+δ,ℓ . (18)
Proof: We recall that

Y j Γ(X j ) 2 = 1 implies that r c=0 γ 2 b Y 2 j X 2(c+t) j = Y j X 2t j .
Thus, for any (j, j ′ ) in J, we have:

W def = r c=0 γ 2 c U c+2 ℓ δ,b,t+c,b+δ,ℓ j,j ′ 2 = X δ j + X δ j ′ 2 ℓ+1 Y j ′ X b j ′ 2 ℓ+1 X 2t j Y 2 j r c=0 γ 2 c X 2c j = X δ j + X δ j ′ 2 ℓ+1 Y j ′ X b j ′ 2 ℓ+1 Y j X 2t j = U c ′ +2 ℓ ′ δ,b ′ ,c ′ ,b ′ +δ ′ ,ℓ ′ j,j ′ with ℓ ′ = ℓ + 1, δ ′ = δ, b ′ = b, c ′ = 2t and c ′ + 2 ℓ ′ δ ′ = 2t + 2 ℓ+1 δ.
In particular, one can easily check that the necessary conditions are b + δ ≤ 2r -1 and t + 2 ℓ δ r -1 in order for this equation to hold. We finish the proof by doing the same procedure for

r c=0 γ 2 c U c+2 ℓ δ,b,t+c,b+δ,ℓ j,j ′ 2 = U c ′ +2 ℓ ′ δ,b ′ ,c ′ ,b ′ +δ ′ ,ℓ ′ j,j ′ .
We can count the number of linearly dependencies predicted by Proposition 7.

Proposition 8: Let N Q he number of vectors of B 2r satisfying Equation [START_REF] Faugère | Algebraic cryptanalysis of McEliece variants with compact keys[END_REF] and let us set u def = ⌊log 2 (2r -1)⌋. Then we have that N Q = (2r -1)(ru -2 u + 1).

Proof: By Proposition 7 we know that N Q is the number of vectors Z 2t+2 ℓ+1 δ,b,2t,b+δ,ℓ+1 obtained with δ = 1, b 0, t 0 and satisfying 0 ℓ u -1, b + δ ≤ 2r -1 and t + 2 ℓ δ r -1. Therefore:

N Q = u-1 l=0 r-1-2 ℓ t=0 (2r -1). (19)
We now want to count the number of linear dependencies induced by Proposition 7 and Proposition 5. The difficulty is that some of the N Q vectors of B 2r are counted twice because they appear both in linear relations of the form ( 16) and "quadratic" equations of the form [START_REF] Faugère | Algebraic cryptanalysis of McEliece variants with compact keys[END_REF]. Let N L∩Q be the number of such vectors. More precisely, let B quad 2r be the subset of vectors of B 2r which are involved in an Equation of type [START_REF] Faugère | Algebraic cryptanalysis of McEliece variants with compact keys[END_REF]. There are equations of type ( 16) which involve only vectors of B quad 2r . Let N 1 be their numbers. Moreover, it is possible by adding two equations of type ( 16) involving at least one vector which is not in B quad 2r to obtain an equation which involves only vectors of B quad 2r . Let N 0 be the number of such sums. Finally, let

N L∩Q def = N 1 + N 0 . It is possible to count such equations. Proposition 9: N L∩Q = (r -1) (u -1 2 )r -2 u + 2 where u def = ⌊log 2 (2r -1)⌋.
Proof: We will consider vectors Z c+2 ℓ ,b,c,b+1,ℓ of B 2r that satisfy Equation [START_REF] Faugère | Algebraic cryptanalysis of McEliece variants with compact keys[END_REF] and such that there exists a linear relation that link them. In other words, we consider all the linear relations of the form i α i Z ci+2 ℓ i ,bi,ci,bi+1,ℓi = 0 with α i in F 2 m and where each Z ci+2 ℓ i ,bi,ci,bi+1,ℓi is equal to a linear relation of the form [START_REF] Faugère | Algebraic cryptanalysis of McEliece variants with compact keys[END_REF]. We will see that the number of independent equations is equal to N L∩Q . First, one can observe that for any such vectors we necessary have c i even and

1 ℓ i u.
We also know by Proposition 5 that for any integers t, ℓ and c such that 0 t r -2, 1 ℓ u and 0 c 2r -2 ℓ -1, we have the following linear relation:

r b=0 γ 2 ℓ b Z c+2 ℓ ,t+b,c,t+b+1,ℓ = Z c * +2 ℓ-1 ,2t,c * ,2t+1,ℓ-1 + Z c+2 ℓ-1 ,2t+1,c,2t+2,ℓ-1
where by definition c * = c + 2 ℓ-1 . Note in particular that whenever c is even then c * is also even and if ℓ 2 then we obtain a linear relation between some vectors that also satisfy quadratic equations of the form [START_REF] Faugère | Algebraic cryptanalysis of McEliece variants with compact keys[END_REF]. Each equation enables to remove one quadratic equation. So if we denote by N 1 the number of equations of the form of ( 16) with c even and ℓ 2, we then have:

N 1 = r-2 t=0 u ℓ=2 1 2 (2r -2 ℓ ) = (r -1) u-1 ℓ=1 (r -2 ℓ ) = (r -1) (u -1)r -2 u + 2 . ( 20
)
Moreover in the case ℓ = 1, Equation ( 17) becomes

r b=0 γ 2 b Z c+2,t+b,c,t+b+1,1 = Z c+2,2t,c,2t+2,0 .
In particular, when c is even, say for instance c = 2t ′ for some integer, then this last equation can be rewritten as:

r b=0 γ 2 b Z 2t ′ +2,t+b,2t ′ ,t+b+1,1 = Z 2t ′ +2,2t,2t ′ ,2t+2,0 . (21)
We know that when t ′ = t then Z 2t ′ +2,2t,2t ′ ,2t+2,0 is zero. In that case we obtain new relations between vectors satisfying quadratic equations that are independent even from those obtained with ℓ 2. As for the case when t = t ′ we also have

Z 2t ′ +2,2t,2t ′ ,2t+2,0 = Z 2t+2,2t ′ ,2t,2t ′ +2,0 .
From this identity and from Equation [START_REF] Patterson | The algebraic decoding of Goppa codes[END_REF] we then obtain new relations of the following form:

r b=0 γ 2 b Z 2t ′ +2,t+b,2t ′ ,t+b+1,1 = r b=0 γ 2 b Z 2t+2,t ′ +b,2t,t ′ +b+1,1 . (22)
This last equation involves only vectors that satisfy also quadratic equations. So the number N 0 of equations of the form [START_REF] Van Tilburg | On the McEliece public-key cryptosystem[END_REF] is given by the number of sets {t, t ′ }. But by assumption t and t ′ should satisfy 0 t r -2 and c = 2t ′ with 0 c 2r -3, which implies that 0 t ′ r -2. Therefore, N 0 is equal to the number (t, t ′ ) such that t t ′ and thus we get:

N 0 = r-2 t=0 r-2 t ′ =t = 1 2 (r -1)r. (23)
Finally, by gathering all the cases we therefore obtain that: Moreover, from Proposition 6 and Proposition 9, we can write:

N L∩Q = N 1 + N 0 = (r -1) (u -1)r -2 u + 2 + 1 2 (r -1)r.
N L -N L∩Q = (r -1)(2ur + 2 -2 u+1 ) -(r -1)(ur - r 2 -2 u + 2) = (r -1) (u + 1 2 )r -2 u .
Therefore by gathering all these equalities we obtain:

|B 2r | -(N L + N Q -N L∩Q ) = r (u + 3 2 )r -2 u - 1 2 .
On the other hand from Proposition 4, we have

1 m T Goppa (r) = 1 2 r ((2e + 1)r -2 e -1)
where e = ⌈log 2 r⌉ + 1. Using the basic inequality 2r -1 < 2r < 2(2r -1), we have therefore

log 2 (2r -1) < log 2 (r) + 1 < log 2 (2r -1) + 1
which finally implies ⌈log 2 r⌉ = u. Thus,

1 m T Goppa (r) = 1 2 r (2u + 3)r -2 u+1 -1 .

IX. CONCLUSION AND CRYPTOGRAPHIC IMPLICATIONS

Based upon these experimental observations, it is straightforward to define a distinguisher between random codes, alternant codes and Goppa codes.

Definition 10: Let m and r be integers such that m 1 and r 1. Let G be a k × n matrix whose entries are in F q with n q m and k def = n -rm. Without loss of generality, we assume that G is systematic i.e., G = (I k | P). Let L P be the linear system associated to G as defined in (4), and D be the dimension of Ker(L P ). We define the Random Code Distinguisher D as the mapping which takes as input G and outputs D(G) in {-1, 0, 1} such that:

D(G) =    -1 if D = T alternant 0 if D = T Goppa 1 otherwise. ( 24
)
The existence of a distinguisher for the specific case of binary Goppa codes is not valid for any value of r and m but tends to be true for codes that have a rate n-mr n very close to one. We will elaborate on this point below. This kind of codes are mainly encountered with the signature scheme [START_REF] Courtois | How to achieve a McEliece-based digital signature scheme[END_REF]. If we assume that the length n is equal to 2 m and we denote by r max the smallest integer r such that N -T Goppa 2 m -mr then any binary Goppa code of degree r < r max can be distinguished (Table I). For example, the binary Goppa code obtained with m = 13 and r = 19 corresponding to a 90-bit security McEliece public key is distinguishable. More interestingly, all the keys proposed in [START_REF] Finiasz | Security bounds for the design of code-based cryptosystems[END_REF] for the CFS signature scheme can be distinguished. Asymptotic Behaviour. When the length n of the code goes to infinity an asymptotic formula can be derived for the smallest rate R crit allowing distinguish a random code from an alternant code or a Goppa code. We derive such a formula when we assume for simplicity that the cardinality q of the base field is fixed and n is chosen as n = q m (in practice n is chosen either in this way or at least of the same order as q m ). We also assume that the dimension k of the code satisfies k = n-rm. We denote the rate k/n of the code by R. Finally, we also make the assumption that the dimensions D alternant and D Goppa are given by their theoretical values T alternant and T Goppa respectively and that the dimension of D random is given by T random def = max 0, mr 2 -k . This critical rate r crit corresponds to the smallest value of r for which T random becomes bigger than T alternant (asymptotically there will be no difference between Goppa codes or alternant codes). It holds that:

r crit def = min{r > 0 : T random ≥ T alternant }. We let R crit def = n -r crit m n = 1 - r crit m n .
Our claim is that Theorem 3: Let n = q m . When q is fixed and m tends to infinity, we have

r crit = 2 q m log q m log m 1 + o(1) , R crit = 1 - 2 m log q q m log m 1 + o(1) .
where all logarithms are taken to base 2. The proof of this theorem is given in the appendix.

In Table I, we have computed the value of 2q m log q m log m for several m (q is equal to 2). This shows that our approximation is rather close to r max computed in practice (even for small values of m).

Concluding remarks. We emphasize that the existence of such a distinguisher does not undermine the security of [START_REF] Mceliece | A Public-Key System Based on Algebraic Coding Theory[END_REF] and [START_REF] Courtois | How to achieve a McEliece-based digital signature scheme[END_REF]. It only shows that the GD assumption should be used in any security reduction with great care.

It has also been observed in [START_REF] Marquez-Corbella | Error-correcting pairs for a public-key cryptosystem[END_REF] that our distinguisher is equivalent to consider the dimension of the square code of the dual of the public code. It should be added that this notion has been used recently to cryptanalyze sucessfully two cryptographic schemes both of them relying on modified generalized Reed-Solomon codes [START_REF] Gauthier | A distinguisher-based attack on a variant of McEliece's cryptosystem based on Reed-Solomon codes[END_REF], [START_REF]A distinguisher-based attack of a homomorphic encryption scheme relying on Reed-Solomon codes[END_REF].

Finally, we mention that [START_REF] Dinh | McEliece and Niederreiter cryptosystems that resist quantum Fourier sampling attacks[END_REF] shows that the natural reduction of GD to a hidden subgroup problem yields negligible information. As a consequence, they rule out the direct analogue of a quantum attack using the so-called Quantum Fourier Sampling (QFS) which breaks number theoretic problems [START_REF] Shor | Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer[END_REF]. More precisely, [START_REF] Dinh | McEliece and Niederreiter cryptosystems that resist quantum Fourier sampling attacks[END_REF] shows that QFS has a negligible advantage against GD when the rate is ≥ 1 -

log q (n) 3/2 √ 5n
= R QFS . Whilst our result is somewhat contradictory with [START_REF] Dinh | McEliece and Niederreiter cryptosystems that resist quantum Fourier sampling attacks[END_REF], it is interesting to observe that R crit and the critical rate R QFS share some similarities.

APPENDIX

A. Experimental Results

B. Proof of Theorem 3

To prove Theorem 3 we will first use the following observation Lemma 8: Let T alternant be as defined in [START_REF] Stern | A method for finding codewords of small weight[END_REF]. Let also T Goppa be as defined in [START_REF] Canteaut | 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[END_REF]. There exists constants K 1 and K 2 (resp. Proof: We recall that T alternant def = 1 2 m(r -1) (2e + 1)r -2 q e+1 -1 q -1 where e def = log q (r -1) . First, we remark that there exists some absolute constants K 3 and K 4 such that for all integers r ≥ 2 2r log q (r) + K 3 r ≤ (2e + 1)r -2 q e+1 -1 q -1 ≤ 2r log q (r) + K 4 r.

K ′ 1 and K ′ 1 and K ′ 2 ) such that mr 2 log q (r) + K 1 ≤ T alternant ≤ mr 2 log q (r) + K 2 , ( 25
) mr 2 (log q (r) + K ′ 1 ≤ T Goppa ≤ mr 2 (log q (r) + K ′ 2 . (26)
The upper bound is clear since:

(2e + 1)r -2 q e+1 -1 q -1 ≤ 2r log q (r) + 2r.

For the lower bound, we remark that:

e ≥ log q (r -1) -1 = log q (r) + log q (1 -1/r) -1.

In addition: q e+1 -1 q -1 ≤ q • q e ≤ rq.

As a consequence:

(2e + 1)r -2 q e+1 -1 q -1 ≥ 2r log q (r) + r 2 log q (1 -1/r) -1 -2q .

Finally, remark that log q (1 -1/r) can be bounded from above by some (negative) constant. So, it holds that:

(2e + 1)r -2 q e+1 -1 q -1 ≥ 2r log q (r) + K 3 r, for some constant K 3 .

Observe now that 1 2 m(r -1) 2 log q (r) + K 3 r = 1 2 (mr -m) 2 log q (r) + K 3 r = 1 2 2mr log q (r) + K 3 mr 2 -2m log q (r) -K 3 mr .

The lower bound on T alternant follows immediately from this. The expression can be lower bounded (resp. upper bounded) by a term of the form K 1 mr 2 (resp. K 2 mr 2 ) for some constant K 1 (resp. K 2 ). This holds for all positive integers r. Finally, we recall that

T Goppa def =        1 2
m(r -1)(r -2) = T alternant for r < q -1, 1 2 mr (2e + 1)r -2q e + 2q e-1 -1 for r q -1, with e being the unique integer such that:

(q -1) 2 q e-2 < r (q -1) 2 q e-1 .

The bound [START_REF] Canteaut | Cryptanalysis of the original McEliece cryptosystem[END_REF] on can be proved in the same way.

From this lemma, we deduce that Lemma 9: There exist two constants C 1 and C 2 such that for every r satisfying mr

2

≥ n -mr we have mr 2 m/2 -log q (r) + C 1 -q m ≤ T random -T alternant , (28) mr 2 m/2 -log q (r) + C 2 -q m ≥ T random -T alternant .

(

) 29
We also have the same inequalities when we replace T random -T alternant with T random -T Goppa .

Proof: For all positive integer values of r such that mr 2 ≥ n -mr, we have:

T random = N -k, = mr 2 -q m + mr, = m 2 r 2 /2 -q m + mr/2.
We can then conclude using Lemma 8.

From this lemma, we derive the following estimate for r crit : Lemma 10: When m goes to infinity we have r crit = 2q m log q m log m 1 + o(1) .

Proof: From Lemma 9, we know that:

T random -T alternant = mr 2 m/2 -log q (r) -q m + O(mr 2 ).

Let r 0 def = 2q m log q m log m . It holds that: 2 log q (r 0 ) = log q (2q m log q) -log q (m log m), = m + log q (2 log q) -log q (m) -log q (log m).

Thus: mr 2 0 m/2 -log q r 0 -q m = 2q m log q log m m/2 -m/2 -log(2 log q) 2 log q + log m 2 log q + log log m 2 log q -q m , = q m log m (log log m -log(2 log q)) .

We also observe that mr 2 0 = 2q m log q log m is negligible compared to q m log m (log log m -log(2 log q)) when m goes to infinity. This can be used to show that T random -T alternant is positive for r = ⌈r 0 ⌉ when m is large enough. Therefore for m large enough, we have r crit ≤ ⌈r 0 ⌉.

On the other hand, let α be any positive constant < 1. We set:

r α def =
2αq m log q m log m .

Notice that the function f (x) = mx 2 m/2 -log q x -q m can be shown to be increasing in the range (0, r α ). Therefore for every r ≤ r α , we have mr 2 m/2 -log q r -q m ≤ 2αq m log q log m m/2 -m/2 + log m 2 log q + log log m 2 log q -log(2α log q) 2 log q -q m , ≤ (α -1)q m + 2αq m log q log m log log m 2 log q -log(2α log q) 2 log q , ≤ (α -1)q m + q m α log log m log m .

Since mr 2 ≤ 2αq m log q log m , it follows that any function of the form mr 2 m/2 -log q r -q m + O(mr 2 ) will be negative for m large enough in the range (0, r α ).

This implies that r crit ≥ r α = 2αq m log q m log m for m large enough. We deduce from this fact which holds for any 0 < α < 1 and from the upper bound r crit ≤ ⌈r 0 ⌉ = 2q m log q m log m that r crit = 2q m log q m log m (1 + o( 1)) when m goes to infinity. Finally, the proof of Theorem 3 is now obtained as follows. We have R crit = q m -mr crit q m , = 1 -2 m log q q m log m 1 + o(1) .

Proposition 10 :

 10 For any integer r 2, we have1 m T Goppa (r) = |B 2r | -N L -N Q + N L∩Q . Proof: Set u def = ⌊log 2 (2r -1)⌋.From Equation (5), we have|B 2r | = (2r -1) (2u + 1)r -2 u+1 + 1which implies from Proposition 8|B 2r | -N Q = (2r -1) (2u + 1)r -2 u+1 + 1 -(2r -1) ((ru -2 u + 1))= (2r -1)((u + 1)r -2 u ).

TABLE I A

 I BINARY GOPPA CODE OF LENGTH n = 2 m AND DEGREE r < rmax IS DISTINGUISHABLE FROM A RANDOM CODE.

	m	8 9 10	11	12	13	14	15	16	17	18	19	20	21	22	23
	rmax	5 8	8	11	16	20	26	34	47	62	85	114 157 213 290 400
	⌈r crit ⌉	5 6	8	11	14	19	25	34	46	62	84	114 156 214 293 402

TABLE II q

 II = 2 AND m = 14.

	r	3	4	5	6	7	8	9	10	11	12	13	14	15	16
	N	861	1540	2415	3486	4753	6216	7875	9730	11781 14028 16471 19110 21945 24976
	k	16342 16328 16314 16300 16286 16272 16258 16244 16230 16216 16202 16188 16174 16160
	Drandom	0	0	0	0	0	0	0	0	0	0	269	2922	5771	8816
	Dalternant	42	126	308	560	882	1274	1848	2520	3290	4158	5124	6188	7350	8816
	T alternant	42	126	308	560	882	1274	1848	2520	3290	4158	5124	6188	7350	8610
	DGoppa	252	532	980	1554	2254	3080	4158	5390	6776	8316	10010 11858 13860 16016
	T Goppa	252	532	980	1554	2254	3080	4158	5390	6776	8316	10010 11858 13860 16016

TABLE III q

 III = 2 AND m = 14.

	r	17	18	19	20	21	22	23	24	25	26	27	28	29	30
	N	28203 31626 35245 39060 43071 47278 51681 56280 61075 66066 71253 76636 82215 87990
	k	16146 16132 16118 16104 16090 16076 16062 16048 16034 16020 16006 15992 15978 15964
	Drandom	12057 15494 19127 22956 26981 31202 35619 40232 45041 50046 55247 60644 66237 72026
	Dalternant 12057 15494 19127 22956 26981 31202 35619 40232 45041 50046 55247 60644 66237 72026
	T alternant 10192 11900 13734 15694 17780 19992 22330 24794 27384 30100 32942 35910 39004 42224
	DGoppa	18564 21294 24206 27300 30576 34034 37674 41496 45500 50046 55247 60644 66237 72026
	T Goppa	18564 21294 24206 27300 30576 34034 37674 41496 45500 49686 54054 58604 63336 68250

TABLE IV q

 IV = 2 AND m = 15.

	r		3	4	5	6	7	8	9	10		11	12	13	14	15	16
	N		990	1770	2775	4005	5460	7140	9045	11175	13530 16110	18915 21945 25200	28680
	k	32723	32708 32693 32678	32663 32648	32633 32618	32603 32588	32573 32558 32543	32528
	D random	0	0	0	0	0	0	0	0		0	0	0	0	0	0
	D Goppa		270	570	1050	1665	2415	3300	4455	5775	7260	8910	10725 12705 14850	17160
	T Goppa		270	570	1050	1665	2415	3300	4455	5775	7260	8910	10725 12705 14850	17160
								TABLE V
								q = 2 AND m = 15.
	r		17	18	19	20	21	22	23	24		25	26	27	28	29	30
	N	32385 36315 40470	44850 49455	54285 59340	64620 70125	75855 81810 87990	94395 101025
	k	32513 32498 32483	32468 32453	32438 32423	32408 32393	32378 32363 32348	32333	32318
	D random		0	3817	7987	12382 17002	21847 26917	32212 37732	43477 49447 55642	62062	68707
	D Goppa	19890 22815 25935	29250 32760	36465 40365	44460 48750	53235 57915 62790	67860	73125
	T Goppa	19890 22815 25935	29250 32760	36465 40365	44460 48750	53235 57915 62790	67860	73125
								TABLE VI
								q = 2 AND m = 15.
	r	31		32	33	34	35	36	37		38		39	40	41	42	43	44
	N	107880 114960	122265 129795	137550 145530	153735 162165	170820 179700	188805 198135	207690 217470
	k	32303	32288	32273	32258	32243	32228	32213	32198	32183	32168	32153	32138	32123	32108
	D random	75577	82672	89992	97537	105307 113302	121522 129967	138637 147532	156652 165997	175567 185362
	D Goppa	78585	84240	90585	97537	105307 113302	121522 129967	138637 147532	156652 165997	175567 185362
	T Goppa	78585	84240	90585	97155	103950 110970	118215 125685	133380 141300	149445 157815	166410 175230

TABLE VII q

 VII = 2 AND m = 16.

	r	3	4	5	6	7	8	9	10	11	12	13	14	15	16
	N	1128	2016	3160	4560	6216	8128	10296 12720	15400 18336	21528 24976 28680	32640
	k	65488	65472 65456 65440	65424 65408	65392 65376	65360 65344	65328 65312 65296	65280
	D random	0	0	0	0	0	0	0	0	0	0	0	0	0	0
	D Goppa	288	608	1120	1776	2576	3520	4752	6160	7744	9504	11440 13552 15840	18304
	T Goppa	288	608	1120	1776	2576	3520	4752	6160	7744	9504	11440 13552 15840	18304
							TABLE VIII
							q = 2 AND m = 16.
	r	17	18	19	20	21	22	23	24	25	26	27	28	29	30
	N	36856	41328 46056	51040 56280	61776 67528	73536 79800	86320 93096 100128	107416 114960
	k	65264	65248 65232	65216 65200	65184 65168	65152 65136	65120 65104	65088	65072	65056
	D random	0	0	0	0	0	0	2360	8384	14664	21200 27992	35040	42344	49904
	D Goppa	21216	24336 27664	31200 34944	38896 43056	47424 52000	56784 61776	66976	72384	78000
	T Goppa	21216	24336 27664	31200 34944	38896 43056	47424 52000	56784 61776	66976	72384	78000

TABLE IX q

 IX = 2 AND m = 16.

	r	31	32	33		34	35	36	37		38	39	40	41		42	43
	N	122760	130816 139128	147696 156520	165600 174936	184528 194376	204480 214840	225456 236328
	k	65040	65024	65008	64992	64976	64960	64944	64928	64912	64896	64880	64864	64848
	D random	57720	65792	74120	82704	91544	100640 109992	119600 129464	139584 149960	160592 171480
	D Goppa	83824	89856	96624	103632 110880	118368 126096	134064 142272	150720 159408	168336 177504
	T Goppa	83824	89856	96624	103632 110880	118368 126096	134064 142272	150720 159408	168336 177504
								TABLE X
								q = 4 AND m = 6.
		r	3	4	5	6	7	8	9	10	11	12	13	14	15	16
		N	153	276	435	630	861	1128 1431 1770	2145 2556	3003 3486 4005	4560
		k	4078 4072 4066	4060 4054	4048 4042 4036	4030 4024	4018 4012 4006	4000
		D random	0	0	0	0	0	0	0	0	0	0	0	0	0	560
		D alternant	6	18	60	120	198	294	408	540	690	858	1044 1248 1470	1710
		T alternant	6	18	60	120	198	294	408	540	690	858	1044 1248 1470	1710
		D Goppa	18	60	120	198	294	408	540	750	990	1260	1560 1890 2250	2640
		T Goppa	18	60	120	198	294	408	540	750	990	1260	1560 1890 2250	2640

TABLE XI q

 XI = 4 AND m = 6.

	r	17	18	19	20	21	22	23	24	25	26	27	28	29	30
	N	5151 5778	6441 7140	7875 8646 9453	10296 11175	12090 13041 14028	15051 16110
	k	3994 3988	3982 3976	3970 3964 3958	3952	3946	3940	3934	3928	3922	3916
	D random	1157 1790	2459 3164	3905 4682 5495	6344	7229	8150	9107	10100	11129 12194
	D alternant	2064 2448	2862 3306	3905 4682 5495	6344	7229	8150	9107	10100	11129 12194
	T alternant	2064 2448	2862 3306	3780 4284 4818	5382	5976	6600	7254	7938	8652	9396
	D Goppa	3060 3510	3990 4500	5040 5610 6210	6840	7500	8190	9107	10100	11129 12194
	T Goppa	3060 3510	3990 4500	5040 5610 6210	6840	7500	8190	8910	9660	10440 11250

This kind of attack is called a Chosen Plaintext Attack (CPA).

Similarly to random codes, Goppa codes asymptotically meet the Gilbert-Varshamov bound. They have also a trivial permutation group like random codes.

According to[START_REF] Courtois | How to achieve a McEliece-based digital signature scheme[END_REF], proving or disproving the hardness of the GD problem will have a significant impact: "Classification issues are in the core of coding theory since its emergence in the 50's. So far nothing significant is known about Goppa codes, more precisely there is no known property invariant by permutation and computable in polynomial time which characterizes Goppa codes. Finding such a property or proving that none exists would be an important breakthrough in coding theory and would also probably seal the fate, for good or ill, of Goppa code-based cryptosystems".

There is no hash function in this model