On the security of a Loidreau rank metric code based encryption scheme

We present a polynomial time attack of a rank metric code based encryption scheme due to Loidreau for some parameters.

1. Processor: Intel® Core™ i5-8250U CPU @ 1.60GHz.

The authors express a deep gratitude to the anonymous referees for their very relevant suggestions. The second author was funded by French ANR projects ANR-15-CE39-0013 Manta and ANR-17-CE39-0007 CBCrypt.

Authors and Affiliations

1. DGA, 60, bd du Général Martial Valin, CS21623 - 75509, Paris cedex 15, France

   Daniel Coggia

2. Inria de Paris, 2 rue Simone Iff, CS 42112 75589, Paris CEDEX 12, France

   Daniel Coggia

3. Inria Saclay - Île-de-France, 1 rue Honoré d’Estienne d’Orves, Bâtiment Alan Turing, Campus de l’École polytechnique, 91120, Palaiseau, France

   Alain Couvreur

4. LIX, UMR 7161, École Polytechnique, 91120, Palaiseau, France

   Alain Couvreur

Corresponding author

Correspondence to Alain Couvreur.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

This is one of several papers published in Designs, Codes and Cryptography comprising the “Special Issue on Coding and Cryptography 2019”.

Proof of Proposition 1

1.1 Preliminaries on Gaussian binomial coefficients

Notation 1

In what follows, we denote by \({\left[ \begin{array}{c} a \\ b \end{array}\right] }_{q^m}\) the Gaussian binomial coefficient representing the number of subspaces of dimension b of a vector space of dimension a over \({\mathbb {F}}_{q^m}\).

Lemma 8

There exists a positive constant C such that for any pair of positive integers n, k such that \(n \geqslant k\), we have

Proof

By definition of Gaussian binomials, we have

Since \(n \geqslant k \), we get

which yields the left hand inequality. To get the other equality, we need to bound from above the product:

where the last equality is obtained by applying the change of variables \(j = k-1-t\). Set

The sequence \(a_k\) is increasing and converges. Indeed,

and the series with general term \(-\log (1 - 1/q^{j+1})\) converges. As a conclusion, the right-hand inequality is obtained by taking

\(\square \)

Remark 2

A finer analysis would permit to prove that \(C \leqslant {\left( \frac{q}{q-1} \right) }^{\frac{q}{q-1}}\). In particular, since \(q \geqslant 2\), we have that \(C \leqslant 4\).

1.2 The proof

Let \({\mathscr {C}_{rand }}\) be a subspace of \({\mathbb {F}}_{q^m}^n\) chosen uniformly at random among its subspaces of dimension k. From \({\mathscr {C}_{rand }}\) we build the map

The image of this map is \({\mathscr {C}_{rand }}+ {\mathscr {C}_{rand }}^{[1]} + \cdots + {\mathscr {C}_{rand }}^{[s]}\) and hence the dimension of \({\mathscr {C}_{rand }}+ {\mathscr {C}_{rand }}^{[1]} + \cdots + {\mathscr {C}_{rand }}^{[s]}\) is related to the dimension of the kernel of \(\Psi \). Therefore, our approach will consist in estimating \({\mathbb {E}}\left( |\ker \Psi |\right) \).

We have

Lemma 9

Let \(\mathscr {A}\) be a subspace of \({\mathbb {F}}_{q^m}^n\) of dimension \(t\leqslant k\). Then

where C is the constant of Lemma 8.

Proof

We have

Using Lemma 8 we get the upper bound,

\(\square \)

For any \(0 \leqslant t \leqslant s+1\), we introduce the set

Thanks to (9) and Lemma 9, we can write that

Lemma 10

Let \(1 \leqslant t \leqslant k-1\). Then,

Proof

Let \(({\textit{\textbf{x}}}_0, \ldots , {\textit{\textbf{x}}}_s) \in E_t\). Since the \({\textit{\textbf{x}}}_i\)’s span a space of dimension t, there exists a unique \((s+1-t)\times (s+1)\) full rank matrix \(\textit{\textbf{M}}\) in reduced echelon form with entries in \({\mathbb {F}}_{q^m}\) such that

Let us count the number of possible \((s+1)\)–tuples \(({\textit{\textbf{x}}}_0, \dots , {\textit{\textbf{x}}}_s)\) satisfying (11) and such that \({\textit{\textbf{x}}}_0 + {\textit{\textbf{x}}}_1^{[1]} +\cdots + {\textit{\textbf{x}}}_s^{[s]} = 0\). For any \(1 \leqslant i \leqslant n\), we have

Let us label the columns of \(\textit{\textbf{M}}\) from 0 to s. Let \({\mathcal {P}} \subseteq \{0, \ldots , s\}\) be the set of indices of columns which are pivots for \(\textit{\textbf{M}}\) and \({\mathcal {P}}^c\) its complementary. We denote by a the smallest element of \({\mathcal {P}}^c\). Notice that

In (12), we can eliminate any \(x_{j,i}\) where \(j\in {\mathcal {P}}\) using (13). By this manner we get an expression depending only on the \(x_{j,i}\)’s for \(j \in {\mathcal {P}}^c\). If we fix the value of the \(x_{r, i}\)’s for any \(r \in {\mathcal {P}}^c \setminus \{a\}\), we obtain an equation of the form

where Q is a q–polynomial of q–degree at most a. There are then at most \(q^{a}\) possible values for \(x_{a, i}\) for any choice of the elements \(x_{r,i}\) with \(r \in {\mathcal {P}}^c \setminus \{i\}\). Using (14) we deduce that there are at most

possible choices for the tuple \((x_{0, i}, \dots , x_{s,i})\). Consequently, Eq. (11) has at most \(q^{mn(t-1) + n(s+1-t)}\) solutions.

Finally, since the full rank \((s+1-t)\times (s+1)\) matrices in row echelon form are in one–to–one correspondence with t–dimensional subspaces of \({\mathbb {F}}_{q^m}^{s+1}\) there are \({\left[ \begin{array}{c} s+1 \\ t \end{array}\right] }_{q^m}\) possible choices for \(\textit{\textbf{M}}\). Using Lemma 8, we deduce the result. \(\square \)

Combining (10) and Lemma 10, we get

By assumption (in the statement of Proposition 1), we have \(s < k\). Next, since \(n \leqslant m\), we see that the exponents in the above sum are all less than or equal 0. More precisely,

Consequently, we have the following result.

Proposition 5

There is a positive constant \(C'\) such that

To conclude the proof of Proposition 1, suppose that

This means that

Using Markov inequality together with Proposition 5, we get

This concludes the proof.

Reprints and permissions