Title: Cryptanalysis of the Faure-Loidreau PKE, a rank-metric code-based cryptosystem with short keys.
Abstract: In 2005, C. Faure and P. Loidreau designed a rank-metric encryption
scheme which was not in the McEliece setting. This scheme has small public and
private keys (a few kiloBytes only) and is based on the hardness of decoding some
rank-metric codes (namely the Gabidulin codes) above half the minimum distance.
In 2016 though, this scheme was subject to a very efficient polynomial time
key-recovery attack by P. Gaborit, A. Otmani and H. Talé-Kalachi. A repaired version was
eventually proposed by A. Wachter-Zeh, S. Puchinger and J. Renner in 2018
to resist the previous structural attack.
In this talk, I will present a variant of a decoder for Gabidulin codes, which can be used
in an alternative attack on the original Faure-Loidreau cryptosystem. I will then show that
the repaired version is vulnerable to a practical plaintext recovery attack.
This is joint work with Alain Couvreur.
