Séminaire de Théorie Algorithmique des Nombres
MinRank Gabidulin Encryption Scheme on Matrix Codes
Victor Dyseryn
( (Telecom Paris) )Salle 2
le 11 février 2025 à 11:00
The McEliece scheme enjoys small ciphertexts, but suffers from a large public key. To reduce sizes, many attempts have been made to instantiate the McEliece scheme with rank metric Gabidulin codes instead of Hamming metric Goppa codes. However they were all broken due to the strong Fqm-linear structure of Gabidulin codes. In the present work, we suggest a new masking of Gabidulin codes. Our masking consists in computing a matrix version of the rank metric vector code C, then in breaking the Fqm-linearity by concatenating a number of rows and columns to the matrix code version of 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. In this talk, we will present our main structural attack that consists in recovering the masked linearity over the extension field which has been lost during the masking process. Overall, 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 98kB) to ciphertexts of size 138B (and public keys of size 41 kB).