Victor Cauchois

Pierre Loidreau
email: pierre.loidreau@m4x.org

On Circulant Involutory MDS Matrices

We give a new algebraic proof of the non-existence of circulant involutory MDS matrices with coefficients in fields of characteristic 2. In odd characteristics we give parameters for the potential existence. If we relax circulancy to θ-circulancy, then there is no restriction to the existence of θ-circulant involutory MDS matrices even for fields of characteristic 2. Finally, we relax further the involutory definition and propose a new direct construction of almost involutory θ-circulant MDS matrices. We show that they can be interesting in hardware implementations.

Introduction

MDS matrices are redundant parts of systematic generator matrices of MDS codes. For cryptographic applications they offer the maximal possible diffusion between the input and the output of the associated linear application. For the purpose of reducing implementation costs, research focuses on circulant and recursive matrices. Indeed, the matrix-vector product can be computed with only a linear number of multipliers in the size of the input rather than a square number if no additional structure was required. Moreover if it is used in SPN block-ciphers, the computation of the inverse product is necessary for decryption. In this setting it is thus interesting to consider involutory matrices or almost involutory matrices. All these problems were investigated in a large number of research papers:

• Concerning circulant matrices: Apart from the design of AES [START_REF] Daemen | The Design of Rijndael -AES -The Advanced Encryption Standard[END_REF], circulantlike MDS matrix constructions were proposed by taking subsquare matrices of Hankel form, see [START_REF] Aidinyan | On matrices with nondegenerate square submatrices[END_REF][START_REF] Roth | On generator matrices of MDS codes[END_REF]. In [START_REF] Roth | On MDS codes via Cauchy matrices[END_REF], the authors showed that generalized Cauchy matrices are redundant part of MDS codes. More recently, [START_REF] Sim | Lightweight MDS involution matrices[END_REF] considered lightweight Hadamard-Cauchy matrices. In [START_REF] Gupta | On constructions of circulant MDS matrices for lightweight cryptography[END_REF], the authors proved that involutory circulant matrices do not exist. In [START_REF] Li | On the construction of lightweight circulant involutory MDS matrices[END_REF], the authors showed that relaxing the definition of circulancy allows to build involutory matrices for some parameters. [START_REF] Liu | Lightweight MDS generalized circulant matrices[END_REF] found very low cost involutory matrices by replacing multiplication by field elements with invertible linear applications.

• Concerning recursive matrices: In [START_REF] Berger | Construction of recursive MDS diffusion layers from Gabidulin codes[END_REF], the author used Gabidulin theory to propose a direct construction of recursive MDS matrices. Recursive MDS matrix constructions were also considered by [START_REF] Augot | Direct construction of recursive MDS diffusion layers using shortened BCH codes[END_REF] where they constructed recursive matrices from shortened cyclic MDS codes. Such structures form the linear diffusion layer core of PHOTON family of hash function [START_REF] Guo | The PHOTON family of lightweight hash functions[END_REF] or LED block cipher [START_REF] Guo | The LED block cipher[END_REF]. The construction of involutory matrices with recursive structures was investigated in [START_REF] Cauchois | Direct construction of quasiinvolutory recursive-like mds matrices from 2-cyclic codes[END_REF] where the authors published a direct construction of MDS matrices, quasi-involutory and which can be recursively implemented with a derived version of an LFSR denoted SLFSR for Skewed Linear Feedback Shift Register. An SLFSR is a logical structure built from a classical LFSR skewed via the action of a Frobenius automorphism.

From a complexity point of view, verifying that a matrix is MDS is strongly exponential since we have to compute all the minors of the matrix and check that they are non-zero. Therefore, it is important to discriminate parameters for which such matrices could exist. Additionally, we would like to provide direct constructions of such matrices even by relaxing constraints. Thus we would not be limited to small size matrices when designing cryptosystems.

In this paper, after recalling some basics of coding theory we introduce a general algebraic framework to study involutory properties of circulant and θ-circulant matrices. These latter matrices form the counterpart of circulant matrices if one considers the q-polynomial ring. In a second part we prove some results on the existence and non-existence of involutory circulant MDS matrices. In a third part we extend the results to the θ-circulant matrices and show that this increases the number of degrees of freedom for the choice of MDS matrices. In a final part by relaxing the involutory property we directly construct MDS θ-circulant matrices which are involutory modulo a permutation.

Our contribution

We provide a new simple proof that circulant involutory matrices do not exist in fields of characteristic 2. In odd characteristics, we extend the result by using our algebraic framework. This gives some restrictions on the existence of the matrices. By generalizing circulancy and considering θ-circulant matrices, the aforementioned restriction can be raised and involutory θ-circulant matrices may exist even for impossible parameters in the previous case. This approach does not provide a direct construction. To obtain a direct construction, we relax the condition on the matrix to be involutory, by authorizing the action of the Frobenius automorphism and a permutation of the coordinates. These restriction have little impact on the hardware implementation costs.

An algebraic framework 2.1 Notations and definitions

Let q be the power of a prime p. Let F q be the field with q elements and F q [X] be the polynomial ring with coefficients in F q . We denote by M m,n (F q ) the set of matrices with m rows and n columns with coefficients in F q .

Definition 1. Let C be a [n, k, d] linear code over F q . Then C is MDS if its mini-mum distance d satisfies the Singleton Bound:

d = n -k + 1.
In cryptography, we are more interested in the so-called MDS matrices defined by: Definition 2. M ∈ M k,n-k (F q ) is MDS if and only if it satisfies one of the two following properties:

• All its minors are non zero.

• It is the redundant part of the generator matrix of an MDS code C under systematic form, i.e. this is the matrix M where

C = (I | M) .
In the design of symmetric encryption schemes we usually need invertible matrices. This implies that we only consider square MDS matrices of order m. These matrices are redundant part of generator matrices under systematic form of MDS codes of length 2m and dimension m.

Definition 3. A matrix M ∈ M m,m (F q
) is involutory if it satisfies the following equation:

M 2 = I m

Circulant matrices and polynomial rings

For g ∈ F q [X], we denote by w t (g) the weight of the polynomial g, corresponding to the number of non-zero coefficients of the polynomial g. We denote by F q,m [X] the set of polynomials of degree less than or equal to m. We introduce the following mapping between monic polynomials and circulant matrices:

Definition 4. Let h(X) = (X m -1) + m-1 i=0 h i X i ∈ F q [X
] be a monic polynomial of degree m. The circulant matrix associated with h is the matrix defined by:

C h =      h 0 h 1 . . . h m-1 h m-1 h 0 . . . h m-2 . . . . . . . . . . . . h 1 h 2 . . . h 0     
Remark 1. This mapping is non-standard in the sense that h 0 is not the constant term of the polynomial h but the constant term translated by 1.

The following proposition sets the algebraic framework.

Proposition 1. Let h(X) = (X m -1)+ m-1 i=0 h i X i ∈ F q [X
] be a monic polynomial of degree m and C h be the circulant matrix associated with h. Then, C h is the matrix in the basis {1, X, . . . , X m-1 } of the mapping:

φ : F q [X]/(X m -1) → F q [X]/(X m -1) Q(X) → Q(X)h(X)
Proof. By linearity, we only need to verify that it is true for the elements of the canonical basis of F q [X]/(X m -1), associated with the canonical basis (e k ) k≤m-1 of F m q . ∀k ∈ {0, . . . , m -1}:

     X k • h(X) = m i=0 X k h i X i = m-k-1 i=0 h i X i+k + k i=1 h m-k-1+i X i e k • C h = (h m-k , . . . , h m-1 , h 0 , . . . , h m-k-1 )
2.3 θ-circulant matrices and q-polynomials rings

Previous framework can be extended to q-polynomial ring: Let θ be a F q -automorphism of F q m . Consider the set { i g i X i , g i ∈ F q m } with the two following operations:

• Addition: usual addition of polynomials

• Multiplication: X * a = a [1] * X where a [i] = θ i (a), ∀i ∈ Z
extended by associativity and distributivity. It forms a ring called q-polynomial ring we denote by F q m [X; θ]. This ring is left and right Euclidean. To distinguish q-polynomials from classical polynomials, we use the notation A X to refer to an element

A ∈ F q m [X; θ].
For h ∈ F q m [X; θ], we denote by w t (h) the Hamming weight of the q-polynomial h, which is its number of non-zero coefficients. We denote by F q m ,m [X; θ] the set of q-polynomials of degree ≤ m.

Definition 5. Let h X = (X m -1) + m-1 i=0 h i X i ∈ F q m [X;
θ] be a monic qpolynomial of degree m. The θ-circulant matrix associated with h is the matrix defined by:

C h,θ =      h 0 h 1 . . . h m-1 h [1] m-1 h [1] 0 . . . h [1] m-2 . . . . . . . . . . . . h [m-1] 1 h [m-1] 2 . . . h [m-1] 0      (1) Proposition 2. Let h X = (X m -1) + m-1 i=0 h i X i ∈ F q m [X;
θ] be a monic qpolynomial of degree m and C h,θ be the θ-circulant matrix associated with h. Then, the matrix C h,θ is the matrix in the basis {1, X, . . . , X m-1 } of the application:

ψ : F q m [X; θ]/(X m -1) → F q m [X; θ]/(X m -1) Q X → Q X h X Proof.
By linearity, we only need to verify that it is true for the elements of the canonical basis of F q m [X; θ]/(X m -1), associated with the canonical basis (e k ) k≤m-1 of F m q . ∀k ∈ {0, . . . , m -1}:

     X k • h X = m i=0 X k h i X i = m-k-1 i=0 h [k] i X i+k + k i=1 h [k] m-k-1+i X i e k • C h,θ = (h [k] m-k , . . . , h [k] m-1 , h [k] 0 , . . . , h [k] m-k-1 )
3 Involutory circulant MDS matrices and polynomial rings

Gupta and Ray in [START_REF] Gupta | On constructions of circulant MDS matrices for lightweight cryptography[END_REF] proved that circulant involutory MDS matrices do not exist in characteristic 2. Based on the framework introduced in section 2.2 we give an alternative simple proof of this result. Then we extend the result to finite fields of any characteristic.

Based on definition 4, we are able to give an algebraic necessary and sufficient condition for such a matrix to be MDS.

Proposition 3. Let h(X) = (X m -1) + m-1 i=0 h i X i ∈ F q [X]
. Let C h be the circulant matrix associated with h. Then, C h is MDS if and only if:

∀Q 1 ∈ F q,m-1 [X] we have w t (Q 1 ) + w t (Q 1 (X)h(X) mod (X m -1)) ≥ m + 1.
Proof.

C h is MDS ⇔ (I m |C h ) is the generator matrix of an MDS code ⇔ ∀(q 0 , . . . , q m-1 ) ∈ F m q , w t ((q 0 , . . . , q m-1 )

• (I m |C h )) ≥ m + 1 ⇔ ∀(q 0 , . . . , q m-1 ) ∈ F m
q , w t (q 0 , . . . , q m-1 ) + w t ((q 0 , . . . , q m-1 )

• C h ) ≥ m + 1 If one considers Q 1 (X) = m-1
i=0 q i X i , then w t (q 0 , . . . , q m-1 ) = w t (Q 1 ). Since from proposition 1, C h corresponds to the multiplication by h(X) in F q [X]/(X m -1), we have:

w t ((q 0 , . . . , q m-1 )

• C h ) = w t (Q 1 (X)h(X) mod (X m -1))),
which proves the proposition.

Example 1. Let F 2 4 be defined by X 4 + X + 1 and α a root of this polynomial. The matrix C h associated with h(X) = (X 4 + 1) +

α 3 X 3 + αX 2 + X + 1 ∈ F 2 4 [X] is a circulant MDS matrix. C h =     1 1 α α 3 α 3 1 1 α α α 3 1 1 1 α α 3 1    
The involutory property for circulant matrices can be written under algebraic form:

Proposition 4. Let h(X) = (X m -1) + m-1 i=0 h i X i ∈ F q [X]. Let C h be the circulant matrix associated with h. Then, C h is involutory if and only if h(X) 2 = 1 mod (X m -1).
Proof. This proposition comes directly from proposition 1 and from the definition of involutory matrices.

A natural question is to determine whether circulant matrices both MDS and involutory exist. A partial answer in characteristic 2 fields for even size matrices was given in [START_REF] Gupta | On constructions of circulant MDS matrices for lightweight cryptography[END_REF]. The following theorem simplifies and extends the proofs to even size MDS matrices in finite fields of any characteristic.

Theorem 1. Let d ≥ 2. There are no involutory circulant MDS matrix of size 2d over fields of characteristic p ≥ 2.

Proof. Suppose that C h is an involutory circulant MDS matrix of size 2d with entries in F q . Let h ∈ F q [X] be the polynomial associated with the circulant matrix C h . The proof is separated into two parts depending on the characteristic of the field.

In characteristic 2: We consider the settings of Proposition 1

. Let Q 1 (X) = X d -1. By hypothesis h 2 (X) -1 = (h(X) -1) 2 = 0 mod X 2d -1. Therefore h(X) - 1 = 0 mod X d -1 therefore Q 2 (X) = Q 1 (X)h(X) mod X 2d -1 = X d -1. Hence w t (Q 1 ) + w t (Q 2 ) = 4 ≤ 2d + 1 and C h is not MDS.
In odd characteristics, notice that X 2d -1 = (X 2 -1)B(X) where B(X) = (X 2(d-1) + X 2(d-2) + . . . + 1) has weight d. Hence X 2d -1 is divisible by X 2 -1 and we have:

C h involutory ⇒ h 2 = 1 mod (X 2d -1) ⇒ h 2 = 1 mod (X 2 -1) ⇒ h 2 = X 2 mod (X 2 -1) Thus, (h -1)(h + 1) = A 1 (X)(X 2 -1) and (h -X)(h + X) = A 2 (X)(X 2 -1) where A 1 , A 2 ∈ F q [X].
We show that (X 2 -1) divides necessarily one of the four polynomials {h -1, h + 1, h -X, h + X}: Suppose X 2 -1 does divides neither h(X) -1 nor h(X) + 1. Since 1 and -1 are the roots of X 2 -1. We have two cases:

1. h(1) = 1 and h(-1) = -1. This implies that h(X) -X contains the roots of X 2 -1 therefore is divisible by X 2 -1;

2. h(1) = -1 and h(-1) = 1. This implies that h(X) + X contains the roots of X 2 -1 therefore is divisible by X 2 -1.

The polynomial (X 2d -1) divides one of the four polynomials:

{B(X)(h -1), B(X)(h + 1), B(X)(h + X), B(X)(h -X)} ∃A(X) ∈ F q [X] such that: • either B(X)h(X) = ±B(X) + A(X)(X 2d -1). • or B(X)h(X) = ±XB(X) + A(X)(X 2d -1)
Since the degree of B(X) is less than 2d -2, the B(X) or XB(X) corresponds to the remainder of B(X)h(X) modulo X 2d -1. Moreover since B(X) has weight d so has XB(X) therefore

w t (B(X)) + w t (B(X)) = w t (B(X)) + w t (XB(X)) = 2d < 2d + 1.
From proposition 1 this implies that C h is not MDS, since by taking

Q 1 (X) = B(X) we have Q 2 (X) = B(X) or Q 2 (X) = XB(X)
and we have found a polynomial that does not satisfy the Hamming weight inequality.

In the particular case of odd characteristics, circulant involutory MDS matrices of odd sizes exist:

Example 2. Consider F 23 be the field with 23 elements. Then, C h , the circulant matrix associated with h(X) = (X 3 -1) + 7X 2 + 7X + 8 is both involutory and MDS:

C g =   8 7 7 7 8 7 7 7 8  
In characteristic 2 there are no such matrices of odd sizes. The result was first proved in [START_REF] Gupta | On constructions of circulant MDS matrices for lightweight cryptography[END_REF]. Here we give an another proof, which is an immediate consequence of previous results.

Theorem 2. Let F q be a finite field of characteristic 2. Let m ≥ 3 be an odd integer.

There are no involutory circulant MDS matrices of size m with entries in F q .

Proof. Suppose that there exists an involutory circulant MDS matrix of size m, say C h associated to the polynomial h. Let g (X) be the derivative of g(X) = (X m -1) that is:

g (X) = mX m-1 .
The polynomial g (X) is prime with g(X). Therefore g(X) has exactly m distinct roots. By hypothesis we have that h(X) 2 = 1 mod X m -1 with h of degree m. Therefore there exist some polynomial A(X) such that:

(h(X) + 1) 2 = A(X)(X m -1).
Therefore, the m roots of X m -1 are also roots of (h(X) + 1) 2 and since they are all simple roots, they are also roots of h(X) + 1. Therefore, h(X) + 1 = 0 mod X m -1. Since h is monic and of degree m necessarily h(X) = X m -1. Therefore C h is not MDS since some of its entries are equal to 0.

In characteristic 2, involutory circulant MDS matrices are of size 1 or 2.

Example 3. Let F 2 4 be defined by X 4 + X + 1 and α a root of this polynomial. The matrix C h associated with h(X) = (X 2 + 1) + α 4 X + α is both involutory and MDS.

C h = α α 4 α 4 α Namely, h(X) 2 = X 4 + α 8 X 2 + α 8 = X 4 mod (X 2 + 1) = X 2 mod (X 2 + 1) = 1 mod (X 2 + 1)
In odd characteristics, the following new theorem shows that there are strong constraints on the size of potential involutory circulant MDS matrices.

Theorem 3. Let m = 2d+1 ≥ 3. Let F q be a field of odd characteristic. If there are circulant involutory MDS matrices of size m then there exists A(X), B(X) ∈ F q [X] such that

• A(X) has degree exactly d • gcd(A(X), B(X)) = 1 • X m -1 = A(X)B(X)
Proof. Suppose there exists an involutory circulant MDS matrix of size m, say C h associated to the polynomial h. Suppose X m -1 is not decomposable into X m -1 = A(X)B(X) where A(X) ∈ F q [X] has degree exactly d. By hypothesis, we have h 2 (X) = 1 mod X m -1. Therefore there exists some polynomial P (X) such that (h(X) -1)(h(X) + 1) = P (X)(X m -1)

In fields of odd characteristics, (h(X) + 1) and (h(X) -1) are coprime. Thus, either gcd(X m -1, h(X) -1) or gcd(X m -1, h(X) + 1) is of degree at least d + 2. There exist then either

B 1 ∈ F q [X] or B 2 ∈ F q [X] of degree at most d -1 such that B 1 (X)(h(X) + 1) or B 2 (X)(h(X) 1) is divided by X m -1. In such a case w t (B i (X)) ≤ d. Since w t (B i (X))+w t (B i (X)) ≤ 2d < 2d+1, for i ∈ {1, 2} and since B 1 (X)h(X) = -B 1 (X) mod (X m -1) or B 2 (X)h(X) = B 2 (X) mod (X m -1), C h is not MDS.
We found circulant involutory MDS matrices by exhaustive search whenever the previous factorization existed. Our conjecture is that for the parameters which are not ruled out by the last three theorems, circulant involutory MDS matrices exist.

Conjecture 1. Let m = 2d + 1 ≥ 3. Let F q be some field of odd characteristic. If X m -1 can be decomposed as A(X)B(X) with A(X) ∈ F q [X] of degree d and gcd(A(X), B(X)) = 1, there exist circulant involutory MDS matrices.

4 θ-circulant matrices and q-polynomial rings

Similarly to classical polynomials, we establish algebraic conditions on q-polynomials to characterize those whose associated θ-circulant matrix is MDS. We denote by mod * g the operation of computing the remainder of the Euclidean division on the right by g:

c X mod * g = r X ⇔ c X = b X * g X + r X , deg(r) < deg(g) Proposition 5. Let h X = (X m -1) + m-1 i=0 h i X i ∈ F q m [X; θ].
Let C h,θ be the θ-circulant matrix associated with h, under the form (1). Then, C h,θ is MDS if and only if ∀Q 1 ∈ F q m ,m-1 [X; θ], we have:

w t (Q 1 X ) + w t (Q 1 X h X mod * (X m -1)) ≥ m + 1 Proof. C h,θ is MDS ⇔ (I m |C h,θ
) is the generator matrix of an MDS code ⇔ ∀(q 0 , . . . , q m-1 ) ∈ F m q m , w t ((q 0 , . . . , q m-1 )

• (I m |C h,θ )) ≥ m + 1 ⇔ ∀(q 0 , . . . , q m-1 ) ∈ F m
q m , w t (q 0 , . . . , q m-1 ) + w t ((q 0 , . . . , q m-1 )

• C h,θ ) ≥ m + 1 If one considers Q 1 X = m-1
i=0 q i X i , then w t (q 0 , . . . , q m-1 ) = w t (Q 1 ). From proposition 2, we know that C h,θ corresponds to right multiplication by h X in F q m [X; θ]/(X m -1), we have then:

w t ((q 0 , . . . , q m-1 ) • C h,θ ) = w t (Q 1 X h X mod * (X m -1))),
which proves the proposition.

Example 4. Let F 2 4 be defined by X 4 + X + 1 and α a root of this polynomial. Let θ be the automorphism defined by a → a2 . The matrix C h,θ associated with h X = (X 4 + 1) + α 10 X 3 + αX

2 + X + 1 ∈ F 2 4 [X; θ] is a θ-circulant MDS matrix. C h,θ =     1 1 α α 10 α 5 1 1 α 2 α 4 α 10 1 1 1 α 8 α 5 1    
The following proposition gives a simple algebraic necessary and sufficient condition on q-polynomials so that their associated θ-circulant matrix is involutory.

Proposition 6. Let h X = (X m -1) + m-1 i=0 h i X i ∈ F q m [X; θ]. Let C h,
θ be the θ-circulant matrix associated with h. Then, C h,θ is a involutory if and only if h X * h X = 1 mod * (X m -1).

Proof. This proposition comes directly from proposition 2 and from the definition of involutory matrices.

Therefore, if one relaxes the condition on the MDS matrix from being circulant to being θ-circulant, this is possible to find involutory matrices with implementation friendly (in a normal basis) properties.

Example 5. Let F 2 4 be defined by X 4 + X + 1 and α a root of this polynomial. Let θ be the automorphism defined by a → a 2 . The matrix C h,θ associated with h X = (X 4 + 1) +

α 7 X 3 + α 14 X 2 + X + α ∈ F 2 4 [X; θ] is a θ-circulant involutory MDS matrix. C h,θ =     α 1 α 14 α 7 α 14 α 2 1 α 13 α 11 α 13 α 4 1 1 α 7 α 11 α 8    
5 Direct Construction of θ-circulant almost involutory MDS matrices

In previous sections, we showed that involutory MDS θ-circulant matrices exist. However this does not give an efficient procedure to find them. The procedure consists in 1. Squaring skew-polynomials of degree m and checking if it can be divided by X m -1.

2. If this is the case then testing the nullity of all the minors of the associated matrix.

Alone, the complexity of the second step is exponential since the number of minors is by itself exponential. Namely for a matrix of size m, the number of minors is equal to

m i=1 m i
Therefore, even for small sizes enumerating the minors becomes rapidly prohibitive. However, by relaxing the involutory condition, we can build directly MDS matrices from Gabidulin codes which are almost involutory. This works for fields of characteristic 2 and matrices of even length. The idea consists in considering the skewed matrix product MM [1] , rather than the usual matrix product, where M

[1] = (m [1] i,j
), provided M = (m i,j ). Computing M [1] is done by applying Galois automorphism on matrix coefficients. For hardware implementations, this can be easily done in a normal basis by simple routing.

The second step consists in searching matrices such that MM [1] is a cyclic permutation and not necessarily the identity. Such a matrix M is called almost-involutory, and can be efficiently implemented in hardware by adding some routing compared to an usual involutory matrix.

Let m ≥ 2 be an integer. We consider F 2 2m and the Frobenius automorphism,

θ(a) = a [1] = a 2 . Let α be a normal element in F 2 2m and G =      α [0] α [1] • • • α [2m-1] α [1] α [2] • • • α [0] . . . . . . . . . . . . α [m-1] α [m] • • • α [m-2]      (2)
The matrix G is a generator matrix of a [2m, m, m + 1] Gabidulin code, [START_REF] Gabidulin | Theory of codes with maximal rank distance[END_REF].

Let G 1 = α [2j+i] m-1,m-1 i=0,j=0
be the m × m matrix composed of even columns of G, and let

G 2 = α [2j+i+1] m-1,m-1 i=0,j=0
, be the m × m matrix composed of odd columns of G.

Theorem 4. Let M = G -1 1 G 2 , then • M is a θ 2 -circulant MDS matrix
• MM [1] is a binary circulant permutation matrix, i.e.

MM [1] =      0 • • • 0 1 1 • • • 0 0 . . . . . . . . . . . . 0 • • • 1 0     
, Let δ i,j be the Kronecker symbol that is δ i,j = 1 if i = j and 0 otherwise. First we need to prove the following lemma: Lemma 1. Let β 0 , . . . , β m-1 , be the first row of G -1 1 , then

1. G -1 1 = β [2i] j m-1,m-1 i=0,j=0
2.

m-1 u=0 β u α [u+2j] = δ 0,j , for all j = 0, . . . , m -1 3.

m-1 u=0 α [2u+i] β

[2u] j = δ i,j , for all i, j = 0, . . . , m -1 2. Build G 1 = α [2j+i] m-1,m-1 i=0,j=0 and G 2 = α [2j+i+1] m-1,m-1 i=0,j=0 . 3. Compute M = G -1 1 G 2 Example 6. Let F 2 8 be defined by X 8 + X 4 + X 3 + X 2 + 1, and α a root of this polynomial. The element α 5 is normal and we consider the Gabidulin code over F 2 8 with generator matrix

Conclusion

Together with a general framework of circulant matrices, we give a new algebraic proof of the non-existence of involutory circulant MDS matrices in fields of characteristic 2.

Relaxing circulancy by considering q-polynomials, we draw general necessary and sufficient conditions for a q-polynomial to yield a MDS matrix or to yield an involutory matrix. We have seen that it may allow designers to build circulant layers that are MDS and involutory as in example 5. Finally, relaxing also the involutory condition, we give a new direct construction of quasi-circulant quasi-involutory MDS matrices from Gabidulin codes.

  10 α 20 α 40 α 80 α 160 α 65 α 130 α 10 α 20 α 40 α 80 α 160 α 65 α 130 α 5 α 20 α 40 α 80 α 160 α 65 α 130 α 5 α 10 α 40 α 80 α 160 α 65 α 130 α 5 α 10 α 20The extraction of the even columns for G 1 and the odd columns for G 2 givesM = G -1 1 G 2 =     α 98 α116 α 132 α 232 α 163 α 137 α 209 α 18 α 72 α 142 α 38 α 71 α 29 α 33 α 58 α 152

≥ 2 m -1

where for j = m -1, since α [2m] = α, the equality comes from α [u+2(j+1)] = α [u] . Therefore β

[2] 0 , . . . , β

[2] m-1 is the second line of G -1 1 . By induction we prove the first item of the lemma. The last item stems from the obvious relation

1 .

Now we prove theorem 4

Proof.

By construction, M is the redundant part of some generator matrix under systematic form of a Gabidulin code of length 2m and of dimension m and is then MDS. From previous lemma, the generic term m i,j of M satisfies:

for all i, j = 0, . . . , m -1 m

i,j , therefore M is a θ 2 -circulant MDS matrix. It remains to prove the last item of the theorem. The generic (i, j)th term of MM [1] is:

Note that the only term in the equation depending on k is α

. Therefore by summing on k and from the third item of lemma, we obtain:

= δ 0,(j-i+1) .

Theorem 4 establishes that the inverse of M -1 = M [1] P, where P is a cyclic permutation matrix. From a hardware implementation point of view, permuting bits consists in routing them, so implies no additional cost. If the chosen basis is normal, then the product with M [1] can be implemented easily with the multipliers implemented for M. The procedure to construct the matrices is:

1. Choose α a normal element in F 2 2m .


Pierre Loidreau

A new rank metric codes based encryption scheme

We design a new McEliece-like rank metric based encryption scheme from Gabidulin codes. We explain why it is not affected by the invariant subspace attacks also known as Overbeck's attacks. The idea of the design mixes two existing approaches designing rank metric based encryption schemes. For a given security our public-keys are more compact than for the same security in the Hamming metric based settings.

Introduction

The security of the main post-quantum (PQ) primitives relies on the difficulty of solving decoding problems in some metrics (Hamming metric for codes, Euclidean metric for lattices). The security of the encryption schemes is generally evaluated relatively to the best existing algorithms solving the considered problems.

At the beginning of the 90's another type of code-based cryptography emerged whose security was based on an alternative metric, the so-called rank metric [START_REF] Gabidulin | Ideals over a non-commutative ring and their applications to cryptography[END_REF]. The difference with McEliece cryptosystem consists in the choice of the family of codes and in the choice of the metric. Originally, there was only one family of codes with an efficient algebraic polynomial-time decoding algorithm up to some bound, the family of Gabidulin codes [START_REF] Gabidulin | Theory of codes with maximum rank distance[END_REF]. The initial proposals were attacked by Gibson who was able to recover a decoder from the public-key in polynomial time, [START_REF] Gibson | Severely denting the Gabidulin version of the McEliece public key cryptosystem[END_REF][START_REF]The security of the Gabidulin public key cryptosystem[END_REF]. Then, there was a succession of reparations and attacks, the latter being usually devastating. Overbeck in 2005 proposed a framework which could be adapted to all variants of Gabidulin codes based encryption schemes, [START_REF] Overbeck | A new structural attack for GPT and variants, Mycrypt[END_REF]. The structural weakness of the scheme came from the fact that Gabidulin codes contain a huge vector space invariant under the Frobenius automorphism. Exploiting this weakness lead to the complete cryptanalysis of all the previous Gabidulin codes based cryptosystems. From this date on, evolutions were proposed claiming to be secure against the existing attacks, [Gab08,GRH09,RGH10]. However, it was recently shown in [START_REF] Otmani | Improved cryptanalysis of rank metric schemes based on Gabidulin codes[END_REF], that all existing variants could be reformulated as instances of the original problem, thus breakable in polynomial-time. Until now the common idea was that although rank metric would be a good candidate for designing code-based primitives with compact keys, a cryptosystem could not be designed from Gabidulin codes.

In the paper we argue against this idea. We show that Gabidulin codes can be used to design effective and secure code-based cryptosystems, moreover with compact keys. By secure we mean that the complexity of an attack consisting in recovering a polynomial-time decoder for the public code is exponential. The point is to scramble sufficiently the structure of Gabidulin codes to avoid existing attacks. Concerning Goppa codes that are subfield subcodes of Generalized Reed-Solomon codes (GRS) on scrambles the structure by keeping the subcode formed with the binary vectors of the parent GRS code. Though GRS codes are unsuitable for use in cryptosystems, Goppa codes are widely admitted as being suitable and even the best choice for the design of secure code-based primitives and even PQ primitives, [AB315]. Unfortunately, this idea does not work for Gabidulin codes since subfield subcodes of Gabidulin codes are isomorphic to the direct product of Gabidulin codes over smaller fields, [START_REF] Gabidulin | Properties of subspace subcodes of Gabidulin codes[END_REF]. We propose a new approach mixing original ideas such as the structure of the encryption scheme and more recent ideas who led to the design of Low Rank Parity-check Codes (LRPC) based encryption schemes. This idea can also be considered as an adaptation to rank metric of an idea in Hamming metric whose interesting instances were broken, [BBC + 16,COTG15]. For a given security of 128 and 256 bits, and a PQ security of 128 Mcbits, we propose a public-key size 20 times smaller than the proposition for long term post-quantum systems, in [AB315] relying on Goppa codes. The parameters being versatile, a designer can tune the parameters according to its needs (smaller key and larger ciphertext expansion or larger key and smaller ciphertext expansion for instance).

The structure of the paper is the following: First we define rank metric, the related decoding problems and we emphasize the fact that the complexity of generic decoding in rank metric is exponentially more difficult than in Hamming metric for the same settings. We evaluate the consequence of Grover algorithm on the generic decoding complexity in a PQ world. In a second part, we present how rank metric is commonly used in the design of encryption schemes. We also briefly detail the reason why Gabidulin codes based encryption schemes were broken. Finally, we show how to hide the structure of Gabidulin codes in a very simple manner, avoiding thus the main weaknesses of Gabidulin codes based cryptosystems. We also analyze the security of the encryption scheme against various attacks and propose sets of parameters.

Rank metric decoding problems

In this section, we show that for the same settings, rank metric decoding problems are exponentially more difficult to solve than their counterparts in Hamming metric.

Rank metric

As an ambient space we consider vectors of length n over a finite field GF (2 m ). Given basis B = {β 1 , . . . , β m } of GF (2 m ) regarded as a GF (2)-vector space, and a vector x = (x 1 , . . . , x n ) ∈ GF (2 m ) n , we consider the transformation:

x → X =    x 11 • • • x 1n . . . . . . . . . x m1 • • • x mn   
where (x 11 , . . . , x m1 ) T is the binary expansion vector of x i in the basis B, i.e.

x i = m j=1
x ji β j .

The rank weight Rk(x) of vector x is: Rk(x) def = Rk(X), where Rk is the usual rank of a binary matrix. Rank metric is independent of the chosen basis and in the following of the paper, we will consider that a binary basis is fixed.

Decoding problems

A rank code C ⊂ GF (2 m )
n is a set of vectors of GF (2 m ) n , together with the distance induced by rank metric.

In applications, it is usual to consider C as being an additive code. In that case, the minimum rank distance of C is the minimum rank weight of any nonzero codeword:

d r (C) def = min x∈C\{0} Rk(x). If the code is GF (2 m )-linear of dimension k, it is called a [n, k, d r ]-code over GF (2 m )
Problem 1 (Bounded distance binary rank decoding (BDR 2 (C, t, y)))

-Instance:

• A 2 m -ary code C =< g 1 , . . . , g K > GF (2) , • An integer t • y ∈ GF (2 m ) n -Problem: Find if it exists λ 1 , . . . , λ K ∈ GF (2) K and e ∈ GF (2 m ) n of rank weight t, such that y = K i=1 λ i g i + e
Solving BDR 2 (C, t, y) is NP -hard. If one considers the matricial form of the problem by expanding every element of GF (2 m ) into a m-dimensional vector over GF (2), then the associated decisional problem is an evolution of the NPcomplete MinRank problem, [START_REF] Courtois | Efficient zero-knowledge authentication based on a linear algebra problem MinRank[END_REF].

Though the complexity of this problem gives some arguments about the difficulty of decoding additive codes in rank metric, a designer will more probably consider linear codes over an extension field GF (2 m ). Therefore, it is more adequate to study the following decoding problem, for GF (2 m )-linear codes.

Problem 2 (Bounded distance 2 m -ary rank decoding (BDR(C, t, y))) -Instance:

• A 2 m -ary code C =< g 1 , . . . , g k > GF (2 m ) , • An integer t • y ∈ GF (2 m ) n -Problem: Find if it exists µ 1 , . . . , µ k ∈ GF (2 m ) k and e ∈ GF (2 m ) n of rank weight t, such that y = k i=1 µ i g i + e
It is not known if the decisional version of this latter problem is NP -complete. However when one considers the dual problem called Rank Syndrome Decoding problem (RSD) a nice result from [START_REF] Gaborit | On the hardness of the decoding and the minimum distance problems for rank codes[END_REF] establishes that if RSD is in ZPP then this would imply that ZPP = NP. The ZPP class is the class of decisional problems solvable by a Turing machine such that:

-The machine runs in polynomial-time of the size of the input -Answers YES, NO or ? ; -The answer YES or NO is the correct answer ; -It answers ? with probability at most 1/2. This statement backs up the feeling that decoding in rank metric is a hard problem.

Hamming metric vs rank metric

In the design of encryption schemes whose security relies on a difficult problem, it is worthwhile to have precise estimation of the best effective complexity of the algorithms solving the problem for randomly and uniformly chosen parameters in a given space.

Decoding in Hamming metric

The complexity of decoding up to some bound a random code in Hamming metric is an old problem, [START_REF] Prange | The use of information sets in decoding cyclic codes[END_REF]. Since the seminal work by Prange a lot of work was done to improve the asymptotic complexity or the effective complexity. The most efficient algorithms are smart refinements of the so-called Information Set Decoding (ISD).

The basics of ISD are: Suppose one wants to decode δn errors in a k dimensional code of length n over GF (2 m ), where δ is less than Varshamov-Gilbert (GV) bound to ensure the uniqueness of the solution. Then one chooses k columns of the generator matrix of the code. If these positions are error-free, and if the k × k matrix has full rank, then decoding consists in making some linear algebra computations and check if the obtained vector has Hamming weight ≤ δn. If this fails then one chooses randomly another set of k positions and proceeds as before, until it works. If any k columns of the generator matrix form a non-singular matrix (MDS code), then after

n k n-δn k
attempts, the probability of success is greater than 1/2. The average complexity of ISD is

n 3 n k n-δn k operations in GF (2 m ).
For constant rate codes, i.e. k = Rn, provided that 0 < R < 1/2, approximations of the Newton binomial gives a running time of:

≈ n 3 2 n[H(R)-H(R-δ)]
binary operations, where

H(R) = -R log 2 R -(1 -R) log 2 (1 -R)

Decoding in rank metric

The first paper giving a precise estimation of the complexity of solving BDR(C, t, y) was published in the, 90's, [START_REF] Chabaud | The cryptographic security of the syndrome decoding problem for rank distance codes[END_REF] and was later improved in [START_REF] Ourivski | New technique for decoding codes in the rank metric and its cryptography applications[END_REF]. Recently a survey unifying different approaches was published [START_REF] Gaborit | On the complexity of the rank syndrome decoding problem[END_REF]. Provided t is less than rank metric GV bound (ensuring uniqueness of the decoding), there exists an algorithm solving BDR(C, t, y) with probability > 1/2 running in: m 3 2 (t-1) (k min (m,n))/n binary ops.

This implies in particular that if m ≥ n the running time is lower bounded by m 3 2 δRn 2 binary ops.

Compared to the n 3 2 n[H(R)-H(R-δ)] complexity of generic ISD for Hamming metric, for the same set of parameters, decoding in rank metric is exponentially more difficult than in Hamming metric.

In Table 1, we fix some decoding complexity. In the second column and third column, we give parameters for codes whose average decoding complexity is approximately equal to the corresponding decoding complexity, in Hamming metric (2nd column) and rank metric (3rd column). The subscripts correspond to the size of the field alphabet, i.e. 2 m , if the considered field is GF (2 m ). Near the parameters we write the minimum size in bytes of the necessary information sufficient to characterize the corresponding code.

The complexity evaluations in Hamming metric are for binary codes and borrowed from [START_REF] Canto-Torres | Analysis of information set decoding for a sub-linear error weight, Post-Quantum Cryptography[END_REF]. The chosen Hamming weight is close to the GV bound. This implies that these are the best possible codes, meaning that any other code satisfying the decoding complexity and rate requirements is necessarily longer than the proposed codes. Concerning rank metric, since for m = n, GV bound corresponds to n(1 -k/n) [START_REF] Loidreau | Asymptotic behaviour of codes in rank metric over finite fields[END_REF] we chose parameters relatively close to this bound to express the decoding complexity. Remark 1. The comparison between rank metric and Hamming metric is not fair when one considers binary codes. Namely, if one fixes the alphabet of the field, the rate of the code in Hamming metric can be kept constant when the lenght goes to infinity. In the rank metric case however this has no sense to do this. The alphabet of the code has to grow to infinity. Therefore the comparison has a sense only when the alphabet size grows.

Post-Quantum security

A study of the PQ security of solving BDR(C, t, y) was already investigated in [START_REF] Gaborit | Ranksynd a PRNG based on rank metric[END_REF]. Since the results are straightforward, we recall how to evaluate this PQ security.

In [START_REF] Bernstein | Post-Quantum Cryptography[END_REF] it is shown that the use of Grover's algorithm implies that the exponential term in the decoding complexity of ISD should be square-rooted. On our previous estimation of the decoding complexity this gives:

≈ n 3 2 n 2 [H(R)-H(R-δ)]
The most efficient algorithm solving BDR(C, t, y) solves the equivalent dual problem RSD, [GRSZ14]: Given a parity-check matrix

H of an [n, k, d] r code C over GF (2 m ), find e ∈ GF (2 m )
n of rank weight t such that

yH T = eH T . (1)
To stress how Grover's algorithm can be employed to improve the decoding complexity we need to recall the principles of the algorithm -e = (e 1 , . . . , e n ) has rank weight t ⇒ for all i, e i ∈ E, a t-dimensional binary subspace of GF (2 m ) ; -Let B = (β 1 , . . . , β t ), a basis of some E such that E ⊂ E ; -System (1) becomes: yH T = BTH T , where T and E are unknown ; -W.l.o.g we can suppose β 1 = 1. Thus solving (1) consists in enumerating t -1 dimensional binary vector subspaces of GF (2 m ) and trying to solve the linear system of (n -k)m equations and t n unknowns.

An assumption is that if the system is overdefined (t n ≤ m(n -k)) then the solution is unique. Therefore the average number of tries to find a suitable vector space is 2 (t-1) (k min (m,n))/n . Remaining linear algebra can be implemented with circuits in O(n 3 ) size. We can apply Grover's algorithm. A lower bound estimation of the PQ complexity of solving BDR(C, t, y) is thus m 3 2 (t-1) (k min (m,n))/(2n) ops.

Rank metric based cryptography

In code-based cryptography, the security is estimated by the decoding complexity of random codes in the considered metric. This estimation requires that the public-key must look like a random code. This implies that the family of codes used as private-key space cannot be distinguished from a family of randomly constructed codes. Given a family F of [n, k, d] codes over a finite field GF (2 m ) with known decoding algorithm up to errors of rank weight t, the original and general procedure to design the pair public/private key pair for a McEliece type cryptosystem is:

1. Select randomly a code in F. The code is given by generator or parity-check matrix G under a form enabling an efficient decoding. 2. Publish a scrambled structure of G → G pub such that G pub looks like random. The scrambling procedure has to be a linear isometry of the metric.

Two types of decoding algorithms are considered:

-Algebraic decoding: It is used for Goppa codes in Hamming metric [START_REF] Mceliece | A public-key system based on algebraic coding theory[END_REF]. This family is recommended for long-term PQ security under well chosen parameters. In rank metric, only Gabidulin codes are of this kind. -Probabilistic decoding: MDPC or QC-MDPC in Hamming metric [START_REF] Misoczki | MDPC-McEliece: New McEliece variants from moderate density parity-check codes[END_REF],

or LRPC in rank metric, [START_REF] Gaborit | Low rank parity check codes and their application to cryptography[END_REF].

Since our interest concerns rank metric, we present how Gabidulin codes and LRPC are used in the design of code-based encryption schemes. We explain the reason why, until now, Gabidulin codes cannot be used in the design of secure encryption schemes. We also present the idea sustaining the design of the family of LRPC since this seminal idea is a natural path which leads us to propose a new families of codes with algebraic decoding to be used in the design of rank metric codes based cryptosystems.

Algebraic decoding based cryptosystems

Gabidulin codes Let n ≤ m and let g = (g 1 , . . . , g n ) ∈ GF (2 m ), where the g i s are linearly independent over GF (2). Let [i] = 2 i such that x → x [i] is the ith power of the Frobenius automorphism x → x 2 . The code Gab k (g), is the linear code with generator matrix

G =      g 1 • • • g n g [1] 1 • • • g [1] n . . . . . . . . . g [k-1] 1 • • • g [k-1] n      , (2)
i.e.

Gab k (g) = {xG | x ∈ GF (2 m ) k }.
These codes can be decoded in polynomial-time for errors of rank weight up to (n -k)/2 , see [START_REF] Gabidulin | Theory of codes with maximum rank distance[END_REF].

Invariant subspace attack From the origins, see [START_REF] Gabidulin | Ideals over a non-commutative ring and their applications to cryptography[END_REF], numerous designs of Gabidulin codes based encryption schemes were proposed relying on the model of McEliece cryptosystem. However, all these proposals were broken by derivations of the so-called invariant subspace attack. The reason is the inherent structure of the family of Gabidulin codes. A detailed analysis can be found in [START_REF] Kshevetskiy | Security of GPT-like public-key cryptosystems based on linear rank codes, 3rd International Workshop on Signal Design and Its Applications in Communications[END_REF][START_REF] Otmani | Improved cryptanalysis of rank metric schemes based on Gabidulin codes[END_REF].

We present the principle of the attacks. This is essential to understand where lies the weakness and how to get rid of it. In every proposed Gabidulin codes based encryption scheme, the public-key G pub can be rewritten under the form

G pub = S(X | G)P, (3)
where P is a binary (n + t) × (n + t) invertible matrix, G is a matrix generating an [n, k, d r ] Gabidulin code under the form (2), and S is an u × k-matrix with entries in GF (2 m ), where u ≤ k. Now consider the action of x → x 2 i def = x [i] on the entries of G pub denoted by

G [i]
pub . We have

G [i] pub = S [i] (X [i] | G [i] )P [i] . Since P is binary this implies G [i] pub = S [i] (X [i] | G [i] )P.
Let C pub be the code generated by G pub and let C

[i] pub be the code obtained by raising the codewords of C pub (resp. C) to the ith power of the Frobenius automorphism. From the structure of the public code, we have

dim C pub + • • • + C [i] pub ≤ min (n, k + i + t). ( 4
)
If C pub were a random u-dimensional code one would expect the dimension of

C pub + • • • + C [i]
pub to be equal to min(n, (i + 1)u) with a high probability. Hence the previous property provides a distinguisher of the public code. Moreover, if k + i + t = n -1, and if the dimension is exactly equal to 1 then a polynomialtime decoder for the public code can be recovered by simple elementary linear algebra.

Probabilistic decoding based cryptosystems

Low Rank Parity-Check Codes The principle consists in selecting randomly a λ-dimensional vector space V ⊂ GF (2 m ).

constructing an (n -k) × n matrix H = (h ij ), where h ij ∈ V are randomly selected.

The private-key consists of the knowledge of H and the public key is G pub , the generator matrix of the code with parity-check matrix H under systematic form. The key idea behind the decoding procedure is: Suppose one receives a ciphertext y = xG pub + e, where G pub H T pub = 0. Then

yH T = xG pub H T 0 +eH T .
Since e has rank t its entries belong to a binary vector space E of dimension t. This implies that the entries of yH T belong to the binary vector space

E * V = {ev | e ∈ E, v ∈ V}.
The dimension of E * V is upper bounded by tλ. If dim(E * V) = tλ a basis for E can be recovered with an estimated error probability of 2 -(n-k+1-tλ) , [START_REF] Gaborit | New results for rank-based cryptography[END_REF].

-The main strength of this scheme is that the private key is randomly selected with entries in a secret λ-dimensional vector space. Thus it prevents all types of attacks attempting to use some algebraic properties to break the scheme. -Concerning the weaknesses of the scheme, the first one is that the estimated residual error decoding probability is non-negligible for small parameters.

The second main weakness comes from the fact that the decoding is probabilistic. This could induce attacks on the model of [START_REF] Guo | A key recovery attak on MDPC with CCA security using decoding errors[END_REF] consisting in guessing the secret vector space by observing the behavior of a decoder.

The new cryptosystem

In the case of Gabidulin codes, the strategy, which works for GRS codes, consisting of scrambling their structure by considering a subfield subcode is a dead-end.

The reason is that a subfield subcode of a Gabidulin code is essentially isomorphic to the direct sum of Gabidulin codes over the subfield, [START_REF] Gabidulin | Properties of subspace subcodes of Gabidulin codes[END_REF].

Our approach consists in scrambling the codes via the choice of a randomly selected vector space of GF (2 m ) of fixed dimension. The essential idea comes from the rank multiplication property used to show that the LRPC decoding procedure works. This could also be interpreted as a rank metric equivalent of the idea in [BBC + 16] which, for short, replaces the permutation matrix in McEliece cryptosystem by a matrix multiplying the Hamming weight of the vectors.

Proposition 1 (Rank multiplication). Let P ∈ M n (V) be an invertible matrix with entries in a binary λ-dimensional vector space V ⊂ GF (2 m ). For all x ∈ GF (2 m ) n , Rk(xP) ≤ λRk(x).

Proof. Consider x = (x 1 , . . . , x n ) ∈ GF (q m ) of rank weight r. Let X =< x 1 , . . . , x n > be generated by < y 1 , . . . , y t >. Suppose moreover that V =< α 1 , . . . , α λ >, then the entries of xP, belong to the vector space < y i α j > i,j which has dimension ≤ λt.

Design of the encryption scheme

The key generation procedure is the following:

-Private key:

• A Gabidulin code of length n over GF (2 m ), dimension k with generator matrix G under the form (2) ; • A non-singular k × k-matrix S with entries in GF (2 m ); • A λ-dimensional subspace of GF (2 m ), denoted by V ; • A non-singular matrix P with entries in V, i.e. P ∈ M n (V).

-Public key: G pub = SGP -1 . The public code C pub is generated by G pub .

The encryption and decryption procedures are: The public-key is a randomly chosen generator matrix of the code

-Encryption of x ∈ GF (2 m
C pub def = CP -1 = {cP -1 | c ∈ C}.
A corollary of Proposition 1 gives: Corollary 1. Let C be a [n, k, d] r code over GF (q m ). Let V be a λ-dimensional subspace of GF (q m ) seen as a GF (q)-vector space. And let P ∈ M n (V). Then

CP -1 def = {cP -1 | c ∈ C}

Security arguments

We analyze the security of the scheme.

1. The first type of attacks consists in decoding the ciphertext in the public code. We suppose that the public code cannot be distinguished from a random code. Therefore the complexity of recovering a plaintext from a ciphertext corresponds to the complexity of solving BDR(C pub , λRk(e), y). From sections 2.3 and 2.4, we have:

-Decoding complexity: m 3 2 (λr-1) (k min (m,n))/n binary operations.

-PQ-security: m 3 2 1 2 (λr-1) (k min (m,n))/n operations. 2. The question of the distinguishability of the public-code from a random code is raised. The arguments presented in section 3.1 do not work. Namely, raising the public-key to the ith power of the Frobenius gives:

G [i] pub = S [i] G [i] (P -1 ) [i]
.

Matrix P has entries in V, but the entries of P -1 have no reason to belong to some strict subspace of GF (2 m ). Therefore (4) is not satisfied and the usual distinguisher for a Gabidulin code does not work. An attacker could try to recover a decoder for the public code by solving

H pub = HP, (5)
where H pub is a (n-k)×n parity-check matrix of the public code C pub under systematic form, H = (h

[i]
j ) is a parity-check matrix of a Gabidulin code, and P has entries in a λ-dimensional vector space. W.l.o.g, we suppose that H is known. This hypothesis might seem very strong but if we consider the case m = n this does not remove security. In that let < h 1 , . . . , h n > 2 be a basis of GF (2 m ) regarded as a GF (2)-vector space, and let a matrix H = ((h j ) [i] ) under the form (2). There exists a binary invertible matrix M such that H = H M. System (5) becomes H pub = H MP P . Since M is binary, P has entries in V. Under this setting, we investigate two ways of solving (5), which gives us a lower bound on the estimation of the complexity of recovering a decoder from the public-key.

-System (5) is an underdefined affine system with n × n unknowns (the entries of P) and n(n -k) equations. Given a solution P 0 of the system, an attacker has to search for a matrix in the coset P 0 + P whose entries belong to a λ-dimensional vector space. A solution is to enumerate the coset of size 2 m(n 2 -n(n-k)) and if the matrices belong to a common λdimensional vector space.

-Another approach consists in decomposing the entries of P = (p ij ) under the form p ij = λ u=1 µ (u) ij α u , where α 1 , . . . , α λ are candidates to be the basis of V, and the µ (u) ij are binary elements. Once the equations are projected on the binary field, we obtain a system with mn(n -k) equations and mλ + λn 2 unknowns. If α 1 , . . . , α λ is fixed then the system is linear and overdefined (λ < n ≤ m) and can thus be solved in polynomial time. For the previous reasons, we estimate that a lower bound on the complexity of recovering a decoder corresponds to the enumeration of λ -1-dimensional GF (2)-subspaces of GF (2 m ). The choice of λ -1 rather than λ is justified since if λ = 1, i.e. V =< α >, then for some element α ∈ GF (2 m ), it is obvious that an attack can be achieved in polynomial time. Namely, P = (1/α)P with P has entries in GF (2). Therefore, we suppose that 1 ∈ V. The lower bound on the complexity is thus 2 (λ-1)m-(λ-1) 2 .

Choice of parameters

Table 2 proposes some parameters for an expected security, and with a ciphertext expansion between 1.6 and 1.8. Since the parameters on can consider to decrease the key-size by increasing the expansion factor, but the designer has to note that case other types of decoding attacks can occur and should be taken into account, [START_REF] Gaborit | New results for rank-based cryptography[END_REF].

For a 2 128 bits security the key-size proposed in [AB315] for a McEliece encryption scheme using Goppa codes is approximately of 1 MB. For an equivalent rate our proposal gives a public-key 20 times smaller.

Acknowledgments

The author expresses deep thanks to Alain Couvreur who pointed out the existence of a straightforward distinguisher if the parameters are not carefully chosen. The proposed parameters avoid the problem. The author also wishes to thank the reviewers who made constructive comments to improve the quality of the paper and pointed out mistakes and misses in the original submission.

We proposed a new code-based public-key cryptosystem based on the derivation of Gabidulin codes. We did not consider security reductions but presented detailed arguments why we think that our proposal makes it possible to design secure code-based encryption schemes in rank metric. Security conversion exist that take as input One-way encryption schemes and convert it into a IND -CCA2 in the random oracle model, [START_REF] Kobara | Semantically secure McEliece public-key cryptosystems-conversions for McEliece PKC, Public-Key Cryptography -PKC 2001[END_REF][START_REF] Berger | Designing an efficient and secure public-key cryptosystem based on reducible rank codes[END_REF]. Our proposal is versatile and can be declined for finite fields of any characteristic since Gabidulin codes have the same structure over any finite field. To evaluate the security we need to replace 2 by the cardinality of the considered base field, say q if we consider Gabidulin codes over GF (q m ).

  ) k : • Choose a random vector e ∈ GF (2 m ) n of rank weight (n -k)/(2λ) ; • Compute y = xG pub + e ; • Send the encrypted message y to the receiver. -Decryption of y: • Compute yP = xSG + eP ; • Since P has entries in V and from Proposition 1 eP has rank weight ≤ λ (n -k)/(2λ) ≤ (n -k)/2 , and can be decoded with G; • Recover xS and eP by decoding and recover x by multiplying with S -1 .

has dimension k

  and minimum rank distance d ≥ d/λ . Proof. Since P is invertible C and CP -1 have the same dimension. Concerning the minimum distance, suppose that d < d/λ. Then let c ∈ CP -1 = 0 with rank weight d . By construction cP ∈ C. From proposition 1, Rk(cP) ≤ d λ < d, which implies that cP = 0. Thus c = 0, which contradicts the hypothesis.

  . PQ Dec. Sec. K. Rec. Sec. Key sizem = n = 50, k = 32, λ = 3, t = 3 ≈ 2 81 ≈ 2 49 ≈ 2 96 3.6 KB m = 96, n = 64, k = 40, λ = 3, t = 4 ≈ 2 139 ≈ 2 80 ≈ 2 188 11.5 KB m = 128, n = 120, k = 80, λ = 5, t = 4 ≈ 2 261 ≈ 2 141 ≈ 2 496 51 KBTable2: Proposition of parameters for the family of codes used in the cryptosystem

Table 1 :

 1 Comparisons of the decoding complexity of codes on GV bound for Hamming metric and for rank metric [n, k, w]q correspond to a q-linear code of length n, dimension k, correcting w errors in the considered metric

	Dec. Complex.	Ham. Met. Gen. Mat.	Rank Met. Gen. Mat.
	2 128	[2400, 2006, 58]2 ≈ 100 KBytes [48, 39, 4] 2 48 ≈ 2.2 KBytes
	2 256	[4150, 3307, 132]2 ≈ 350 KBytes [70, 50, 5] 2 70 ≈ 8.7 KBytes