Considerations for Rank-based Cryptosystems

Cryptosystems based on rank metric codes have been considered as an alternative to McEliece cryptosystems due to the relative difficulty of solving the rank syndrome decoding problem. Generic attacks have recently seen several improvements, notably in the work of Gaborit et al., who give an improved algorithm using linearized polynomials which yields a polynomial time algorithm for certain parameters. On the structural side, many of the proposals for cryptosystems based on Gabidulin codes have proven to be weak, following an attack by Overbeck in 2001. Of the Gabidulin based systems managing to resist Overbeck's attack, several were recently broken by Horlemann-Trautmann et al. using an attack based on finding the elements of rank one in some extended code. In this paper, we extend the polynomial time algorithm of Gaborit using the same underlying idea as Horlemann-Trautmann et al., and then demonstrate how codes with implicit structural weakness may be exploited, even if the explicit structure is not determined. We use this attack to break a Gabidulin code based cryptosystem which has so far resisted structural attacks.