Back to overview

Extension of Overbeck’s attack for Gabidulin-based cryptosystems

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

Original article (peer-reviewed)

Journal Designs, Codes and Cryptography
Volume (Issue) 86(2)
Page(s) 319 - 340
Title of proceedings Designs, Codes and Cryptography
DOI 10.1007/s10623-017-0343-7


Cryptosystems based on codes in the rank metric were introduced in 1991 by Gabidulin, Paramanov, and Tretjakov (GPT) and have been studied as a promising alternative to cryptosystems based on codes in the Hamming metric. In particular, it was observed that the combinatorial solution for solving the rank analogy of the syndrome decoding problem appears significantly harder. Early proposals were often made with an underlying Gabidulin code structure. Gibson, in 1995, made a promising attack which was later extended by Overbeck in 2008 to cryptanalyze many of the systems in the literature. Improved systems were then designed to resist the attack of Overbeck and yet continue to use Gabidulin codes. In this paper, we generalize Overbeck’s attack to break the GPT cryptosystem for all possible parameter sets, and then extend the attack to cryptanalyze particular variants which explicitly resist the attack of Overbeck.