Two modifications for Loidreau’s code-based cryptosystem

Abstract

This paper presents two modifications for Loidreau’s cryptosystem, a rank metric-based cryptosystem constructed by using Gabidulin codes in the McEliece setting. Recently a polynomial-time key recovery attack was proposed to break this cryptosystem in some cases. To prevent this attack, we propose the use of subcodes to disguise the secret codes in Modification I. In Modification II, we choose a random matrix of low column rank to mix with the secret matrix. Our analysis shows that these two modifications can both resist the existing structural attacks. Furthermore, these modifications have a much more compact representation of public keys compared to Classic McEliece, which has been selected into the fourth round of the NIST-PQC project.

1 Introduction

In 1978, McEliece [41] proposed the first code-based public-key cryptosystem, namely the McEliece cryptosystem based on Goppa codes. Since then cryptologists have made extensive study on its security [11, 16, 31, 33]. Apart from some weak keys [40], the McEliece cryptosystem remains secure up to now. The main drawback of this cryptosystem lies in its large public-key size, which makes it unpractical in many situations. To overcome this problem, many variants have been proposed. In 1986, Niederreiter [43] introduced a knapsack-type cryptosystem using GRS codes, which was shown to be insecure by Sidelnikov and Shestakov in [51]. But if we use Goppa codes in the Niederreiter setting, it was proved to be equivalent to the McEliece cryptosystem in terms of security [34]. GRS codes allow us to reduce the public-key size due to their optimal error-correcting capability. Many variants based on GRS codes were proposed after Niederreiter’s work. However, almost all of these variants were broken one after another because of GRS codes being highly structured. In the BBCRS cryptosystem [5], the authors proposed the use of a dense matrix rather than a permutation matrix to disguise the structure of the underlying GRS code. In this proposal, the column scrambler is a matrix of the form $(R+T)^{-1}$, where T is a sparse matrix and R is a dense matrix of low rank. With this approach, the public code seems quite different from GRS codes. This variant therefore can resist some known structural attacks, such as the Sidelnikov-Shestakov attack [51]. However, in [14, 15] the authors presented a polynomial-time key recovery attack against this variant in some cases. Although we can adjust the parameters to prevent such an attack, it would bring some other problems such as the decryption complexity increasing exponentially and a higher request of error-correcting capability for the underlying code.

In 1985 Gabiduin [18] introduced a new family of rank metric codes, known as the Gabidulin codes. Since the complexity of decoding general rank metric codes is much higher than that of decoding Hamming metric codes [12, 45], it is feasible to obtain much smaller public-key sizes by building cryptosystems in the rank metric. In [21] the authors proposed to use Gabidulin codes in the McEliece setting and introduced the GPT cryptosystem. Unfortunately, several structural attacks were put forward to completely break this system [27, 30, 46].To prevent these attacks, variants based on different masking skills for Gabidulin codes were proposed [19, 22, 37, 47, 48]. But in [44] the authors declared the failure of all the previous masking techniques for Gabidulin codes. In [17] Faure and Loidreau proposed a cryptosystem also relying on Gabidulin codes but not in the McEliece setting, which can be seen as a rank metric counterpart of Augot-Finiasz cryptosystem [4]. Until the work in [23], the Faure-Loidreau cryptosystem had never been severely attacked. Two reparations of this scheme aimed at resisting this attack were proposed independently and differently in [32, 49]. Bombar and Couvreur [9] investigated the supercode decoding of Gabidulin codes and induced from this decoder a polynomial-time attack on these two reparations. Loidreau [38] proposed a cryptosystem constructed by using Gabidulin codes in the McEliece setting. Different from the original GPT cryptosystem, the isometric matrix is replaced with a matrix whose inverse is taken over an $\mathbb {F}_q$-subspace of $\mathbb {F}_{q^m}$ of dimension $\lambda$. By doing this, the public code seems quite random. Loidreau claimed that his proposal could prevent the existing structural attacks. However, this claim was proved to be invalid by the authors in [13] when $\lambda =2$ and the code rate is greater than 1/2. Soon after this, the author in [26] generalized this attack to the case of $\lambda >2$ and the code rate being greater than $1-\frac{1}{\lambda }$. However, it is feasible to prevent this attack even when the secret code rate is greater than $1-\frac{1}{\lambda }$ according to our analysis in the present paper.

The rest of this paper is organised as follows. In Sect. 2 notations and some concepts about rank metric codes used throughout this paper are given. Section 3 is devoted to a simple description of Loidreau’s cryptosystem. In Sect. 4 we shall introduce part of Coggia-Couvreur attack. Following this, our two modifications for Loidreau’s cryptosystem will be introduced in Sect. 5, then security analysis of our modifications will be given in Sect. 6. In Sect. 7, we will give some suggested parameters for different security levels and make a comparison on public-key size with some NIST-PQC submissions. Sect. 8 concludes this paper.

2 Preliminaries

2.1 Notations and basic concepts

Let q be a prime power. Denote by $\mathbb {F}_q$ the finite field with q elements, and by $\mathbb {F}_{q^m}$ an extension field of $\mathbb {F}_q$ of degree m. For positive integers k, n, denote by $\mathcal {M}_{k,n}(\mathbb {F}_{q^m})$ the space of $k\times n$ matrices over $\mathbb {F}_{q^m}$, and by $GL_n(\mathbb {F}_{q^m})$ the space of invertible matrices in $\mathcal {M}_{n,n}(\mathbb {F}_{q^m})$. For a matrix $M\in \mathcal {M}_{k,n}(\mathbb {F}_{q^m})$, the column rank of M with respect to $\mathbb {F}_q$, denoted by $\text {Clr}_q(M)$, is the largest number of columns of M linearly independent over $\mathbb {F}_q$. Denote by $\langle M\rangle _{q^m}$ the vector space spanned by the rows of M over $\mathbb {F}_{q^m}$.

An [n, k] linear code $\mathcal {C}$ over $\mathbb {F}_{q^m}$ is a k-dimensional subspace of $\mathbb {F}_{q^m}^n$. The dual code of $\mathcal {C}$, denoted by $\mathcal {C}^\perp$, is the orthogonal space of $\mathcal {C}$ under the usual Euclidean inner product over $\mathbb {F}_{q^m}^n$. A $k\times n$ full-rank matrix $G\in \mathcal {M}_{k,n}(\mathbb {F}_{q^m})$ is called a generator matrix of $\mathcal {C}$ if the vector space $\langle G\rangle _{q^m}$ is exactly the code $\mathcal {C}$. A generator matrix of $\mathcal {C}^\perp$ is called a parity-check matrix of $\mathcal {C}$.

2.2 Rank metric codes

Now we recall some basic concepts about rank metric and rank metric codes.

Definition 1

For a vector $\varvec{x}=(x_1,\cdots ,x_n)\in \mathbb {F}_{q^m}^n$, the rank support of $\varvec{x}$ is defined to be $\text {Supp}(\varvec{x})=\langle x_1,\cdots ,x_n\rangle _q$.

Definition 2

For a vector $\varvec{x}\in \mathbb {F}_{q^m}^n$, the rank weight of $\varvec{x}$ is defined as $w_R(\varvec{x})=\dim _q(\text {Supp}(\varvec{x}))$.

Remark 1

For a matrix $M\in \mathcal {M}_{k,n}(\mathbb {F}_{q^m})$, the rank support of M is defined as $\text {Supp}(M)=\sum _{i=1}^k\text {Supp}(\varvec{m}_i)$, where $\varvec{m}_i$ denotes the i-th row of M. And the rank weight of M is defined as $w_R(M)=\dim _q(\text {Supp}(M))$.

Definition 3

For two vectors $\varvec{x},\varvec{y}\in \mathbb {F}_{q^m}^n$, the rank distance between $\varvec{x}$ and $\varvec{y}$ is defined as $d_R(\varvec{x},\varvec{y})=w_R(\varvec{x}-\varvec{y})$.

It is easy to verify that $d_R(\cdot ,\cdot )$ defines a proper metric on $\mathbb {F}_{q^m}^n$. A linear code endowed with the rank metric is called a rank metric code.

Definition 4

For a rank metric code $\mathcal {C}\subseteq \mathbb {F}_{q^m}^n$, the minimum rank distance of $\mathcal {C}$ is defined to be $d(\mathcal {C})=\min \{w_R(\varvec{x}):\varvec{x}\in \mathcal {C}\backslash \{\varvec{0}\}\}$.

Note that the minimum rank (Hamming) distance of a linear code equals its minimum rank (Hamming) weight. For Hamming metric codes, the minimum distance d of an [n, k] linear code satisfies the Singleton bound $d\leqslant n-k+1$ [35]. Similarly, the minimum rank distance of a rank metric code satisfies the following Singleton-style bound. And a rank metric code attaining the Singleton-style bound is called a Maximum Rank Distance (MRD) code.

Proposition 1

(Singleton-style bound) [20] For positive integers $n\leqslant m$, let $\mathcal {C}\subseteq \mathbb {F}_{q^m}^n$ be an [n, k] rank metric code, then the minimum rank distance of $\mathcal {C}$ with respect to $\mathbb {F}_q$ satisfies the following inequality

$$\begin{aligned} d(\mathcal {C})\leqslant n-k+1. \end{aligned}$$

The following proposition states a fact that the maximum rank weight of a rank metric code is bounded from above by the column rank of its generator matrix.

Proposition 2

For a matrix $M\in \mathcal {M}_{k,n}(\mathbb {F}_{q^m})$ with $\text {Clr}_q(M)=r$, the maximum rank weight of the code $\langle M\rangle _{q^m}$ is bounded by r from above.

Proof

It suffices to prove that $w_R(\varvec{v})\leqslant r$ for any $\varvec{v}\in \langle M\rangle _{q^m}$. Note that $\text {Clr}_q(M)=r$, then there exists $Q\in GL_n(\mathbb {F}_q)$ such that $MQ=[M'|0]$, where $M'\in \mathcal {M}_{k,r}(\mathbb {F}_{q^m})$ with $\text {Clr}_q(M')=r$. For any $\varvec{v}\in \langle M\rangle _{q^m}$, there exists $\varvec{x}\in \mathbb {F}_{q^m}^k$ such that $\varvec{v}=\varvec{x}M$ and

$$\begin{aligned} \varvec{v}Q=\varvec{x}MQ=\varvec{x}[M'|0]=(\varvec{x}'||\varvec{0}), \end{aligned}$$

where $\varvec{x}'\in \mathbb {F}_{q^m}^r$. Then $w_R(\varvec{v})=w_R(\varvec{v}Q)\leqslant r$, which leads to the conclusion immediately.

2.3 Gabidulin codes

Gabidulin codes are actually an analogue of GRS codes in the rank metric, and these two types of codes resemble each other closely in the construction principle. GRS codes admit generator matrices with the Vandermonde structure, while Gabidulin codes can be described through Moore matrices defined as follows.

Definition 5

For $a\in \mathbb {F}_{q^m}$ and an integer s, we denote by $a^{[s]}=a^{q^s}$ the s-th Frobenius power of a. A matrix $G\in \mathcal {M}_{k,n}(\mathbb {F}_{q^m})$ is called a Moore matrix generated by $\varvec{a}=(a_1,\cdots ,a_n)\in \mathbb {F}_{q^m}^n$ if the s-th row of G equals the coordinate-wise Frobenius power $\varvec{a}^{[s-1]}=(a_1^{[s-1]},\cdots ,a_n^{[s-1]})$ for $1\leqslant s\leqslant k$, that is

$$\begin{aligned} G= \begin{pmatrix} a_1&{}a_2&{}\cdots &{}a_n\\ a_1^{[1]}&{}a_2^{[1]}&{}\cdots &{}a_n^{[1]}\\ \vdots &{}\vdots &{}&{}\vdots \\ a_1^{[k-1]}&{}a_2^{[k-1]}&{}\cdots &{}a_n^{[k-1]} \end{pmatrix}. \end{aligned}$$

(1)

For a matrix $G=(G_{ij})\in \mathcal {M}_{k,n}(\mathbb {F}_{q^m})$, we define $G^{[s]}=(G_{ij}^{[s]})$. For a set $S\subseteq \mathbb {F}_{q^m}^n$, we define $S^{[s]}=\{\varvec{x}^{[s]}:\varvec{x}\in S\}$. For a linear code $\mathcal {C}\subseteq \mathbb {F}_{q^m}^n$, it is easy to verify that $\mathcal {C}^{[s]}$ is also an $\mathbb {F}_{q^m}$-linear code.

Definition 6

(Gabidulin codes) For positive integers $k\leqslant n\leqslant m$, let $\varvec{a}\in \mathbb {F}_{q^m}^n$ with $w_R(\varvec{a})=n$ and G be the $k\times n$ Moore matrix generated by $\varvec{a}$. The [n, k] Gabidulin code $\mathcal {G}_{n,k}(\varvec{a})$ over $\mathbb {F}_{q^m}$ generated by $\varvec{a}$ is defined to be the linear space $\langle G\rangle _{q^m}$.

A major reason for Gabidulin codes being widely used in the design of cryptosystems consists in their remarkable error-correcting capability and simple algebraic structure. Now we recall some properties of Gabidulin codes through the following two theorems.

Theorem 1

[28] The Gabidulin code $\mathcal {G}_{n,k}(\varvec{a})$ is an MRD code. In other words, $\mathcal {G}_{n,k}(\varvec{a})$ attains the Singleton-style bound for rank metric codes.

It is easy to see from Theorem 1 that $d(\mathcal {G}_{n,k}(\varvec{a}))=n-k+1$, which implies that any $\lfloor \frac{n-k}{2}\rfloor$ rank errors can be corrected in theory. Indeed, several efficient decoding algorithms for Gabidulin codes already exist [18, 36, 50].

Theorem 2

[23] The dual code of $\mathcal {G}_{n,k}(\varvec{a})$ is the Gabidulin code $\mathcal {G}_{n,n-k}(\varvec{b}^{[-n+k+1)]})$ for some $\varvec{b}\in \mathcal {G}_{n,n-1}(\varvec{a})^\perp$ with $w_R(\varvec{b})=n$.

3 Loidreau’s cryptosystem

Now we give a simple description of Loidreau’s cryptosystem proposed in [38]. For a desired security level, choose a finite field $\mathbb {F}_q$ and positive integers $\lambda \ll k<n\leqslant m$. Loidreau’s cryptosystem consists of the following three algorithms.

• Key generation

  Randomly choose a vector $\varvec{a}\in \mathbb {F}_{q^m}^n$ with $w_R(\varvec{a})=n$, let G be a generator matrix of $\mathcal {G}_{n,k}(\varvec{a})$. Let $\mathcal {V}\subset \mathbb {F}_{q^m}$ be a randomly chosen $\mathbb {F}_q$-linear space of dimension $\lambda$. Randomly choose $P\in GL_n(\mathcal {V})$ such that $w_R(P)=\lambda$ and compute $G_{pub}=GP^{-1}$. We publish $(G_{pub},t)$ as the public key where $t=\lfloor \frac{n-k}{2\lambda }\rfloor$, and keep $(\varvec{a},P)$ as the private key.

• Encryption

  For a plaintext $\varvec{m}\in \mathbb {F}_{q^m}^k$, randomly choose a vector $\varvec{e}\in \mathbb {F}_{q^m}^n$ with $w_R(\varvec{e})=t$. The ciphertext corresponding to $\varvec{m}$ is computed as $\varvec{c}=\varvec{m}G_{pub}+\varvec{e}$.

• Decryption

  For a ciphertext $\varvec{c}\in \mathbb {F}_{q^m}^n$, compute $\varvec{c}'=\varvec{c}P=\varvec{m}G+\varvec{e}P$. Because of $w_R(\varvec{e}P)\leqslant w_R(\varvec{e})\cdot w_R(P)\leqslant \lfloor \frac{n-k}{2}\rfloor$, decoding $\varvec{c}'$ will lead to $\varvec{e}'=\varvec{e}P$. Then one can recover $\varvec{e}$ by computing $\varvec{e}'P^{-1}$ and hence the plaintext $\varvec{m}$ by solving the linear system $\varvec{m}G_{pub}=\varvec{c}-\varvec{e}$.

4 Coggia–Couvreur attack

Before describing Coggia–Couvreur attack, we first introduce a distinguisher for Gabidulin codes, which provides an approach for us to distinguish Gabidulin codes from general ones.

4.1 A distinguisher for Gabidulin codes

Most cryptosystems based on Gabidulin codes have been proved to be insecure against structural attacks. Although these attacks were proposed to cryptanalyze different variants, the principle for them is based on the observation that one can distinguish Gabidulin codes from general ones by performing a simple operation on these codes.

Given a random linear code $\mathcal {C}\subseteq \mathbb {F}_{q^m}^n$ of dimension $k\leqslant n/2$, the expected dimension of the code $\mathcal {C}+\mathcal {C}^{[1]}$ equals 2k, or equivalently $\mathcal {C}\cap \mathcal {C}^{[1]}=\{\varvec{0}\}$ holds with high probability. But for a Gabidulin code $\mathcal {G}_{n,k}(\varvec{a})$, we have $\mathcal {G}_{n,k}(\varvec{a})+\mathcal {G}_{n,k}(\varvec{a})^{[1]}=\mathcal {G}_{n,k+1}(\varvec{a})$, or equivalently $\dim _{q^m}(\mathcal {G}_{n,k}(\varvec{a})+\mathcal {G}_{n,k}(\varvec{a})^{[1]})=k+1$. More generally, we have the following two propositions.

Proposition 3

[13] Let $\mathcal {C}\subseteq \mathbb {F}_{q^m}^n$ be a random linear code of length n and dimension k. For a non-negative integer l and a positive integer $s<k$, we have

$$\begin{aligned} \text {Pr}\left( \dim _{q^m}(\mathcal {C}+\mathcal {C}^{[1]}+ \cdots +\mathcal {C}^{[s]})\leqslant \min \{n,(s+1)k\}-l\right) =\mathcal {O}(q^{-ml}). \end{aligned}$$

Proposition 4

[13] Let $k\leqslant n$ and s be a positive integer, then for any $\varvec{a}\in \mathbb {F}_{q^m}^n$ with $w_R(\varvec{a})=n$, we have

$$\begin{aligned} \mathcal {G}_{n,k}(\varvec{a})\cap \mathcal {G}_{n,k}(\varvec{a})^{[1]}&=\mathcal {G}_{n,k-1}(\varvec{a}^{[1]});\\ \mathcal {G}_{n,k}(\varvec{a})+\cdots +\mathcal {G}_{n,k}(\varvec{a})^{[s]}&= \mathcal {G}_{n,k+s}(\varvec{a}). \end{aligned}$$

4.2 Description of Coggia–Couvreur attack

In this part we investigate the structural vulnerability of Loidreau’s cryptosystem in the case of $\lambda =2$ and the rate of the public code $\mathcal {C}_{pub}=\langle G_{pub}\rangle _{q^m}$ being greater than 1/2. The principle for Coggia-Couvreur attack lies in Propositions 3 and 4. Instead of operating the public code directly, Coggia and Couvreur considered the dual of the public code because of the following lemma.

Lemma 1

[13] Any parity-check matrix $H_{pub}$ of $\mathcal {C}_{pub}$ can be expressed as

$$\begin{aligned} H_{pub}=H_{sec}P^T, \end{aligned}$$

where $H_{sec}$ is a parity-check matrix of the secret Gabidulin code $\mathcal {G}_{n,k}(\varvec{a})$.

The authors considered the case of $\lambda =2$, namely $\mathcal {V}\subseteq \mathbb {F}_{q^m}$ has dimension 2 over $\mathbb {F}_q$. Assume that $\mathcal {V}=\langle \alpha ,\beta \rangle _{\mathbb {F}_q}$ for some $\alpha ,\beta \in \mathbb {F}_{q^m}^*$. Let $H'_{sec}=\alpha H_{sec}$ and $P'=\alpha ^{-1}P$, then $H_{pub}=H'_{sec}P'^T$. It is clear that $H_{sec}'$ spans the same code as $H_{sec}$ and entries of $P'$ are contained in $\mathcal {V}'=\langle 1,\alpha ^{-1}\beta \rangle _{\mathbb {F}_q}$. Hence it is reasonable to suppose $\mathcal {V}=\langle 1,\gamma \rangle _{\mathbb {F}_q}$ for some $\gamma \in \mathbb {F}_{q^m}^*$. In this situation, we express $P^T$ in the form of

$$\begin{aligned} P^T=P_0+\gamma P_1, \end{aligned}$$

where $P_0,P_1\in \mathcal {M}_{n,n}(\mathbb {F}_q)$.

According to Theorem 2, there exists $\varvec{b}\in \mathcal {G}_{n,n-1}(\varvec{a})^\perp$ with $w_R(\varvec{b})=n$ such that $\mathcal {G}_{n,k}(\varvec{a})^\perp =\mathcal {G}_{n,n-k}(\varvec{b})$. We define

$$\begin{aligned} \varvec{g}=\varvec{b}P_0, \varvec{h}=\varvec{b}P_1. \end{aligned}$$

As for the triple $(\gamma ,\varvec{g},\varvec{h})$, the authors made the following two assumptions:

• (1) $\mathcal {G}_{n,n-k+2}(\varvec{g})\cap \mathcal {G}_{n,n-k+2}(\varvec{h})=\{\varvec{0}\}$ and $w_R(\varvec{g}),w_R(\varvec{h})\ge n-k+2$;

• (2) $m>2$ and $\gamma$ is not contained in any proper subfield of $\mathbb {F}_{q^m}$.

The rationality for these two assumptions can be explained as follows. According to the authors’ experiments in MAGMA [10], Assumption (1) holds with an extremely high probability. Apparently $m>2$ is reasonable because of $m\geqslant n$. On the other hand, if $\gamma$ is contained in some proper subfield of $\mathbb {F}_{q^m}$, then the adversary can find $\gamma$ through the exhausting method for the reason that even the union of all proper subfields of $\mathbb {F}_{q^m}$ contains much less elements than $\mathbb {F}_{q^m}$. Hence $\gamma$ cannot be contained in any proper subfield of $\mathbb {F}_{q^m}$.

The core of Coggia–Couvreur attack is to find the triple $(\gamma ,\varvec{g},\varvec{h})$ or its equivalent form (see [13] for more details). And with the knowledge of the triple $(\gamma ,\varvec{g},\varvec{h})$ or its equivalent form, one can decrypt any ciphertext in polynomial time and therefore completely break Loidreau’s cryptosystem.

The following two lemmas are useful for analysing the security of our modifications.

Lemma 2

[13] The code $\mathcal {C}_{pub}^\perp$ is spanned by

$$\begin{aligned} \varvec{g}+\gamma \varvec{h},\varvec{g}^{[1]}+\gamma \varvec{h}^{[1]}, \cdots ,\varvec{g}^{[n-k-1]}+\gamma \varvec{h}^{[n-k-1]}. \end{aligned}$$

(2)

Lemma 3

[13] Under Assumption (1), we have that $\mathcal {C}_{pub}^\perp +{\mathcal {C}_{pub}^\perp }^{[1]}$ is spanned by

$$\begin{aligned} \varvec{g}+\gamma \varvec{h}\text { and }\varvec{g}^{[1]},\varvec{h}^{[1]},\cdots ,\varvec{g}^{[n-k-1]},\varvec{h}^{[n-k-1]}\text { and } \varvec{g}^{[n-k]}+\gamma ^{[1]}\varvec{h}^{[n-k]}, \end{aligned}$$

and

$$\begin{aligned} (\mathcal {C}_{pub}^\perp +{\mathcal {C}_{pub}^\perp }^{[1]}) \cap ({\mathcal {C}_{pub}^\perp }^{[1]}+{\mathcal {C}_{pub}^\perp }^{[2]}) \end{aligned}$$

is spanned by

$$\begin{aligned} \varvec{g}^{[1]}+\gamma ^{[1]}\varvec{h}^{[1]}\ \text {and}\ \varvec{g}^{[2]},\varvec{h}^{[2]}, \cdots ,\varvec{g}^{[n-k-1]},\varvec{h}^{[n-k-1]}\ \text {and}\ \varvec{g}^{[n-k]}+\gamma ^{[1]}\varvec{h}^{[n-k]}. \end{aligned}$$

Remark 2

Similar to Lemma 3, it is easy to verify that

$$\begin{aligned} (\mathcal {C}_{pub}^\perp +{\mathcal {C}_{pub}^\perp }^{[1]}) \cap ({\mathcal {C}_{pub}^\perp }^{[1]}+{\mathcal {C}_{pub}^\perp }^{[2]}) \cap \cdots \cap ({\mathcal {C}_{pub}^\perp }^{[n-k-1]}+{\mathcal {C}_{pub}^\perp }^{[n-k]}) \end{aligned}$$

(3)

yields a code spanned by

$$\begin{aligned} \varvec{g}^{[n-k-1]}+\gamma ^{[n-k-1]}\varvec{h}^{[n-k-1]}\ \text {and}\ \varvec{g}^{[n-k]}+\gamma ^{[1]}\varvec{h}^{[n-k]}. \end{aligned}$$

(4)

The key point for Coggia–Couvreur attack is that one can obtain (4) by computing (3). But if ${\mathcal {C}_{pub}^\perp }^{[i]}+{\mathcal {C}_{pub}^\perp }^{[i+1]}(0\leqslant i\leqslant n-k-1)$ happens to be the full space $\mathbb {F}_{q^m}^n$, computing (4) will lead to nothing but the full space itself, which means that Coggia-Couvreur attack will fail in this situation. Our first modification for Loidreau’s cryptosystem is inspired by this observation. On the other hand, if $\mathcal {C}_{pub}^\perp$ does not contain the full code spanned by (2), then one cannot obtain (4) from (3) either even if ${\mathcal {C}_{pub}^\perp }^{[i]}+{\mathcal {C}_{pub}^\perp }^{[i+1]}(0\leqslant i\leqslant n-k-1)$ is not the full space. Modification II is based on this observation and this is true according to our analysis in Sect. 6.

5 Our modifications

In code-based cryptography, randomness is widely used in both the key generation and encryption procedures. In terms of the intersection of a given linear code and a randomly chosen linear space, we have the following proposition.

Proposition 5

Let n, k, l be positive integers with $k+l<n$. Let $\mathcal {C}\subseteq {\mathbb {F}_{q^m}^n}$ be some fixed linear code of dimension k, and $\mathcal {V}$ be a randomly and uniformly chosen subspace of $\mathbb {F}_{q^m}^n$ of dimension l. Then with high probability, we have $\mathcal {C}\cap \mathcal {V}=\{\varvec{0}\}$.

Remark 3

Proposition 5 states a fact that for a linear code $\mathcal {C}$ and a randomly chosen linear space $\mathcal {V}$, we have that $\mathcal {C}\cap \mathcal {V}=\{\varvec{0}\}$ with high probability. Meanwhile, it is reasonable to conclude that for a $k\times n$ full-rank matrix H and a randomly chosen $l\times n$ full-rank matrix A with $k+l<n$, the block matrix $\begin{pmatrix}A\\ H\end{pmatrix}$ has full rank with high probability.

5.1 Description of Modification I

For a desired security level, choose a finite field $\mathbb {F}_q$ and positive integers $\lambda \ll k<n\leqslant m$ and $l\geqslant k-\frac{n}{2}$. Our first modification consists of the following three procedures.

• Key generation

  Randomly choose $\varvec{a}\in \mathbb {F}_{q^m}^n$ with $w_R(\varvec{a})=n$. Let $\mathcal {G}=\mathcal {G}_{n,k}(\varvec{a})$ be an [n, k] Gabidulin code with H as a parity-check matrix. Randomly choose $A\in \mathcal {M}_{l,n}(\mathbb {F}_{q^m})$ of full rank and set $H_{sub}=\begin{pmatrix}A\\ H\end{pmatrix}$. By Remark 3, $H_{sub}$ has rank $n-k+l$ with high probability. Let $G_{sub}$ be a generator matrix of $\langle H_{sub}\rangle _{q^m}^\perp$, which is actually a subcode of $\mathcal {G}$ of dimension $k'=k-l$. Randomly choose an $\mathbb {F}_q$-linear space $\mathcal {V}\subseteq \mathbb {F}_{q^m}$ with $\dim _q(\mathcal {V})=\lambda$ and $P\in GL_n(\mathcal {V})$ with $w_R(P)=\lambda$. Without loss of generality, we assume that the submatrix of $G_{sub}P^{-1}$ from the first $k'$ columns is invertible. Choose a matrix $S\in GL_{k'}(\mathbb {F}_{q^m})$ to change $G_{pub}=SG_{sub}P^{-1}$ into systematic form. We publish $(G_{pub},t)$ as the public key where $t=\lfloor \frac{n-k}{2\lambda }\rfloor$, and keep $(\varvec{a},P)$ as the private key.

• Encryption

  For a plaintext $\varvec{m}\in \mathbb {F}_{q^m}^{k'}$, randomly choose $\varvec{e}\in \mathbb {F}_{q^m}^n$ with $w_R(\varvec{e})=t$. Then the ciphertext corresponding to $\varvec{m}$ is computed as $\varvec{c}=\varvec{m}G_{pub}+\varvec{e}$.

• Decryption

• For a ciphertext $\varvec{c}\in \mathbb {F}_{q^m}^n$, compute $\varvec{c}'=\varvec{c}P=\varvec{m}SG_{sub}+\varvec{e}P$. Since $w_R(\varvec{e}P)\leqslant w_R(\varvec{e})\cdot \lambda \leqslant \lfloor \frac{n-k}{2}\rfloor$. Applying the decoder of $\mathcal {G}$ to $\varvec{c}'$ leads to $\varvec{e}'=\varvec{e}P$, then we compute $\varvec{e}=\varvec{e}'P^{-1}$. The restriction of $\varvec{c}-\varvec{e}$ to the first $k'$ coordinates will be $\varvec{m}$.

Remark 4

According to the analysis in Sect. 4.2, we can always suppose $1\in \mathcal {V}$. If $\lambda =1$, then $\mathcal {V}=\mathbb {F}_q$ and $P^{-1}\in GL_n(\mathbb {F}_q)$, which implies that $G_{pub}$ spans a subcode of $\mathcal {G}$. Then one can exploit the r-Frobenius weak attack [29] to this modification. To prevent this attack, we should make sure that $\lambda \geqslant 2$ in Modification I.

5.2 Description of Modification II

For a desired security level, choose a finite field $\mathbb {F}_q$ and positive integers $\lambda \ll k<n\leqslant m$ and $l\ll \min \{k,n-k\}$. Our second modification consists of the following three procedures.

• Key generation

  Randomly choose $\varvec{a}\in \mathbb {F}_{q^m}^n$ with $w_R(\varvec{a})=n$. Let $\mathcal {G}=\mathcal {G}_{n,k}(\varvec{a})$ be an [n, k] Gabidulin code with G as a generator matrix. Randomly choose $M\in \mathcal {M}_{k,n}(\mathbb {F}_{q^m})$ with $\text {Clr}_q(M)=l$ and let $G_M=G+M$. It is easy to see that $G_M$ is of full rank. Randomly choose an $\mathbb {F}_q$-linear space $\mathcal {V}\subseteq \mathbb {F}_{q^m}$ with $\dim _q(\mathcal {V})=\lambda$ and $P\in GL_n(\mathcal {V})$ with $w_R(P)=\lambda$. Without loss of generality, we assume that the submatrix of $G_MP^{-1}$ from the first k columns is invertible. Choose a matrix $S\in GL_k(\mathbb {F}_{q^m})$ to change $G_{pub}=SG_MP^{-1}$ into systematic form. We publish $(G_{pub},t)$ as the public key where $t=\lfloor \frac{n-k-2l}{2\lambda }\rfloor$, and keep (S, G, P) as the private key.

• Encryption

  For a plaintext $\varvec{m}\in \mathbb {F}_{q^m}^k$, randomly choose a vector $\varvec{e}\in \mathbb {F}_{q^m}^n$ with $w_R(\varvec{e})=t$. Then the ciphertext corresponding to $\varvec{m}$ is computed as $\varvec{c}=\varvec{m}G_{pub}+\varvec{e}$.

• Decryption

  For a ciphertext $\varvec{c}\in \mathbb {F}_{q^m}^n$, compute $\varvec{c}'=\varvec{c}P=\varvec{m}SG+\varvec{m}SM+\varvec{e}P$. Because of

  $$\begin{aligned} w_R(\varvec{m}SM+\varvec{e}P)\leqslant w_R(\varvec{m}SM)+w_R(\varvec{e}P)\leqslant l+\lambda t\leqslant \lfloor \frac{n-k}{2}\rfloor , \end{aligned}$$

  applying the decoder of $\mathcal {G}$ to $\varvec{c}'$ will lead to $\varvec{m}SG$. Then the plaintext $\varvec{m}$ can be recovered by solving the linear system $\varvec{m}G_{pub}=\varvec{c}-\varvec{e}$ with a complexity of $\mathcal {O}(n^3)$.

Remark 5

With a similar analysis as in Remark 4, we should make sure that $\lambda \geqslant 2$ in this modification. Otherwise, Modification II can be reduced to the GPT cryptosystem that has been completely broken.

6 Security analysis

We now discuss the security of our two modifications in the following two cases, namely the structural attacks and the generic attacks.

6.1 Structural attacks

These attacks aim to recover the code structure or an equivalent private key from the public information. In [38], Loidreau’s cryptosystem was shown to resist the invariant subspace attack, which is also known as Overbeck’s attack. Note that our modifications exploit the same technique to disguise the structure of Gabidulin code, naturally we believe that our modifications can also prevent Overbeck’s attack.

Loidreau [38] proposed an exponential attack to recover an efficient decoder of the public code for the case of $m=n$, which requires a complexity of $\mathcal {O}\big (((m-k)^2m+\lambda m^2)^3q^{(\lambda -1)m-(\lambda -1)^2}\big )$. In a talk [39] at CBCrypto 2021, Loidreau modified this attack to deal with the general case where $m=n$ is not a must, requiring a complexity of $\mathcal {O}\big (((n-k)^2m+\lambda nm)^3q^{(\lambda -1)m-(\lambda -1)^2}\big )$. When applying this modified attack to Modification I, we obtain a complexity of

$$\begin{aligned} \mathcal {O}\big (((n-k)(n-k+l)m+\lambda nm)^3q^{(\lambda -1)m-(\lambda -1)^2}\big ). \end{aligned}$$

For Modification II, things are a little more complicated. Note that $\text {Clr}_q(M)=l$, there exists $T\in GL_n(\mathbb {F}_q)$ such that $MT=[M^*|0]$ where $M^*\in \mathcal {M}_{k,l}(\mathbb {F}_{q^m})$ with $\text {Clr}_q(M^*)=l$. Let $P'=PT$, then $G_{pub}=S[G_{lt}+M^*|G_{rt}]P'^{-1}$, where $G_{lt}$ denotes the left most l columns of GT and $G_{rt}$ the right most $n-l$ columns respectively. It is clear that $G_{rt}$ generates an $[n-l,k]$ Gabidulin code, denoted by $\mathcal {G}_{rt}$. Let $H_{pub}\in \mathcal {M}_{n-k,n}(\mathbb {F}_{q^m})$ be a parity-check matrix of $\mathcal {C}_{pub}$, then $H_{pub}$ can be expressed as

$$\begin{aligned} H_{pub}= \begin{pmatrix} A\\ 0|\,H_{rt} \end{pmatrix}P'^T, \end{aligned}$$

(5)

where $A\in \mathcal {M}_{l,n}(\mathbb {F}_{q^m})$ and $H_{rt}\in \mathcal {M}_{n-k-l,n-l}(\mathbb {F}_{q^m})$ forms a parity-check matrix of $\mathcal {G}_{rt}$. Let $H_{mr}\in \mathcal {M}_{n-l-k,m}(\mathbb {F}_{q^m})$ be a Moore matrix generated by a vector whose components form a basis of $\mathbb {F}_{q^m}$ over $\mathbb {F}_q$. It is easy to see that there exists $Q\in \mathcal {M}_{n,m}(\mathbb {F}_q)$ and $S'\in \mathcal {M}_{n-l-k,n-k}(\mathbb {F}_{q^m})$ such that

$$\begin{aligned} S'H_{pub}=H_{mr}Q^T{P'}^T=H_{mr}{P''}^T, \end{aligned}$$

where $P''=P'Q$ and clearly $\text {Supp}(P')=\text {Supp}(P'')$. With a similar analysis to [39], one obtains a linear system of $(n-l-k)n$ equations and $(n-k)(n-k-l)m+\lambda mn$ variables by enumerating $\lambda -1$-dimensional supspaces of $\mathbb {F}_{q^m}$ over $\mathbb {F}_q$. The complexity of this attack is

$$\begin{aligned} \mathcal {O}\big (((n-k)(n-k-l)m+\lambda mn)^3q^{(\lambda -1)m-(\lambda -1)^2}\big ). \end{aligned}$$

In the remaining part, we explain why our two modifications can prevent the Coggia-Couvreur attack. Firstly, we introduce a distinguisher for the public code of Loidreau’s cryptosystem.

Proposition 6

[13] For an instance of Loidreau’s cryptosystem with parameters $(m,n,k,\lambda )$, the dual of the public code satisfies

$$\begin{aligned} \dim _{q^m}(\mathcal {C}_{pub}^\perp +{\mathcal {C}_{pub}^\perp }^{[1]} +\cdots +{\mathcal {C}_{pub}^\perp }^{[\lambda ]})\leqslant \lambda \dim _{q^m}(\mathcal {C}_{pub}^\perp )+\lambda . \end{aligned}$$

However, for a random linear code we have the following proposition.

Proposition 7

[13] For an [n, k] random linear code $\mathcal {C}_{rand}\subseteq \mathbb {F}_{q^m}^n$, the following equality holds with high probability

$$\begin{aligned} \dim _{q^m}(\mathcal {C}_{rand}^\perp +{\mathcal {C}_{rand}^\perp }^{[1]}+ \cdots +{\mathcal {C}_{rand}^\perp }^{[\lambda ]})=\min \{n,(\lambda +1)(n-k)\}. \end{aligned}$$

6.1.1 Analysis of Modification I

Firstly, we shall introduce the following proposition.

Proposition 8

Let $\mathcal {C}\subseteq \mathbb {F}_{q^m}^n$ be an [n, k] linear code that has G as a generator matrix. For any integer s, $\mathcal {C}^{[s]}$ is also an [n, k] linear code over $\mathbb {F}_{q^m}$ and has $G^{[s]}$ as a generator matrix.

Proof

The proof is trivial and therefore omitted here. $\square$

Let $\mathcal {C}_{pub}=\langle G_{pub}\rangle _{q^m}$ be the public code of Modification I. Now we show that ${\mathcal {C}_{pub}^\perp }^{[i]}+{\mathcal {C}_{pub}^\perp }^{[i+1]}\,(0\leqslant i\leqslant n-k-1)$ is exactly the full space $\mathbb {F}_{q^m}^n$, namely all these $n-k$ codes have dimension n. By Proposition 8, it suffices to compute the dimension of $\mathcal {C}_{pub}^\perp +{\mathcal {C}_{pub}^\perp }^{[1]}$.

Let $H_{pub}$ be a parity-check matrix of $\mathcal {C}_{pub}$, then $H_{pub}=H_{sub}P^T$ and

$$\begin{aligned} \mathcal {C}_{pub}^\perp =\langle H_{sub}P^T\rangle _{q^m}=\langle HP^T\rangle _{q^m}+\langle AP^T\rangle _{q^m}. \end{aligned}$$

Hence

$$\begin{aligned} \mathcal {C}_{pub}^\perp +{\mathcal {C}_{pub}^\perp }^{[1]}=\langle HP^T\rangle _{q^m}+\langle HP^T\rangle _{q^m}^{[1]}+\langle AP^T\rangle _{q^m}+\langle AP^T\rangle _{q^m}^{[1]}. \end{aligned}$$

According to Lemma 3, $\langle HP^T\rangle _{q^m}+\langle HP^T\rangle _{q^m}^{[1]}$ is spanned by

$$\begin{aligned} \varvec{g}+\gamma \varvec{h}\ \text {and}\ \varvec{g}^{[1]},\varvec{h}^{[1]},\cdots ,\varvec{g}^{[n-k-1]},\varvec{h}^{[n-k-1]}\ \text {and}\ \varvec{g}^{[n-k]}+\gamma ^{[1]}\varvec{h}^{[n-k]}, \end{aligned}$$

(6)

where $\gamma ,\varvec{g}$ and $\varvec{h}$ are defined as in Sect. 4.

Note that these $2(n-k)$ vectors in (6) are linearly independent over $\mathbb {F}_{q^m}$. Indeed, if there exist $x_i,y_i\in \mathbb {F}_{q^m}\,(0\leqslant i\leqslant n-k-1)$ such that

$$\begin{aligned} x_0(\varvec{g}+\gamma \varvec{h})+y_0(\varvec{g}^{[n-k]}+\gamma ^{[1]}\varvec{h}^{[n-k]}) +\sum _{i=1}^{n-k-1}x_i\varvec{g}^{[i]}+\sum _{i=1}^{n-k-1}y_i\varvec{h}^{[i]}=\varvec{0}. \end{aligned}$$

Then we have

$$\begin{aligned} y_0\varvec{g}^{[n-k]}+\sum _{i=0}^{n-k-1}x_i\varvec{g}^{[i]}=-x_0\gamma \varvec{h}-y_0\gamma ^{[1]}\varvec{h}^{[n-k]}-\sum _{i=1}^{n-k-1}y_i\varvec{h}^{[i]}. \end{aligned}$$

It is clear that $y_0\varvec{g}^{[n-k]}+\sum _{i=0}^{n-k-1}x_i\varvec{g}^{[i]}\in \mathcal {G}_{n,n-k+2}(\varvec{g})$ and $-x_0\gamma \varvec{h}-y_0\gamma ^{[1]}\varvec{h}^{[n-k]}-\sum _{i=1}^{n-k-1}y_i\varvec{h}^{[i]}\in \mathcal {G}_{n,n-k+2}(\varvec{h})$. Hence $x_i=y_i=0\,(0\leqslant i\leqslant n-k-1)$ because of Assumption (1).

By Proposition 3, we have that $\dim _{q^m}(\langle AP^T\rangle _{q^m}+\langle AP^T\rangle _{q^m}^{[1]})=2l$ holds with high probability. Together with $l\geqslant k-\frac{n}{2}$ and Proposition 5, we have that $\dim _{q^m}(\mathcal {C}_{pub}^\perp +{\mathcal {C}_{pub}^\perp }^{[1]})=n=\min \{2(n-k+l),n\}$. Furthermore, we have $\dim _{q^m}({\mathcal {C}_{pub}^\perp }^{[i-1]}+{\mathcal {C}_{pub}^\perp }^{[i]})=n$ because of Proposition 8, or equivalently ${\mathcal {C}_{pub}^\perp }^{[i-1]}+{\mathcal {C}_{pub}^\perp }^{[i]}=\mathbb {F}_{q^m}^n$ for $1\leqslant i\leqslant n-k$, which means that by computing the intersection (3) the adversary can obtain nothing but the full space itself. Hence Coggia-Couvreur attack will fail in this situation.

6.1.2 Analysis of Modification II

Note that $\text {Clr}_q(M)=l$, then $1\leqslant \text {Rank}(M)\leqslant l$. Assume that $\text {Rank}(M)=l'$, then $\dim _{q^m}(\langle M\rangle _{q^m})=l'\leqslant l$. By Proposition 2, we have $w_R(\varvec{v})\leqslant l$ for any $\varvec{v}\in \langle M\rangle _{q^m}$. Together with $d(\mathcal {G})=n-k+1\gg l$, we have $\langle M\rangle _{q^m}\cap \mathcal {G}=\{\varvec{0}\}$.

Let $\mathcal {C}_{pub}=\langle G_{pub}\rangle _{q^m}=\langle SG_MP^{-1}\rangle _{q^m}$, then a parity-check matrix for $\mathcal {C}_{pub}$ can be written as $H_{pub}=H_MP^T$, where $H_M$ is an $(n-k)\times n$ full-rank matrix such that $SG_MH_M^T=0$. It is easy to see that $\langle H_M\rangle _{q^m}$ contains a subcode of $\mathcal {G}^\perp$ of dimension $n-k-l'$. Hence $\mathcal {C}_{pub}^\perp$ contains a subcode of $\mathcal {C}_1$ of dimension $n-k-l'$, where $\mathcal {C}_1$ is spanned by

$$\begin{aligned} \varvec{g}+\gamma \varvec{h},\varvec{g}^{[1]}+\gamma \varvec{h}^{[1]},\cdots ,\varvec{g}^{[r]}+\gamma \varvec{h}^{[r]},\ \text {where r=n-k-1}. \end{aligned}$$

Similarly ${\mathcal {C}_{pub}^\perp }^{[1]}$ contains a subcode of $\mathcal {C}_2$ of dimension $n-k-l'$, where $\mathcal {C}_2$ is spanned by

$$\begin{aligned} \varvec{g}^{[1]}+\gamma ^{[1]}\varvec{h}^{[1]},\varvec{g}^{[2]}+\gamma ^{[1]}\varvec{h}^{[2]},\cdots ,\varvec{g}^{[r+1]}+\gamma ^{[1]}\varvec{h}^{[r+1]}. \end{aligned}$$

Finally we have that $\mathcal {C}_{pub}^\perp +{\mathcal {C}_{pub}^\perp }^{[1]}$ contains a subcode of $\mathcal {C}=\mathcal {C}_1+\mathcal {C}_2$ of dimension at most $2(n-k-l')$, where $\mathcal {C}$ is spanned by

$$\begin{aligned} \varvec{g}+\gamma \varvec{h}\ \text {and}\ \varvec{g}^{[1]},\varvec{h}^{[1]},\cdots , \varvec{g}^{[r]},\varvec{h}^{[r]}\ \text {and}\ \varvec{g}^{[r+1]}+\gamma ^{[1]}\varvec{h}^{[r+1]}. \end{aligned}$$

In Coggia–Couvreur attack, the adversary can obtain (4) by computing (3). Our analysis shows that the adversary cannot perform the same operation on Modification II to obtain (4). Here we demonstrate this point with the method of reduction to absurdity.

Assume that

$$\begin{aligned} \langle \varvec{g}^{[r]}+\gamma ^{[r]}\varvec{h}^{[r]},\varvec{g}^{[r+1]}+\gamma ^{[1]} \varvec{h}^{[r+1]}\rangle _{q^m}\subseteq \bigcap _{i=0}^r ({\mathcal {C}_{pub}^\perp }^{[i]}+{\mathcal {C}_{pub}^\perp }^{[i+1]}). \end{aligned}$$

(7)

Then for any $0\leqslant i\leqslant r$, we have

$$\begin{aligned} \varvec{g}^{[r]}+\gamma ^{[r]}\varvec{h}^{[r]},\varvec{g}^{[r+1]}+\gamma ^{[1]}\varvec{h}^{[r+1]}\in {\mathcal {C}_{pub}^\perp }^{[i]}+{\mathcal {C}_{pub}^\perp }^{[i+1]}. \end{aligned}$$

(8)

Applying the inverse of the i-th Frobenius map to both sides of (8), there will be

$$\begin{aligned} \varvec{g}^{[r-i]}+\gamma ^{[r-i]}\varvec{h}^{[r-i]},\varvec{g}^{[r-i+1]}+\gamma ^{[1-i]}\varvec{h}^{[r-i+1]}\in \mathcal {C}_{pub}^\perp +{\mathcal {C}_{pub}^\perp }^{[1]}, \end{aligned}$$

or equivalently

$$\begin{aligned} \varvec{g}+\gamma \varvec{h}\ \text {and}\ \varvec{g}^{[1]},\varvec{h}^{[1]},\cdots , \varvec{g}^{[r]},\varvec{h}^{[r]}\ \text {and}\ \varvec{g}^{[r+1]}+\gamma ^{[1]}\varvec{h}^{[r+1]}\in \mathcal {C}_{pub}^\perp +{\mathcal {C}_{pub}^\perp }^{[1]}. \end{aligned}$$

This implies that $\mathcal {C}\subseteq \mathcal {C}_{pub}^\perp +{\mathcal {C}_{pub}^\perp }^{[1]}$, which conflicts with the previous conclusion that $\mathcal {C}_{pub}^\perp +{\mathcal {C}_{pub}^\perp }^{[1]}$ contains a subcode of $\mathcal {C}$ of dimension at most $2(n-k-l')$. Hence the Assumption (7) cannot be true and therefore the adversary cannot recover (4) from (3) as Coggia–Couvreur attack on Loidreau’s cryptosystem. Therefore Coggia–Couvreur attack does not work on Modification II.

Furthermore, we show that the distinguisher based on Propositions 6 and 7 does not work on Modification II for properly chosen parameters. Here we follow the notation introduced in (5). Let $\mathcal {C}_0=\langle AP'^T\rangle$ and $\mathcal {C}_1=\langle [0|H_{rt}]P'^T\rangle$, then $\mathcal {C}_{pub}^\perp =\mathcal {C}_0+\mathcal {C}_1$. It is easy to see that

$$\begin{aligned} \dim (\mathcal {C}_0+\mathcal {C}_0^{[1]}+\cdots +\mathcal {C}_0^{[\lambda ]})=(\lambda+1)l \text{ and } \dim (\mathcal {C}_1+\mathcal {C}_1^{[1]}+\cdots +\mathcal {C}_1^{[\lambda ]})=\lambda (n-k-l)+\lambda, \end{aligned}$$

then with high probability

$$\begin{aligned} \dim (\mathcal {C}_{pub}^\perp +{\mathcal {C}_{pub}^\perp }^{[1]}+\cdots +{\mathcal {C}_{pub}^\perp }^{[\lambda ]})=(\lambda +1)l+\lambda (n-k-l)+\lambda=\lambda (n-k)+\lambda +l. \end{aligned}$$

Together with Proposition 7, we conclude that if the parameters are chosen such that $n\leqslant \min \{\lambda (n-k)+\lambda +l,(\lambda +1)(n-k)\}$, then one cannot distinguish the public code $\mathcal {C}_{pub}$ from random ones.

6.2 Generic attacks

In the context of code-based cryptography, an adversary without the private key has to deal with the problem of decoding general linear codes or equivalently the syndrome decoding problem, which has been proved to be NP-complete by Berlekamp et al. in [8]. However, the general decoding problem in the rank metric, or equivalently the rank syndrome decoding (RSD) problem, is not known to be NP-complete. In the paper [25], the authors proved that a randomized reduction exists from the RSD problem to the general decoding problem in the Hamming metric.

In what follows, we will first introduce the RSD problem in coding theory, then present two types of attacks on this problem, namely the combinatorial attack and the algebraic attack. After that, we will establish a connection between our modifications and the RSD problem.

Definition 7

(Rank syndrome decoding (RSD) problem) For positive integers m, n, k and t, let $H\in \mathcal {M}_{n-k,n}(\mathbb {F}_{q^m})$ with full rank and $\varvec{s}\in \mathbb {F}_{q^m}^{n-k}$. The RSD problem $\mathcal {R}(q,m,n,k,t)$ is to search for $\varvec{x}\in \mathbb {F}_{q^m}^n$ such that $\varvec{s}=\varvec{x}H^T$ and $w_R(\varvec{x})\leqslant t$.

The main idea of combinatorial attacks consists in solving a multivariate linear system obtained from the parity-check equation, whose variables are components of $e_i\,(1\leqslant i\leqslant n)$ with respect to a potential support of $\varvec{e}$. Up to now, the best known combinatorial attacks can be found in [3, 24, 45], as summarized in Table 1.

Table 1 Best known combinatorial attacks on the RSD problem

As for the algebraic attack, the main idea consists in converting an RSD instance into a quadratic system and then solving this system using algebraic approaches. Here in this paper, we mainly consider the attacks proposed in [6, 7, 24], whose complexity and applicable condition are summarized in Table 2, where $\omega =2.81$ is the linear algebra constant.

Table 2 Best known algebraic attacks on the RSD problem

Conversion into an RSD instance. For Modification I, let $H_{pub}\in \mathcal {M}_{n-k+l,n}$ be a parity-check matrix of the public code. Let $\varvec{c}=\varvec{m}G_{pub}+\varvec{e}$ be a valid ciphertext, then compute $\varvec{s}=\varvec{c}H_{pub}^T=\varvec{e}H_{pub}^T$. This implies that we obtain an RSD instance of parameters $(q,m,n,k-l,t)$. A similar analysis of Modification II leaves us an RSD instance of parameters (q, m, n, k, t). Apparently these two instances both have a unique solution because of the uniqueness of the decrypting process.

7 Parameters and public key sizes

Now we consider the practical security of our two modifications and give some suggested parameters. In Modification I, the public key is a systematic generator matrix of an $[n,k-l]$ rank metric code, resulting in a public-key size of $(k-l)(n-k+l)\cdot m\log _2(q)$ bits. In Modification II, the public key is a systematic generator matrix of an [n, k] rank metric code, resulting in a public-key size of $k(n-k)\cdot m\log _2(q)$ bits.

In Table 3, we suggest some parameters for security of at least 128 bits, 192 bits, and 256 bits. When considering the practical security, we consider the complexity assessment of the structural attacks presented in Sect. 6.1, as well as the complexity of generic attacks described in Sect. 6.2. In Table 4, we make a comparison on public-key sizes with some other code-based cryptosystems that have been selected as the fourth round candidates of the NIST PQC Standardization Process. These candidates are HQC [42], BIKE [2], and Classic McEliece [1]. From Table 4 we can see that our modifications behave pretty well in public-key representation compared to Classic McEliece without using codes endowed with the cyclic or quasi-cyclic structure.

Table 3 Parameters and public key size (in bytes)

Table 4 Comparison on public-key sizes (in bytes)

8 Conclusion

In this paper, we have presented two simple but effective approaches to repair Loidreau’s cryptosystem. According to our analysis, both of these two modifications can resist the existing structural attacks designed for cryptosystems based on Gabidulin codes, including Overbeck’s attack and Coggia–Couvreur attack. Additionally, our two modifications have an obvious advantage in public-key representation compared to some code-based cryptosystems that have been selected into the fourth round of the NIST PQC project.