Back to overview

Considerations for Rank-based Cryptosystems

Type of publication Peer-reviewed
Publikationsform Original article (peer-reviewed)
Publication date 2016
Author Horlemann-Trautmann Anna-Lena, Marshall Kyle, Rosenthal Joachim,
Project Algebraic Constructions and Decoding of Subspace Codes
Show all

Original article (peer-reviewed)

Journal 2016 IEEE International Symposium on Information Theory (ISIT)
Page(s) 2544 - 2548
Title of proceedings 2016 IEEE International Symposium on Information Theory (ISIT)
DOI 10.1109/ISIT.2016.7541758

Open Access


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.