  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.
