Nicolas Aragon
email: nicolas.aragon@etu.unilim.fr

Philippe Gaborit
email: gaborit@unilim.fr

Adrien Hauteville
email: adrien.hauteville@unilim.fr

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

Improvement of Generic Attacks on the Rank Syndrome Decoding Problem

Rank metric code-based cryptography exists for several years. The security of many cryptosystems is based on the difficulty of decoding a random code. Any improvement in the complexity of the best decoding algorithms can have a big impact on the security of these schemes.

In this article, we present an improvement on the recent GRS algorithm [1] and we obtain a complexity of O (n -k) 3 m 3 q w (k+1)m n -m for decoding an error of weight w in an [n, k] F 2 m -linear code.

1 Presentation of rank metric codes

Definitions

Let us introduce the matrix codes. Definition 1.1 (Linear matrix codes). A linear matrix code C of length m × n and dimension K over F q is a subspace of dimension K of M m×n (F q ). We say C is an [m × n, K] q linear matrix cod, or simply an [m × n, K] code if there is no ambiguity.

We define the rank metric over matrix codes as such:

• the distance between two words A and B is d R (A, B) def = Rank(A -B).

• the weight of a word A is |A| R def = Rank(A) = d R (A, 0).

An important family of matrix code are the F q m -linear codes. Definition 1.2 (F q m -linear codes). A F q m -linear code C of length n and dimension k is a subspace of dimension k of F n q m . We say C is an [n, k] q m linear code, or simply an [n, k] code if there is no ambiguity.

A natural way to define the rank metric over F q m -linear codes is to consider the matrix associated to a word of F n q m . Definition 1.3 (Associated matrix). Let x = (x 1 , . . . , x n ) ∈ F n q m and β = (β 1 , dots, β m ) a basis of F q m /F q .

x can be represented by an m × n matrix M x such that its i th column represents the coordinates of x i in the basis β.

x

↔    x 11 . . . x 1n . . . . . . x m1 . . . x mn    with x j = m i=1 x ij β i for all j ∈ [1..n]. By definition, |x| R def = |M x | R and d R (x, y) = d R (M x , M y ).
These definition do not depend on the choice of the basis.

The advantage of F q m -linear codes with respect to matrix codes is that they have a much compact representation. Indeed, we can associate an [m × n, km] q matrix code to an [n, k] q m linear code. The matrix code can be represented by (n -k)km 2 coefficients in F q that is (n -k)km 2 log 2 q bits whereas the F q mlinear can be represented by (n -k)k coefficients in F q m that is (n -k)km log 2 q bits. Definition 1.4 (Support of a word). Let x ∈ F n q m . The support of x is the F q -subspace of F q m generated by the coordinates of x. It is denoted Supp(x).

Supp(x) = x 1 , . . . , x n Fq
The weight of a word is equal to the dimension of its support. In the case of matrix codes, we can consider the subspace of F m q generated by the columns of the matrix, called the columns support, or the subspace of F n q generated by its rows, called the rows support.

Hard problem in rank metric

Rank-based cryptography relies on difficult problems in rank metric. These problem are the same as in the Hamming metric, but with the rank metric. In this subsection, we only consider F q m -linear codes but all the problems are defined exactly the same way for linear matrix codes.

The first one corresponds to the decoding problem by syndromes.

Definition 1.5 (Rank Syndrome Decoding (RSD) problem). Let H be the paritycheck matrix of an [n, k] code, s ∈ F q m n -k and w an integer. The RSD problem consists to find e ∈ F n q m such that:

• He T = s • |e| R = w
The second problem is the search for small-weight codewords. Remark: If H is an parity-check matrix of C, the small-weight codeword problem corresponds to an instance of the RSD problem with s = 0.

Generic algorithms 1.4 Basic algorithm

In the article [START_REF] Gaborit | On the complexity of the rank syndrome decoding problem[END_REF], the general idea to solve the RSD problem is to find a subspace F such that Supp(e) ⊂ F . Then we can express the coordinates of x in a basis of F and solve the linear system given by the parity-check equations. There are two possible cases we will describe more precisely.

• first case: n m.

Let F be a subspace of F q m of dimension r and (F 1 , . . . , F r ) a basis of F . Let us assume that Supp(e) ⊂ F .

⇒ ∀i ∈ [1..n], e i = r j=1 λ ij F j
This gives us nr unknowns over F q .

We can now rewrite the parity-check equations in these unknowns:

He T = s (1)
⇔      H 11 e 1 + • • • + H 1n e n = s 1 . . . . . . . . . H n-k,1 e 1 + • • • + H n-k,n e n = s n-k ⇔      r j=1 (λ 1j H 11 F j + • • • + λ nj H 1n F j ) = s 1 . . . . . . . . . r j=1 (λ 1j H n-k,1 F j + • • • + λ nj H n-k,n F j ) = s n-k (2)
Now, we need embed these n-k equations over F q m into (n-k)m equations over F q . Let ϕ i the i th canonical projection from F q m on F q :

ϕ i : F q m → F q m i=1 x i β i → x i
We have:

He T = s ⇔ ∀i ∈ [1..m],      r j=1 λ 1j ϕ i (H 11 F j ) + • • • + λ nj ϕ i (H 1n F j ) = ϕ i (s 1 ) . . . . . . . . . r j=1 λ 1j ϕ i (H n-k,1 F j ) + • • • + λ nj ϕ i (H n-k,n F j ) = ϕ i (s n-k )
Since we assume Supp(e) ⊂ F , this system has at least one solution. We want more equations than unknowns to "eliminate" the false solutions. So we have:

(n -k)m nr ⇔ r m - km n
The complexity of the algorithm is O (n-k) 3 m 3 p where p is the probability that Supp(e) ⊂ F . p is equal to the number of subspaces of dimension w in a subspace of dimension r divided by the total number of subspaces of dimension w in F q m . By definition, these numbers are expressed by the Gaussian coefficients.

p = r w q m w q ≈ q -w(m-r)
By taking r = m -km n we obtain a complexity of O (n -k) 3 m 3 q w km n • second case: m > n. In this case we consider the matrix code associated to the F q m -linear code. Instead of searching for a subspace which contains the columns support of the matrix of the error, we search for a subspace F of F n q which contains the rows support of the error. The remainder of the algorithm is the same, the only differences are:

the number of unknowns is mr, which implies r n -k the probability to choose a "good" F is

  r w   q   n w   q ≈ q -w(n-r) .
Thus, the complexity in this case is O (n -k) 3 m 3 q wk .

Improvements of the algorithm

In the last algorithm, we do not use the F q m -linearity of the code. In this subsection, we will see two ways to use the linearity to improve the complexity of our algorithm. The main idea is to consider the code C = C + F q m e, where C is the code with parity-check matrix H. The problem is reduced to the search for a codeword of weight w in C . If e is the only solution of the equation Hx T = s, |x| R = w, then the only codewords of C of weight w are of the form αe, α ∈ F * q m . Instead of looking for the support E of e, we can look for any multiple αE of the support. There is two strategies to exploit this idea:

• in the first case, we specialize one element of the support by searching for small weight codeword c such that 1 ∈ Supp(c) (or any other scalar). We need to compute the probability that F ⊃ Supp(c), knowing that 1 ∈ F . This probability is given by the formula

  w -1 r -1   q   w -1 m -1   q ≈ q (w-1)(m-r) . Since C is of dimension k + 1, we take r = m(n-k-1) max(m,n)
which gives us a complexity of O (n -k) 3 m 3 q (w-1) min(k+1, (k+1)m n ) .

• the idea is to choose F at random like in the first algorithm, if F contains a multiple αE of E, we can compute the codeword αe of C . There is at most

q m -1 q-1 subspace of this form, because αE = βE if α/β ∈ F * q .
In the following we will suppose that all this subspaces are different, which is always true if m is prime (see appendix A). We need to compute the probability that F of dimension m(n-k-1) n = m -m(k+1) n contains any subspaces of the form αE, α ∈ F * q m . We can approximate it by the product of the number of of these subspaces by the probability that F contains a fixed subspace of dimension w. This approximation is correct if q m -1 q -1 r w q m w q ⇔ q m+w(r-w) q w(m-w) .

We obtain a complexity of O (n -k) 3 m 3 q w (k+1)m n -m .

In the case m n, the second strategies is always better. The gain in the exponent is equal to m -(k+1)m n = m -mR ≈ m(1 -R ) where R is the rate of C . In the case m > n the second strategy may also be faster for some parameters.

Definition 1 .

 1 6 (Small-weight codeword problem). Let C be an [n, k] code and w an integer. The problem consists to find a codeword c ∈ C such that |c| R = w.

A On the multiples of subspace of F q m

In this section, we study the probability that E = αE, where E is a subspace of

which proves the first point. Moreover m divides m ⇒ m divides m ∧ d = 1. So F q (α) = F q which proves the second point. Now let m = am with a > 1 and E an F q -subspace of F q m of dimension dm . The probability that E is an F q m -subspace of dimension d is