Ilaria Zappatore. An extension of Overbeck's attack with an application to cryptanalysis of Twisted Gabidulin-based schemes

The first McEliece-like scheme based on rank metric codes was proposed by Gabidulin, Paramonov and Tretjakov in 1991. This system is based on Gabidulin codes and is called GPT, after its three authors. It has been attacked and repaired several times, until 2008, when Overbeck proposed a polynomial-time attack that breaks GPT and its improvements. One natural approach to circumventing this attack is to replace the Gabidulin codes with another family of rank metric codes equipped with an efficient decoding algorithm. Indeed, in 2018, Putchinger, Renner and Wachter-Zeh proposed to replace Gabidulin codes with twisted Gabidulin codes. 

In this talk, first, we discuss the decoding of Gabidulin and twisted Gabidulin codes from a cryptographic point of view, and we observe that these codes can be decoded solely from the knowledge of a generator matrix. This observation has significant consequences in the cryptanalysis of the correspondent scheme. We then extend and revisit the Overbeck's attack on the generalized GPT encryption scheme instantiated with Gabidulin codes, for different ranks of the distortion matrix. Finally, we see how we can apply this attack to the case of an instantiation with twisted Gabidulin codes.