  The McEliece scheme is a generic frame which allows to use any error
correcting code of which there exists an efficient decoding algorithm to design
an encryption scheme by hiding the generator matrix code. Similarly, the
Niederreiter frame is the dual version of the McEliece scheme, and achieves
smaller ciphertexts. We propose a generalization of the McEliece frame and the
Niederreiter frame to matrix codes and the MinRank problem, that we apply to
Gabidulin matrix codes (Gabidulin rank codes considered as matrix codes). The
masking we consider consists in starting from a rank code C, to consider a
matrix version of C and to concatenate a certain number of rows and columns to
the matrix codes version of the rank code C and then apply to an isometry for
matric codes. The security of the schemes relies on the MinRank problem to
decrypt a ciphertext, and the structural security of the scheme relies on a new
problem EGMC-Indistinguishability problem that we introduce and that we study
in detail. The main structural attack that we propose consists in trying to
recover the masked linearity over the extension field which is lost during the
masking process. Overall, starting from Gabidulin codes we obtain a very
appealing tradeoff between the size of ciphertext and the size of the public
key. For 128b of security we propose parameters ranging from ciphertext of size
65 B (and public keys of size 98 kB) to ciphertext of size 138B (and public key
of size 41 kB). Our new approach permits to achieve better trade-off between
ciphertexts and public key than the classical McEliece scheme. Our new approach
permits to obtain an alternative scheme to the classic McEliece scheme, to
obtain very small ciphertexts, with moreover smaller public keys than in the
classic McEliece scheme. For 256 bits of security, we can obtain ciphertext as
low as 119B, or public key as low as 87kB.
