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

Ludovic Perret
email: ludovic.perret@lip6.fr

Frédéric De Portzamparc
email: frederic.urvoydeportzamparc@gemalto.com

Algebraic Attack against Variants of McEliece with Goppa Polynomial of a Special Form

Keywords: public-key cryptography, McEliece cryptosystem, algebraic cryptanalysis

In this paper, we present a new algebraic attack against some special cases of Wild McEliece Incognito, a generalization of the original McEliece cryptosystem. This attack does not threaten the original McEliece cryptosystem. We prove that recovering the secret key for such schemes is equivalent to solving a system of polynomial equations whose solutions have the structure of a usual vector space. Consequently, to recover a basis of this vector space, we can greatly reduce the number of variables in the corresponding algebraic system. From these solutions, we can then deduce the basis of a GRS code. Finally, the last step of the cryptanalysis of those schemes corresponds to attacking a McEliece scheme instantiated with particular GRS codes (with a polynomial relation between the support and the multipliers) which can be done in polynomial-time thanks to a variant of the Sidelnikov-Shestakov attack. For Wild McEliece & Incognito, we also show that solving the corresponding algebraic system is notably easier in the case of a non-prime base field Fq. To support our theoretical results, we have been able to practically break several parameters defined over a non-prime base field q ∈ {9, 16, 25, 27, 32}, t 6, extension degrees m ∈ {2, 3}, security level up to 2 129 against information set decoding in few minutes or hours.

Introduction

Algebraic cryptanalysis is a general attack technique which reduces the security of a cryptographic primitive to the difficulty of solving a non-linear system of equations. Although the efficiency of general polynomial system solvers such as Gröbner bases, SAT solvers . . ., is constantly progressing such algorithms all face the intrinsic hardness of solving polynomial equations. As a consequence, the success of an algebraic attack relies crucially in the ability to find the best modelling in term of algebraic equations.

In [START_REF] Faugère | Algebraic cryptanalysis of Mceliece variants with compact keys[END_REF][START_REF] Faugère | Algebraic Cryptanalysis of McEliece variants with compact keys -toward a complexity analysis[END_REF], Faugère, Otmani, Perret and Tillich (FOPT) show -in particular -that the key-recovery of McEliece [START_REF] Mceliece | A Public-Key System Based on Algebraic Coding Theory[END_REF] can be reduced to the solving of a system of non-linear equations. This key-recovery system can be greatly simplified for socalled compact variants of McEliece, e.g. [START_REF] Berger | Reducing key length of the McEliece cryptosystem[END_REF][START_REF] Misoczki | Compact McEliece keys from Goppa codes[END_REF][START_REF] Barreto | Monoidic codes in cryptography[END_REF][START_REF] Heyse | Implementation of McEliece based on quasi-dyadic Goppa codes for embedded devices[END_REF][START_REF] Persichetti | Compact McEliece keys based on quasi-dyadic srivastava codes[END_REF][START_REF] Barbier | Key reduction of McEliece's cryptosystem using list decoding[END_REF], leading to an efficient attack against various compact schemes [START_REF] Faugère | Algebraic cryptanalysis of Mceliece variants with compact keys[END_REF][START_REF] Faugère | Structural cryptanalysis of McEliece schemes with compact keys[END_REF]. However, it is not clear whether the attack of [START_REF] Faugère | Algebraic cryptanalysis of Mceliece variants with compact keys[END_REF][START_REF] Faugère | Algebraic Cryptanalysis of McEliece variants with compact keys -toward a complexity analysis[END_REF] could be efficient against non-compact variants of McEliece, the bottleneck being the huge number of variables and the high degree of the equations involved in the algebraic modelling.

We present a novel algebraic modelling that applies to the original McEliece system and to generalizations such as Wild McEliece [START_REF] Bernstein | Wild McEliece[END_REF] and Wild McEliece Incognito [START_REF] Bernstein | Wild McEliece incognito[END_REF]. Note, however, that the resulting attack works only in some special cases, and in particular does not work for the original McEliece system. Wild McEliece uses Wild Goppa codes, that is Goppa codes over F q , q 2, with a Goppa polynomial of the form Γ q-1 (Γ being an univariate polynomial of low degree). This form of the Goppa polynomial, generalizing the form used in the original McEliece system for q = 2, allows to increase the number of errors that can be added to a message (in comparison to a random Goppa polynomial of the same degree). In [START_REF] Bernstein | Wild McEliece incognito[END_REF], Bernstein, Lange, and Peters generalized this idea by using Goppa polynomials of the form f Γ q-1 , with f another univariate polynomial. We shall call such Goppa codes Masked Wild Goppa codes. Like the authors of [START_REF] Bernstein | Wild McEliece incognito[END_REF], we refer to this version as Wild McEliece Incognito. All in all, Wild McEliece/Wild McEliece Incognito allow the users to select parameters with a resistance to all known attacks, so in particular to the algebraic attack of [START_REF] Faugère | Algebraic cryptanalysis of Mceliece variants with compact keys[END_REF][START_REF] Faugère | Algebraic Cryptanalysis of McEliece variants with compact keys -toward a complexity analysis[END_REF], similar to that of binary Goppa codes but with much smaller keys. The security of Wild McEliece defined over quadratic extension has been recently investigated in [START_REF] Couvreur | Polynomial time attack on wild McEliece over quadratic extensions[END_REF], where the authors presented a polynomial time attack on the key when t = deg(Γ ) > 1.

Our Contributions

We present a completely new algebraic attack dedicated to Wild McEliece and Wild McEliece Incognito. To do so, we show that the key-recovery for such schemes is equivalent to finding the basis of a vector-space which is hidden in the zero-set of an algebraic system. To our knowledge, this is a new computational problem that never appeared in algebraic cryptanalysis before. Compared to the algebraic attack proposed in [START_REF] Faugère | Algebraic cryptanalysis of Mceliece variants with compact keys[END_REF] for McEliece, our modelling intrinsically involves less variables. Informally, the multiplicity of the Goppa polynomial implies that the solutions of the algebraic system considered here have a structure of vector space. When the base field is F q with q > 2, this simplifies its resolution. For instance, for a Wild McEliece Incognito scheme with parameters q = 32, m = 2, n = 864, t = 2, deg(f ) = 36), we end up with an algebraic system having only 9 variables ( [START_REF] Faugère | Algebraic cryptanalysis of Mceliece variants with compact keys[END_REF] would require to consider algebraic equations with 1060 variables in the same situation). On a very high level, our attack proceeds in two main steps. dimension d. Consequently, we can reduce the number of variables by fixing d variables in the initial and repeat several times the solving step to recover a basis of the vector space solution. This is the most computationally difficult part of the attack. 2. Linear algebra to recover the secret key. The second phase is the treatment of the solutions obtained at the first step so as to obtain a private description which allows to decode the public-key as efficiently as the private key. It involves computing intersections of vector spaces, solving linear systems, and polynomial interpolation. Thus, this part can be done efficiently, i.e. in polynomial time.

We detail below the main ingredients of our attack.

An Algebraic Modelling with a Vector Space Structure on the Zero Set. Let G pub = (g i,j ) 0 i n-1

0 j k-1
∈ F k×n q be the public matrix of a Wild McEliece Incognito scheme. We denote by m its extension degree, and set t = deg(Γ ). Our attack considers the system

W q,a (Z) = u∈Pa    n-1 j=0 g i,j Z u j = 0 | 0 i k -1    , (1)
with P a = {1, 2, . . . , p a -1} ∪ {p a , p a+1 , . . . , q} being a subset of {1, . . . , q}.

As a comparison, the modelling of Faugère, Otmani, Perret and Tillich [14] will necessarily introduce variables X = (X 0 , . . . , X n-1 ), Y = (Y 0 , . . . , Y n-1 ) and W = (W 0 , . . . , W n-1 ) for all the support and multipliers (that is, the vectors y = Γ (x) -1 and w = f (x) -1 ). In [START_REF] Faugère | Algebraic cryptanalysis of Mceliece variants with compact keys[END_REF], the system is as follows:

0 u t-1    n-1 j=0 g i,j Y j X u j = 0 | 0 i k -1    .
In our context, [START_REF] Faugère | Algebraic cryptanalysis of Mceliece variants with compact keys[END_REF] would induce a system containing monomials of the forms

Y ℓ Y i X ℓ X i and even Y ℓ Y i X ℓ X i W ℓ W i (for some ℓ X , ℓ Y , ℓ W ).
Here, we use a single vector of variables Z = (Z 0 , . . . , Z n-1 ) and write very simple homogeneous equations. The secret-key x, y and w will be recovered from Z, but in a second step. The main advantage of this approach (Theorem 2) is that the solutions of W q,a (Z) have a very unexpected property for a non-linear system: they form a vector space. This allows to reduce the number of "free" unknowns in W q,a (Z) by the dimension of the solutions. For example, we end up with a system containing only 9 variables for an Incognito scheme with parameters q = 32, m = 2, n = 864, t = 2, deg(f ) = 36). The algebraic description of Goppa codes proposed in [START_REF] Faugère | Algebraic cryptanalysis of Mceliece variants with compact keys[END_REF] would require to consider algebraic equations with 1060 variables for the same parameters.

To be more precise, the vector space underlying the solutions of (1) is closely related to Generalized Reed-Solomon (GRS) codes.

Definition 1 (Generalized Reed-Solomon codes). Let x = (x 0 , . . . , x n-1 ) ∈ (F q m ) n where all x i 's are distinct and y = (y 0 , . . . , y n-1 ) ∈ F * q m n . The Generalized Reed-Solomon code of dimension t, denoted by GRS t (x, y), is defined as follows

GRS t (x, y) def = (y 0 Q(x 0 ), . . . , y n-1 Q(x n-1 )) | Q ∈ F q m [z], deg(Q) t -1 .
We shall call x the support of the code, and y the multipliers.

Theorem 2 shows that the solutions of W q,a (Z) contain a vector-space which is generated by sums of codewords of Generalized Reed-Solomon (GRS) codes GRS t (x ℓ , y ℓ ) (where (x, y) is a key equivalent to the secret key). In Section 3.2, we explain more precisely how we can take advantage of this special structure for solving [START_REF] Barbier | Key reduction of McEliece's cryptosystem using list decoding[END_REF] and recover a basis of the vector subspace.

A Method to Isolate a GRS Code From a Sum of GRS. From a basis of this sum of GRS, we want to recover the basis of the code GRS t (x, y). We refer to this phase as the disentanglement. We expose our solution in Section 4, which relies on a well-chosen intersection of codes. It is rigorously proved in characteristic 2 (Proposition 6). For other characteristics, we launched more than 100, 000 experiments and observed that Proposition 6 still held in all cases.

A Sidelnikov-Shestakov-Like Algorithm Recovering the Goppa Polynomial. Given a basis of a Generalized Reed-Solomon code GRS t (x, y), the Sidelnikov-Shestakov attack [START_REF] Sidelnikov | On the insecurity of cryptosystems based on generalized Reed-Solomon codes[END_REF] consists in recovering the secret pair of vectors (x, y). It is well-known that the Sidelnikov-Shestakov attack works in polynomialtime. In our case, we have to address a slight variant of this problem. There is a polynomial relation Γ (z) linking x and y which is part of the private key. In Section 4.2, we provide an adaptation of [START_REF] Sidelnikov | On the insecurity of cryptosystems based on generalized Reed-Solomon codes[END_REF] to obtain a key (x ′ , y ′ , Γ ′ ) equivalent to the secret key, also in polynomial time. We are unaware of such an algorithm published so far.

A Weakness of Codes Defined Over non-prime Base Fields. Independently of our algebraic attack, we prove a general result about Goppa codes defined over F q (with q = p s , p prime and s > 0) and whose polynomials have a factor Γ (z) with multiplicity q. We show in Section 5 that the coordinate-vectors over F p of the codewords of such a public code are codewords of a Wild Goppa code, defined over F p , with same secret support and Goppa polynomial Γ (z) p (Theorem 8). In other words, this construction gives access, from the public key, to a new code implying the same private elements. As a consequence, using non-prime base fields reveals more information on the secret key than expected by the designers. Any key-recovery attack can benefit from it. This is then an intrinsic weakness of Goppa codes defined over non-prime base fields. In our context, this property provides additional linear equations between the variables Z j 's of the system (1). We can reduce the number of variables from (p s -1)mt to (p -1)mst essential variables, and make the codes defined over fields F q with q = p s notably weaker (Corollary 10).

Impact of our Work

In order to evaluate the efficiency of our attack, we considered various parameters for which [START_REF] Bernstein | Wild McEliece[END_REF] said that strength is "unclear" and that an attack would not be a "surprise" but for which no actual attack was known.

Information Set Decoding (ISD) is a generic decoding technique which allows message-recovery. This technique has been intensively studied since 1988 (e.g. [START_REF] Leon | A probabilistic algorithm for computing minimum weights of large error-correcting codes[END_REF][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][START_REF] Bernstein | Attacking and defending the McEliece cryptosystem[END_REF][START_REF] Bernstein | Smaller decoding exponents: Ball-collision decoding[END_REF][START_REF] May | Decoding random linear codes in O(2 0.054n )[END_REF][START_REF] Becker | Decoding random binary linear codes in 2 n/20 : How 1 + 1 = 0 improves information set decoding[END_REF]) and remains the reference to choose secure parameters in codebased cryptography. The latest results from [START_REF] Peters | Information-set decoding for linear codes over Fq[END_REF] have been used to generate the parameters for Wild McEliece and Wild McEliece Incognito.

In [6, Table 7.1] numerous keys are presented which illustrate the key size reduction when the size of the field q grows. Another consequence of increasing q is pointed out by the authors of [START_REF] Bernstein | Wild McEliece[END_REF]: the low number of irreducible polynomials in F q m [z] entails a possible vulnerability against the SSA structural attack ( [START_REF] Loidreau | Weak keys in the McEliece public-key cryptosystem[END_REF][START_REF] Sendrier | Finding the permutation between equivalent linear codes: The support splitting algorithm[END_REF]). Although the designers provide a protection (using non full-support codes) such that [START_REF] Loidreau | Weak keys in the McEliece public-key cryptosystem[END_REF] is completely infeasible today, they warn that further progress in [START_REF] Loidreau | Weak keys in the McEliece public-key cryptosystem[END_REF] may jeopardize the parameters with q > 9 and thus estimate that those parameters have unclear security. Our experiments reveal that, in the case of non-prime base fields, it is already possible to recover the secret key in some minutes with our attack using off-the-shelf tools (Magma [START_REF] Bosma | The Magma algebra system I: The user language[END_REF] V2. .

Getting around the alleged vulnerability against SSA was the main motivation for proposing Incognito: in [8, Table 5.1], they propose parameters considered fully secure, as all ISD-complexities are above 2 128 and numbers of possible Goppa polynomials greater than 2 256 . It turns out that, in the case of nonprime base fields, the extra-shield introduced in Incognito is not a protection against our attack. We can practically break the recommended parameters for q ∈ {16, 27, 32}. However, we could not solve (in less than two days) the algebraic systems involved for extension degrees m 4 or t 7, and for codes over F p , p prime. So, it does not threaten the original McEliece cryptosystem. To conclude, we highlight that Theorem 2 is valid for all Goppa codes whose Goppa polynomial has multiplicities and should be then taken into account by designers in the future. Figure 1 provides a diagram which recapitulates all the steps performed to solve the system (1) and recover the secret key.

Coding Theory Background

Let F q be a finite field of q = p s elements (p prime, and s > 0). To define conveniently the various kinds of codes we will deal with, we introduce the following Vandermonde-like matrices:

V t (x, y) def =      y 0 • • • y n-1 y 0 x 0 • • • y n-1 x n-1 . . . . . . y 0 x t-1 0 • • • y n-1 x t-1 n-1      , (2)
where x = (x 0 , . . . , x n-1 ), y = (y 0 , . . . , y n-1

) ∈ F n q m × F n q m . Wq,a(Z) = u∈Pa n-1 j=0 gi,jZ u j = 0 | 0 i k -1
We solve the system several times by fixing many variables.

       Solve(Wq,a(Z) {Z = (1, . . . , 0, Zd a , . . . , Zn-1)}) → v (0) . . . . . . Solve (Wq,a(Z) {Z = (0, . . . , 1, Zd a , . . . , Zn-1)}) → v (da-1) CΣ = Span v (0) , . . . , v (da-1) = ℓ∈La GRSt(x ℓ , y ℓ )
We perform the Fröbenius alignement to have a cleaner vector space (i.e. same Fröbenius power on all the solutions).

We perform a suitable intersection CΣ ∩ (CΣ) p s-a to recover a single GRS.

GRSt(x, y) p s-a

We adapt Sidelnikov-Shestakov attack to recover the secret key.

Secret x, y, Γ (z) Secret f (z) for incognito
For Incognito, a extra linear algebra step allows to recover the last part of the secret key. With suitable x and y, the rows of such matrices V t (x, y) define Generalized Reed-Solomon (GRS) codes (Definition 1). Alternant and Goppa codes can be viewed as the restriction of duals of GRS codes to the base field F q .

Definition 2 (Alternant/Goppa Codes). Let x = (x 0 , . . . , x n-1 ) ∈ (F q m ) n where all x i 's are distinct and y ∈ (F * q m ) n . The alternant code of order t is defined as A t (x, y)

def = c ∈ F n q | V t (x, y)c T = 0 .
As for GRS codes, x is the support, and y the multipliers. Let g(z) ∈ F q m [z] be of degree t satisfying g(x i ) = 0 for all i, 0 i n -1. We define the Goppa code over F q associated to g(z) as the code G q (x, g(z)) def = A t (x, y), with y = g(x) -1 . The dimension k of G q (x, g(z)) satisfies k n -tm. The polynomial g(z) is called the Goppa polynomial, and m is the extension degree. Equivalently, G q x, g(z) can be defined as:

G q x, g(z) def = c = (c 0 , . . . , c n-1 ) ∈ F n q | n-1 i=0 c i z -x i ≡ 0 mod g(z) .
Goppa codes naturally inherit a decoding algorithm that corrects up to t 2 errors. This bound can be improved to correct more errors by using Wild Goppa codes, introduced by Bernstein, Lange, and Peters in [START_REF] Bernstein | Wild McEliece[END_REF]. We also recall the version of Wild Goppa code used in Wild McEliece Incognito [START_REF] Bernstein | Wild McEliece incognito[END_REF]. We call such special version of Wild Goppa codes: Masked Wild Goppa codes. Definition 3 (Wild Goppa/Masked Wild Goppa). Let x be an n-tuple (x 0 , . . . , x n-1 ) of distinct elements of

F q m . Let Γ (z) ∈ F q m [z] (resp. f (z) ∈ F q m [z]) be a squarefree polynomial of degree t (resp. u) satisfying Γ (x i ) = 0 (resp. f (x i ) = 0) for all i, 0 i n -1. A Wild Goppa code is a Goppa code whose Goppa polynomial is of the form g(z) = Γ (z) q-1 . A Masked Wild Goppa code is a Wild Goppa code whose Goppa polynomial is such that g(z) = f (z)Γ (z) q-1 .
The reason for using those Goppa polynomials lies in the following result.

Theorem 1. [START_REF] Bernstein | Wild McEliece[END_REF][START_REF] Bernstein | Wild McEliece incognito[END_REF] Let the notations be as in Definition 3. It holds that

G q x, f (z)Γ q-1 (z) = G q x, f (z)Γ q (z) .
(3)

Thus, the code G q x, f (z)Γ q (z) has dimension n -m ((q -1)t + u).
This is a generalization of a well-known property for q = 2. The advantage of Wild Goppa codes (i.e. f = 1) compared to standard Goppa codes is that ⌊qt/2⌋ errors can be decoded efficiently (instead of ⌊(q -1)t/2⌋) for the same code dimension (n -(q -1)mt in most cases). In fact, we can decode up to ⌊qt/2⌋ + 2 using list decoding. This increases the difficulty of the syndrome decoding problem. Hence, for a given level of security, codes with smaller keys can be used (for details, see [6, Section 7] and [8, Section 5]).

An Algebraic Modelling with a Vector Space Structure on the Zero Set

The core idea of our attack is to construct, thanks to the public matrix, an algebraic system whose solution set S has a very surprising structure (Definition 4 ). It appears that S includes the union of several vector spaces. The vector spaces correspond in fact to sums of GRS codes (Definition 1) which have almost the same support x and multiplier vector y as the public-key of the attacked Wild McEliece Incognito scheme (Theorem 3). These vectors give a key-equivalent to the secret-key.

Description of the New Modelling

We consider the following algebraic equations: Definition 4. Let q = p s (p prime and s 0). Let G pub = (g i,j ) 0 i n-1

0 j k-1
be a generator matrix of a masked Wild Goppa code C pub = G q (x, f (z)Γ q-1 (z)). For an integer a, 0 < a s, we define the system W q,a (Z) as follows :

W q,a (Z) = u∈Pa    n-1 j=0 g i,j Z u j = 0 | 0 i k -1    ( 4
)
with P a = {1, 2, . . . , p a -1} ∪ {p a , p a+1 , . . . , q}.

The parameter a in P a determines the exponents considered for the Z j 's in the system (4). For a = s, we consider all the powers Z u j where u ranges in {1, . . . , q}. Removing some exponents leads to a system with fewer equations and may seem counter-intuitive at first sight (the more equations, the better it is for solving a polynomial system). However, the situation is different here due to the specific structure of the solutions of W q,a (Z), described in the following theorem.

Theorem 2. Let the notations be as in Definition 4. Let y = Γ (x) -1 , t = deg(Γ ) and L a = 0 r s-1-a {p r , 2p r , . . . , (p -1)p r } ∪ {p s-a }. The solutions S of W q,a (Z) contain the union of m vector spaces which are sums of GRS codes:

0 e m-1 ℓ∈La GRS t (x ℓ , y ℓ ) q e ⊆ S,
with GRS t (x ℓ , y ℓ ) q e denoting all the elements of GRS t (x ℓ , y ℓ ) with coordinates raised to the power q e , with 0 e m -1.

Remark 1. When all the powers {1, . . . , q} are considered in the system, that is a = s, then L a is reduced to {1} and the solution set is a union of GRS codes. If a < s, the solution set is a bit more complex, but it has the great advantage of having a larger dimension; allowing then to solve the system (4) more efficiently. We will formalize this in Section 3.2.

Note that we state in Theorem 2 that we know a subset of the solutions. In practice, as the system is highly overdefined, we always observed that this subset was all the solutions.

Proof. The full proof of this result is postponed in Section A.3. We just give the global idea of the proof. The goal is to show the elements of ℓ∈La GRS t (x ℓ , y ℓ ) q e are solutions of W q,a (Z). We can assume that e = 0 w.lo.g.

Let z = (z 1 , . . . , z n ) ∈ ℓ∈La GRS t (x ℓ , y ℓ ). We write the coordinates of z as z j = ℓ∈La y ℓ j Q ℓ (x ℓ j ), where the Q ℓ 's are polynomials of degree t -1 of F q m [z]. We have to prove that n-1 j=0 g i,j z u j = 0 for u ∈ P 1 ∪ P 2 , where P 1 = {1, 2, . . . , p a -1}, P 2 = {p a , . . . , p s }.

The idea is to develop z u j = ℓ∈La y ℓ j Q ℓ (x ℓ j ) u with Newton multinomial.

The development is performed slightly differently whether u ∈ P 1 or u ∈ P 2 (see Appendix A.3). In both cases, we end up with a result of the form z u j = ux,uy α ux,uy y uy j x ux j , so that our sum writes:

n-1 j=0 g i,j z u j = ux,uy   α ux,uy n-1 j=0 g i,j y uy j x ux j   . (5)
Then, we apply the next lemma (proved in Appendix A.2).

Lemma 3 Let G pub be a generator matrix of a masked Wild Goppa code

C pub = G q (x, f (z)Γ q-1 (z)),y = Γ (x) -1 , w = f (x) -1 and t = deg(Γ (z).
The values of x, y, and w satisfy the following set of equations for any value of u x , u y , u, b verifying the conditions 0 u y q, 0 u

x u y t -1, 0 u deg(f ) -1, b ∈ {0, 1} and (b, u y ) = (0, 0): n-1 j=0 g i,j (w i x u i ) b y uy j x ux j = 0 | 0 i k -1 .
We set b = 0 and obtain that n-1 j=0 g i,j y uy j x ux j = 0 for (u y , u x ) such that 1 u y t and 0 u x u y t -1. Thus to conclude that n-1 j=0 g i,j z u j = 0, we check that all the couples (u x , u y ) appearing in the sum (5) satisfy those conditions.

Recovering a Basis of the Vector Subspace

We now explain more precisely how to use the particular structure of the solution set for solving the non-linear system (4). When looking for a vector in a subspace of F n q m of dimension d, then you can safely fix d coordinates arbitrarily and complete the n -d so as to obtain a vector of this subspace. This corresponds to computing intersections of your subspace with d hyperplanes. With this idea, we deduce the following corollary of Theorem 2.

Corollary 4 Let C pub = G q (x, f (z)Γ q-1 (z)) be a masked Wild Goppa code. Let t = deg(Γ ), W q,a (Z), and L a be as defined in Theorem 2. Then, we can fix t × #L a variables Z i to arbitrary values in W q,a (Z). The system obtained has m solutions (counted without multiplicities), one for each sum ℓ∈La GRS t (x ℓ , y ℓ ) q e . In the rest of this article, we set λ a,t = t × #L a . Our purpose is to find a basis of one of the vector spaces ℓ∈La GRS t (x ℓ , y ℓ ) q e . To do so, we pick λ a,t independent solutions of W q,a (Z) by fixing the variables Z 0 , Z 1 , . . . , Z λa,t-1 in W q,a,t (Z) accordingly. Namely, for 0 i λ a,t -1, we pick one solution v (i) among the m solutions of the system

W q,a (Z) {Z i = 1, Z j = 0 | 0 j = i λ a,t -1}.
Thanks to Theorem 3 and Definition 1, we know that those solutions can be written as follows, for Q i,ℓ ∈ F q m [z] of degree lower than t and 0 e i m -1: v (i) = 0, . . . , 1, . . . , 0, ℓ∈La y q e i λa,t Q i,ℓ (x qei λa,t ), . . . ∈ ℓ∈La GRS t (x ℓ , y ℓ ) q e i . (6)

After λ a,t resolutions of W q,a (Z), the solutions v (i) are not necessarily a basis of one of the vector spaces ℓ∈La GRS t (x ℓ , y ℓ ) q e because the Fröbenius exponents need not be identical for all v (i) 's. We explain in the next paragraph why this is not an issue in practice.

Simplication: Fröbenius Alignment. Let {v (i) } 0 i λa,t-1 be as defined in [START_REF] Bernstein | Wild McEliece[END_REF]. We can suppose without loss of generality that q 0 = q 1 = . . . = q λa,t-1 . This simplification requires less than m (λa,t-1) Fröbenius evaluations on the solutions. Indeed, v ∈ ℓ∈La GRS t (x ℓ , y ℓ ) q e , implies that v q ∈ ℓ∈La GRS t (x ℓ , y ℓ ) q e+1 . For the parameters considered in [START_REF] Bernstein | Wild McEliece[END_REF][START_REF] Bernstein | Wild McEliece incognito[END_REF], m and t are rather small, making the cost of the Fröbenius alignment negligible. In the rest of this article, we assume that q 0 = . . . = q λa,t-1 = 0, which is not a stronger assumption since the private elements of C pub are already defined up to Fröbenius endomorphism.

Example 1. Pick for instance q = 8 and solve the system W q,a with a = 2. Thanks to Theorem 2, after re-alignment of the Fröbenius exponents, we have a basis of the vector space GRS t (x, y) + GRS t (x 2 , y 2 ), that is:

(y i Q(x i ) + y 2 i R(x 2 i )) 0 i n-1 |Q, R ∈ F q m [z], deg(Q), deg(R) t -1 .

Recovering the Secret Key from a Sum of GRS -A Linear Algebra Step

Once we know a basis (v (i) ) 0 i λa,t-1 of ℓ∈La GRS t (x ℓ , y ℓ ), we aim at recovering the basis of a single GRS code. This disentanglement is done in Paragraph 4.1. Then, we show in 4.2 how to recover a private support x and Goppa polynomial Γ (z) of the masked Wild Goppa code. This is the full description of a plain Wild Goppa code. In the Incognito case (deg(f ) > 0), we explain in 4.3 that an extra linear step enables to find f . To sum up, the purpose of this section is to prove the following theorem.

Theorem 5. Let q = p s (p prime and s 0). Let G pub = (g i,j ) 0 i n-1

0 j k-1
be a generator matrix of a masked Wild Goppa code

C pub = G q (x, f (z)Γ q-1 (z)). Let y = Γ (x) -1 , t = deg(Γ ), and
V = ℓ∈La GRS t (x ℓ , y ℓ ) where L a = s-1-a r=0 {p r , 2p r , . . . , (p -1)p r } ∪ p s-a .
Once V is given, we can recover in polynomial-time a support x ′ and polynomials

f ′ (z), Γ ′ (z) ∈ F q m [z] such that C pub = G q (x ′ , f ′ (Γ ′ ) q-1
). Stated differently, we can recover in polynomial-time a key (x ′ , Γ ′ , f ′ ) equivalent to the secret-key as soon as the system (4) has been solved.

Disentanglement of the System Solutions

The Sidelnikov-Shestakov [START_REF] Sidelnikov | On the insecurity of cryptosystems based on generalized Reed-Solomon codes[END_REF] attack is a well known attack against McEliece schemes instantiated with GRS codes [START_REF] Niederreiter | Knapsack-type cryptosystems and algebraic coding theory[END_REF]. In our case, we can have a sum of GRS codes. In this situation, it seems not possible to apply directly [START_REF] Sidelnikov | On the insecurity of cryptosystems based on generalized Reed-Solomon codes[END_REF] (because the vectors of ℓ∈La GRS t (x ℓ , y ℓ ) do not have the desired form; that is (y 0 Q(x 0 ), . . . , y n-1 Q(x n-1 )). To overcome this issue, we propose to use wellchosen intersections to recover a basis suitable for Sidelnikov-Shestakov. To gain intuition, we provide a small example.

Example 2. We continue with the example 1. By squaring all the elements of GRS t (x, y) + GRS t (x 2 , y 2 ), we have a basis of GRS t (x 2 , y 2 ) + GRS t (x 4 , y 4 ):

(y 2 i Q(x 2 i ) + y 4 i R(x 4 i )) 0 i n-1 |Q, R ∈ F q m [z], deg(Q), deg(R) t -1 .
We prove in Proposition 6 that, in charac. 2,

GRS t (x, y) + GRS t (x 2 , y 2 ) ∩ GRS t (x 2 , y 2 ) + GRS t (x 4 , y 4 ) = GRS t (x 2 , y 2 ).
Hence, we have a basis of GRS t (x 2 , y 2 ).

Our general method to disentangle the solutions is proved in characteristic 2, but for other characteristics we need the following assumption:

Assumption 1 Let q = p s with p prime. Let x ∈ F n q m be a support and y ∈ F n q m be defined by y = Γ (x) -1 for some polynomial Γ (z) ∈ F q m [z] of degree t. Let L and L ′ be two subsets of {1, . . . , q} with (#L + #L ′ )t < n. Then, we have that:

ℓ∈L GRS t (x ℓ , y ℓ ) ℓ∈L ′ GRS t (x ℓ , y ℓ ) = ℓ∈L∩L ′ GRS t (x ℓ , y ℓ ).
For the specific subsets L that we encountered, this assumption is rigorously proved in characteristic 2 (see Proposition 6). For bigger characteristics, though we could not find a formal proof, we launched more than 100, 000 experiments and found out that equality held in all cases. Now we generalize the method of intersection of codes proposed in Example 2.

Proposition 6 Let q = p s (p prime and s 0). Let also a, 0 < a s, and L a = 0 r s-1-a {p r , 2p r , . . . , (p -1)p r } ∪ {p s-a } . Then:

ℓ∈La GRS t (x ℓ , y ℓ ) ∩ ℓ∈La GRS t (x ℓ , y ℓ ) p (s-a)
= GRS t (x p s-a , y p s-a ).

Proof. Let Φ : (m 0 , . . . , m n-1 ) ∈ F n q m → (m p s-a 0 , . . . , m p s-a n-1 ). First, remark that, as p s-a is a power of the characteristic, it holds that Φ GRS t (x ℓ , y ℓ ) = GRS t (x p s-a ℓ , y p s-a ℓ ) for all ℓ, and Φ ℓ∈La GRS t (x ℓ , y ℓ ) = ℓ∈Φ(La) GRS t (x ℓ , y ℓ ). When p = 2, we fully prove the proposition in Appendix A.4. Otherwise (when p > 2), we rely on Assumption 1 with the sets L a and Φ (L a ) = s-a r 2(s-a)-1 {p r , 2p r , . . . , (p -1)p r } ∪ p 2(s-a) .

Then, we have L a ∩ Φ (L a ) = {p s-a }, and the desired equality.

⊓ ⊔

Once a basis of GRS t (x p s-a , y p s-a ) is known, we recover x, y and Γ (z) thanks to a variant of Sidelnikov-Shestakov described below.

Sidelnikov-Shestakov Adapted To Recover the Goppa Polynomial

In our attack, we have to adapt the classical Sidelnikov-Shestakov attack for special GRS codes, namely those for which there is an additional polynomial relation between the support and the multipliers.

Proposition 7 Let x be an n-tuple (x 0 , . . . , x n-1 ) of distinct elements of F q m and Γ (z) ∈ F q m [z] be a squarefree polynomial of degree t such that Γ (x i ) = 0, for all i, 0 i n -1 Let G GRS be the generator matrix of a GRS code GRS t x, Γ (x) -1 . There is a polynomial-time algorithm which allows to recover a n-tuple x ′ = (x ′ 0 , . . . , x ′ n-1 ) of distinct elements of F q m and a squarefree polynomial

Γ ′ (z) ∈ F q m [z] of degree t such that Γ ′ (x ′ i ) = 0, for all i, 0 i n -1 and GRS t x, Γ (x) -1 = GRS t x ′ , Γ ′ (x ′ ) -1 .
This problem is very close to the one addressed in [START_REF] Sidelnikov | On the insecurity of cryptosystems based on generalized Reed-Solomon codes[END_REF]. The only issue is that the homographic transformation on the support used in the original attack indeed preserves the GRS structure but not the polynomial link. Thus, polynomial interpolation over x and y -1 is not possible. We propose to avoid this homographic transformation by considering a well chosen extended code. Definition 5. Let C be a linear code of length n over F q . The extended code of C , denoted by C , is a code of length n + 1 obtained by adding to each codeword m = (m 0 , . . . , m n-1 ) the coordinate -n-1 j=0 m j . Our algorithm, proved in the full version of this paper , is then the following.

Algorithm 1 Extended Version of Sidelnikov-Shestakov algorithm

Input : GGRS generator matrix of CGRS = GRSt(x, y), with y = Γ (x) -1 (deg(Γ ) = t) Output : Secret x, y, and Γ (z) 1: Build P = (pi,j) 0 i n-t-1

0 j n-1
a generator matrix of the dual of CGRS.

2: Deduce P a matrix of the extended code ( Definition 5) of the code spanned by P 3: Build It|U , with U = (ui,j) 0 i t t+1 j n a parity-check matrix of the code spanned by P in systematic form 4: Solve the linear system with unknowns Xi's to find x ui,j u i ′ ,j

(X i ′ -Xj) = ui,n u i ′ ,n (Xi -Xj) | 0 i, i ′ t, t + 1 j n -1 .
5: Solve the linear system with unknowns Yi's to find y (the xi's were found at previous step)

n-1 i=0 pj,ix ℓ i Yi = 0 | 0 j n -t -1, 0 ℓ t -1 .
6: Interpolate Γ (z) from x and y -1

Recovery of the Incognito Polynomial by Solving a Linear System

An extra step is necessary in the Incognito case to recover the other factor f of the Goppa polynomial. To do so, we recover the multipliers associated to f , that is the vector w = f (x) -1 . Then, we perform polynomial interpolation. We note that once x and y = Γ (x) -1 are known, many of the equations of Lemma 3 become linear in w. Namely,

q uy=1 n-1 j=0 g i,j w i y uy j x ux j = 0 | 0 i k -1, 0 u x u y t + deg(f ) -1 .
In practice, we observed that the linear system obtained has a rank defect and is not sufficient to find w. However, we can also use the fact that

C pub ⊂ G (x, f (z)) to prove that n-1 j=0 g i,j w i x deg(f ) i = 1 LC(f )   n-1 j=0 g i,j   .
(This is rigorously done in the full version of this article.) Since x is known and setting LC(f ) = 1, we obtain new linear equations in the components of w. Putting all the linear equations together, experiments show then that we obtain a unique solution w, and f by polynomial interpolation.

Weakness of Non-Prime Base Fields

The most (computationally) difficult part of our attack against Wild McEliece Incognito is to solve the algebraic system defined in Theorem 2. In this part, we aim at giving a better idea of the complexity of resolution by determining the exact number of "free variables" in the system. Namely, we show that we can eliminate many variables thanks to linear equations. The system W q,a (Z) = u∈Pa n-1 j=0 g i,j Z u j = 0 | 0 i k -1 of Theorem 2 obviously contains k linear equations by picking u = 1 (1 ∈ P a by definition). We can easily derive other linear equations by applying the additive map z → z (q m /p u ) to all the equations in degree p u . As the solutions lie in F q m , it holds that (Z p u j ) q m /p u = Z j , and for 0

i k -1   n-1 j=0 g i,j Z p u j   q m /p u = n-1 j=0 g q m /p u i,j Z j = 0.
However, we observed that those linear equations were very redundant. To explain those linear dependencies, we found out a property of the masked Wild Goppa codes G q (x, f (z)Γ (z) q ) (Theorem 8). Namely, by simple operations on their generator matrices, we can build a generator matrix of the code G p (x, Γ (z) p ) over F p . This latter matrix allows to write many independent linear equations implying the private elements of C pub . Theorem 8. Let q = p s (p prime, and s > 0). Let G pub = (g i,j ) 0 i n-1 0 j k-1 be a generator matrix of a masked Wild Goppa code C pub = G q (x, f (z)Γ (z) q-1 ). We consider the scalar restriction of m ∈ C pub ⊆ F n q into F s p . This yields s components m (0) , . . . , m (s-1) ∈ F n p (we write each m ∈ F n q over a F p -basis, i.e. m = m (0) θ 0 + • • • + m (s-1) θ s-1 ). Let C Fp ⊆ F n p be the code generated by the coordinate vectors m (0) , . . . , m (s-1) for all the codewords m ∈ C pub . Then, it holds that C Fp ⊆ G p (x, Γ (z) p ). The proof can be found in the full version of this paper.In practice, we observed equality in the inclusion provided s dim(C pub ) > dim(G p (x, Γ (z) p )). Note that G p (x, Γ (z) p ) is a Wild Goppa code with the same private elements x and y = Γ (x) -1 as C pub . This provides extra equations on the variables Z of W q,a (Z) (proved in the full version): Proposition 9 Let C pub = G q (x, f (z)Γ q-1 (z)) and W q,a (Z) the associated system for 1 a s. Let GFp = ( g i,j ) 0 i n-1 0 j kp-1 be a generator matrix of G p (x, Γ (z) p ) (with k p = dim (G p (x, Γ (z) p ))). Then, the solutions of W q,a (Z) satisfy:

p-1 ℓ=0    n-1 j=0 g i,j Z j = 0 | 0 u t -1, 0 i k p -1    .
As k p n -(p -1)mst (and in practice k p = n -(p -1)mst), we have the following corollary.

Corollary 10

The knowledge of G pub gives access to n-(p-1)mst independent linear relations between the Z i 's. The system W q,a (Z) contains (at most) (p -1)mst free variables.

Remark 2. The number of "free" variables given in Corollary 10 is given without taking into account the vector space structure of the solutions. Thanks to Corollary 4, we know that λ a,t extra variables can be fixed to arbitrary values in W q,a (Z).

For a Goppa polynomial of same degree, but without multiplicities, the number of free variables in the system would be n -k (p s -1)mt instead of (p -1)mst. In particular, for a masked code, the number of variables describing it does not depend on the degree of the incognito polynomial f and the attack is not harder for masked codes. This explains why the codes defined over non-prime fields are the weakest ones.

Practical Experiments

We report below various experimental results performed with our attack on various parameters for which [START_REF] Bernstein | Wild McEliece[END_REF] said that strength is "unclear" and that an attack would not be a "surprise" but for which no actual attack was known. We also generated our own keys/parameters to see how the attack scales. We performed our experiments with off-the-shelf tools (Magma [START_REF] Bosma | The Magma algebra system I: The user language[END_REF] V2.19-1) and using a 2.93 GHz Intel PC with 128 Gb. of RAM. As the polynomial system solving is by far the most costly step, we give timings only for this one. We performed it using the F 4 algorithm ( [START_REF] Faugère | A new efficient algorithm for computing gröbner bases (F4)[END_REF]) of Magma. As explained in Section 4, it is necessary to solve the systems W q,a (Z) a number of times equal to the dimension of the vector space of the solutions (Theorem 2). These resolutions are completely independent and can be executed in parallel. This is why we give the timings under the form (number of separate resolutions) × (time for one resolution). By #Z, we denote the number of free variables remaining in the system after cleaning up the linear equations (Corollary 10) and fixing coordinates thanks to the vector space structure of the solutions (Corollary 4). The general formula is #Z = ((p -1)ms -#L a ) t for q = p s and s > 1.

In the experiments, we tried various parameters a for the systems W q,a (Z). We give a comparison on some examples in Table 1 (the system W q,a (Z) with a = s can be solved in a reasonable amount of time in actually few cases). It appeared that a should be chosen so as to maximize the dimension of the solution set (Theorem 2). This choice minimizes the number of variables. Namely, the best choice is to set a = 1 when p > 2. When p = 2, setting a = 1 would yield only "linear" equations (of degree 2 u , u s). So, we set a = 2 and the systems W 2 u ,2 (Z) contain only cubic equations. We recall that for a = s, Assumption 1 is not necessary, whereas we rely on it when a < s and p = 2. In the rest of the experiments, we always pick the best choice for a.

In Table 2, we present experimental results performed with Wild McEliece (when deg(f ) = 0) and Incognito (deg(f ) > 0) parameters. For Wild McEliece, all the parameters in the scope of our attack were quoted in [6, Table 7.1] with the international biohazard symbol . The reason is that, for those parameters, enumerating all the possible Goppa polynomials is computationaly feasible. In the current state of the art, to apply the SSA attack ( [START_REF] Loidreau | Weak keys in the McEliece public-key cryptosystem[END_REF]), one would not only have to enumerate the irreducible polynomials of F q m [z], but also all the possible support sets, as the support-splitting algorithm uses the support set as input. This introduces a factor q m n in the cost of SSA, chosen by the designers in order to make the attack infeasible. However, the authors of [START_REF] Bernstein | Wild McEliece[END_REF] conclude that, even if no attack is known against those instances, algorithmical progress in support enumeration may be possible and therefor they do not recommend their use. In the case of non-prime base fields, experiments show that our attack represents a far more serious threat for the security of some of those instances: for q ∈ {32, 27, 16} we could find the secret keys of parameters with high ISD complexity. We indicate, for each set of parameters, the ISD complexity (obtained thanks to Peters' software1 ), as it remains the reference to evaluate the security of a McEliece scheme. We also give the complexity of an SSA attack, which is in the current state-of-the-art q m n • q mt /t. Regarding Wild McEliece Incognito, we broke the parameters indicated with a security of 2 128 in [8, Table 5.1] for q ∈ {32, 27, 16}. For some other nonprime base fields, we give the hardest parameters in the scope of our attack in roughly one day of computation. Note that here, SSA complexity is given by q m n • (q m(t+s) /(ts)).

For the sake of completeness, we also include in Tables 2 Wild McEliece schemes with a quadratic extension. In [START_REF] Couvreur | Polynomial time attack on wild McEliece over quadratic extensions[END_REF], the authors already presented a polytime attack in this particular case: it applies for the parameters with q = 32, but not for the other ones. We want to stress that our attack also works for m = 2 and any t ( [START_REF] Couvreur | Polynomial time attack on wild McEliece over quadratic extensions[END_REF] does not work in the extreme case t = 1). Also, we emphasize that, whilst solving a non-linear system, our attack is actually faster than [START_REF] Couvreur | Polynomial time attack on wild McEliece over quadratic extensions[END_REF] in some cases. For q = 32 and t = 4, the attack of [START_REF] Couvreur | Polynomial time attack on wild McEliece over quadratic extensions[END_REF] requires 49.5 minutes (using a non-optimized Magma implementation according to the authors). We can mount our attack in several seconds with the techniques of this paper. Conclusion and Future Work. In practice, we could not solve (in less than two days) the algebraic systems involved when the number of free variables #Z exceeds 65. We recall the relation #Z = ((p -1)ms -#L a ) t (for q = p s and s > 1), which should help the designers to scale their parameters. An important remaining open question is to give a precise complexity estimates for the polynomial system solving phase in those cases.

Fig. 1 .

 1 Fig. 1. Overview of the attack.

  q m t n k deg(f ) Solving Wq,a(Z) with a = s Solving Wq,a(Z), optimal a 10 min) (#Z = 51) 15× 3.0 s (a = 1, #Z = 39)

Table 1 .

 1 Comparison of the resolution times of Wq,a(Z) for various possible a's. The smallest possible a gives the best timings.

Table 2 .

 2 Practical experiments with Wild McEliece & Incognito parameters. ISD complexity is obtained thanks to Peters' software 1 . SSA attack complexity is given under the form (support enumeration)•(Goppa polynomial enumeration).

	q m t n	k deg(f ) Key (kB) ISD	SSA	Solving Wq,a(Z), optimal a
	32 2 4 841 601	0	92	2 128 2 688 • 2 38	16× 10 s (#Z = 36)
	32 2 5 800 505	0	93	2 136 2 771 • 2 48 20× (2 min 45s) (#Z = 40)
	27 3 3 1312 1078	0	45	2 113 2 6947 • 2 41	15× 3.0 s (#Z = 39)
	27 3 4 1407 1095	0	203	2 128 2 7304 • 2 55 20× (6 min 34 s) (#Z = 52)
	27 3 5 1700 1310	0	304	2 158 2 8343 • 2 69 25× (1h 59 min) (#Z = 65)
	27 3 5 1800 1410	0	327	2 160 2 8679 • 2 69 25× (1h 37 min) (#Z = 65)
	16 3 6 1316 1046	0	141	2 129 2 3703 • 2 69 18× (36h 26 min) (#Z = 54)
	32 2 3 852 621	24	90	2 130 2 663 • 2 273	12× 0.6 s (#Z = 18)
	27 3 2 1500 1218 42	204	2 128 2 5253 • 2 225	10× 0.9 s (#Z = 26)
	25 3 3 1206 915	25	155	2 117 2 7643 • 2 632 15× (1h 2 min) (#Z = 57)
	16 3 6 1328 1010 16	160	2 125 2 3716 • 2 265 18× (36h 35 min) (#Z = 54)
	9 3 6 728 542	14	40	2 81 2 2759 • 2 191 18× (25h 13 min) (#Z = 54)

available at http://christianepeters.wordpress.com/publications/tools/

Acknowledgements. This work was supported in part by the HPAC grant (ANR ANR-11-BS02-013) of the French National Research Agency. The authors would also like to thank (some of) the referees as well as PC chairs for their usefull comments on a preliminary version of this paper.

A Appendix

A.1 A Technical Lemma

We prove a technical lemma which is useful for the proofs of Sections 3 and 4.

Lemma 1. Let q = p s (p prime and s > 0), and

z] be a polynomial of degree t. For all j, it holds that:

where F (j) (Q) = γ p j t z t + • • • + γ p j 0 is the polynomial of same degree as Q obtained by raising all the coefficients to the p j -power.

A.2 Proof of Lemma 3

We want to prove that, under the conditions of Lemma 3 (that is 0

Proof. The crucial remark is that, for any c

for all 0 u y q and 0 b 1 (and (u y , b) = (0, 0)). In other words, for those u y , b , it holds that

As G q (x, f (z) b Γ uy (z)) has parity check matrix V dtot (x, w b y uy ) (with d tot = b deg(f ) + u y t), the matrix products V dtot (x, w b y uy ) × G T pub = 0 dtot×k yield all the relations of the lemma.

⊓ ⊔

A.3 Proof of Theorem 2 Proof. We give the multinomial development of the

u under the form z u j = ux,uy α ux,uy y uy j x ux j and show that u x , u y satisfy the conditions of Lemma 3. This is done separately for u ∈ P 1 and u ∈ P 2 .

Case u ∈ P 1 . We pick u ∈ {1, 2, . . . , p a -1} and use the multinomial formula to expand ℓ∈La y ℓ j Q ℓ (x ℓ j ) u . Namely, with L a = #L a , we have:

Let's look at each term y uy j x ux j in the sum. For u 1 , . . . , u L non-negative integers with u 1 + . . . + u L = u, it holds that u y = ℓ∈La ℓu ℓ max(L a ) ℓ∈La u ℓ p s-a u p s . For each y uy j , several terms y uy j x ux j appear after expanding ℓ∈La Q ℓ (x ℓ j ) u ℓ . In Q ℓ (x ℓ j ) u ℓ the maximal power u x appearing is ℓu ℓ (t -1) (as Q ℓ has degree t -1). Thus, in ℓ∈La Q ℓ (x ℓ j ) u ℓ , the maximal power is (t-1) ℓ∈La ℓu ℓ = (t-1)u y tu y -1.

Case u ∈ P 2 . We pick b ∈ {a, . . . , s}. Then e < s. The exponent ℓp b then writes ℓp b = αp e p ds = αp e q d . As g q i,j = g i,j it holds that

As the F (b-ds) (R ℓ )'s have degree lower than t, all the terms of the sum are of the form y uy j x ux j with u y q (since αp e < p s ) and u x u y t -1.

⊓ ⊔

A.4 Proof of Proposition 6

When p = 2, we prove Proposition 6 without resorting to Assumption 1. We use the fact that the polynomial Γ (z) linking x and y -1 is irreducible in the construction proposed in [START_REF] Bernstein | Wild McEliece[END_REF][START_REF] Bernstein | Wild McEliece incognito[END_REF]. For p = 2, L a is reduced to powers of 2, namely L a = {p u } 0 u s-a . So the proof consists in showing that the intersection

Proof. We pick v ∈ I. There exist polynomials R p u , Q p s-a+u ∈ F q m [z] (with 0 u s -a) of degree lower than t such that

, we obtain polynomial relations in the x i 's by multiplying by Γ (x i ) p 2(s-a) . This yields n relations,

We suppose here that the degree of this polynomial relation is lower than n, that is (t -1)p 2(s-a) < n, so that we can deduce the polynomial equality:

Modulo Γ (z) all polynomials vanish but one, this yields Q p 2(s-a) (z p 2(s-a) ) ≡ 0 mod Γ (z). Thanks to Lemma 1, we have s-a) )(z) has same degree as Q p 2(s-a) (z), which has degree lower than t (notations as in the proof of Theorem 2). Hence we deduce that F (u) (Q p 2(s-a) )(z) = 0 and also its Fröbenius Q p 2(s-a) = 0. Then, we look at the new relation of type [START_REF] Bernstein | Smaller decoding exponents: Ball-collision decoding[END_REF] and start over with the polynomial Q p 2(s-a)-1 (z p 2(s-a)-1 ). The proof that Q p 2(s-a)-1 = 0 is identical. One after the other, we prove that all the polynomials R p u , Q p s-a+u are zero except the matching polynomials R p s-a and Q p s-a which are equal, so that z ∈ GRS t (x p s-a , y p s-a ). The problem when p = 2 is that the set L a contains exponents which are not a pure power of p. ⊓ ⊔