Thomas Debris-Alazard

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

Two attacks on rank metric code-based schemes: RankSign and an IBE scheme

Keywords: Code-based cryptography, cryptanalysis, rank metric, signature scheme, identity based encryption

. This signature scheme is based on the rank metric and enjoys remarkably small key sizes, about 10KBytes for an intended level of security of 128 bits. Unfortunately we will show that all the parameters proposed for this scheme in [5] can be broken by an algebraic attack that exploits the fact that the augmented LRPC codes used in this scheme have very low weight codewords. Therefore, without RankSign the IBE cannot be instantiated at this time. As a second contribution we will show that the problem is deeper than finding a new signature in rankbased cryptography, we also found an attack on the generic problem upon which its security reduction relies. However, contrarily to the RankSign scheme, it seems that the parameters of the IBE scheme could be chosen in order to avoid our attack. Finally, we have also shown that if one replaces the rank metric in the [25] IBE scheme by the Hamming metric, then a devastating attack can be found.

Introduction

1.1 An efficient code-based signature scheme: RankSign and a code-based Identity-Based-Encryption scheme Code-based signature schemes. It is a long standing open problem to build an efficient and secure signature scheme based on the hardness of decoding a linear code which could compete in all respects with DSA or RSA. Such schemes could indeed give a quantum resistant signature for replacing in practice the aforementioned signature schemes that are well known to be broken by quantum computers.

A first partial answer to this question was given in [START_REF] Courtois | How to achieve a McEliece-based digital signature scheme[END_REF]. It consisted in adapting the Niederreiter scheme [START_REF] Niederreiter | Knapsack-type cryptosystems and algebraic coding theory[END_REF] for this purpose. This requires a linear code for which there exists an efficient decoding algorithm for a non-negligible set of inputs. This means that if H is an r × n parity-check matrix of the code, there exists for a non-negligible set of elements s in {0, 1} r an efficient way to find a word e in {0, 1} n of smallest Hamming weight such that He = s . The authors of [START_REF] Courtois | How to achieve a McEliece-based digital signature scheme[END_REF] noticed that very high rate Goppa codes are able to fulfill this task, and their scheme can indeed be considered as the first step towards a solution of the aforementioned problem. However, the poor scaling of the key size when security has to be increased prevents this scheme to be a completely satisfying answer to this issue. The rank metric. There has been some exciting progress in this area for another metric, namely the rank metric [START_REF] Gaborit | Ranksign: An efficient signature algorithm based on the rank metric (extended version on arxiv)[END_REF]. A code-based signature scheme whose security relies on decoding codes with respect to the rank metric has been proposed there. It is called RankSign. Strictly speaking, the rank metric consists in viewing an element in F N q (when N is a product N = m × n) as an m × n matrix over F q and the rank distance between two elements x and y is defined as the rank of the matrix xy. This depends of course on how N is viewed as a product of two elements. Decoding in this metric is known to be an NP hard problem [START_REF] Buss | The computational complexity of some problems of linear algebra[END_REF][START_REF] Courtois | Efficient zero-knowledge authentication based on a linear algebra problem MinRank[END_REF]. In the particular case of [START_REF] Gaborit | Ranksign: An efficient signature algorithm based on the rank metric (extended version on arxiv)[END_REF], the codes which are considered are not F q -linear but, as is customary in the setting of rank metric based cryptography, F q m -linear: the codes are here subspaces of F n q m . Here the elements x = (x 1 , . . . , x n ) of F n q m are viewed as m × n matrices by expressing each coordinate x i in a certain fixed F q -basis of F q m . This yields a column vector x i in F m q and the concatenation of these column vectors yields an m × n matrix Mat(x) = x 1 . . . x n that allows to put a rank metric over F n q m . This allows to reduce the key size by a factor of m when compared to the F q -linear setting (for more details see the paragraph at the end of Section 2).

Decoding such codes for the rank metric is not known to be NP-hard anymore. There is however a randomized reduction of this problem to decode an F q -linear code for the Hamming metric [START_REF] Gaborit | On the hardness the decoding and the minimum distance problems for rank codes[END_REF] when the degree m of the extension field is sufficiently big. This situation is in some sense reminiscent to the current thread in cryptography based on codes or on lattices where structured codes (for instance quasi-cyclic codes) or structured lattices (corresponding to an additional ring structure) are taken. However the F q m -linear case has an advantage over the other structured proposals, in the sense that it has a randomized reduction to an NP complete problem. This is not the case for the other structured proposals. Relying on F q m -linear codes is one of the main reason why RankSign enjoys noticeably small public key sizes: it is about 10KBytes for 128 bits of security for the parameters proposed in the NIST submission [START_REF] Aragon | Ranksign -a signature proposal for the NIST's call-. first round submission to the NIST post-quantum cryptography call[END_REF]. Furthermore, RankSign comes with a security proof showing that there is no leakage coming from signing many times. It also proved to be a fundamental building block in the Identity-Based-Encryption (IBE) scheme based on the rank metric suggested in [START_REF] Gaborit | Identity-based encryption from rank metric[END_REF].

A new IBE scheme based on codes. The concept of IBE was introduced by Shamir in 1984 [START_REF] Shamir | Identity-based cryptosystems and signature schemes[END_REF]. It gives an alternative to the standard notion of publickey encryption. In an IBE scheme, the public key associated with a user can be an arbitrary identity string, such as his e-mail address, and others can send encrypted messages to a user using his identity without having to rely on a public-key infrastructure, given short public parameters. The main technical difference between a Public Key Encryption (PKE) and IBE is the way the public and private keys are bound and the way of verifying those keys. In a PKE scheme, verification is achieved through the use of a certificate which relies on a public-key infrastructure. In an IBE, there is no need of verification of the public key but the private key is managed by a Trusted Authority (TA).

There are two issues that makes the design of IBE extremely hard: the requirement that public keys are arbitrary strings and the ability to extract decryption keys from the public keys. In fact, it took nearly twenty years for the problem of designing an efficient method to implement an IBE to be solved. The known methods of designing IBE are based on different tools: from elliptic curve pairings [START_REF] Sakai | Cryptosystems based on pairing[END_REF] and [START_REF] Boneh | Identity-based encryption from the Weil pairing[END_REF]; from the quadratic residue problem [START_REF] Courtois | Efficient zero-knowledge authentication based on a linear algebra problem MinRank[END_REF]; from the Learning-With-Error (LWE) problem [START_REF] Gentry | Trapdoors for hard lattices and new cryptographic constructions[END_REF]; from the computational Diffie-Hellman assumption [START_REF] Döttling | Identity-based encryption from the Diffie-Hellman assumption[END_REF] and finally from the Rank Support Learning (RSL) problem [START_REF] Gaborit | Identity-based encryption from rank metric[END_REF]. The last scheme based on codes is an adaptation of the [START_REF] Gentry | Trapdoors for hard lattices and new cryptographic constructions[END_REF] technique, but instead of relying on the Hamming metric it relies on the rank metric. It has to be noted that there has been some recent and exciting progress in the design of IBE. In [START_REF] Döttling | From selective IBE to full IBE and selective HIBE[END_REF] it has been shown how to generalize the work of [START_REF] Döttling | Identity-based encryption from the Diffie-Hellman assumption[END_REF] by introducing a new primitive, One-Time Signatures with Encryption (OTSE), that enables to construct fully secure IBE schemes. Furthermore it was shown in [START_REF] Döttling | New constructions of identity-based and key-dependent message secure encryption schemes[END_REF] how to instantiate OTSE primitives from LWE and the Low Parity Noise problems (LPN). This gave after the IBE's [START_REF] Gentry | Trapdoors for hard lattices and new cryptographic constructions[END_REF] and [START_REF] Gaborit | Identity-based encryption from rank metric[END_REF] the third scheme which may hope to resist to a quantum computer.

Our contribution

An efficient attack on RankSign. Our first contribution is that despite the fact that the security of RankSign might very well be founded on a hard problem (namely distinguishing an augmented LRPC code from a random linear code), we show here that all the parameters proposed for RankSign in [START_REF] Aragon | Ranksign -a signature proposal for the NIST's call-. first round submission to the NIST post-quantum cryptography call[END_REF] can be broken by a suitable algebraic attack. The problem is actually deeper than that, because the attack is actually polynomial in nature and can not really be thwarted by changing the parameters. The attack builds upon the following observations -The RankSign scheme is based on augmented LRPC codes; -To have an efficient signature scheme, the parameters of the augmented LRPC codes have to be chosen very carefully; -For the whole range of admissible parameters, it turns out rather unexpectedly that these augmented LRPC codes have very low-weight codewords. This can be proved by subspace product considerations; -These low-weight codewords can be recovered by algebraic techniques and reveal enough of the secret trapdoor used in the scheme to be able to sign like a legitimate user.

This attack has also a significant impact on the IBE proposal [START_REF] Gaborit | Identity-based encryption from rank metric[END_REF] whose security is based on the security of RankSign. Right now, there is no backup solution for instantiating this IBE scheme, since RankSign was the only rankmetric code based signature scheme following the hash and sign paradigm that is needed in the IBE scheme.

An efficient attack on the IBE [START_REF] Gaborit | Identity-based encryption from rank metric[END_REF]. Our second contribution is to show that the problem is deeper than finding a new hash and sign signature scheme in rank-based cryptography to instantiate the IBE proposed in [START_REF] Gaborit | Identity-based encryption from rank metric[END_REF]. Actually the security of this IBE scheme does not solely rely on the rank metric code-based signature scheme and the rank syndrome decoding, it also relies on the Rank Support Learning (RSL) problem. We show here that the RSL problem is much easier for the parameters proposed in the IBE scheme [START_REF] Gaborit | Identity-based encryption from rank metric[END_REF] and can be broken by a suitable algebraic attack. Interestingly enough, the approach for breaking the RSL problem is similar to what we did for RankSign:

we exhibit a matrix code that can be deduced from the public data that contains many low-weight codewords and whose support reveals the secret support of the RSL problem; we find such low weight codewords efficiently by solving a largely overdetermined bilinear system.

However in this case, contrarily to the RankSign scheme, even if the set of parameters that could defeat our attack is small, it is non empty and our attack could be thwarted by choosing the parameters appropriately and if an appropriate signature scheme were found.

We have also explored whether it is possible to change in the IBE scheme of [START_REF] Gaborit | Identity-based encryption from rank metric[END_REF] the rank metric by the Hamming metric. It turns out that the problem is much worse for the Hamming case. Indeed by adapting the IBE [START_REF] Gaborit | Identity-based encryption from rank metric[END_REF] to the Hamming metric, based on the remark that signatures must have a small weight, we show that even the simplest generic attack, namely the Prange algorithm [START_REF] Prange | The use of information sets in decoding cyclic codes[END_REF], breaks the IBE in the Hamming setting in polynomial time, and this irrespective of the way the parameters are chosen.

2 Generalities on rank metric and F q m -linear codes

Definitions and notation

We provide here notation and definitions that are used throughout the paper.

Big O notation. We will use the family of Bachmann-Landau notations,

f (n) = o(g(n)), f (n) = O(g(n)), f (n) = Ω(g(n)), f (n) = Θ(g(n)), f (n) = ω(g(n)) meaning respectively that lim n→∞ f (n) g(n) = 0, lim sup n→∞ |f (n)| g(n) < ∞, lim inf n→∞ f (n) g(n) > 0, f (n) = O(g(n)) and f (n) = Ω(g(n)), lim n→∞ |f (n)| |g(n)| = ∞.
Vector notation. Vectors will be written using bold lower-case letters, e.g. x. The ith component of x is denoted by x i . Vectors are in row notation. Matrices will be written as bold capital letters, e.g. X, and the i-th column of a matrix X is denoted X i . The rank of a matrix X will be simply denoted by |X|.

Field notation. Let q be a power of a prime number. We will denote by F q the finite field of cardinality q.

Coding theory notation. A linear code C over a finite field F q of length n and dimension k is a subspace of the vector space F n q of dimension k. We say that it has parameters [n, k] or that it is an [n, k]-code. A generator matrix G for it is a full rank k × n matrix over F q which is such that

C = {uG : u ∈ F k q }.
In other words, the rows of G form a basis of C. A parity-check matrix H for it is a full-rank (n -k) × n matrix over F q such that

C = {c ∈ F n q : Hc = 0}.
In other words, C is the null space of H. Rank metric codes basically consist in viewing codewords as matrices. More precisely, when N is the product of two numbers m and n, N = mn we will equip the vector space F N q with the rank metric by viewing its elements as matrices over

F m×n q , i.e. d(X, Y) = |X -Y|.
An [m × n, K] matrix code of dimension K over F m×n q is a subspace of F m×n q of dimension K. Such a code is equipped in a natural way with the rank metric. There is a particular subclass of matrix codes that has the nice property to be specified much more compactly than a generic matrix code. It consists in taking a linear code over an extension field F q m of F q of length n. Such a code can be viewed as a matrix code consisting of matrices in F m×n q by expressing each coordinate c i of a codeword c = (c i ) 1≤i≤n in a fixed F q basis of F q m . When the F q m -linear code is of dimension k the dimension of the matrix code viewed as an F q -subspace of F m×n q is K = k.m. More precisely we bring in the following definition.

Definition 1 (Matrix code associated to an F q m linear code). Let C be an [n, k]-linear code over F q m , that is a subspace of F n q m of dimension k over F q m , and let (β 1 . . . β m ) be a basis of F q m over F q . Each word c ∈ C can be represented by an m × n matrix Mat(c) = (M ij ) 1≤i≤m 1≤j≤n over F q , with c j = m i=1 M ij β i . The set {Mat(c), c ∈ C} is the [m × n, k.m] matrix code over F q associated to the F q m linear code C. The (rank) weight of c is defined as the rank of the associated matrix, that is

|c| = |Mat(c)|.
This definition depends of course on the basis chosen for F q m . However changing the basis does not change the distance between codewords. The point of defining matrix codes in this way is that they have a more compact description. It is readily seen that an [m×n, k.m] matrix code over F q can be specified from a systematic generator matrix (i.e. a matrix of the form 1 k.m |P with 1 k.m being the identity matrix of size k.m) by k(n -k)m 2 log 2 q bits whereas an F q m -linear code uses only k(n -k) log 2 q m = k(n -k)m log 2 q bits. This is particularly interesting for cryptographic applications where this notion is directly related to the public key size. This is basically what explains why in general McEliece cryptosystems based on rank metric matrix codes have a smaller keysize than McEliece cryptosystems based on the Hamming metric. All of these proposals (see for instance [START_REF] Gabidulin | Ideals over a noncommutative ring and their applications to cryptography[END_REF][START_REF] Gabidulin | Modified GPT PKC with right scrambler[END_REF][START_REF] Ernst | Attacks and counter-attacks on the GPT public key cryptosystem[END_REF][START_REF] Gaborit | Low rank parity check codes and their application to cryptography[END_REF][START_REF] Gaborit | Ranksign: An efficient signature algorithm based on the rank metric (extended version on arxiv)[END_REF][START_REF] Aragon | LOCKER-LOw rank parity ChecK codes EncRyption[END_REF][START_REF] Aguilar Melchor | Rank quasi cyclic (RQC). first round submission to the NIST post-quantum cryptography call[END_REF]) are actually built from matrix codes over F q obtained from F q m -linear codes. In a sense, they can be viewed as structured matrix codes, much in the same way as quasi-cyclic linear codes can be viewed as structured versions of linear codes. In the latter case, the code is globally invariant by a linear isometric transform on the codewords corresponding to shifts of a certain length. In the F q m linear case the code is globally invariant by an isometric linear transformation that corresponds to multiplication in F q m .

Rank code-based cryptography

Rank-based cryptography relies on the hardness of decoding for the rank metric. This problem is the rank metric analogue of the well known decoding problem in the Hamming metric [START_REF] Berlekamp | On the inherent intractability of certain coding problems[END_REF]. We give it here its syndrome formulation:

Problem 1 (Rank (Metric) Syndrome Decoding Problem). Instance: A full-rank (n -k) × n matrix H over F q m with k ≤ n, a syndrome s ∈ F n-k q m and w an integer. Output: An error e ∈ F n q m such that |e| = w and He = s . This problem has recently been proven hard in [START_REF] Gaborit | On the hardness the decoding and the minimum distance problems for rank codes[END_REF] by a probabilistic reduction to the decoding problem in the Hamming metric which is known to be NPcomplete [START_REF] Berlekamp | On the inherent intractability of certain coding problems[END_REF]. This problem has typically a unique solution when w is below the Varshamov-Gilbert distance w rVG (q, m, n, k) for the rank metric which is defined as Definition 2 (Varshamov-Gilbert distance for the rank metric). The Varshamov-Gilbert distance w rVG (q, m, n, k) for F q m linear codes of dimension k in the rank metric is defined as the smallest t for which q m(n-k) ≤ B t where B t is the size of the ball of radius t in the rank metric. Remark 1. 1. q m(n-k) can be viewed as the number of different syndromes s ∈ F n-k q m . 2. From [START_REF] Loidreau | Asymptotic behaviour of codes in rank metric over finite fields[END_REF] we have when either m or n tends to infinity

w rVG (q, m, n, k) = m + n -(m -n) 2 + 4km 2 (1 + o(1)). (1)
The best algorithms for solving the decoding problem in the rank metric are exponential in n 2 as long as m = Θ(n), w = Θ(n) but w stays below the Singleton bound which is defined by Definition 3 (Singleton distance in the rank metric). The rank Singleton distance w rS (q, m, n, k) for F q m linear codes of dimension k is defined as

w rS (q, m, n, k) = (n-k)m max(m,n) + 1
The usual notion of the support of a vector is generally relevant to decoding in the Hamming metric and corresponds for a vector x = (x i ) 1≤i≤n to the set of positions i in {1, . . . , n} such that x i = 0. Various decoding algorithms for the Hamming metric [START_REF] Prange | The use of information sets in decoding cyclic codes[END_REF][START_REF] Pil | An observation on the security of McEliece's public-key cryptosystem[END_REF][START_REF] Stern | A method for finding codewords of small weight[END_REF][START_REF] Dumer | On minimum distance decoding of linear codes[END_REF][START_REF] Finiasz | Security bounds for the design of codebased cryptosystems[END_REF][START_REF] Daniel | 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][START_REF] May | On computing nearest neighbors with applications to decoding of binary linear codes[END_REF][START_REF] Debris | Statistical decoding[END_REF][START_REF] Both | Optimizing BJMM with Nearest Neighbors: Full Decoding in 2 2/21n and McEliece Security[END_REF] use this notion in a rather fundamental way. The definition of the support of a vector has to be changed a little bit to be relevant to the rank metric. This notion was first put forward in [START_REF] Gaborit | On the complexity of the rank syndrome decoding problem[END_REF][START_REF] Gaborit | On the complexity of the rank syndrome decoding problem[END_REF] to obtain an analogue of the Prange decoder [START_REF] Prange | The use of information sets in decoding cyclic codes[END_REF] for the rank metric.

Definition 4 (Support). Let x = (x i ) 1≤i≤n be a vector of F n q m , its support is defined as:

Supp(x) = x 1 , • • • , x n Fq .
This notion of support is among other things relied to the rank metric as it is easily verified that for any vector x of F n q m we have |x| = dim(Supp(x)).

The RankSign scheme

We recall in this section basic facts about RankSign [START_REF] Gaborit | Ranksign: An efficient signature algorithm based on the rank metric (extended version on arxiv)[END_REF]. It is based on augmented LRPC codes. Roughly speaking it is a hash and sign signature scheme: the message m that has to be signed is hashed by a hash function H and the signature is equal to f -1 (H(m)) where f is a trapdoor one-way function. In this way the pair (m, f -1 (H(m))) forms a valid signature. Recall now that code-based cryptography relies on Problem 1 (rank syndrome decoding) which amounts to consider here the following one way-function to build a signature primitive:

f H : S w -→ F n-k q m e -→ eH
where S w denotes the words of F n q m of rank weight w, H a parity-check matrix of size (n -k) × n. To introduce a trapdoor in f H authors of [START_REF] Gaborit | Low rank parity check codes and their application to cryptography[END_REF] proposed to use parity-check matrices of the family of augmented LRPC codes. Indeed, when the underlying LRPC structure is known (roughly speaking, this is the trapdoor), there is a decoding algorithm based on the LRPC structure that computes for any (or for a good fraction) s ∈ F n-k q m an e ∈ F n q m of weight w such that He = s . This decoding algorithm is probabilistic and the parameters of the code have to be chosen in a very specific fashion in order to have a probability of success very close to 1 (see Fact 1 at the end of this section). The following definition will be useful for our discussion.

Definition 5 (Homogeneous Matrix

). A matrix H = (H ij ) 1≤i≤n-k 1≤j≤n over F q m is
homogeneous of weight d if all its coefficients generate an F q -vector space of dimension d:

dim H ij : 1 ≤ i ≤ n -k, 1 ≤ j ≤ n Fq = d
LRPC (Low Rank Parity Check) codes of weight d and augmented LRPC codes of type (d, t) are defined from homogeneous matrices of weight d as Definition 6 (LRPC and augmented LRPC code). An LRPC code over F q m of weight d is a code that admits a parity-check matrix H with entries in F q m that is homogeneous of weight d whereas an augmented LRPC code of type (d, t) over F q m is a code that admits a parity-check matrix H = H|R P where H is a homogeneous matrix of rank d over F q m , R is a matrix with t columns that has its entries in F q m and P is a square and invertible matrix with entries in F q that has the same number of columns as H . Remark 2. Note that any invertible P ∈ F n×n q is an isometry for the rank metric, since for any x ∈ F n q m we have Supp(x) = Supp(xP) and therefore |x| = |xP|.

The public key and the secret key for RankSign are given by: public key: H pub which is a random (n -k) × n parity-check matrix of an augmented LRPC code of type (d, t). It is of the form

H pub = QH with H = H|R P where Q is an invertible (n -k) × (n -k) matrix over F q m ,
H is a homogeneous matrix of rank d over F q m , R is a matrix with t columns that has its entries in F q m and P is a square and invertible matrix with entries in F q that has the same number of columns as H .

secret key: The matrix H sec = H|R .

From the knowledge of this last matrix a signature is computed by using a decoding algorithm devised for LRPC codes. Recall that LRPC codes can be viewed as analogues of LDPC codes for the rank metric. In particular, they enjoy an efficient decoding algorithm based on their low rank parity-check matrix. Roughly speaking, Algorithm 1 of [START_REF] Gaborit | Low rank parity check codes and their application to cryptography[END_REF] decodes up to w errors when dw ≤ n -k in polynomial time (see [START_REF] Gaborit | Low rank parity check codes and their application to cryptography[END_REF]Theorem 1]). It uses in a crucial way the notion of the linear span of a product of subspaces of F q m : Definition 7. Let U and V be two subspaces of F q m , then

U • V = uv : u ∈ U, v ∈ V Fq .
Roughly speaking, Algorithm 1 of [START_REF] Gaborit | Low rank parity check codes and their application to cryptography[END_REF] works as follows when we have to recover an error e of weight w from the knowledge of its syndrome s with respect to a parity-check matrix

H = (H ij ) 1≤i≤n-k 1≤j≤n over F q m that is homogeneous of weight d, that is s = He . (2) 1. Let U = H ij : 1 ≤ i ≤ n -k, 1 ≤ j ≤ n Fq , V = Supp(e) and W = Supp(s).
U and W are known, whereas V is unknown to the decoder. By definition U is of dimension d and it is convenient to bring in a basis {f 1 , . . . , f d } for it.

It turns out that we typically have

W = U • V . Moreover it is clear that in such a case V ⊂ f -1 1 W ∩ f -1 2 W • • • f -1 d W .
It also turns out that we typically have

V = f -1 1 W ∩ f -1 2 W • • • f -1 d W.
V is therefore computed by taking the intersection of all the f -1 i W 's. 3. Once we have the support of e (V = Supp(e)), the error e = (e 1 , . . . , e n ) can be recovered by solving the linear equation He = s with the additional constraints e i ∈ Supp(e) for i ∈ {1, . . . , n}. There are in this case enough linear constraints to recover a unique e.

The last algorithm seems to apply when there is a unique solution to [START_REF] Alekhnovich | More on average case vs approximation complexity[END_REF]. It can also be used with a slight modification (by adding "erasures" [START_REF] Gaborit | Ranksign: An efficient signature algorithm based on the rank metric (extended version on arxiv)[END_REF]) for weights for which there are many solutions to it (this is typically the regime which is used for the RankSign scheme). It namely turns out, see [START_REF] Gaborit | Ranksign: An efficient signature algorithm based on the rank metric (extended version on arxiv)[END_REF], that this decoder can for a certain range of parameters be used for a large fraction of possible syndromes s ∈ F n-k q m

to produce an error e of weight w that satisfies [START_REF] Alekhnovich | More on average case vs approximation complexity[END_REF]. It can even be required that Supp(e) contains a subspace T of some dimension t. Furthermore this procedure can also be generalized to a parity-check matrix of an augmented LRPC code. More precisely to summarize the discussion that can be found in [START_REF] Gaborit | Ranksign: An efficient signature algorithm based on the rank metric (extended version on arxiv)[END_REF][START_REF] Aragon | Ranksign -a signature proposal for the NIST's call-. first round submission to the NIST post-quantum cryptography call[END_REF] Fact 1 Let H be a random homogeneous matrix of weight d in

F (n-k)×n q m
, H = H|R P where R is a matrix with t columns that has its entries in F q m and P is a square and invertible matrix with entries in F q that has the same number of columns as H . There is a probabilistic polynomial time algorithm that outputs for a large fraction of syndromes s ∈ F n-k q m , subspaces T of F q m of F q -dimension t , an error e of weight w whose support contains the subspace T that satisfies H e = s as soon as the parameters n, k, t, t , d, w satisfy

m = (w -t )(d + 1) (3)
n -k = d(w -t -t ) (4) n = (n -k)d. (5)

Identity-Based-Encryption in code-based cryptography

We recall in this section the [START_REF] Gaborit | Identity-based encryption from rank metric[END_REF] approach for obtaining an IBE scheme whose security relies on code-based assumptions. In some sense, this scheme can be viewed as an adaptation of the first quantum-safe IBE which was introduced by [START_REF] Gentry | Trapdoors for hard lattices and new cryptographic constructions[END_REF] in the paradigm of lattice-based cryptography. It relies among other things on two fundamental building blocks: a hash and sign primitive and an encryption scheme related to it. The adaptation relies on two building blocks: i) a signature scheme, RankSign whose security relies on code-based assumptions for the rank metric, ii) a new encryption scheme, namely RankPKE [START_REF] Gaborit | Identity-based encryption from rank metric[END_REF], based on the Rank Support Leaning (RSL) problem. [START_REF] Gaborit | Identity-based encryption from rank metric[END_REF] gives a security proof of the IBE scheme that relies on two assumptions: i) the key security of RankSign and ii) the difficulty of RSL. Furthermore, the work of [START_REF] Gaborit | Identity-based encryption from rank metric[END_REF] can be easily generalized to the more common Hamming metric. It is why we present in what follows the [START_REF] Gaborit | Identity-based encryption from rank metric[END_REF] IBE scheme with codes independently of the metric. Roughly speaking, an IBE is a specific public-key encryption scheme that allows senders to encrypt messages thanks to the receiver's identity (such as its email address). To permit this protocol there is a third party, say a Key Derivation Center, which owns a master secret-key MSK and an associated public-key MPK that allows to compute from any identity id a related secret quantity sk id that will be used in a public-key encryption scheme involving an arbitrary sender and the receiver of identity id, with the pair of public/secret key ((id, MPK), sk id ). In this paradigm any identity id needs to be matched with a secret key sk id and to achieve this goal it was proposed in [START_REF] Gentry | Trapdoors for hard lattices and new cryptographic constructions[END_REF] to use a hash and sign primitive. Roughly speaking, for a trapdoor function f and a hash function H the Key Derivation Center will compute from id the quantity f -1 (H(id)) which will be used as sk id . We summarize in Figure 1 how this IBE works. In the case of [START_REF] Gentry | Trapdoors for hard lattices and new cryptographic constructions[END_REF], signatures sample short vectors whose addition with the hash of the identity gives lattice points. Then this is used as a secret-key of an encryption scheme whose security relies on the hardness of the LWE problem (see [START_REF] Gentry | Trapdoors for hard lattices and new cryptographic constructions[END_REF]Section 7.1,p26]). We give now the general framework of [START_REF] Gaborit | Identity-based encryption from rank metric[END_REF] for obtaining a code-based IBE scheme. It is only given in the rank metric case in [START_REF] Gaborit | Identity-based encryption from rank metric[END_REF], but the approach is really more general than this and can be given for the Hamming metric too. We will detail what happens for both metrics here.

As explained above, this scheme builds upon a hash and sign primitive and the authors of [START_REF] Gaborit | Identity-based encryption from rank metric[END_REF] proposed RankSign there but in our description the signature scheme is just a black-box.

Let C sgn be a code of length n sgn and dimension k sgn for which there is a trapdoor that enables to compute for any y ∈ F nsgn 2 a codeword c y ∈ C sgn at distance w sgn . Let w dec be an integer, C dec be a code of length n dec and dimension k dec such that it exists a polynomial algorithm to decode a linear (in the length) error weight. Let G Csgn and G C dec be generator matrices of the codes C sgn and C dec respectively. Then it is proposed in [START_REF] Gaborit | Identity-based encryption from rank metric[END_REF] to set master secret and public keys as:

-MSK be the trapdoor which enables to decode at distance w sgn in C sgn ;

-MPK = (C sgn , C dec ).
Let id be an identity and H be a hash function whose range is

F nsgn 2 or F nsgn q m
according to the metric which is used. The key derivation center computes with MSK and id a vector u id such that: sk id = u id .

|u id G Csgn -H(id)| =
We are now ready to present the encryption scheme whose public/secret key is ((G Csgn , G C dec , id), u id ) and which in the particular case of the rank metric is the RankPKE scheme introduced in [START_REF] Gaborit | Identity-based encryption from rank metric[END_REF]. This primitive is related to the work of Alekhnovich [START_REF] Alekhnovich | More on average case vs approximation complexity[END_REF].

-Encryption. Let m be the message that will be encrypted. We will denote by F the finite field F 2 or F q m depending on the Hamming or rank metric. The authors of [START_REF] Gaborit | Identity-based encryption from rank metric[END_REF] introduced the trapdoor function:

g G Csgn ,G C dec ,id : F k dec -→ F (ksgn+1)×n dec m -→ G Csgn E H(id)E + mG C dec
where E has a size n sgn × n dec . In the case of the rank metric E is a matrix uniformly picked at random among the homogeneous matrices of weight w dec and in the case of the Hamming metric, E is picked uniformly at random among the matrices whose columns have all weight w dec .

-Decryption. The secret key u id is used as

(u id , -1)g G Csgn ,G C dec ,id (m) = (u id , -1) G Csgn E H(id)E + mG C dec = u id G Csgn -H(id) E -mG C dec
It can be verified that under certain restrictions on w sgn and w dec , the weight of the vector u id G Csgn -H(id) E is low enough, so that a decoding algorithm for C dec will recover m. The following proposition gives a constraint on these parameters so that decoding is possible in principle.

Proposition 1. In order to be able to decode asymptotically at constant rate R, there should exist an ε(R) > 0 such that all the parameters n sgn , w sgn and w dec have to verify

• in the rank metric case

w sgn w dec = (1 -ε(R)) min(m, n dec ) (7)
• in the Hamming metric case

w sgn w dec = O(n sgn ). ( 8
)
Proof. We separate the proof in two parts. Rank metric. In this case, as proved in [25, §3.2] the rank weight of the error term u id G Csgn -H(id) E is with high probability w sgn w dec . Recall that C dec is a code over the alphabet F q m . A necessary condition to be able to decode with a fixed rate code is that the dimension of the support of the error is at most some fraction of the dimension m of the whole space F q m and of the length n dec of the code we decode. This means that

w sgn w dec ≤ (1 -ε(R)) min(m, n dec ).
Hamming metric. Recall that u id G Csgn -H(id) has Hamming weight w sgn (see ( 6)). It is easily verified that the probability for one bit of u id G Csgn -H(id) E to be equal to 1 is of the form (1/2)(1 -e -2wsgnw dec /n(1+O(1)) ) when the columns of E are picked uniformly at random among the words of Hamming weight w dec . Furthermore the relative weight of u id G Csgn -H(id) E concentrates around this probability and a necessary condition to be able to decode at constant rate asymptotically is that this relative weight is a constant < 1/2. Therefore it is necessary to have w sgn w dec = O(n sgn ).

The constraint set on the parameters by this proposition is crucial to instantiate the IBE in code-based cryptography. Unfortunately, this constraint implies a fatal weakness for the Hamming based scheme and a hard to meet condition for the rank metric in order to have a secure scheme as we will see in what follows.

The RSL problem. We recall here the assumption upon which the security of RankPKE relies (the previous encryption scheme in rank metric), namely the Rank Support Leaning (RSL) problem introduced in [START_REF] Gaborit | Identity-based encryption from rank metric[END_REF]. This problem is a rank syndrome decoding problem with syndromes that are associated to errors that all share the same support which is the secret.

Problem 2 ( RSL -Rank Support Learning). Parameters: n, k, N, w Instance: (A, AE) where A is a full rank matrix of size (n -k) × n, E a matrix of size n × N where all its coefficients belong to a same subspace F of F q m of dimension w Output: the subspace F . Remark 3. Let (A, AE) be an instance of RSL. The matrix A is of full-rank of size (n -k) × n and we can perform Gaussian elimination on its rows to get a matrix S such that SA = [I n-k |A ]. The pair (SA, SAE) is still an instance of RSL with the same parameters and secret subspace F , it is why we can always assume that for any instance of RSL the matrix A is in systematic form.

Attack on RankSign

The problem with RankSign : low rank codewords in the augmented LRPC code

A natural way to attack RankSign is to find low weight codewords in the dual of the augmented LRPC code. Recall that the public parity-check matrix used in the scheme is a matrix H pub where

H pub = QH
with H = H|R P where H is a homogeneous matrix of rank d over F q m , R is a matrix with t columns that has its entries in F q m , P is a square and invertible matrix with entries in F q that has the same number of columns as H and Q is a square and invertible matrix over F q m which has the same number of rows as H . If we call C pub the "public code" with parity-check matrix H pub , then the dual code C ⊥ pub that has for generator matrix H pub has codewords of weight ≤ d+t since rows of H P belong to this code, and all of its rows have rank weight ≤ d+t since the rows of H have weight at most d+t and P is an isometry for the rank metric. The authors have chosen the parameters of the RankSign scheme so that finding codewords of weight t + d in C ⊥ pub is above the security level of the scheme. However, it turns out that due to the peculiar parameters chosen in the RankSign scheme (see Fact 1), C pub has many very low weight codewords. This is the main problem in RankSign. Before we give a precise statement together with its proof, we will give a general result showing that LRPC codes may have under certain circumstances low weight codewords. Lemma 1. Let C be an LRPC code of length n and dimension k over F q m that is associated to an homogeneous matrix H that has all its entries in a subspace F of F q m . Furthermore we suppose there exists a subspace F of F q m such that

(n -k) dim(F • F ) < n dim F .
Then there exist non-zero codewords in the LRPC code whose support is included in F . They are therefore of rank weight at most dim F . Furthermore this set of codewords, that is

C = {c ∈ C : c i ∈ F , ∀i ∈ 1, n } forms an F q subspace of F n q m that is of dimension ≥ n dim F -(n-k) dim(F •F ).
Proof. Denote the entry in row i and column j of H by H i,j . A codeword c of the LRPC code satisfies

∀i ∈ 1, n -k , n j=1 H i,j c j = 0. ( 9
)
Looking in addition for a codeword c that has all its entries in F and expressing these n -k linear equations over F q m in a basis of F • F (since n j=1 H i,j c j belongs by definition to F • F ) and expressing each c j in a F q basis {f 1 , . . . ,

f d } of F as c j = d =1 c j, f we obtain (n -k) dim(F • F ) linear equations over F q involving n dim F unknowns (the c j, 's) in F q . The solution space is therefore of dimension greater ≥ n dim F -(n -k) dim(F • F ).
Remark 4. This theorem proves the existence of low rank codewords in an LRPCcode under some conditions but it does not give any efficient way to find them.

By using this lemma, we will prove the following corollary that explains that the augmented LRPC codes that are used in the RankSign signature necessarily contain many rank weight 2 codewords. This is in a sense a consequence of the constraint (5) on the parameters of RankSign.

Corollary 1. Let C pub be an [n+t, k+t] public code of RankSign over F q m which has been obtained from an [n, k] LRPC-code that is associated to a homogeneous matrix H that has all its entries in an F q subspace F of F q m . Consider a subspace F of F of dimension 2 and let

C pub = {c ∈ C pub : c i ∈ F , ∀i ∈ 1, n + t } . C pub is an F q subspace of F n+t q m . If (5) holds, that is n = (n -k)d, then dim Fq C pub ≥ n/d. Proof. Let H pub ∈ F (n-k)×(n+t) q m
be the public parity-check matrix for the RankSign public code C pub . Recall that H pub has been obtained as H pub = Q H|R P where:

-P is a non-singular matrix with entries in F q of size (n + t)

× (n + t), -Q is an invertible matrix of F q m of size (n -k) × (n -k), -R is a random matrix of F q m of size (n -k) × t, -H is a homogeneous (n -k) × n matrix of weight d with all its entries in F . Choose a basis {x 1 , x 2 , . . . , x d } of F such that {x 1 , x 2 } is a basis of F . We observe now that F • F = x i x j : i ∈ 1, d , j ∈ 1, 2 Fq .

The cardinality of the set {x

i x j : i ∈ 1, d , j ∈ 1, 2 } is actually 2d -1 because x 1 x 2 = x 2 x 1 . This implies that dim(F • F ) ≤ 2d -1.
It leads to the following inequalities,

n dim(F ) -(n -k) dim(F • F ) ≥ 2n -(n -k)(2d -1) = 2d(n -k) -(n -k)(2d -1) (since n = (n -k)d) = n -k = n d (since n = (n -k)d).
Let C LRPC be the LRPC code of weight d associated to the parity-check matrix H and let C LRPC be an F q subspace of it that is defined by

C LRPC = {c ∈ C LRPC : c i ∈ F , ∀i ∈ 1, n } .
By applying Lemma 1 we know that

dim Fq C LRPC ≥ n d . (10)
Consider now

C pub ={(c LRPC , 0 t )(P -1 ) : c LRPC ∈ C LRPC },
where 0 t denotes the vector with t zeros. From [START_REF] Both | Optimizing BJMM with Nearest Neighbors: Full Decoding in 2 2/21n and McEliece Security[END_REF] we deduce that

dim Fq C pub ≥ n d .
Moreover the entries of any element c in C pub belong to F because the entries of P are in F q . Let us now prove that C pub is contained in C pub . To verify this, consider an element c in C pub . It can be written as c = (c LRPC , 0 t )(P -1 ) . We observe now that

H pub c = H pub P -1 (c LRPC , 0 t ) = Q H|R PP -1 (c LRPC , 0 t ) = Q H|R (c LRPC , 0 t ) = QHc LRPC ( R ∈ F (n-k)×t q m
) = 0 (c LRPC belongs to the code of parity-check matrix H)

This proves that C pub ⊂ C pub which concludes the proof.

Weight 1 codewords in a projected code

Corollary 1 shows that there are many weight 2 codewords in C pub . We can even restrict our search further by noticing that without loss of generality we may assume that the space F in which the entries of the secret parity-check matrix H of the LRPC code are taken contains 1. Indeed, for any α in F × q m , αH is also a parity-check matrix of the LRPC code and has its entries in αF . By choosing α such that αF contains 1 we get our claim. Consider now a supplementary space V of 1 Fq = F q with respect to F q m , that is an F q -space of dimension m -1 such that

F q m = V ⊕ F q .
The previous discussion implies that there is a matrix-code in F (m-1)×(n+t) q , deduced from C pub by projecting the entries onto V , that contains codewords of weight 1. More specifically, consider an

F q basis {β 1 , β 2 , • • • , β m } of F q m such that β m = 1 and for c = (c i ) 1≤i≤n+t ∈ F n+t q m consider Mat proj (c) = (M ij ) 1≤i≤m-1 1≤j≤n+t ∈ F (m-1)×(n+t) q where c j = m i=1 M ij β i . Now let C proj pub be the matrix-code in F (m-1)×(n+t) q de- fined by C proj pub = Mat proj (c) : c ∈ C pub .

It is clear that

Fact 2 C proj pub contains codewords of rank weight 1.

These are just the codewords c which are of the form Mat proj (c) where c ∈ C pub with C pub being defined from a subspace F of F that contains 1 (we can make this assumption since we can assume that F contains 1).

C proj pub has the structure of an F q -subspace of F (m-1)×(n+t) q

. It is typically of dimension (k + t)m (i.e. the same as the F q dimension of C pub ). Moreover once we have these rank weight 1 codewords in C proj pub we can lift them to obtain rank weight ≤ 2 codewords in C pub because for any c ∈ C pub the last row of Mat(c) can be uniquely recovered from Mat proj (c) by performing linear combinations of the entries of Mat proj (c). We call this operation deducing c from Mat proj (c) lifting from C proj pub to C pub .

Outline of the attack

Finding codewords of rank 1 in C proj pub obviously reveals much of the secret LRPC structure. Lifting elements in C proj pub that are of rank 1 to C pub as explained at the end of Subsection 5.2 yields codewords of C pub that have typically rank weight 2. This can be used to reveal F and actually the whole subspace F by finding enough rank 1 codewords in C proj pub . Once F is recovered a suitable form for a parity-check matrix of C pub can be found that allows signing like a legitimate user. For the case of the parameters of RankSign proposed in [START_REF] Gaborit | Ranksign: An efficient signature algorithm based on the rank metric (extended version on arxiv)[END_REF][START_REF] Aragon | Ranksign -a signature proposal for the NIST's call-. first round submission to the NIST post-quantum cryptography call[END_REF] for which we always have d = 2 we will proceed slightly differently here. Roughly speaking, our attack can be decomposed as follows 1. We find a particular element M in C proj pub of rank weight 1 by solving a certain bilinear system with Gröbner bases techniques.

2. We lift M ∈ C proj pub to c ∈ C pub and compute F = Supp(c). 3. We compute from F the F q -subspace

C pub = {c = (c i ) 1≤i≤n+t ∈ C pub : c i ∈ F ∀i ∈ 1, n + t }. When d = 2 this set has typically dimension k. 4.
We use this subspace of C pub to find a suitable parity-check matrix for C pub which allows us to sign like a legitimate user.

Steps 2. and 3. are straightforward. We just give details for Steps 1. and 4. in what follows.

Finding rank 1 matrices in C proj pub by solving a bilinear system

The basic bilinear system. Finding rank 1 matrices in C proj pub can be formulated as an instance of the MinRank problem [START_REF] Buss | The computational complexity of some problems of linear algebra[END_REF][START_REF] Courtois | Efficient zero-knowledge authentication based on a linear algebra problem MinRank[END_REF]. We could use standard techniques for solving this problem [START_REF] Kipnis | Cryptanalysis of the HFE public key cryptosystem by relinearization[END_REF][START_REF] Faugère | Cryptanalysis of Minrank[END_REF][START_REF] Faugère | Computing loci of rank defects of linear matrices using gröbner bases and applications to cryptology[END_REF][START_REF] Spaenlenhauer | Résolution de systèmes multi-homogènes et determinantiels[END_REF] but we found that it is better here to use the algebraic modelling suggested in [START_REF] Aragon | Ranksign -a signature proposal for the NIST's call-. first round submission to the NIST post-quantum cryptography call[END_REF]. It basically consists in setting up an algebraic system with unknowns x = (x 1 , . . . , x m-1 ) ∈ F m-1 q and y ∈ F n+t q where the unknown matrix M in C proj pub that should be of rank 1 has the form

M =      x 1 y 1 x 1 y 2 . . . x 1 y n+t x 2 y 1 x 2 y 2 . . . x 2 y n+t . . . . . . . . . . . . x m-1 y 1 x m-1 y 2 . . . x m-1 y n+t      .
Recall that C proj pub has the structure of an F q subspace of F where m (i-1)(n+t)+j = M i,j , we can compute a parity-check matrix H proj pub for it. It is an ((m -1)(n + t) -(k + t)m) × (m -1)(n + t) matrix that we denote by

H proj pub = (H proj ij ) 1≤i≤(m-1)(n+t)-(k+t)m 1≤j≤(m-1)(n+t)
. This matrix gives (m-1)(n+t)-(k+t)m bilinear equations that have to be satisfied by the x i 's and the y j 's:

             n+t j=1 m-1 i=1 H proj 1,(i-1)(n+t)+j x i y j = 0 . . . n+t j=1 m-1 i=1 H proj (n+t)(m-1)-(k+t)m,(i-1)(n+t)+j x i y j = 0 (11)
Restricting the number of solutions. We have solved the bilinear system [START_REF] Buss | The computational complexity of some problems of linear algebra[END_REF] with standard Gröbner bases techniques that are implemented in Magma.

To speed-up the resolution of the bilinear system with Gröbner bases techniques (especially the change of order that is performed after a first computation of a Gröbner basis for a suitable order to deduce a basis for the lexicographic order which is more suited for outputting a solution) it is helpful to use additional equations that restrict the solution space which is otherwise really huge in this case. The purpose of the following discussion is to show where these solutions come from and how to restrict them. By bilinearity of System [START_REF] Buss | The computational complexity of some problems of linear algebra[END_REF] we may fix

x 1 = 1 ( 12
)
when there is a solution x such that x 1 = 0). Furthermore, the fact that C pub is an F q vector space of dimension n/d induces that for a given x solution to [START_REF] Buss | The computational complexity of some problems of linear algebra[END_REF] the set of corresponding y's also forms a vector space of dimension n/d. We may therefore rather safely assume that we can choose

∀i ∈ 1, n d -1 , y i = 0 and y n/d = 1. ( 13
)
There is an additional degree of freedom on x coming from the fact that even if d = 2 there are several spaces αF for which 1 ∈ αF . To verify this, let us study in more detail the case when F is of dimension 2, say F = a, b Fq . We wish to understand what are the possible values for z ∈ F q m such that there exists c = 0 for which a, b Fq = c 1, z Fq . The possible values for x will then be the projection of those z to the F q space β 1 , . . . , β m-1 Fq . The possible values for z are then obtained from studying the possible values for c. There are two cases to consider:

-Case 1: c = µ a+bν for µ ∈ F × q and ν ∈ F q . In such a case z = βb a+bν + δ for

β ∈ F × q , δ ∈ F q . -Case 2: c = µ b for µ ∈ F × q . Here z = α a b + δ for α ∈ F × q , δ ∈ F q .
Since the δ term vanishes after projecting x onto β 1 , . . . , β m-1 Fq we have essentially two degrees of freedom over F q for x. One has already been taken into account when setting x 1 = 1. We can add a second one x 2 = α where α is arbitrary in F q . We have actually chosen in our experiments that

(x 2 -α)(x 2 -β) = 0 ( 14
)
for some random α and β in F q . This has resulted in some gain in the computation of the solution space. Finally the following proposition summarizes the system we have solved.

Proposition 2. By eliminating variables using Equations ( 12),( 13) and ( 14) in (11) we have

-nm -k(m + 1) -t + 2 equations; -m -1 + n + t unknowns.
In the "typical regime" where m ≈ n, k ≈ n 2 and t n we have a number of equations of order n 2 and a number of unknowns of order n, therefore typically the regime where we expect that the Gröbner basis techniques take polynomial time.

Numerical results

We give in Table 1 our numerical results to find a codeword of rank 2 in any public code of the RankSign scheme for parameters chosen according to [START_REF] Aragon | Ranksign -a signature proposal for the NIST's call-. first round submission to the NIST post-quantum cryptography call[END_REF]. These results have been obtained with an Intel Core i5 processor, clocked at 1.6 GHz using a single core, with 8 Go of RAM.

Intended Security [START_REF] Aragon | Ranksign -a signature proposal for the NIST's call-. first round submission to the NIST post-quantum cryptography call[END_REF] (n,k,m,d,t,q

Finishing the attack

We present in this subsection the end of our attack which consists in being able to sign with only the knowledge of the public key. It holds for the parameters chosen for the NIST competition [START_REF] Aragon | Ranksign -a signature proposal for the NIST's call-. first round submission to the NIST post-quantum cryptography call[END_REF] for which d = 2. Observe that ( 5) implies that we have k = n -k = n/2. We have at that point obtained the code C pub (see §5.3, Point 3.) that has dimension (over F q ) ≥ n/d = n/2 = k. This code is just F q -linear, but it will be convenient to extend it by considering its F q m -linear extension, that we denote F q m ⊗ C pub that is defined by the F q m -linear subspace of F n+t q m obtained from linear combinations over F q m of codewords in C pub . In other words if we denote by {c 1 , . . . , c k } an F q -basis of C pub , then

F q m ⊗ C pub = c 1 , . . . , c k F q m .
To simplify the discussion we make now the following assumption (which was corroborated by our experiments)

Assumption 1 dim F q m ⊗ C pub = k.
The rationale behind this assumption is that (i) the dimension of C pub is very likely to be n/d which is equal to k and (ii) an F q basis of C pub is very likely to be an F q m basis too.

Lemma 2. Under Assumption 1 the code F q m ⊗ C pub ⊥ has length n + t, dimension n + t -k and is an LRPC-code that is associated to a homogeneous matrix that has all its entries in an F q subspace F of F q m of dimension 2 which contains 1. Furthermore, the sets

D ={c ∈ F q m ⊗ C pub ⊥ : Supp(c) ⊆ F q } and D ={c ∈ F q m ⊗ C pub ⊥ : Supp(c) ⊆ F }
are F q -subspaces of dimension ≥ t and ≥ n -k + 2t respectively.

Proof. By Assumption 1, F q m ⊗C pub is of dimension k and its dual F q m ⊗ C pub ⊥ has therefore dimension n+t-k. There is a generator matrix for F q m ⊗C pub that is formed by rows taken from C pub . It is homogeneous of weight 2. Say that its entries generate a space F . This is also a parity-check matrix of the dual code.

F q m ⊗ C pub ⊥
is therefore an LRPC code of weight 2.

By applying now Lemma 1 to it with F = F q , we have

(n + t) dim Fq (F q ) -(n + t -(n + t -k)) dim(F • F q ) = n + t -2k = t (because 2k = n)
which gives the result for the set D. We apply once again Lemma 1 but this time with F = F . Say F = 1, x 1 Fq . This gives a lower bound on the dimension of D which is

(n + t) dim(F ) -(n + t -(n + t -k)) dim(F • F ) ≥ 2(n + t) -3k (because F • F = 1, x 1 , x 2 1 Fq ) = n -k + 2t (because 2k = n).
To end our attack we make now the following assumption that was again corroborated in our experiments.

Assumption 2 We can extract from sets D and D a basis of F q m ⊗ C pub ⊥ with 1. t codewords of support F q , 2. n -k codewords of a same support of rank 2 which contains 1. Lemma 3. Under Assumptions 1 and 2 there exists a parity-check matrix H ∈

F (n+t-k)×(n+t) q m
of F q m ⊗ C pub , an invertible matrix P of size n + t with entries in the small field F q and an invertible matrix S of size n + t -k with entries in F q m such that

SH P = I t 0 0 R
where R is homogeneous of degree 2 and of size (n -k) × n.

The proof of this lemma can be found in the long version of the paper []. The idea now to sign as a legitimate user will be to use the matrix R and the decoder of Fact 1 (see Section §3). Recall that to make a signature for the matrix H pub (which defines the public code C pub ) and a message m, we look for an error e of rank w satisfying n -k = d(w -t -t ) (see Equation ( 4) of Fact 1), such that H pub e = s with s = H(m) (the hash of the message). The algorithm that follows performs this task:

1. We compute y ∈ F n+t q m such that H pub y = s . 2. Let y = y(P -1 ) and we compute s = (SH P)y . 3. Let s 1 be the first t coordinates of s , s 2 its last n -k ones. We apply the decoder of §3 with:

-The subspace T = Supp(s 1 )+T where T is a random subspace of F q m of dimension t .

-The parity-check matrix R and the syndrome s 2 . Then we get a vector e such that T ⊆ Supp(e ) and Re = s 2 . 4. We compute e = (s 1 , e )P .

The correctness of this algorithm is proved in the long version of the paper []. To summarize, in essence with codewords of rank 2 in the public code of RankSign and under Assumptions 1 and 2, we can compute signatures that are valid.

Attack on the IBE in the rank metric

In the previous section we showed that RankSign is not a secure signature scheme. This also shows the insecurity of the IBE proposal made in [START_REF] Gaborit | Identity-based encryption from rank metric[END_REF] since it is partly based on it. It could be thought that it just suffices to replace in the IBE scheme [START_REF] Gaborit | Identity-based encryption from rank metric[END_REF] RankSign by another signature scheme in the rank metric. This is already problematic, since RankSign was the only known rank metric code-based signature scheme up to now. We will actually show here that the problem is deeper than this. We namely show that the parameters proposed in [START_REF] Gaborit | Identity-based encryption from rank metric[END_REF] can be broken by an algebraic attack that attacks the RSL problem directly and not the underlying signature scheme. We will however show that the constraints on the parameters of the scheme coming from Proposition 1 together with the new constraint for avoiding the algebraic attack exposed here can in theory be met. In the IBE [START_REF] Gaborit | Identity-based encryption from rank metric[END_REF] we are given a matrix G Csgn of size k sgn × n sgn whose coefficients live in F q m and the matrix G Csgn E where E has size n sgn ×n dec with all its coefficients which live in a same secret subspace F of dimension w dec and an attacker wants to recover F . We show in §6.1 that under the condition n dec > w dec (n sgn -k sgn ) (which is verified in [START_REF] Gaborit | Identity-based encryption from rank metric[END_REF]) the code C defined by

C = {e(G sgn E) : e ∈ F n dec q } ⊆ F ksgn q m . (15)
is an F q -subspace which contains words of weight ≤ w dec which reveal F . It turns out that the subspace C = C ∩ F ksgn of words of C whose coordinates all live in F is of dimension ≥ n dec -w dec (n sgn -k sgn ). We then apply standard algebraic techniques in Subsection §6.2 to recover C and therefore F from it. This breaks all the parameters proposed in [START_REF] Gaborit | Identity-based encryption from rank metric[END_REF]. We conclude this section by showing that there is in principle a way to choose the parameters of the IBE scheme to possibly avoid this attack.

Low rank codewords from instances of the RSL problem

We prove here that a certain F q -linear code that contains many low-weight codewords can be computed by the attacker. This is explained by Theorem 1. Let (A, AE) be an instance of RSL for parameters n, k, N, w with

A ∈ F (n-k)×n q m
in systematic form and

E ∈ F n×N q m
where all its coefficients belong to a same subspace F of dimension w. Furthermore, we suppose that N > wk.

(

) 16
Let C ={e(AE) : e ∈ F N q } ; C = C ∩ F n-k . C is an F q -subspace of C of dimension ≥ N -wk.

Proof. Let us first decompose E in two parts E1

E2 where E 1 is formed by the first n -k rows of E and E 2 by the last k ones. The matrix A is in systematic form, namely (I n-k |A ) where A ∈ F (n-k)×k q m , which gives:

AE = E 1 + A E 2
Therefore, to prove our theorem we just need to show that

S ={e ∈ F N q : E 2 e = 0}
is an F q -subspace of dimension greater than N -wk. Indeed, for each error e of S we have (AE)e = E 1 e which belongs to F n-k as coefficients of E 1 are in the F q -subspace F and those of e are in F q . Denote the entry in row i and column j of E 2 by E i,j . A word of S satisfies

∀i ∈ 1, k , N j=1 E i,j e j = 0.
Looking in addition for e that has all its entries in F q and expressing these k linear equations over F q m in a basis of F (since N j=1 E i,j e j belongs by definition to F • F q = F ) we obtain k dim(F ) = kw linear equations over F q involving N unknowns (the e j 's) in F q . The solution space is therefore of dimension greater than N -wk which concludes the proof of the theorem.

How to find low rank codewords in instances of the RSL problem

Theorem 1 showed that there are many codewords of weight ≤ w dec in the code C defined in [START_REF] Döttling | From selective IBE to full IBE and selective HIBE[END_REF]. Let us show now how these codewords can be recovered by an algebraic attack. The sufficient condition n dec > w dec (n sgn -k sgn ) ensuring the existence of such codewords is met for the parameters proposed in [START_REF] Gaborit | Identity-based encryption from rank metric[END_REF].

To explain our algebraic modeling of the problem, let us first recall that for a fixed basis (β 1 , • • • , β m ) of F q m over F q we can view elements of F ksgn q m as matrices of size m × k sgn :

∀x ∈ F ksgn q m , Mat(x) = (X i,j ) ∈ F m×ksgn q where x j = m i=1 β i X i,j .
The associated matrix code C Mat is defined as:

C Mat ={Mat(c) : c ∈ C} ⊆ F m×ksgn q .
It is easily verified that this matrix-code has dimension n dec . It is clear now by applying Theorem 1 that: Fact 3. C Mat contains codewords of rank ≤ dim(F ) which form a F q -subspace of dimension ≥ n dec -w dec (n sgn -k sgn ).

These are just the codewords c which are of the form Mat(c) where c ∈ C with Supp(c) ⊆ F . We do not expect other codewords of this rank in C Mat since w dec is much smaller than the Varshamov-Gilbert bound in the case of the parameters proposed in [START_REF] Gaborit | Identity-based encryption from rank metric[END_REF].

The basic bilinear system. Finding codewords of rank w dec in C Mat can be expressed as an instance of the MinRank problem [START_REF] Buss | The computational complexity of some problems of linear algebra[END_REF][START_REF] Courtois | Efficient zero-knowledge authentication based on a linear algebra problem MinRank[END_REF]. Once again we propose the algebraic modeling which was suggested in [START_REF] Aragon | Ranksign -a signature proposal for the NIST's call-. first round submission to the NIST post-quantum cryptography call[END_REF]. It consists here in setting up the algebraic system with unknowns x i = (x i 1 , • • • , x i m ) ∈ F m q and y i j ∈ F ksgn q for 1 ≤ i ≤ w dec and 1 ≤ j ≤ k sgn where the x i 's can be thought as a basis of the unknown subspace F and the y i j 's as coordinates of the codeword in this basis. In that case the codeword M of C Mat of rank w dec has the following form:

M =      w dec i=1 x i 1 y i 1 w dec i=1 x i 1 y i 2 . . . w dec i=1 x i 1 y i ksgn w dec i=1 x i 2 y i 1 w dec i=1 x i 2 y i 2 . . . w dec i=1 x i 2 y i ksgn . . . . . . . . . . . . w dec i=1 x i m y i 1 w dec i=1 x i m y i 2 . . . w dec i=1 x i m y i ksgn     
.

Recall now that C Mat has the structure of an F q -subspace of F m×ksgn q of dimension n dec . By viewing the elements of C Mat as vectors of F mksgn q , i.e. the matrix M = (M ij ) 1≤i≤m 1≤j≤ksgn is viewed as the vector m = (m ) 1≤ ≤mksgn where m (i-1)ksgn+j = M i,j , we can compute a parity-check matrix H Mat for it. It is an (mk sgnn dec ) × mk sgn matrix that we denote by

H Mat = (H Mat ij ) 1≤i≤mksgn-n dec 1≤j≤mksgn
. This matrix gives mk sgn -n dec bilinear equations that have to be satisfied by the x l i 's and the y l j 's:

               w dec l=1 ksgn j=1 m i=1
H Mat 1,(i-1)ksgn+j x l i y l j = 0 . . . Restricting the number of solutions. We have solved the bilinear system [START_REF] Döttling | New constructions of identity-based and key-dependent message secure encryption schemes[END_REF] with Gröbner basis techniques that are implemented in Magma. To speedup the resolution, as in the case of the attack on RankSign, we add new equations to [START_REF] Döttling | New constructions of identity-based and key-dependent message secure encryption schemes[END_REF] which come from the vectorial structure of F and the set of solutions.

With our notation we can view F as an F q subspace of F m q of dimension w dec generated by the rows of the matrix:

     x 1 1 • • • x 1 m x 2 1 • • • x 2 m . . . . . . x w dec 1 • • • x w dec m     
In this way, we can put this matrix into systematic form, it will generate the same subspace. Therefore we can add equations ∀(i, j) ∈ 1, w dec 2 , j = i, x j i = 0 and x i i = 1 [START_REF] Dumer | On minimum distance decoding of linear codes[END_REF] without modifying the set of codewords of rank w dec . Furthermore, this set is an F q -subspace of dimension greater than n dec -(n sgn -k sgn )w dec and as in the case of the attack on RankSign we may assume that for a random subset I ⊆ 1, k sgn × 1, w dec of size n dec -(n sgn -k sgn ) -1 there is an element in this set for which: ∀(j, i) ∈ I, y i j = 0 and y i0 j0 = 1 for (i 0 , j 0 ) / ∈ I.

Equations ( 18) and ( 19) enable us to reduce the number of variables of the previous bilinear system. The following proposition summarizes the number of equations and variables that we finally get.

Proposition 3. By eliminating variables using Equations ( 18) and ( 19) in [START_REF] Döttling | New constructions of identity-based and key-dependent message secure encryption schemes[END_REF] we obtain mk sgn + w 2 dec + (n sgn -k sgn ) equations; mw dec + k sgn w dec unknowns.

In the "typical regime" where m ≈ n sgn ≈ k sgn and w dec ≈ n ε sgn for some ε in (0, 1) we have a number of equations of order n 2 sgn and a number of unknowns of order n 1+ε sgn , therefore typically the regime where we expect that the Gröbner basis techniques take subexponential time.

Numerical results

We give in Table 2 our numerical results to find codewords of rank w dec in instances of the RSL problem for the parameters chosen according to [START_REF] Gaborit | Identity-based encryption from rank metric[END_REF]. These results have been obtained with an Intel Core i5 processor, clocked at 1.6 GHz using a single core, with 8 Go of RAM. In our implementation, we verified that when we generated an instance whose associated secret is the subspace F we only got codewords whose coordinates live in this subspace and therefore revealed it.

Avoiding the attack

Although our attack breaks the parameters proposed in [START_REF] Gaborit | Identity-based encryption from rank metric[END_REF], there might in principle be a way to instantiate the IBE with a new signature scheme. Recall that the constraints that have to be satisfied are given by

w rVG (q, m, n sgn , k sgn ) ≤ w sgn ≤ m(n sgn -k sgn ) max(m, n sgn ) (signature constraint) (20)
w sgn w dec ≤ w rVG (q, m, n dec , k dec ) (decoding works) [START_REF] Finiasz | Security bounds for the design of codebased cryptosystems[END_REF] w dec (n sgn -k sgn ) ≥ n dec (for avoiding our attack).

The lower-bound in [START_REF] Faugère | Cryptanalysis of Minrank[END_REF] ensures that we can find a signature whereas the role of the upper-bound is to ensure that the problem of finding a signature does not become easy. The constraint ( 21) is here to ensure that the decoding procedure used for recovering the plaintext works and the last constraint is here to avoid our attack. This set of parameters is non-empty under the condition to find an efficient hash and sign signature scheme. For instance, if we have a signature scheme which achieves the lower bound [START_REF] Faugère | Cryptanalysis of Minrank[END_REF], namely w sgn = w rVG (q, m, n sgn , k sgn ) we can choose:

n sgn = 100 ; k sgn = 75 ; n dec = 96 ; k dec = 4 ; w dec = 4.
More generally, if one wants to set parameters of the IBE [START_REF] Gaborit | Identity-based encryption from rank metric[END_REF] we propose to proceed in the following way. We first propose to choose m = n sgn and a signature code for which the ratio wrVG(q,m,nsgn,ksgn) nsgn-ksgn is sufficiently small (it can even approach 1 2 ) and we choose

w sgn = (1 -ε)(n sgn -k sgn ) (23)
for some appropriate ε. We then choose an F q m -linear code of parameters [n dec , k dec ] of sufficiently small dimension such that

w rVG (q, m, n dec , k dec ) ≥ (1 -ε)n dec .
This is possible in principle. Therefore we can choose w dec such that w sgn w dec ≥ (1 -ε)n dec and for which (21) holds. By satisfying the two first constraints [START_REF] Faugère | Cryptanalysis of Minrank[END_REF] and [START_REF] Finiasz | Security bounds for the design of codebased cryptosystems[END_REF] in this way, we also satisfy the last one, namely Equation ( 22). This can be verified by arguing that

w dec (n sgn -k sgn ) = w sgn w dec 1 -ε (we use (23)) ≥ n dec (1 -ε)
1 -ε (we use the particular choice of w dec )

= n dec

Comparison with previous attacks against RSL

Recall here that the Rank Support Learning (RSL) problem for parameters n, k, N, w can also be expressed as follows: we have access to a matrix of full rank A ∈ F

(n-k)×n q m and to N syndromes Ae for e chosen uniformly at random in F n where F is some fixed subspace of F q m of dimension w. The problem is then to recover F . When N = 1 this is just the Rank Syndrome Decoding (RSD) problem (see Problem 1 in §2.2). It is readily verified that the difficulty of RSL decreases when N grows, however the question for cryptographic purposes is: "how large N can be while RSL remains hard?" In [25, §4, p14] a first answer was given by showing that N has to verify N < wn [START_REF] Gabidulin | Ideals over a noncommutative ring and their applications to cryptography[END_REF] otherwise a polynomial attack can easily be mounted. Here, we strengthen this condition on N , we require namely that in order to avoid our new attack we should have

N ≤ wk (k < n). ( 25
)
where k is the dimension of the code of parity-check matrix A ∈ F

(n-k)×n q m used in the instance of RSL. This condition is clearly stronger since we always have k < n at the cost of trading a polynomial attack in the case where ( 24) is met with a subexponential attack when (25) is not met.

In the context of the IBE it is actually significantly stronger. This comes from the fact that in this context we really expect that under reasonable assumptions that k n. This can be explained as follows. In this case [START_REF] Gaborit | Identity-based encryption from rank metric[END_REF] translates into n dec ≤ w dec (n sgn -k sgn ). The point is that in the typical regime which is needed for the IBE, we have n sgn -k sgn n sgn . By typical regime we mean here that we can assume that for the IBE [START_REF] Gaborit | Identity-based encryption from rank metric[END_REF] we have

Assumption 3 k sgn n sgn = Ω(1); (26)
m = Θ(n sgn ); (27)
w dec = ω(1) (28)
This assumption is minimal in the special case of the IBE [START_REF] Gaborit | Identity-based encryption from rank metric[END_REF] as we are going to explain. Equations ( 26) and ( 27) ensure that we are in the regime where the Gilbert-Varshamov and the Singleton bounds do not collapse which is essential as explained in the previous subsection to obtain parameters avoiding our attack on RSL.

Equation ( 28) permits to avoid a polynomial attack against the RSL problem. Indeed, suppose that w dec is bounded, which is w dec = O(1). Recall that in the IBE, instances of RSL have the following form (G Csgn , G sgn E) where G Csgn ∈ F ksgn×nsgn q m and E is homogeneous with underlying subspace F of dimension w dec . Solving here the Rank Syndrome Decoding for G Csgn , a weight w dec and the first column of E as syndrome will give with high probability F as w dec is smaller than the Varshamov-Gilbert bound. By using Gröbner basis techniques for this and writing equations in the small field F q this gives:

1. n sgn w dec unknowns; 2. mk sgn bilinear equations.

Under Assumptions ( 26), [START_REF] Gaborit | On the complexity of the rank syndrome decoding problem[END_REF] and the fact that k sgn ≤ n sgn , we have mk sgn = Θ(n sgn k sgn ) = Θ(n 2 sgn ). On the other hand, the number of unknowns is O(n sgn ) as w dec = O(1). This is the regimewhere we expect to solve the corresponding bilinear system in polynomial time. Therefore we can safely assume that w dec tends to infinity to avoid such a polynomial attack.

Assumption 3 leads in this case to the following proposition Proposition 4. Under Assumption 3, we have when n sgn tends to infinity:

n sgn -k sgn = o(n sgn ).
Proof. From Proposition 1 we have:

w sgn w dec ≤ min(n dec , m)
and thus from Assumption 3:

w sgn w dec = O(n sgn ) which gives w sgn n sgn = O 1 w dec . ( 29
)
Under Assumption 3 we have that w dec tends to infinity. Therefore we get

w sgn = o(n sgn ) (30)
Now under the signature constraint (see ( 20)) we have that w sgn ≥ w rVG (q, m, n sgn , k sgn ). From Equation (1) and Assumption 3, particularly [START_REF] Gaborit | On the complexity of the rank syndrome decoding problem[END_REF], it is easily verified that the last inequality and (30) imply n sgn -k sgn = o(n sgn ) which concludes the proof of the proposition.

Attack on the IBE in the Hamming metric

The purpose of this section is to show that there is an even more fundamental problem with the general IBE scheme given in Section 4 in the Hamming metric. We will namely prove here that due to the constraint on the parameters coming from Proposition 1, we can not find a set of parameters which would avoid an attack based on using generic decoding techniques. Even the simplest of those techniques, namely the Prange algorithm [START_REF] Prange | The use of information sets in decoding cyclic codes[END_REF], breaks the IBE in the Hamming metric in polynomial time. We refer the reader to Section §4 where we introduced all the notations that we are going to use.

To show that the IBE can be attacked in the Hamming metric we proceed as follows. The attacker knows G Csgn E and that the columns of E have weight w dec . We will show that we can solve efficiently for the range of parameters admissible for the IBE the following syndrome decoding problem: given a matrix G Csgn ∈ F such that there exists e ∈ F nsgn 2 of weight w dec for which G Csgn e = s , we want to recover e. This allows to recover the columns of E and therefore E. The scheme is broken with this knowledge, since the attacker also knows H(id)E + mG C dec , H(id) and G C dec . This is used to derive mG C dec and finally m.

To solve this decoding problem, we use the Prange algorithm (see [START_REF] Prange | The use of information sets in decoding cyclic codes[END_REF]) whose complexity is, up to a polynomial factor in n sgn , equal to ( nsgn w dec ) ( ksgn w dec )

In the special case of the IBE we proved in Proposition 1 that the parameters have to verify the following constraint:

w sgn w dec = O(n sgn ).

Now the parameter w sgn can not be too small either, since for fixed w sgn the algorithms for decoding linear codes also solve the signature forgery in polynomial time. This problem amounts in the case of the IBE to find a u id such that |u id G Csgn -H(id)| = w sgn .

We will therefore make a minimal assumption that ensures that the decoding algorithms for solving this problem have at least some (small) subexponential complexity. We also make the same assumption for the aforementioned recovery of e. This is obtained by assuming that Assumption 4 For some ε, ε > 0,

Concluding remarks

We have presented here our attacks against the rank-based signature scheme RankSign and the IBE scheme proposed in [START_REF] Gaborit | Identity-based encryption from rank metric[END_REF]. Several comments can be made.

Attack on RankSign. We actually showed that in the case of RankSign, the complexity is polynomial for all possible strategies for choosing the parameters.

Repairing the RankSign scheme seems to require to modify the scheme itself, not just adjust the parameters. It might be tempting to conjecture that the approach against RankSign could also be used to mount an attack on the NIST submissions based on LRPC codes such as [START_REF] Aragon | LAKE-Low rAnk parity check codes Key Exchange[END_REF][START_REF] Aragon | LOCKER-LOw rank parity ChecK codes EncRyption[END_REF]. Roughly speaking our approach consists in looking for low weight codewords in the LRPC code instead of looking for low weight codewords in the usual suspect, that is the dual of the LRPC code, that has in this case low weight codewords by definition of the LRPC code. This approach does not seem to carry over to the LRPC codes considered in those submissions. The point is that our approach was successful for RankSign because of the way the parameters of the LRPC code had to be chosen. In particular the length n, the dimension k and the weight of the LRPC code have to satisfy

n = (n -k)d.
It is precisely this equality that is responsible for the weight 2 codewords in the LRPC code. If d is not too small (say > 3) and (n -k)d is sufficiently above n, then the whole approach considered here fails at the very beginning.

Attack on the IBE [START_REF] Gaborit | Identity-based encryption from rank metric[END_REF]. The attack on RankSign also breaks the IBE proposal of [START_REF] Gaborit | Identity-based encryption from rank metric[END_REF] since it is based partly on the RankSign primitive. We have shown here that the problem is actually deeper than this by showing that even if a secure signature scheme replaces in the IBE, RankSign, then an attack that breaks directly the RSL problem which is the other problem on which the IBE is based, can be mounted for the parameters proposed in [START_REF] Gaborit | Identity-based encryption from rank metric[END_REF]. Again, as in the case of RankSign, the reason why this attack was successful comes from the fact that the constraints on the parameters that are necessary for the scheme to work properly work in favor of ensuring that a certain code that can be computed from the public data has low weight codewords. These low codewords are then found by an algebraic attack. However, contrarily to the RankSign case, where the conditions on the parameters force a certain code to have codewords of low weight, this phenomenon can be avoided by a very careful choice of the parameters in the IBE. This opens the way for repairing the scheme of [START_REF] Gaborit | Identity-based encryption from rank metric[END_REF] if a secure signature scheme is found for the rank metric.

We have also studied whether the [START_REF] Gaborit | Identity-based encryption from rank metric[END_REF] approach for obtaining an IBE scheme based on coding assumptions could work in the Hamming metric. However in this case, and contrarily to what happens in the rank metric, we have given a devastating polynomial attack in the Hamming metric relying on using the simplest generic decoding algorithm [START_REF] Prange | The use of information sets in decoding cyclic codes[END_REF] that can not be avoided by any reasonable choice of parameters. It seems that following the GPV [START_REF] Gentry | Trapdoors for hard lattices and new cryptographic constructions[END_REF]/ [START_REF] Gaborit | Identity-based encryption from rank metric[END_REF] approach for obtaining an IBE scheme is a dead end in the case of the Hamming metric.

To conclude this discussion on [START_REF] Gaborit | Identity-based encryption from rank metric[END_REF], we would like to stress that our result in the Hamming case does not imply the impossibility of designing an IBE based on coding theory. It only suggests to investigate other paradigms rather than trying to adapt the GPV strategy. For instance, the recent progress of [START_REF] Döttling | Identity-based encryption from the Diffie-Hellman assumption[END_REF][START_REF] Döttling | From selective IBE to full IBE and selective HIBE[END_REF][START_REF] Döttling | New constructions of identity-based and key-dependent message secure encryption schemes[END_REF] made on the design of IBE's, particularly with the concept of one-time signatures with encryption, might be applied to cryptography based on decoding assumptions.

Fig. 1 .

 1 Fig. 1. IBE in the GPV context

  w sgn where |•| denotes either the Hamming or rank metric[START_REF] Becker | Decoding random binary linear codes in 2 n/20 : How 1 + 1 = 0 improves information set decoding[END_REF] This is used as the secret key associated to the identity id:

(m- 1 )

 1 ×(n+t) q of dimension (k + t)m. By viewing the elements of C proj pub as vectors of F (m-1)(n+t) q , i.e. the matrix M = (M ij ) 1≤i≤m-1 1≤j≤n+t is viewed as the vector m = (m ) 1≤ ≤(m-1)(n+t)

wProposition 5 .

 5 dec = Ω(n ε ) ; w sgn = Ω(n ε ) Under Assumption 4, the Prange algorithm breaks the IBE scheme in Hamming metric in polynomial time in n sgn . The proof of this proposition is given in the long version of the paper [].

Table 1 .

 1 Attack on NIST's parameters of RankSign

		)	Time Maximum Memory Usage
	128 bits	(20, 10, 21, 2, 2, 2 32 ) 20.12 s	49 MB
	128 bits	(24, 12, 24, 2, 2, 2 24 ) 31.75 s	65 MB
	192 bits	(24, 12, 27, 2, 3, 2 32 ) 125.64 s	97 MB
	256 bits	(28, 14, 30, 2, 3, 2 32 ) 256.90 s	137 MB

Table 2 .

 2 Intended Security (nsgn, ksgn, m, w dec , n dec , k dec , q) Time Maximum Memory Usage Attack on parameters of the rank-based IBE[START_REF] Gaborit | Identity-based encryption from rank metric[END_REF]

	128 bits	(100, 80, 96, 4, 96, 9, 2 192 )	626s	1.7 GB

Thomas Debris-Alazard and Jean-Pierre Tillich