# Two Public Key Cryptosystems Based on Expanded Gabidulin Codes

Wenshuo Guo and Fang-Wei Fu Wenshuo Guo is with the Chern Institute of
Mathematics and LPMC, Nankai University, Tianjin 300071, China. E-mail:
<EMAIL_ADDRESS>Fu is with the Chern Institute of
Mathematics and LPMC, Nankai University, Tianjin 300071, China. E-mail:
<EMAIL_ADDRESS>
###### Abstract

This paper presents two public key cryptosystems based on the so-called
expanded Gabidulin codes, which are constructed by expanding Gabidulin codes
over the base field. Exploiting the fast decoder of Gabidulin codes, we
propose an efficient algorithm to decode these new codes when the noise vector
satisfies a certain condition. Additionally, these new codes have an excellent
error-correcting capability because of the optimality of their parent
Gabidulin codes. With different masking techniques, we give two encryption
schemes by using expanded Gabidulin codes in the McEliece setting. Being
constructed over the base field, these two proposals can prevent the existing
structural attacks using the Frobenius map. Based on the distinguisher for
Gabidulin codes, we propose a distinguisher for expanded Gabidulin codes by
introducing the concept of the so-called twisted Frobenius power. It turns out
that the public code in our proposals seems indistinguishable from random
codes under this distinguisher. Furthermore, our proposals have an obvious
advantage in public key representation without using the cyclic or quasi-
cyclic structure compared to some other code-based cryptosystems. To achieve
the security of 256 bits, for instance, a public key size of 37583 bytes is
enough for our first proposal, while around 1044992 bytes are needed for
Classic McEliece selected as a candidate of the third round of the NIST PQC
project.

Keywords Post-quantum cryptography $\cdot$ Code-based cryptography $\cdot$
Rank metric codes $\cdot$ Expanded Gabidulin codes

##  1 Introduction

Over the past decades, cryptosystems based on coding theory have been drawing
more and more attention due to the rapid development of quantum computers. The
first code-based cryptosystem, known as McEliece cryptosystem [1] based on
Goppa codes, was proposed by McEliece in 1978. The principle for McEliece’s
proposal is to first encode the plaintext with a random generator matrix of
the distorted Goppa code and then add some random errors. Since then various
studies[2, 3, 4, 5, 6] have been made to investigate the security of McEliece
cryptosystem.

In addition to potential resistance against quantum computer attacks, McEliece
cryptosystem has pretty fast encryption and decryption procedures. However,
this system has never been used in practice due to the large public key size.
To overcome this problem, some variants were proposed one after another. For
instance, the authors in [7] proposed to use the automorphism groups of Goppa
codes to build decodable error patterns of larger weight, which greatly
enhances the system against decoding attacks. By doing this, smaller codes are
allowed in the design of encryption schemes to reduce the public key size.
Unfortunately, this variant was shown to be vulnerable against the chosen-
plaintext attacks proposed in [8]. In [9], the authors proposed the family of
quasi-dyadic Goppa codes, which admit a very compact representation of parity-
check or generator matrix, for efficiently designing syndrome-based
cryptosystems. However, the authors in [10] mounted an efficient key-recovery
attack against this variant for almost all the proposed parameters.

Besides endowing Goppa codes with some special structures, replacing Goppa
codes with other families of codes is another approach to shorten the public
keys. For instance, Niederreiter [11] introduced a knapsack-type cryptosystem
based on generalized Reed-Solomon (GRS) codes. In Niederreiter’s proposal, the
message sender first converts the plaintext into a vector of fixed weight and
then multiplies it with a parity-check matrix of the public code. The
advantage of GRS codes consists in their optimal error-correcting capability,
which enables us to reduce the public key size by exploiting codes with
smaller parameters. However, this variant was proved to be insecure by
Sidelnikov and Shestakov in [12] for the reason that GRS codes are highly
structured. But if we use Goppa codes in the Niederreiter setting, it was
proved to be equivalent to McEliece cryptosystem in terms of security [15]. To
strengthen resistance against structural attacks, the authors in [16]
performed a column-mixing transformation instead of a simple permutation to
the underlying GRS code. According to their analysis, this variant could
prevent some well-known attacks, such as Sidelnikov-Shestakov attack [12] and
Wieschebrink’s attack [17]. However, in[18] the authors presented a polynomial
key-recovery attack in some cases. Although one can adjust the parameters to
prevent such an attack, it would introduce some other problems, such as the
decryption complexity increasing dramatically and a higher request of error-
correcting capability for the underlying code. In [19], the authors introduced
the concept of expanded GRS codes and designed an encryption scheme by using
these codes in the Niederreiter setting. However, this scheme was already
partially broken by Couvreur and Lequesne in [14] for the case of $\lambda=2$
and $m=3$.

In [21] Gabidulin introduced a new family of rank metric codes, known as
Gabidulin codes, which can be seen as an analogue of GRS codes in the rank
metric. The particular appeal of rank metric codes is that the general
decoding problem is much more difficult than that of Hamming metric codes [22,
23]. This inspires us to obtain a much smaller public key size by building
cryptosystems in the rank metric. In [24] the authors proposed the GPT
cryptosystem by using Gabidulin codes in the McEliece setting, which requires
a public key size of only a few thousand bits for the security of $100$ bits.
Similar to the cryptosystems based on GRS codes, the GPT cryptosystem and some
of its variants [25, 26, 27, 28] have been subjected to many structural
attacks [29, 30, 31, 32]. Faure and Loidreau proposed another cryptosystem
[34] that is quite different from the GPT proposal. The security of this
scheme closely relates to the intractability of reconstructing linearized
polynomials. Until the work in [35], the Faure-Loidreau scheme had never been
severely attacked. In [36] Loidreau designed another rank metric based
cryptosystem in the McEliece setting, where a column-mixing transformation was
imposed to the underlying code with the inverse of an invertible matrix whose
entries are taken from an $\mathbb{F}_{q}$-subspace of $\mathbb{F}_{q^{m}}$ of
dimension $\lambda$. Loidreau claimed that their proposal could prevent all
the existing structural attacks. However, this claim was proved to be
invalidated by the authors in [38] for the case of $\lambda=2$ and the code
rate being greater than $1/2$. Not long after this, the author in [39]
extended this attack to the case of $\lambda=3$.

In [33], Berger et al. used the so-called Gabidulin matrix codes to design
cryptosystems, which can be seen as a rank metric counterpart of expanded GRS
codes. Our work in the present paper is inspired by the variants [19, 33] and
uses the so-called expanded Gabidulin codes as the underlying code.
Benefitting from the optimality of their parent Gabidulin codes, these new
codes have excellent capability of correcting Hamming errors. This enables us
to reduce the public key size by exploiting smaller codes. Because of our
proposals being constructed over the base field, all the existing structural
attacks based on the Frobenius map do not work any longer.

The rest of this paper is arranged as follows. In Section 2, notations and
some basic concepts about rank metric codes and Gabidulin codes will be given.
In Section 3, we shall introduce the so-called expanded Gabidulin codes and
propose an efficient algorithm to decode these new codes. Section 4 introduces
two hard problems in coding theory, as well as the best known generic attacks
on them. Section 5 is devoted to a formal description of our two proposals
constructed by using expanded Gabidulin codes in the McEliece setting. Section
6 gives the security analysis of our proposals, including structural attacks
and generic attacks. In Section 7, we give some suggested parameters for
different security levels and make a comparison on public key size with some
other code-based cryptosystems. Following this, we make a few concluding
remarks in Section 8.

##  2 Preliminaries

In this section we first introduce some notations used throughout this paper,
and recall some basic concepts about linear codes and rank metric codes. After
that, we will introduce the definition of Gabidulin codes and some related
results.

###  2.1 Notations and basic concepts

Let $q$ be a prime power. Denote by $\mathbb{F}_{q}$ the finite field with $q$
elements, and $\mathbb{F}_{q^{m}}$ an extension field of $\mathbb{F}_{q}$ of
degree $m$. For two positive integers $k$ and $n$, let
$\mathcal{M}_{k,n}(\mathbb{F}_{q})$ denote the space of all $k\times n$
matrices over $\mathbb{F}_{q}$, and $GL_{n}(\mathbb{F}_{q})$ the general
linear group of all invertible matrices in
$\mathcal{M}_{n,n}(\mathbb{F}_{q})$. For a matrix
$M\in\mathcal{M}_{k,n}(\mathbb{F}_{q})$, let $\langle
M\rangle_{\mathbb{F}_{q}}$ be the vector space spanned by the rows of $M$ over
$\mathbb{F}_{q}$.

An $[n,k]$ linear code $\mathcal{C}$ over $\mathbb{F}_{q}$ is a
$k$-dimensional subspace of $\mathbb{F}_{q}^{n}$. An element of $\mathcal{C}$
is called a codeword of $\mathcal{C}$. The dual code of $\mathcal{C}$, denoted
by $\mathcal{C}^{\perp}$, is the orthogonal space of $\mathcal{C}$ under the
usual inner product over $\mathbb{F}_{q}^{n}$. A matrix $G$ is called a
generator matrix of $\mathcal{C}$ if its rows form a basis of $\mathcal{C}$. A
generator matrix $H$ of $\mathcal{C}^{\perp}$ is called a parity-check matrix
of $\mathcal{C}$. For a codeword $\bm{c}\in\mathcal{C}$, the Hamming weight of
$\bm{c}$, denoted by $w_{H}(\bm{c})$, is the number of nonzero components of
$\bm{c}$. The minimum Hamming distance of $\mathcal{C}$, denoted by
$d_{H}(\mathcal{C})$, is defined as the minimum Hamming weight of nonzero
codewords in $\mathcal{C}$. The minimum Hamming distance of $\mathcal{C}$ has
$n-k+1$ as an upper bound, and we call $\mathcal{C}$ Maximum Distance
Separable (MDS) when $d_{H}(\mathcal{C})$ reaches to this bound.

###  2.2 Rank metric codes

Now we recall some basic concepts about rank metric codes.

######  Definition 1.

For a vector $\bm{x}\in\mathbb{F}_{q^{m}}^{n}$, the rank support of $\bm{x}$,
denoted by $\textnormal{Supp}(\bm{x})$, is defined as the linear space spanned
by the components of $\bm{x}$ over $\mathbb{F}_{q}$.

######  Definition 2.

For a vector $\bm{x}\in\mathbb{F}_{q^{m}}^{n}$, the rank weight of $\bm{x}$,
denoted by $w_{R}(\bm{x})$, is defined as the dimension of
$\textnormal{Supp}(\bm{x})$ over $\mathbb{F}_{q}$.

######  Definition 3.

For two vectors $\bm{x},\bm{y}\in\mathbb{F}_{q^{m}}^{n}$, the rank distance
between $\bm{x}$ and $\bm{y}$, denoted by $d_{R}(\bm{x},\bm{y})$, is defined
to be the rank weight of $\bm{x}-\bm{y}$.

######  Definition 4.

For a linear code $\mathcal{C}\subseteq\mathbb{F}_{q^{m}}^{n}$, the minimum
rank distance of $\mathcal{C}$, denoted by $d_{R}(\mathcal{C})$, is defined to
be the minimum rank weight of nonzero codewords in $\mathcal{C}$.

A linear code endowed with the rank metric is called a rank metric code.
Similar to Hamming metric codes, the minimum rank distance of a rank metric
code is bounded from above by the Singleton-type bound as described in the
following proposition.

######  Proposition 1 (Singleton-type bound).

[37] For positive integers $k\leqslant n\leqslant m$, let $\mathcal{C}$ be an
$[n,k]$ rank metric code over $\mathbb{F}_{q^{m}}$, then the minimum rank
distance of $\mathcal{C}$ with respect to $\mathbb{F}_{q}$ satisfies the
following inequality

$d_{R}(\mathcal{C})\leqslant n-k+1.$

######  Remark 1.

A rank metric code attaining the Singleton-type bound is called a Maximum Rank
Distance (MRD) code. Let $\mathcal{C}\subseteq\mathbb{F}_{q^{m}}^{n}$ be an
$[n,k]$ MRD code and $\bm{c}\in\mathcal{C}$ be a nonzero codeword with
$w_{H}(\bm{c})=d_{H}(\mathcal{C})$. It is clear that $n-k+1\leqslant
w_{R}(\bm{c})\leqslant w_{H}(\bm{c})\leqslant n-k+1$. Then
$w_{H}(\bm{c})=n-k+1$, which implies that an MRD code is MDS in the Hamming
metric.

###  2.3 Gabidulin codes

For an integer $i$, we denote by $[i]=q^{i}$ the $i$-th Frobenius power. Under
this notation, $\alpha^{q^{i}}$ can be simply written as $\alpha^{[i]}$ for
any $\alpha\in\mathbb{F}_{q^{m}}$. For a vector
$\bm{v}\in\mathbb{F}_{q^{m}}^{n}$, we denote by $\bm{v}^{[i]}$ the $i$-th
component-wise Frobenius power of $\bm{v}$. For a linear code
$\mathcal{C}\subseteq\mathbb{F}_{q^{m}}^{n}$, the $i$-th Frobenius power of
$\mathcal{C}$ is defined as
$\mathcal{C}^{[i]}=\\{\bm{c}^{[i]}:\bm{c}\in\mathcal{C}\\}$.

######  Definition 5 (Gabidulin codes).

For positive integers $k\leqslant n\leqslant m$, let
$\bm{g}=(g_{1},\ldots,g_{n})\in\mathbb{F}_{q^{m}}^{n}$ with $w_{R}(\bm{g})=n$.
The $[n,k]$ Gabidulin code $\textnormal{Gab}_{n,k}(\bm{g})$ generated by
$\bm{g}$ is defined to be a linear code having a generator matrix of the form

$G=\begin{pmatrix}g_{1}&g_{2}&\cdots&g_{n}\\\
g_{1}^{[1]}&g_{2}^{[1]}&\cdots&g_{n}^{[1]}\\\ \vdots&\vdots&\ddots&\vdots\\\
g_{1}^{[k-1]}&g_{2}^{[k-1]}&\cdots&g_{n}^{[k-1]}\end{pmatrix}.$

Similar to GRS codes in the Hamming metric, Gabidulin codes also admit an
excellent error-correcting capability and simple algebraic structure. The
following two theorems describe some properties of Gabidulin codes.

######  Theorem 6.

[40] A Gabidulin code is an MRD code. In other words, the minimum rank weight
of $\textnormal{Gab}_{n,k}(\bm{g})$ attains the Singleton-type bound.

This implies that the Gabidulin code $\textnormal{Gab}_{n,k}(\bm{g})$ can
theoretically correct up to $\lfloor\frac{n-k}{2}\rfloor$ rank errors, which
is an important reason for Gabidulin codes being widely used in the design of
cryptosystems.

######  Theorem 7.

[35] The dual of a Gabidulin code is also a Gabidulin code. Specifically, we
have
$\textnormal{Gab}_{n,k}(\bm{g})^{\perp}=\textnormal{Gab}_{n,n-k}(\bm{h}^{q^{-(n-k-1)}})$
for some $\bm{h}\in\textnormal{Gab}_{n,n-1}(\bm{g})^{\perp}$ with
$w_{R}(\bm{h})=n$, where $\bm{h}^{j}$ denotes the $j$-th component-wise power
of $\bm{h}$.

##  3 Expanded Gabidulin codes

In this section, we first introduce the definition of expanded Gabidulin
codes, then investigate some of their algebraic properties. After that, we
propose an efficient algorithm to decode these codes.

###  3.1 Expanded Gabidulin codes

Note that $\mathbb{F}_{q^{m}}$ can be viewed as an $\mathbb{F}_{q}$-linear
space of dimension $m$. Let $\mathcal{B}=(\alpha_{1},\ldots,\alpha_{m})$ be a
basis of $\mathbb{F}_{q^{m}}$ over $\mathbb{F}_{q}$. For any
$\alpha\in\mathbb{F}_{q^{m}}$, there exists
$(a_{1},\ldots,a_{m})\in\mathbb{F}_{q}^{m}$ such that
$\alpha=\sum_{i=1}^{m}a_{i}\alpha_{i}$. Based on this observation, we define
an $\mathbb{F}_{q}$-linear isomorphism from $\mathbb{F}_{q^{m}}$ to
$\mathbb{F}_{q}^{m}$ with respect to $\mathcal{B}$ as follows

$\displaystyle\phi_{\mathcal{B}}:\mathbb{F}_{q^{m}}$
$\displaystyle\longmapsto\mathbb{F}_{q}^{m},$
$\displaystyle\sum_{i=1}^{m}a_{i}\alpha_{i}$
$\displaystyle\longmapsto(a_{1},\ldots,a_{m}).$

For a vector $\bm{v}=(v_{1},\ldots,v_{n})\in\mathbb{F}_{q^{m}}^{n}$, we define
$\phi_{\mathcal{B}}(\bm{v})=(\phi_{\mathcal{B}}(v_{1}),\ldots,\phi_{\mathcal{B}}(v_{n}))\in\mathbb{F}_{q}^{mn}$.
For a linear code $\mathcal{C}\subseteq\mathbb{F}_{q^{m}}^{n}$, we define
$\phi_{\mathcal{B}}(\mathcal{C})=\\{\phi_{\mathcal{B}}(\bm{c}):\bm{c}\in\mathcal{C}\\}$.

For convenience, we need to introduce a matrix representation of this
transformation in [33, 14]. For any $\alpha\in\mathbb{F}_{q^{m}}^{*}$, there
exists a unique $M_{\alpha}\in GL_{m}(\mathbb{F}_{q})$ such that
$\alpha\mathcal{B}^{T}=M_{\alpha}\mathcal{B}^{T}$. Apparently $M_{\alpha}$
depends on the choice of $\mathcal{B}$. For a fixed $\mathcal{B}$, we define
an $\mathbb{F}_{q}$-linear homomorphism from $\mathbb{F}_{q^{m}}^{*}$ to
$GL_{m}(\mathbb{F}_{q})$ as $\Phi_{\mathcal{B}}(\alpha)=M_{\alpha}$. And
specially, we define $\Phi_{\mathcal{B}}(0)=0_{m\times m}$. It is easy to
verify that

$\Phi_{\mathcal{B}}(\alpha)=\begin{pmatrix}\phi_{\mathcal{B}}(\alpha\alpha_{1})\\\
\vdots\\\ \phi_{\mathcal{B}}(\alpha\alpha_{m})\end{pmatrix}.$

For a vector $\bm{v}\in\mathbb{F}_{q^{m}}^{n}$, we define
$\Phi_{\mathcal{B}}(\bm{v})=\begin{pmatrix}\Phi_{\mathcal{B}}(v_{1}),\ldots,\Phi_{\mathcal{B}}(v_{n})\end{pmatrix}\in\mathcal{M}_{m,nm}(\mathbb{F}_{q})$.
For a matrix $M=(M_{ij})\in\mathcal{M}_{k,n}(\mathbb{F}_{q})$, we define
$\Phi_{\mathcal{B}}(M)=(\Phi_{\mathcal{B}}(M_{ij}))\in\mathcal{M}_{km,nm}(\mathbb{F}_{q})$.

Now we give an effective method to perform this operation, which is based on
the following theorem.

######  Theorem 8.

[20] Let $\mathcal{B}=(\alpha_{1},\ldots,\alpha_{m})$ be a basis of
$\mathbb{F}_{q^{m}}$ over $\mathbb{F}_{q}$, then there exists another basis
$\mathcal{B}^{*}=(\alpha_{1}^{*},\ldots,\alpha_{m}^{*})$ such that for
$1\leqslant i,j\leqslant m$ we have

$\textnormal{Tr}(\alpha_{i}\alpha_{j}^{*})=\begin{cases}1\quad\textnormal{for}\
i=j,\\\ 0\quad\textnormal{for}\ i\neq j,\end{cases}$ (1)

where $\textnormal{Tr}(\cdot)$ denotes the trace function
$\textnormal{Tr}(x)=\sum_{i=0}^{m-1}x^{q^{i}}$.

######  Remark 2.

A basis $\mathcal{B}^{*}$ satisfying the condition (1) is called a dual basis
of $\mathcal{B}$. Furthermore, $\mathcal{B}^{*}$ is uniquely determined by
$\mathcal{B}$. For any $\alpha\in\mathbb{F}_{q^{m}}$, let
$(a_{1},\ldots,a_{m})\in\mathbb{F}_{q}^{m}$ such that
$\alpha=\sum_{i=1}^{m}a_{i}\alpha_{i}$. Then we can obtain $a_{j}$ for
$1\leqslant j\leqslant m$ by computing

$\displaystyle\textnormal{Tr}(\alpha\alpha_{j}^{*})$
$\displaystyle=\textnormal{Tr}(\sum_{i=1}^{m}a_{i}\alpha_{i}\alpha_{j}^{*})=\sum_{i=1}^{m}a_{i}\textnormal{Tr}(\alpha_{i}\alpha_{j}^{*})=a_{j}.$

Finally we have
$\phi_{\mathcal{B}}(\alpha)=(\textnormal{Tr}(\alpha\alpha_{1}^{*}),\ldots,\textnormal{Tr}(\alpha\alpha_{m}^{*}))$.

Now we formally introduce the concept of expanded Gabidulin codes.

######  Definition 9 (Expanded Gabidulin codes).

Let $\mathcal{G}$ be an $[n,k]$ Gabidulin code over $\mathbb{F}_{q^{m}}$. For
a basis $\mathcal{B}$ of $\mathbb{F}_{q^{m}}$ over $\mathbb{F}_{q}$, let
$\phi_{\mathcal{B}}$ be the associated $\mathbb{F}_{q}$-linear isomorphism
from $\mathbb{F}_{q^{m}}$ to $\mathbb{F}_{q}^{m}$. The expanded code of
$\mathcal{G}$ induced by $\phi_{\mathcal{B}}$ is defined as
$\widehat{\mathcal{G}}=\\{\phi_{\mathcal{B}}(\bm{c}):\bm{c}\in\mathcal{G}\\}$.
Meanwhile, we call $\mathcal{G}$ the parent Gabidulin code of
$\widehat{\mathcal{G}}$.

It is easy to verify that $\widehat{\mathcal{G}}$ forms an $[nm,km]$ linear
code over $\mathbb{F}_{q}$. The following proposition gives a method of
constructing a generator (parity-check) matrix of an expanded Gabidulin code
when a generator (parity-check) matrix of its parent Gabidulin code is known.

######  Proposition 2.

[13] Let $\mathcal{G}\subseteq\mathbb{F}_{q^{m}}^{n}$ be an $[n,k]$ Gabidulin
code. For a basis $\mathcal{B}=(\alpha_{1},\ldots,\alpha_{m})$ of
$\mathbb{F}_{q^{m}}$ over $\mathbb{F}_{q}$, let $\widehat{\mathcal{G}}$ be the
expanded code of $\mathcal{G}$ induced by $\phi_{\mathcal{B}}$. Then we have
the following conclusions.

  * (1)

Let $G=\begin{bmatrix}\bm{g}_{1}^{T},\ldots,\bm{g}_{k}^{T}\end{bmatrix}^{T}$
be a generator matrix of $\mathcal{G}$, then $\widehat{\mathcal{G}}$ has an
$mk\times mn$ generator matrix of the form

$\widehat{G}=\Phi_{\mathcal{B}}(G)=\begin{bmatrix}\phi_{\mathcal{B}}(\alpha_{1}\bm{g}_{1})^{T},\ldots,\phi_{\mathcal{B}}(\alpha_{m}\bm{g}_{1})^{T},\ldots,\phi_{\mathcal{B}}(\alpha_{1}\bm{g}_{k})^{T},\ldots,\phi_{\mathcal{B}}(\alpha_{m}\bm{g}_{k})^{T}\end{bmatrix}^{T}.$

We call such $\Phi_{\mathcal{B}}(G)$ a normal generator matrix of
$\widehat{\mathcal{G}}$.

  * (2)

Let $H=\begin{bmatrix}\bm{h}_{1}^{T},\ldots,\bm{h}_{n}^{T}\end{bmatrix}$ be a
parity-check matrix of $\mathcal{G}$, then $\widehat{\mathcal{G}}$ has an
$m(n-k)\times nm$ parity-check matrix of the form

$\displaystyle\widehat{H}=\Phi_{\mathcal{B}}(H^{T})^{T}=\begin{bmatrix}\phi_{\mathcal{B}}(\alpha_{1}\bm{h}_{1})^{T},\ldots,\phi_{\mathcal{B}}(\alpha_{m}\bm{h}_{1})^{T},\ldots,\phi_{\mathcal{B}}(\alpha_{1}\bm{h}_{n})^{T},\ldots,\phi_{\mathcal{B}}(\alpha_{m}\bm{h}_{n})^{T}\end{bmatrix}.$
(2)

Note that Gabidulin codes are optimal in both the Hamming metric and rank
metric. However, expanded Gabidulin codes are far from optimal in the Hamming
metric. Specifically, we have the following proposition.

######  Proposition 3.

Let $\mathcal{G}$ be an $[n,k]$ Gabidulin code over $\mathbb{F}_{q^{m}}$. For
a basis $\mathcal{B}$ of $\mathbb{F}_{q^{m}}$ over $\mathbb{F}_{q}$, denote by
$\widehat{\mathcal{G}}$ the expanded code of $\mathcal{G}$ induced by
$\phi_{\mathcal{B}}$. Then the minimum Hamming distance of
$\widehat{\mathcal{G}}$ satisfies the following inequality

$n-k+1\leqslant d_{H}(\widehat{\mathcal{G}})\leqslant m(n-k)+1.$

In particular, with a proper choice of $\mathcal{B}$, the minimum Hamming
distance of $\widehat{\mathcal{G}}$ can reach to $n-k+1$.

###### Proof.

For any $\widehat{\bm{u}}\in\widehat{\mathcal{G}}$, there exists
$\bm{u}=(u_{1},\ldots,u_{n})\in\mathcal{G}$ such that
$\widehat{\bm{u}}=\phi_{\mathcal{B}}(\bm{u})$. Since $\mathcal{G}$ is MDS in
the Hamming metric, then $w_{H}(\bm{u})\geqslant n-k+1$ for a nonzero
$\bm{u}$. Let $I=\\{1\leqslant i\leqslant n:u_{i}\neq 0\\}$, then
$|I|\geqslant n-k+1$. Apparently $w_{H}(\widehat{\bm{u}})=\sum_{i\in
I}w_{H}(\phi_{\mathcal{B}}(u_{i}))\geqslant n-k+1$ because of
$w_{H}(\phi_{\mathcal{B}}(\alpha))\geqslant 1$ for any
$\alpha\in\mathbb{F}_{q^{m}}^{*}$, which implies that
$d_{H}(\widehat{\mathcal{G}})\geqslant n-k+1$. On the other hand, by the
Singleton bound for Hamming metric codes, it is clear that
$d_{H}(\widehat{\mathcal{G}})\leqslant m(n-k)+1$.

Let $\bm{v}=(v_{1},\ldots,v_{n})\in\mathcal{G}$ with $w_{H}(\bm{v})=n-k+1$,
and let $S=\\{v_{i}\neq 0:1\leqslant i\leqslant n\\}$. If
$S\subseteq\mathcal{B}$, then
$w_{H}(\phi_{\mathcal{B}}({\bm{v}}))=\sum_{v_{i}\neq
0}w_{H}(\phi_{\mathcal{B}}(v_{i}))=n-k+1$ because of
$w_{H}(\phi_{\mathcal{B}}(\alpha))=1$ for any $\alpha\in\mathcal{B}$. This
implies that $d_{H}(\widehat{\mathcal{G}})=n-k+1$. ∎

###  3.2 Decoding expanded Gabidulin codes

As for Gabidulin codes, several efficient decoding algorithms [21, 41, 42]
already exist. Now we investigate the decoding problem of expanded Gabidulin
codes. Our analysis shows that when the noise vector satisfies a certain
condition, decoding an expanded Gabidulin code can be converted into decoding
the parent Gabidulin code.

Let $\mathcal{G}\subseteq\mathbb{F}_{q^{m}}^{n}$ be an $[n,k]$ Gabidulin code
having $H$ as a parity-check matrix. Let $\mathcal{B}$ be a basis of
$\mathbb{F}_{q^{m}}$ over $\mathbb{F}_{q}$, we denote by
$\widehat{\mathcal{G}}$ an expanded code of $\mathcal{G}$ induced by
$\phi_{\mathcal{B}}$. Let $\bm{y}=\bm{c}+\bm{e}$ be the received word, where
$\bm{c}\in\widehat{\mathcal{G}}$ and
$\bm{e}=(\bm{e}_{1},\ldots,\bm{e}_{n})\in\mathbb{F}_{q}^{mn}$ is the noise
vector with $\bm{e}_{j}=(e_{1j},\ldots,e_{mj})\in\mathbb{F}_{q}^{m}$. Let
$E\in\mathcal{M}_{n,m}(\mathbb{F}_{q})$ be a matrix whose $j$-th row is
$\bm{e}_{j}$, called the error matrix corresponding to $\bm{e}$. If the
following inequality holds

$\textrm{Rank}(E)\leqslant\lfloor\frac{n-k}{2}\rfloor,$

then we say $\bm{e}$ satisfies the decodable condition. In this situation, we
can obtain a fast decoder $\mathscr{D}_{\widehat{\mathcal{G}}}$ for
$\widehat{\mathcal{G}}$ to decode $\bm{y}$ by exploiting the syndrome decoder
of $\mathcal{G}$.

Denote by $\widehat{H}$ a parity-check matrix of $\widehat{\mathcal{G}}$. It
is easy to see that

$\displaystyle\bm{y}\widehat{H}^{T}$
$\displaystyle=\bm{e}\widehat{H}^{T}=\sum_{j=1}^{n}\sum_{i=1}^{m}e_{ij}\phi_{\mathcal{B}}(\alpha_{i}\bm{h}_{j})=\phi_{\mathcal{B}}(\sum_{j=1}^{n}\sum_{i=1}^{m}e_{ij}\alpha_{i}\bm{h}_{j})=\phi_{\mathcal{B}}(\sum_{j=1}^{n}e_{j}^{*}\bm{h}_{j})=\phi_{\mathcal{B}}(\bm{e}^{*}H^{T}),$

where $\bm{e}^{*}=(e_{1}^{*},\ldots,e_{n}^{*})\in\mathbb{F}_{q^{m}}^{n}$ with
$e_{j}^{*}=\sum_{i=1}^{m}e_{ij}\alpha_{i}$. It is clear that
$\bm{e}^{*}=\mathcal{B}E^{T}$, then
$w_{R}(\bm{e}^{*})=\textrm{Rank}(E)\leqslant\lfloor\frac{n-k}{2}\rfloor$.
Applying the decoder of $\mathcal{G}$ to
$\phi_{\mathcal{B}}^{-1}(\bm{y}\widehat{H}^{T})=\bm{e}^{*}H^{T}$ will lead to
$\bm{e}^{*}$, then we can recover $\bm{e}$ by computing
$\phi_{\mathcal{B}}(\bm{e}^{*})$.

Apparently four steps are needed to decode expanded Gabidulin codes. Firstly,
we shall compute the syndrome of the received word $\bm{y}$, which requires an
operation of multiplying $\bm{y}$ and $\widehat{H}^{T}$ together with a
complexity of $\mathcal{O}(m^{2}n(n-k))$ in $\mathbb{F}_{q}$. Secondly, we
shall perform the inverse transformation of $\phi_{\mathcal{B}}$ to the
syndrome obtained in the first step, requiring a complexity of
$\mathcal{O}(mn)$ in $\mathbb{F}_{q^{m}}$. The third step shall call the fast
decoder of the parent Gabidulin code to obtain an error vector $\bm{e}^{*}$
with $w_{R}(\bm{e}^{*})\leqslant\lfloor\frac{n-k}{2}\rfloor$, which requires a
complexity of $\mathcal{O}(\frac{5}{2}n^{2}-\frac{3}{2}k^{2})$ in
$\mathbb{F}_{q^{m}}$ [41]. In the last step, we shall compute
$\phi_{\mathcal{B}}(\bm{e}^{*})$ through the method described in Remark 2 with
a complexity of $\mathcal{O}(((m-1)(q-1)+1)mn)$ in $\mathbb{F}_{q^{m}}$.
Finally the total complexity of decoding expanded Gabidulin codes is
$\mathcal{O}(m^{2}n(q-1)+mn(3-q)+\frac{5}{2}n^{2}-\frac{3}{2}k^{2})$ in
$\mathbb{F}_{q^{m}}$ plus $\mathcal{O}(m^{2}n(n-k))$ in $\mathbb{F}_{q}$.

##  4 Two hard problems

The security of our two proposals in this paper mainly involves two hard
problems in coding theory, namely the rank syndrom decoding (RSD) problem and
MinRank problem. In this section, we will give a description of these two
problems and some well known attacks on them.

###  4.1 RSD problem

######  Definition 10 (RSD problem).

Let $H\in\mathcal{M}_{n-k,n}(\mathbb{F}_{q^{m}})$ be a matrix of full rank,
$\bm{s}\in\mathbb{F}_{q^{m}}^{n-k}$ and $t$ be a positive integer. An RSD
instance $\mathcal{R}(q,m,n,k,t)$ is to solve $\bm{s}=\bm{e}H^{T}$ for
$\bm{e}\in\mathbb{F}_{q^{m}}^{n}$ such that $w_{R}(\bm{e})\leqslant t$.

The RSD problem plays a crucial role in rank metric based cryptography.
Although this problem is not known to be NP-complete, it is believed to be
hard by the community. Up to now, the best known combinatorial attacks on this
problem can be found in [22, 43, 44, 45]. In what follows, we will recall the
principle of the combinatorial attack proposed in [44]. Although there are
some improvements [45] for this attack, they are not applicable to our
proposals.

To make the description concise, here we introduce a notation used in the
sequel. For positive integers $w<v<u$, by
$\textnormal{P}_{\mathbb{F}_{q}}(u,v,w)$ we denote the probability that a
random space of dimension $v$ in a space of dimension $u$ contains a given
space of dimension $w$. Using the Gaussian binomial, we have

$\textnormal{P}_{\mathbb{F}_{q}}(u,v,w)=\begin{bmatrix}u-w\\\
v-w\end{bmatrix}_{q}\bigg{/}\begin{bmatrix}u\\\
v\end{bmatrix}_{q}=\prod_{i=0}^{v-w-1}\frac{q^{u-w}-q^{i}}{q^{v-w}-q^{i}}\bigg{/}\prod_{i=0}^{v-1}\frac{q^{u}-q^{i}}{q^{v}-q^{i}}\sim\frac{1}{q^{w(u-v)}}.$

For an RSD instance $\mathcal{R}(q,m,n,k,t)$, we consider the following two
cases to solve the problem.

  * Case $\bm{1}$: $n>m$. Let $\mathcal{B}$ be a basis of $\mathbb{F}_{q^{m}}$ over $\mathbb{F}_{q}$, then there exists $E\in\mathcal{M}_{m,n}(\mathbb{F}_{q})$ with $\textrm{Rank}(E)\leqslant t$ such that $\bm{e}=\mathcal{B}E$. Let $\mathcal{E}=\langle E^{T}\rangle_{\mathbb{F}_{q}}$ and $\mathcal{V}\subseteq\mathbb{F}_{q}^{m}$ be an $\mathbb{F}_{q}$-linear space of dimension $t^{\prime}\geqslant t$. If $\mathcal{E}\subseteq\mathcal{V}$, then one can express $\bm{e}$ in a basis of $\mathcal{V}$ over $\mathbb{F}_{q}$. By computing $\bm{s}=\bm{e}H^{T}$ and expanding this system over the base field, one obtains a linear system of $m(n-k)$ equations and $nt^{\prime}$ variables over $\mathbb{F}_{q}$. To have only one solution with overwhelming probability, one needs $nt^{\prime}\leqslant m(n-k)$, then $t^{\prime}\leqslant m-\left\lceil\frac{km}{n}\right\rceil$. By taking $t^{\prime}=m-\left\lceil\frac{km}{n}\right\rceil$, one gets a complexity of $\mathcal{O}(m^{3}(n-k)^{3}/p)$ in $\mathbb{F}_{q}$, where $p=\textnormal{P}_{\mathbb{F}_{q}}(m,t^{\prime},t)$.

  * Case $\bm{2}$: $n\leqslant m$. Let $\mathcal{B}$ be a basis of $\mathbb{F}_{q^{m}}$ over $\mathbb{F}_{q}$, then there exists $E\in\mathcal{M}_{m,n}(\mathbb{F}_{q})$ with $\textrm{Rank}(E)\leqslant t$ such that $\bm{e}=\mathcal{B}E$. Let $\mathcal{E}=\langle E\rangle_{\mathbb{F}_{q}}$ and $\mathcal{V}\subseteq\mathbb{F}_{q}^{n}$ be an $\mathbb{F}_{q}$-linear space of dimension $t^{\prime}\geqslant t$. If $\mathcal{E}\subseteq\mathcal{V}$, then one can express $E$ in a basis of $\mathcal{V}$ over $\mathbb{F}_{q}$. By computing $\bm{s}=\bm{e}H^{T}$ and expanding this system over the base field, one obtains a linear system of $m(n-k)$ equations and $mt^{\prime}$ variables over $\mathbb{F}_{q}$. To have only one solution with overwhelming probability, one needs $mt^{\prime}\leqslant m(n-k)$, then $t^{\prime}\leqslant n-k$. By taking $t^{\prime}=n-k$, one gets a complexity of $\mathcal{O}\left(m^{3}(n-k)^{3}/p\right)$ in $\mathbb{F}_{q}$, where $p=\textnormal{P}_{\mathbb{F}_{q}}(n,t^{\prime},t)$.

###  4.2 MinRank problem

######  Definition 11 (MinRank problem).

For a finite field $\mathbb{F}_{q}$ and positive integers $m,n,k,t$, let
$M_{1},\ldots,$
$M_{k}\in\mathcal{M}_{m,n}(\mathbb{F}_{q})$. A MinRank instance of parameters
$(q,m,n,k,t)$ is to search for $x_{1},\ldots,x_{k}\in\mathbb{F}_{q}$ such that
$\textnormal{Rank}(\sum_{i=1}^{k}x_{i}M_{i})\leqslant t$.

The MinRank problem was first introduced and proven NP-complete by Buss et al.
in [46]. This problem is of great importance in both multivariate cryptography
[48] and rank metric based cryptography [44]. In Table 1, we give the best
algebraic attacks in [47] on the MinRank problem, where $\omega=2.8$ is the
linear algebra constant.

Condition |  Complexity
---|---
$A=k\binom{n}{t},B=m\binom{n}{t+1}$, $A-1\leqslant B$ | $\mathcal{O}(BA^{\omega-1})$
$A_{b}=\binom{n}{t}\binom{k+b-1}{b},B_{b}=\sum_{i=1}^{b}(-1)^{i+1}\binom{n}{t+i}\binom{m+i-1}{i}\binom{k+b-i-1}{b-i}$, $b=\min\\{b:A_{b}-1\leqslant B_{b}\\}$ and $q>b,b<t+2$ | $\mathcal{O}\left(k(t+1)A_{b}^{2}\right)$
$A_{b}=\sum_{j=1}^{b}\binom{n}{t}\binom{k}{j},B_{b}=\sum_{j=1}^{b}\sum_{i=1}^{j}(-1)^{i+1}\binom{n}{t+i}\binom{m+i-1}{i}\binom{k}{j-i}$, $b=\min\\{b:A_{b}-1\leqslant B_{b}\\}$ and $q=2,b<t+2$ | $\mathcal{O}\left(k(t+1)A_{b}^{2}\right)$
Table 1: Best algebraic attacks on the MinRank problem.

##  5 Description of our proposals

Now we give a formal description of our two proposals.

###  5.1 Proposal i@

For a given security level, choose a finite field $\mathbb{F}_{q}$ and
positive integers $k<n\leqslant m$ and $\lambda$ such that
$\frac{m(n-k)}{n}<\lambda<m$. Let $K=\lambda n-m(n-k)$ and $N=\lambda n$. For
$0\leqslant j\leqslant n-1$, we define $I_{j}=\\{mj+1,\ldots,mj+\lambda\\}$
and let $S=\cup_{j=0}^{n-1}I_{j}$. Now we give a formal description of our
first proposal through the following three procedures.

  * •

Key generation
Let $\mathcal{G}\subseteq\mathbb{F}_{q^{m}}^{n}$ be an $[n,k]$ Gabidulin code.
Randomly choose a basis $\mathcal{B}=(\alpha_{1},\ldots,\alpha_{m})$ of
$\mathbb{F}_{q^{m}}$ over $\mathbb{F}_{q}$ and let
$\widehat{\mathcal{G}}=\phi_{\mathcal{B}}(\mathcal{G})$. Denote by
$\widehat{H}$ a parity-check matrix of $\widehat{\mathcal{G}}$ of the form
$(\ref{paritycheck})$, and $\widehat{H}_{S}$ a submatrix of $\widehat{H}$ from
the columns indexed by $S$. Let
$\widehat{\mathcal{G}}_{S}=\langle\widehat{H}_{S}\rangle_{\mathbb{F}_{q}}^{\perp}$
and $\widehat{G}_{S}$ be a generator matrix of $\widehat{\mathcal{G}}_{S}$.
Randomly choose $A\in GL_{\lambda}(\mathbb{F}_{q})$ and set $T=I_{n}\otimes
A$, where $I_{n}$ is the identity matrix of order $n$. Randomly choose $M\in
GL_{K}(\mathbb{F}_{q})$ such that $G_{pub}=M\widehat{G}_{S}T^{-1}$ is of
systematic form. If such an $M$ does not exist, then repeat the process above.
The public key is $(G_{pub},t)$ where $t=\lfloor\frac{n-k}{2}\rfloor$, and the
secret key is $(\widehat{H}_{S},A,\mathscr{D}_{\widehat{\mathcal{G}}})$ where
$\mathscr{D}_{\widehat{\mathcal{G}}}$ is the fast decoder of
$\widehat{\mathcal{G}}$.

  * •

Encryption
For a plaintext $\bm{x}\in\mathbb{F}_{q}^{K}$, randomly choose
$E\in\mathcal{M}_{n,\lambda}(\mathbb{F}_{q})$ with $\textrm{Rank}(E)=t$. Let
$\bm{e}=(\bm{e}_{1},\ldots,\bm{e}_{n})\in\mathbb{F}_{q}^{N}$, where
$\bm{e}_{i}$ is the $i$-th row vector of $E$. The ciphertext corresponding to
$\bm{x}$ is computed as $\bm{y}=\bm{x}G_{pub}+\bm{e}$.

  * •

Decryption
For a ciphertext $\bm{y}\in\mathbb{F}_{q}^{N}$, let $\bm{e}^{\prime}=\bm{e}T$
and compute

$\displaystyle\bm{s}=\bm{y}T\widehat{H}_{S}^{T}=\bm{x}M\widehat{G}_{S}T^{-1}T\widehat{H}_{S}^{T}+\bm{e}T\widehat{H}_{S}^{T}=\bm{e}^{\prime}\widehat{H}_{S}^{T}.$

Applying $\mathscr{D}_{\widehat{\mathcal{G}}}$ to $\bm{s}$ will lead to a
vector $\bm{e}^{\prime\prime}\in\mathbb{F}_{q}^{mn}$. The restriction of
$\bm{e}^{\prime\prime}$ to $S$ will be $\bm{e}^{\prime}$, then we can recover
$\bm{e}$ by computing $\bm{e}^{\prime}T^{-1}$. The plaintext will be the
restriction of $\bm{y}-\bm{e}$ to the first $K$ coordinates.

Correctness of Decryption. Let
$\bm{e}^{\prime}=(\bm{e}^{\prime}_{1},\ldots,\bm{e}^{\prime}_{n})$, where
$\bm{e}^{\prime}_{i}=\bm{e}_{i}A$. Define
$E^{\prime}\in\mathcal{M}_{n,\lambda}(\mathbb{F}_{q})$ to be a matrix whose
$i$-th row vector is $\bm{e}^{\prime}_{i}$. Let
$\bm{e}^{\prime\prime}=(\bm{e}^{\prime\prime}_{1},\ldots,\bm{e}^{\prime\prime}_{n})$,
where $\bm{e}^{\prime\prime}_{i}=(\bm{e}^{\prime}_{i},\bm{0})$ and $\bm{0}$
denotes the zero vector of length $m-\lambda$. Define
$E^{\prime\prime}\in\mathcal{M}_{n,m}(\mathbb{F}_{q})$ to be a matrix whose
$i$-th row vector is $\bm{e}^{\prime\prime}_{i}$. It is easy to see that

$\displaystyle
E^{\prime\prime}=[E^{\prime}|0_{n\times(m-\lambda)}]=[EA|0_{n\times(m-\lambda)}].$

Then

$\displaystyle\textrm{Rank}(E^{\prime\prime})=\textrm{Rank}(E^{\prime})=\textrm{Rank}(E)=t,$

which implies that $\bm{e}^{\prime\prime}$ satisfies the decodable condition
described in Section 3.2. Applying the fast decoder of $\widehat{\mathcal{G}}$
to
$\bm{s}=\bm{e}^{\prime}\widehat{H}_{S}^{T}=\bm{e}^{\prime\prime}\widehat{H}^{T}$
will lead to $\bm{e}^{\prime\prime}$, then the restriction of
$\bm{e}^{\prime\prime}$ to $S$ will be $\bm{e}^{\prime}$.

###  5.2 Proposal ii@

For a given security level, choose a finite field $\mathbb{F}_{q}$ and
positive integers $\lambda\ll k<n\leqslant m$. Let $K=km$ and $N=nm$. Now we
give a formal description of our second proposal through the following three
procedures.

  * •

Key generation
Let $\mathcal{G}\subseteq\mathbb{F}_{q^{m}}^{n}$ be an $[n,k]$ Gabidulin code.
Randomly choose a basis $\mathcal{B}=(\alpha_{1},\ldots,\alpha_{m})$ of
$\mathbb{F}_{q^{m}}$ over $\mathbb{F}_{q}$, and let
$\widehat{\mathcal{G}}=\phi_{\mathcal{B}}(\mathcal{G})$ be an $[N,K]$ expanded
code of $\mathcal{G}$. Let $\widehat{G}$ be a generator matrix of
$\widehat{\mathcal{G}}$, and $\widehat{H}$ a parity-check matrix of the form
$(\ref{paritycheck})$. Let
$u_{f}=\lfloor\frac{n}{\lambda}\rfloor,u_{c}=\lceil\frac{n}{\lambda}\rceil$
and $v=n-\lambda u_{f}$. Randomly choose $A\in GL_{m\lambda}(\mathbb{F}_{q})$
such that the $mv\times mv$ submatrix $A_{sub}$ in the top left corner of $A$
is invertible. Let

$T=\begin{pmatrix}A_{ten}&\\\ &A_{sub}\end{pmatrix}\in
GL_{N}(\mathbb{F}_{q}),$

where $A_{ten}$ is the tensor product $I_{u_{f}}\otimes A$. If the first $K$
columns of $\widehat{G}T^{-1}$ are linearly independent over $\mathbb{F}_{q}$,
then choose $M\in GL_{K}(\mathbb{F}_{q})$ to convert
$G_{pub}=M\widehat{G}T^{-1}$ into systematic form. Otherwise, one rechooses
the matrix $T$. Then the public key is $(G_{pub},t)$ where
$t=\lfloor\frac{n-k}{2\lambda}\rfloor$, and the private key is
$(\widehat{H},A,\mathscr{D}_{\widehat{\mathcal{G}}})$ where
$\mathscr{D}_{\widehat{\mathcal{G}}}$ is the fast decoder of
$\widehat{\mathcal{G}}$.

  * •

Encryption
For a plaintext $\bm{x}\in\mathbb{F}_{q}^{K}$, randomly choose
$E\in\mathcal{M}_{u_{c},m\lambda}(\mathbb{F}_{q})$ of the form

$\displaystyle
E=\begin{pmatrix}\bm{e}_{1}&\cdots&\cdots&\cdots&\bm{e}_{\lambda-1}&\bm{e}_{\lambda}\\\
\bm{e}_{1+\lambda}&\cdots&\cdots&\cdots&\bm{e}_{2\lambda-1}&\bm{e}_{2\lambda}\\\
\vdots&\ddots&\ddots&\ddots&\vdots&\vdots\\\
\bm{e}_{1+(u_{c}-1)\lambda}&\cdots&\bm{e}_{n}&\cdots&\bm{0}&\bm{0}\\\
\end{pmatrix}$ (3)

such that $\textrm{Rank}(E)=t$, where $\bm{e}_{i}\in\mathbb{F}_{q}^{m}$ for
$1\leqslant i\leqslant n$. Let
$\bm{e}=(\bm{e}_{1},\ldots,\bm{e}_{n})\in\mathbb{F}_{q}^{N}$, then the
ciphertext corresponding to $\bm{x}$ is computed as
$\bm{y}=\bm{x}G_{pub}+\bm{e}$.

  * •

Decryption
For a ciphertext $\bm{y}\in\mathbb{F}_{q}^{N}$, compute
$\bm{s}=\bm{y}T\widehat{H}^{T}=\bm{e}T\widehat{H}^{T}$. Applying
$\mathscr{D}_{\widehat{\mathcal{G}}}$ to $\bm{s}$ will lead to
$\bm{e}^{\prime}=\bm{e}T$, then one can recover $\bm{e}$ by computing
$\bm{e}^{\prime}T^{-1}$. The restriction of $\bm{y}-\bm{e}$ to the first $K$
coordinates will be the plaintext.

Correctness of Decryption. First, we introduce the following proposition.

######  Proposition 4.

Given $\lambda$ matrices
$M_{1},M_{2},\ldots,M_{\lambda}\in\mathcal{M}_{u,v}(\mathbb{F}_{q})$, let

$M=[M_{1},M_{2},\ldots,M_{\lambda}]\ \textnormal{and}\
M^{\prime}=\begin{pmatrix}M_{1}\\\ M_{2}\\\ \vdots\\\
M_{\lambda}\end{pmatrix}.$

Suppose $\textrm{Rank}(M)=t$, then there must be
$\textrm{Rank}(M^{\prime})\leqslant\lambda t$.

###### Proof.

Note that $\textrm{Rank}(M)=t$, then $\textrm{Rank}(M_{i})\leqslant t$ for
$1\leqslant i\leqslant\lambda$. Hence
$\textrm{Rank}(M^{\prime})\leqslant\sum_{i=1}^{\lambda}\textrm{Rank}(M_{i})\leqslant\lambda
t$. ∎

From the decrypting process of Proposal ii@, it suffices to prove that
$\bm{e}^{\prime}$ satisfies the decodable condition described in Section 3.2.
Let
$\bm{e}^{\prime}=(\bm{e}^{\prime}_{1},\bm{e}^{\prime}_{2},\ldots,\bm{e}^{\prime}_{n})$,
where $\bm{e}^{\prime}_{i}\in\mathbb{F}_{q}^{m}$ for $1\leqslant i\leqslant
n$, then there exist
$\bm{e}^{\prime}_{n+1},\ldots,\bm{e}^{\prime}_{u_{c}\lambda}\in\mathbb{F}_{q}^{m}$
such that

$E^{\prime}=\begin{pmatrix}\bm{e}^{\prime}_{1}&\cdots&\cdots&\cdots&\bm{e}^{\prime}_{\lambda-1}&\bm{e}^{\prime}_{\lambda}\\\
\bm{e}^{\prime}_{1+\lambda}&\cdots&\cdots&\cdots&\bm{e}^{\prime}_{2\lambda-1}&\bm{e}^{\prime}_{2\lambda}\\\
\vdots&\ddots&\ddots&\ddots&\vdots&\vdots\\\
\bm{e}^{\prime}_{1+(u_{c}-1)\lambda}&\cdots&\bm{e}^{\prime}_{n}&\bm{e}^{\prime}_{n+1}&\cdots&\bm{e}^{\prime}_{u_{c}\lambda}\\\
\end{pmatrix}=EA=[E^{\prime}_{1},E^{\prime}_{2},\ldots,E^{\prime}_{\lambda}],$

where $E^{\prime}_{i}\in\mathcal{M}_{u_{c},m}(\mathbb{F}_{q})$ for $1\leqslant
i\leqslant\lambda$. Apparently we have
$\textrm{Rank}(E^{\prime})=\textrm{Rank}(E)=t$. Let

$F=\begin{pmatrix}\bm{e}^{\prime}_{1}\\\ \bm{e}^{\prime}_{2}\\\ \vdots\\\
\bm{e}^{\prime}_{n}\end{pmatrix}\ \textnormal{and}\
F^{\prime}=\begin{pmatrix}E^{\prime}_{1}\\\ E^{\prime}_{2}\\\ \vdots\\\
E^{\prime}_{\lambda}\end{pmatrix},$

then $\textrm{Rank}(F)\leqslant\textrm{Rank}(F^{\prime})\leqslant\lambda
t\leqslant\lfloor\frac{n-k}{2}\rfloor$ by Proposition 4.

######  Remark 3.

The cryptosystem presented above deals with the general situation where
$\lambda$ does not divide $n$, or equivalently $u_{f}\neq u_{c}$. As for the
case of $u_{f}=u_{c}$, just a few changes are needed in the key generation
procedure. To generate the column scrambling matrix $T^{-1}$, any $A\in
GL_{m\lambda}(\mathbb{F}_{q})$ is feasible for computing $T=I_{u_{f}}\otimes
A$.

##  6 Security analysis

This section mainly discusses the security of the proposed cryptosystems.
Attacks on code-based cryptosystems can be divided into two categories, namely
structural attacks and generic attacks. A structural attack aims to recover
the structure of the underlying code from the published information, which
amounts to recovering the private key or its equivalent form that can be used
to decrypt any valid ciphertext in polynomial time. A generic attack is to
recover the plaintext directly without knowing the private key, which implies
that one has to deal with the underlying hard problem.

In the remainder of this section, we will first introduce a distinguisher for
Gabidulin codes and expalin why our proposals can prevent the existing
structural attacks. Following this, we introduce the concept of twisted
Frobenius power and build a distinguisher for expanded Gabidulin code, which
provides an approach for us to distinguish expanded Gabidulin codes from
random linear codes. After that, we will investigate the practical security of
our proposals from two aspects.

###  6.1 Existing structural attacks

Now we describe some properties of Gabidulin codes under the Frobenius map,
which will be useful for us to explain why our proposals can prevent the
related structural attacks. The following two propositions provide an approach
for us to distinguish Gabidulin codes from general ones.

######  Proposition 5.

[35] Let $\mathcal{G}\subseteq\mathbb{F}_{q^{m}}^{n}$ be an $[n,k]$ Gabidulin
code. For any positive integer $i$, the following equality holds

$\displaystyle\dim(\mathcal{G}+\mathcal{G}^{[1]}+\cdots+\mathcal{G}^{[i]})=\min\\{n,k+i\\}.$

######  Proposition 6.

[35] Let $\mathcal{C}\subseteq\mathbb{F}_{q^{m}}^{n}$ be an $[n,k]$ random
linear code. For any positive integer $i$, the following equality holds with
high probability

$\displaystyle\dim(\mathcal{C}+\mathcal{C}^{[1]}+\cdots+\mathcal{C}^{[i]})=\min\\{n,k(i+1)\\}.$

Most cryptosystems based on Gabidulin codes have been shown to be insecure due
to their vulnerability against structural attacks, such as Overbeck’s
attack[30], Coggia-Couvreu attack[38] and the attack proposed in [35].
Although these attacks were designed to cryptanalyze different variants, most
of them rely on the fact that one can distinguish Gabidulin codes from general
ones by observing how their dimensions behave under the Frobenius map
according to Proposition 5 and 6. However, this property is no longer valid
when considering our proposals. Since our proposals are built over the base
field $\mathbb{F}_{q}$, it is clear that
$\widehat{\mathcal{G}}^{[i]}=\widehat{\mathcal{G}}$ for any integer $i$. In
this situation, Gabidulin codes will be indistinguishable from random codes.
Hence it is reasonable to conclude that all these attacks do not work on our
proposals.

###  6.2 A distinguisher for expanded Gabidulin codes

Let $\mathcal{G}\subseteq\mathbb{F}_{q^{m}}^{n}$ be an $[n,k]$ Gabidulin code,
and $\widehat{\mathcal{G}}$ an expanded code of $\mathcal{G}$ with respect to
a basis $\mathcal{B}$ of $\mathbb{F}_{q^{m}}$ over $\mathbb{F}_{q}$. Given a
generator matrix of $\widehat{\mathcal{G}}$, Berger et al. [33] proposed an
efficient approach to compute $\mathcal{G}^{[s]}$ for some $0\leqslant
s\leqslant m-1$, which is also an $[n,k]$ Gabidulin code. A key point is that
one can recover a normal generator matrix of $\widehat{\mathcal{G}}$, which
can be done by reducing any generator matrix of $\widehat{\mathcal{G}}$ into
systematic form. Hence the direct application of expanded Gabidulin codes will
lead to an insecure scheme. Indeed, one can obtain more information from a
generator matrix of $\widehat{\mathcal{G}}$. For instance, one can recover the
expanded code of $\mathcal{G}^{[s]}$ without knowing the basis $\mathcal{B}$.
To do this, we need to introduce the concept of twisted Frobenius power.

Let $G\in\mathcal{M}_{K,N}(\mathbb{F}_{q})$, where $K=km$ and $N=nm$. For
$1\leqslant i\leqslant k$ and $1\leqslant j\leqslant n$, let
$I_{i}=\\{(i-1)m+1,\ldots,im\\}$ and $J_{j}=\\{(j-1)m+1,\ldots,jm\\}$. Denote
by $G_{ij}$ the submatrix of $G$ from the rows indexed by $I_{i}$ and columns
indexed by $J_{j}$. For a positive integer $s$, we define
$G^{(s)}=(G_{ij}^{q^{s}})$ to be the $s$-th twisted Frobenius power of $G$,
where $G_{ij}^{q^{s}}$ denotes the usual $q^{s}$-th power of $G_{ij}$. For a
sequence $\bm{s}=(1,2,\ldots,N)$, we partition $\bm{s}$ into $n$ blocks, each
of which has length $m$. Let $\mathcal{C}$ be an $[n,k]$ linear code over
$\mathbb{F}_{q^{m}}$, and $\widehat{\mathcal{C}}$ an $[N,K]$ expanded code of
$\mathcal{C}$. Let $I_{1},\ldots,I_{k}$ be $k$ blocks of $\bm{s}$, if
$I=\cup_{i=1}^{k}I_{i}$ forms an information set of $\widehat{\mathcal{C}}$,
then we call $I$ a block information set of $\widehat{\mathcal{C}}$. It is
clear that $\widehat{\mathcal{C}}$ admits at least one block information set.
In the sequel, when we talk about a block information set of a linear code, we
always mean the first one in lexicographic order. Let $I$ be a block
information set of $\widehat{\mathcal{C}}$, and
$G_{I}\in\mathcal{M}_{K,N}(\mathbb{F}_{q})$ a generator matrix of
$\widehat{\mathcal{C}}$, where the submatrix of $G_{I}$ from the columns
indexed by $I$ forms an identity matrix of order $K$. Then we define the
$s$-th twisted Frobenius power of $\widehat{\mathcal{C}}$ as
$\widehat{\mathcal{C}}^{(s)}=\langle G_{I}^{(s)}\rangle_{\mathbb{F}_{q}}$. It
is easy to see that $\widehat{\mathcal{C}}^{(s)}$ is an expanded code of
$\mathcal{C}^{[s]}$ with respect to $\mathcal{B}$ and does not rely on the
choice of the block information set.

The concept of twisted Frobenius power actually provides an approach for us to
compute the expanded code of $\mathcal{C}^{[s]}$ even if the corresponding
basis is not known. Furthermore, we have the following two propositions, which
describe an effective distinguisher for expanded Gabidulin codes from an
expanded code of a random one.

######  Proposition 7.

Let $\mathcal{G}\subseteq\mathbb{F}_{q^{m}}^{n}$ be an $[n,k]$ Gabidulin code,
and $\widehat{\mathcal{G}}\subseteq\mathbb{F}_{q}^{N}$ an expanded code of
$\mathcal{G}$ with respect to a basis $\mathcal{B}$ of $\mathbb{F}_{q^{m}}$
over $\mathbb{F}_{q}$. For any positive integer $i$, the following equality
holds

$\displaystyle\dim(\widehat{\mathcal{G}}+\widehat{\mathcal{G}}^{(1)}+\cdots+\widehat{\mathcal{G}}^{(i)})=\min\\{N,(k+i)m\\}.$

###### Proof.

Note that $\widehat{\mathcal{G}}^{(i)}=\phi_{\mathcal{B}}(\mathcal{G}^{[i]})$,
then

$\displaystyle\widehat{\mathcal{G}}+\widehat{\mathcal{G}}^{(1)}+\cdots+\widehat{\mathcal{G}}^{(i)}$
$\displaystyle=\phi_{\mathcal{B}}(\mathcal{G})+\phi_{\mathcal{B}}(\mathcal{G}^{[1]})+\cdots+\phi_{\mathcal{B}}(\mathcal{G}^{[i]})$
$\displaystyle=\phi_{\mathcal{B}}(\mathcal{G}+\mathcal{G}^{[1]}+\cdots+\mathcal{G}^{[i]}).$

It follows that

$\dim(\widehat{\mathcal{G}}+\widehat{\mathcal{G}}^{(1)}+\cdots+\widehat{\mathcal{G}}^{(i)})=m\dim(\mathcal{G}+\mathcal{G}^{[1]}+\cdots+\mathcal{G}^{[i]}),$

which leads to the conclusion immediately from Propostion 5. ∎

######  Proposition 8.

Let $\widehat{\mathcal{C}}\subseteq\mathbb{F}_{q}^{N}$ be an expanded code of
an $[n,k]$ random code $\mathcal{C}\subseteq\mathbb{F}_{q^{m}}^{n}$. For any
positive integer $i$, the following equality holds with high probability

$\displaystyle\dim(\widehat{\mathcal{C}}+\widehat{\mathcal{C}}^{(1)}+\cdots+\widehat{\mathcal{C}}^{(i)})=\min\\{N,k(i+1)m\\}.$

###### Proof.

Similar to the proof of Proposition 7, the conclusion is obtained immediately
from Proposition 6. ∎

An expanded code always has a block information set. However, a random code
may not have one, such as a linear code $\mathcal{C}$ generated by a matrix
$G$ that has a full-zero column in each block. If a linear code has a block
information set, then we define its twisted Frobenius power following the way
described above. Otherwise, we choose a generator matrix of $\mathcal{C}$ at
random, say $G$, and compute $\mathcal{C}^{(s)}=\langle
G^{(s)}\rangle_{\mathbb{F}_{q}}$. In both situations, however,
$\mathcal{C}^{(s)}$ generally depends on the choice of the block information
set or the generator matrix $G$. Furthermore, we have a heuristic from
Proposition 8 described as follows, which has been verified practically
through numerous experiments.

Heuristic. Let $\mathcal{C}\subseteq\mathbb{F}_{q}^{N}$ be an $[N,K]$ random
code, where $N=nm$ and $K=km$. For any positive integer $i$, the following
equality holds with high probability

$\displaystyle\dim(\widehat{\mathcal{C}}+\widehat{\mathcal{C}}^{(1)}+\cdots+\widehat{\mathcal{C}}^{(i)})=\min\\{N,k(i+1)m\\}.$

With this heuristic and Propositions 7,8, we actually build a distinguisher
for expanded Gabidulin codes. By definition, the applicable condition for
computing the twisted Frobenius power of a code is that both the length and
dimension should be multiples of the extension degree. In our implementation,
we choose $m=n$ and therefore this applicable condition is satisfied.
According to our experimental results, both the public code and its dual in
our two proposals behave more like a random code. Therefore, we believe that
these two proposals can prevent a potential attack based on this
distinguisher.

###  6.3 Generic attacks

In this section, we will show that decrypting a valid ciphertext in our
proposals can be converted into solving a MinRank instance. To facilitate the
description of problems, we introduce an $\mathbb{F}_{q}$-linear isomorphism
$\sigma_{n}$ from $\mathbb{F}_{q}^{ns}$ to
$\mathcal{M}_{n,s}(\mathbb{F}_{q})$. For a vector
$\bm{x}=(\bm{x}_{1},\ldots,\bm{x}_{n})\in\mathbb{F}_{q}^{ns}$ with
$\bm{x}_{i}\in\mathbb{F}_{q}^{s}$, we define $\sigma_{n}(\bm{x})$ as

$\sigma_{n}(\bm{x})=\begin{bmatrix}\bm{x}_{1}^{T},\ldots,\bm{x}_{n}^{T}\end{bmatrix}^{T}\in\mathcal{M}_{n,s}(\mathbb{F}_{q}).$

For a set $\mathcal{X}\subseteq\mathbb{F}_{q}^{ns}$, we define
$\sigma_{n}(\mathcal{X})=\\{\sigma_{n}(\bm{x}):\bm{x}\in\mathcal{X}\\}$. For
any $\bm{x}\in\mathbb{F}_{q}^{ns}$, by $w_{R}(\bm{x})$ we mean the usual rank
of $\sigma_{n}(\bm{x})$ hereafter when no ambiguity arises.

Reducing Proposal i@ to the MinRank problem. In Proposal i@, $K=\lambda
n-m(n-k),N=\lambda n$ and $t=\lfloor\frac{n-k}{2}\rfloor$. Let
$\bm{y}=\bm{c}+\bm{e}$ be a valid ciphertext in Proposal i@, where
$\bm{c}\in\mathcal{G}_{pub}$ and $\bm{e}\in\mathbb{F}_{q}^{N}$ with
$w_{R}(\bm{e})\leqslant t$. Let $M_{0}=\sigma_{n}(\bm{y})$, and
$M_{i}=\sigma_{n}(\bm{m}_{i})$ where $\bm{m}_{i}$ denotes the $i$-th row of
$G_{pub}$ for $1\leqslant i\leqslant K$. Then recovering $\bm{e}$ can be
reduced to a MinRank instance of parameters $(q,n,\lambda,K+1,t)$, that is to
search for $a_{0},a_{1},\ldots,a_{K}\in\mathbb{F}_{q}$ such that
$\textrm{Rank}(\sum_{i=0}^{K}a_{i}M_{i})\leqslant t$.

Reducing Proposal ii@ to the MinRank problem. In Proposal ii@, $K=km,N=nm$ and
$t=\lfloor\frac{n-k}{2\lambda}\rfloor$. Let $\bm{y}=\bm{c}+\bm{e}$ be a valid
ciphertext in Proposal ii@, where $\bm{c}\in\mathcal{G}_{pub}$ and
$\bm{e}\in\mathbb{F}_{q}^{N}$ with $w_{R}(\bm{e})\leqslant\lambda t$. Let
$M_{0}=\sigma_{n}(\bm{y})$, and $M_{i}=\sigma_{n}(\bm{m}_{i})$ where
$\bm{m}_{i}$ denotes the $i$-th row of $G_{pub}$ for $1\leqslant i\leqslant
K$. Then recovering $\bm{e}$ can be reduced to a MinRank instance of
parameters $(q,n,m,K+1,\lambda t)$, that is to search for
$a_{0},a_{1},\ldots,a_{K}\in\mathbb{F}_{q}$ such that
$\textrm{Rank}(\sum_{i=0}^{K}a_{i}M_{i})\leqslant\lambda t$.

####  6.3.1 Combinatorial attacks

Based on the idea of combinatorial attacks on the RSD problem described in
Section 4.1, we now propose a combinatorial attack to evaluate the practical
security our two proposals.

Proposal<EMAIL_ADDRESS>In the case of $n>\lambda$, let $\mathcal{E}=\langle
E\rangle_{\mathbb{F}_{q}}$ and $\mathcal{V}\subseteq\mathbb{F}_{q}^{\lambda}$
be an $\mathbb{F}_{q}$-space of dimension $t^{\prime}\geqslant t$. If
$\mathcal{E}\subseteq\mathcal{V}$, then one can express $E$ in a basis of
$\mathcal{V}$ over $\mathbb{F}_{q}$. With the same analysis as Case $1$ in
Section 4.1, one can obtain a linear system of $m(n-k)$ equations with
$nt^{\prime}$ variables in $\mathbb{F}_{q}$. Let $m(n-k)\geqslant
nt^{\prime}$, then $t^{\prime}\leqslant m-\lceil\frac{km}{n}\rceil$. By taking
$t^{\prime}=m-\left\lceil\frac{km}{n}\right\rceil$, one gets a complexity of
$\mathcal{O}\big{(}m^{3}(n-k)^{3}q^{t(\lambda-m+\lceil\frac{km}{n}\rceil)}\big{)}$.

In the case of $n\leqslant\lambda$, let $\mathcal{E}=\langle
E^{T}\rangle_{\mathbb{F}_{q}}$ and $\mathcal{V}\subseteq\mathbb{F}_{q}^{n}$ be
an $\mathbb{F}_{q}$-space of dimension $t^{\prime}\geqslant t$. If
$\mathcal{E}\subseteq\mathcal{V}$, then one can express $E$ in a basis of
$\mathcal{V}$ over $\mathbb{F}_{q}$. With the same analysis as Case $2$ in
Section 4.1, one can obtain a linear system of $m(n-k)$ equations with
$\lambda t^{\prime}$ variables in $\mathbb{F}_{q}$. Let
$m(n-k)\geqslant\lambda t^{\prime}$, then
$t^{\prime}\leqslant\lfloor\frac{m(n-k)}{\lambda}\rfloor$. By taking
$t^{\prime}=\lfloor\frac{m(n-k)}{\lambda}\rfloor$, one gets a complexity of
$\mathcal{O}\big{(}m^{3}(n-k)^{3}q^{t(n-\lfloor\frac{m(n-k)}{\lambda}\rfloor)}\big{)}$.

Proposal<EMAIL_ADDRESS>On the one hand,
$\mathcal{E}=\langle\bm{e}_{1},\ldots,\bm{e}_{n}\rangle_{\mathbb{F}_{q}}$ has
dimension at most $\lambda t$. Because of $n\leqslant m$, with the same
analysis as Case $2$ in Section 4.1, one gets a complexity of
$\mathcal{O}\big{(}m^{3}(n-k)^{3}q^{\lambda tk}\big{)}$.

On the other hand, $\bm{e}$ is obtained from
$E\in\mathcal{M}_{u_{c},m\lambda}(\mathbb{F}_{q})$ with $\textrm{Rank}(E)=t$.
For $\lambda\geqslant 2$, it is clear that
$u_{c}=\lceil\frac{n}{\lambda}\rceil<n<m\lambda$. Let $\mathcal{E}=\langle
E^{T}\rangle_{\mathbb{F}_{q}}$ and
$\mathcal{V}\subseteq\mathbb{F}_{q}^{u_{c}}$ be an $\mathbb{F}_{q}$-space of
dimension $t^{\prime}\geqslant t$. If $\mathcal{E}\subseteq\mathcal{V}$, then
one can express $E$ in a basis of $\mathcal{V}$ over $\mathbb{F}_{q}$. With
the same analysis as Case $2$ in Section 4.1, one can obtain a linear system
of $m(n-k)$ equations and $m\lambda t^{\prime}$ variables in $\mathbb{F}_{q}$.
Let $m(n-k)\geqslant m\lambda t^{\prime}$, then
$t^{\prime}\leqslant\lfloor\frac{n-k}{\lambda}\rfloor$. By taking
$t^{\prime}=\lfloor\frac{n-k}{\lambda}\rfloor$, one gets a complexity of
$\mathcal{O}(m^{3}(n-k)^{3}q^{t(u_{c}-\lfloor\frac{n-k}{\lambda}\rfloor)})$.

####  6.3.2 Algebraic attacks

Having reduced the proposals to a MinRank instance, one can directly apply the
algebraic attacks described in Table 1 to evaluate the practical security.

##  7 Parameters and performance

In this section, we compute the public key size and information rate of the
proposed cryptosystems for the security of 128 bits, 192 bits and 256 bits
against the generic attacks described in Section 6.3. After that we will make
a comparison on public key size with some other code-based cryptosystems.

In Proposal i@, the public key is a systematic generator matrix of a $[\lambda
n,\lambda n-mr]$ code where $r=n-k$, resulting in a public key size of
$mr(n\lambda-mr)\cdot log_{2}(q)$ bits. In Proposal ii@, the public key is a
systematic generator matrix of an $[mn,mk]$ code, resulting in a public key
size of $rkm^{2}\cdot log_{2}(q)$ bits. As for the information rate, this
value is evaluated as $(n\lambda-mr)/n\lambda$ for Proposal i@, and $k/n$ for
Proposal ii@ respectively.

Instance |  Parameters |  Key Size |  Rate |  Security
---|---|---|---|---
$q$ | $m$ | $n$ | $k$ | $\lambda$
Proposal i@ | 2 | 31 | 31 | 19 | 29 | 24506 | 0.59 | 128
2 | 38 | 38 | 20 | 36 | 58482 | 0.50 | 192
2 | 45 | 45 | 25 | 43 | 116438 | 0.53 | 256
Proposal ii@ | 2 | 56 | 56 | 28 | 2 | 307328 | 0.49 | 128
2 | 72 | 72 | 32 | 2 | 829440 | 0.44 | 192
2 | 84 | 84 | 40 | 2 | 1552320 | 0.48 | 256
Table 2: Public key size (in bytes) and information rate. Instance |  Parameters |  Key Size |  Rate |  Security
---|---|---|---|---
$q$ | $m$ | $n$ | $k$ | $\lambda$
Proposal i@ | 7 | 20 | 20 | 12 | 18 | 11230 | 0.56 | 128
7 | 24 | 24 | 14 | 22 | 24256 | 0.55 | 192
7 | 28 | 28 | 16 | 26 | 46221 | 0.54 | 256
Proposal ii@ | 7 | 35 | 35 | 23 | 2 | 118646 | 0.66 | 128
7 | 45 | 45 | 29 | 2 | 329724 | 0.64 | 192
7 | 51 | 51 | 31 | 2 | 565900 | 0.61 | 256
Table 3: Public key size (in bytes) and information rate. Instance |  Parameters |  Key Size |  Rate |  Security
---|---|---|---|---
$q$ | $m$ | $n$ | $k$ | $\lambda$
Proposal i@ | 13 | 18 | 18 | 12 | 16 | 8993 | 0.63 | 128
13 | 21 | 21 | 11 | 19 | 18359 | 0.47 | 192
13 | 25 | 25 | 15 | 23 | 37583 | 0.57 | 256
Proposal ii@ | 13 | 29 | 29 | 17 | 2 | 79358 | 0.59 | 128
13 | 37 | 37 | 21 | 2 | 212768 | 0.57 | 192
13 | 43 | 43 | 23 | 2 | 393422 | 0.53 | 256
Table 4: Public key size (in bytes) and information rate.

We investigate the performance of the proposed cryptosystems in three cases,
as summarized in Tables 2, 3 and 4. Taking the public key size as a more
important issue, we suggest the parameter sets in Table 4 for the
corresponding security level. With such a choice of parameter sets, we make a
comparison on public key size with some other code-based cryptosystems in
Table 5.

Instance Security |  128 |  192 |  256
---|---|---|---
Classic McEliece [51] | 261120 | 524160 | 1044992
BGR [33] | 11571 |  | 47104
HQC [50] | 2249 | 4522 | 7245
BIKE [49] | 1540 | 3082 | 5121
Proposal i@ | 8993 | 18359 | 37583
Proposal ii@ | 79358 | 212768 | 393422
Table 5: Comparison on public key size (in bytes).

##  8 Conclusion

This paper presents two cryptosystems by using expanded Gabidulin codes in the
McEliece setting. In our proposals, the underlying expanded Gabidulin code is
divided into $n$ blocks, with each block having size $m$. By definition, each
block corresponds to one component of the parent Gabidulin code. To destroy
this correspondence, in Proposal i@ we first shorten the expanded Gabidulin
code, then perform a column-mixing transformation to each block. In Proposal
ii@, we adopt a rather different column-mixing transformation to the
underlying code by mixing $\lambda$ neighbouring blocks. The greatest
advantage of using expanded Gabidulin codes is that all existing structural
attacks based on the Frobenius map no longer make sense. Additionally, an
effective distinguisher is introduced for expanded Gabidulin codes, and the
public code in these two proposals seems indistinguishable from random codes
under this distinguisher. Furthermore, our proposals have a clear advantage in
public key representation over some other code-based cryptosystems. For
instance, we have reduced the public key size by around 96% compared to
Classic McEliece entering the third round of the NIST PQC project.

  * Acknowledgements

This research is supported by the National Key Research and Development
Program of China (Grant No. 2018YFA0704703), the National Natural Science
Foundation of China (Grant No. 61971243), the Natural Science Foundation of
Tianjin (20JCZDJC00610), and the Fundamental Research Funds for the Central
Universities of China (Nankai University).

## References

  * [1] McEliece, R.J.: A public key cryptosystem based on algebraic coding theory. Jet Propuls. Lab. DSN Progr. Rep. 42-44, 114–116 (1978).
  * [2] Lee, P.J., Brickell, E.F.: An observation on the security of McEliece’s public key cryptosystem. In: Guenther, C.G. (Ed.): Proceedings of Advances in Cryptology-EUROCRYPT’88, LNCS, vol. 330, pp. 275–280. Springer (1988).
  * [3] Canteaut, A., Sendrier, N.: Cryptanalysis of the original McEliece cryptosystem. In: Ohta, K., Pei, D. (Eds.): Proceedings of ASIACRYPT’98, LNCS, vol. 1514, pp. 187–199. Springer (2000).
  * [4] Loidreau, P., Sendrier, N.: Weak keys in the McEliece public key cryptosystem. IEEE Trans. Inf. Theory 47(3), 1207–1211 (2001).
  * [5] Faugère, J.-C., Gauthier-Umana, V., Otmani, A., Perret, L., Tillich, J.-P.: A distinguisher for high-rate McEliece cryptosystems. IEEE Trans. Inf. Theory 59(10), 6830–6844 (2013).
  * [6] Couvreur, A., Otmani, A., Tillich, J.-P.: Polynomial time attack on wild McEliece over quadratic extensions. IEEE Trans. Inf. Theory 63(1), 404–427 (2016).
  * [7] Loidreau, P.: Strengthening McEliece cryptosystem. In: Okamoto, T. (Ed.): Proceedings of ASIACRYPT 2000, LNCS, vol. 1976, pp. 585–598. Springer (2000).
  * [8] Kobara, K., Imai, H.: On the one-wayness against chosen-plaintext attacks of the Loidreau’s modified McEliece PKC. IEEE Trans. Inf. Theory 49(12), 3160–3168 (2003).
  * [9] Misoczki, R., Barreto, P.S.: Compact McEliece keys from Goppa codes. In: M.J. Jacobson Jr., Rijmen V., Safavi-Naini R. (Eds.): Proceedings of SAC 2009, LNCS, vol. 5867, pp. 376–392. Springer (2009).
  * [10] Faugère, J.-C., Otmani, A., Perret, L., Tillich J.-P.: Algebraic cryptanalysis of McEliece variants with compact keys. In: Gilbert, H. (Ed.): Proceedings of EUROCRYPT 2010, LNCS, vol. 6110, pp. 279–298. Springer (2010).
  * [11] Niederreiter, H.: Knapsack-type cryptosystems and algebraic coding theory. Prob. Contr. Inform. Theory 15(2), 159–166 (1986).
  * [12] Sidelnikov, V.M., Shestakov, S.O.: On insecurity of cryptosystems based on generalized Reed-Solomon codes. Discret. Math. Appl. 2(4), 439–444 (1992).
  * [13] Wu, Y.: On expanded cyclic and Reed-Solomon codes. IEEE. Trans. Inf. Theory 57(2), 601–620 (2011).
  * [14] Couvreur, A., Lequesne, M.: On the security of subspace subcodes of Reed-Solomon codes for public key encryption. IEEE. Trans. Inf. Theory 68(1), 632–648 (2022).
  * [15] Li, Y.X., Deng, R.H., Wang, X.M.: On the equivalence of McEliece’s and Niederreiter’s public key cryptosystems. IEEE Trans. Inf. Theory 40(1), 271–273 (1994).
  * [16] Baldi, M., Bianchi, M., Chiaraluce, F., Rosenthal J., Schipani, D.: Enhanced public key security for the McEliece cryptosystem. J. Cryptology 29(1), 1–27 (2016).
  * [17] Wieschebrink, C.: Cryptanalysis of the Niederreiter public key scheme based on GRS subcodes. In: Sendrier, N. (Ed.): Proceedings of PQCrypto 2010, LNCS, vol. 6061, pp. 61–72. Springer (2010).
  * [18] Couvreur, A., Gaborit, P., Otmani, A., Tillich, J.-P.: Distinguisher-based attacks on public key cryptosystems using Reed-Solomon codes. Des. Codes Cryptogr. 73(2), 641–666 (2014).
  * [19] Khathuria, K., Rosenthal, J., Weger, V.: Encryption scheme based on expanded Reed-Solomon codes. Adv. Math. Commun. 15(2), 207–218 (2021).
  * [20] Mullen, G.L., Panario, D.: Handbook of Finite Fields. CRC Press (2013).
  * [21] Gabidulin, E.M.: Theory of codes with maximum rank distance. Prob. Peredachi Inf. 21(1), 3–16 (1985).
  * [22] Chabaud, F., Stern, J.: The cryptographic security of the syndrome decoding problem for rank distance codes. In: Proceedings of International Conference on the Theory and Application of Cryptology and Information Security, pp. 368–381. Springer (1996).
  * [23] Ourivski, A.V., Johansson, T.: New technique for decoding codes in the rank metric and its cryptography applications. Probl. Inf. Transm. 38(3), 237–246 (2002).
  * [24] Gabidulin, E.M., Paramonov, A.V., Tretjakov, O.V.: Ideals over a non-commutative ring and their application in cryptology. In: Davies, D.W. (Ed.): Proceedings of Advances in Cryptology-EUROCRYPT’91, LNCS, vol. 547, pp. 482–489. Springer (1991).
  * [25] Gabidulin, E.M.: Attacks and counter-attacks on the GPT public key cryptosystem. Des. Codes Cryptogr. 48(2), 171–177 (2008).
  * [26] Gabidulin, E.M., Rashwan, H., Honary, B.: On improving security of GPT cryptosystems. In: Proceedings of 2009 IEEE International Symposium on Information Theory, pp. 1110–1114. IEEE (2009).
  * [27] Loidreau, P.: Designing a rank metric based McEliece cryptosystem. In: Sendrier, N. (Ed.): Proceedings of PQCrypto 2010, LNCS, vol. 6061, pp. 142–152. Springer (2010).
  * [28] Rashwan, H., Gabidulin, E.M., Honary, B.: A smart approach for GPT cryptosystem based on rank codes. In: Proceedings of 2010 IEEE International Symposium on Information Theory, pp. 2463–2467. IEEE (2010).
  * [29] Gibson, K.: The security of the Gabidulin public key cryptosystem. In: Proceedings of Advances in Cryptology-EUROCRYPT’96, LNCS, vol. 1070, pp. 212–223. Springer (1996).
  * [30] Overbeck, R.: Structural attacks for public key cryptosystems based on Gabidulin codes. J. Cryptology 21(2), 280–301 (2008).
  * [31] Horlemann-Trautmann, A.-L., Marshall, K., Rosenthal, J.: Extension of Overbeck’s attack for Gabidulin-based cryptosystems. Des. Codes Cryptogr. 86(2), 319–340 (2018).
  * [32] Otmani, A., Kalachi, H.T., Ndjeya, S.: Improved cryptanalysis of rank metric schemes based on Gabidulin codes. Des. Codes Cryptogr. 86(9), 1983–1996 (2018).
  * [33] Berger, T.P., Gaborit, P., Ruatta, O.: Gabidulin matrix codes and their application to small ciphertext size cryptosystems. In: Patra, A. Smart, N.P. (Eds.): Proceedings of INDOCRYPT 2017, LNCS, vol. 10698, pp. 247-266. Springer (2017).
  * [34] Faure, C., Loidreau, P.: A new public key cryptosystem based on the problem of reconstructing $p$-polynomials. In: Ytrehus, $\varnothing$. (Ed.): Proceedings of WCC 2005, LNCS, vol. 3969, pp. 304–315. Springer (2005).
  * [35] Gaborit, P., Otmani, A., Kalachi, H.T.: Polynomial-time key recovery attack on the Faure–Loidreau scheme based on Gabidulin codes. Des. Codes Cryptogr. 86(7),1391–1403 (2018).
  * [36] Loidreau, P.: A new rank metric codes based encryption scheme. In: Lange, T., Takagi, T. (Eds.): Proceedings of PQCrypto 2017, LNCS, vol. 10346, pp. 3–17. Springer (2017).
  * [37] Gabidulin, E.M., Ourivski, A.V., Honary, B., Ammar, B.: Reducible rank codes and their applications to cryptography. IEEE Trans. Inf. Theory 49(12), 3289–3293 (2003).
  * [38] Coggia, D., Couvreur, A.: On the security of a Loidreau rank metric code based encryption scheme. Des. Codes Cryptogr. 88(9), 1941–1957 (2020).
  * [39] Ghatak, A: Extending Coggia–Couvreur attack on Loidreau’s rank-metric cryptosystem. Des. Codes Cryptogr. (2021). https://doi.org/10.1007/s10623-021-00972-7.
  * [40] Horlemann-Trautmann, A.-L., Marshall, K.: New criteria for MRD and Gabidulin codes and some rank-metric code constructions. arXiv:1507.08641 [cs.IT] (2015).
  * [41] Loidreau, P.: A Welch-Berlekamp like algorithm for decoding Gabidulin codes. In: Ytrehus, $\varnothing$. (Ed.): Proceedings of WCC 2005, LNCS, vol. 3969, pp. 36–45. Springer (2005).
  * [42] Richter, G., Plass, S.: Error and erasure decoding of rank-codes with a modified Berlekamp-Massey algorithm. ITG FACHBERICHT, pp. 203–210 (2004).
  * [43] Ourivski, A.V., Johansson, T.: New technique for decoding codes in the rank metric and its cryptography applications. Problems Inform. Transm. 38(3), 237–246 (2002).
  * [44] Gaborit, P., Ruatta, O., Schrek, J.: On the complexity of the rank syndrome decoding problem. IEEE Trans. Inf. Theory 62(2), 1006–1019 (2016).
  * [45] Aragon, N., Gaborit, P., Hauteville, A., Tillich, J.-P.: A new algorithm for solving the rank syndrome decoding problem. In: Proceedings of 2018 IEEE International Symposium on Information Theory (ISIT), pp. 2421–2425. IEEE (2018).
  * [46] Buss, J.F., Frandsen, G.S., Shallit, J.O.: The computational complexity of some problems of linear algebra. J. Comput. Syst. Sci. 58(3), 572–596 (1999).
  * [47] Bardet, M., Bros, M., Cabarcas, D., et al.: Improvements of algebraic attacks for solving the rank decoding and MinRank problems. In: Moriai, S., Wang, H. (Eds.): Proceedings of ASIACRYPT 2020, LNCS, vol. 12491, pp. 507–536. IACR (2020).
  * [48] Cabarcas, D., Smith-Tone, D., Verbel, J.A.: Key recovery attack for ZHFE. In: Lange, T., Takagi, T. (Eds.): Proceedings of PQCrypto 2017, LNCS, vol. 10346, pp. 289–308. Springer (2017).
  * [49] Aragon, N., Barreto, P.S., et al.: BIKE: bit flipping key encapsulation. https://bikesuite.org/files/v4.1/BIKE_Spec.2020.10.22.1.pdf. Accessed October 10, 2020.
  * [50] Melchor, C.A., Aragon, N., et al.: Hamming quasi-cyclic (HQC). http://pqc-hqc.org/doc/hqc-specification_2020-10-01.pdf. Accessed October 10, 2020.
  * [51] Albrecht, M.R., Bernstein, D.J., et al.: Classic McEliece: conservative code-based cryptography. https://classic.mceliece.org/nist/mceliece-20201010.pdf. Accessed October 10, 2020.