MinRank Gabidulin Encryption Scheme on Matrix Codes

The McEliece scheme is a generic frame introduced in [28], which allows to use any error correcting code for which there exists an efficient decoding algorithm to design an encryption scheme by hiding the generator matrix of the code. Similarly, the Niederreiter frame, introduced in [30], is the dual version of the McEliece scheme, and achieves smaller ciphertexts. In the present paper, we propose a generalization of the McEliece 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, computing a matrix version of C and then concatenating a certain number of rows and columns to the matrix code version of the rank code C before applying an isometry for matrix codes, i.e. right and left multiplications by fixed random matrices. The security of the schemes relies on the MinRank problem to decrypt a ciphertext, and the structural security of the scheme relies on the new 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 trade off between the size of the ciphertext and the size of the public key. For 128 bits of security we propose parameters ranging from ciphertexts of size 65 B (and public keys of size 98 kB) to ciphertexts of size 138 B (and public keys of size 41 kB). For 256 bits of security, we can obtain ciphertext as low as 119 B, or public key as low as 87 kB. Our new approach permits to achieve a better trade-off between ciphertexts and public key than the classical McEliece scheme instantiated with Goppa codes.