Header

UZH-Logo

Maintenance Infos

Extension of Overbeck’s attack for Gabidulin-based cryptosystems


Horlemann-Trautmann, Anna-Lena; Marshall, Kyle; Rosenthal, Joachim (2018). Extension of Overbeck’s attack for Gabidulin-based cryptosystems. Designs, Codes and Cryptography, 86(2):319-340.

Abstract

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.

Abstract

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.

Statistics

Citations

Dimensions.ai Metrics
9 citations in Web of Science®
14 citations in Scopus®
Google Scholar™

Altmetrics

Downloads

30 downloads since deposited on 08 Mar 2018
12 downloads since 12 months
Detailed statistics

Additional indexing

Item Type:Journal Article, refereed, original work
Communities & Collections:07 Faculty of Science > Institute of Mathematics
Dewey Decimal Classification:510 Mathematics
Scopus Subject Areas:Physical Sciences > Computer Science Applications
Physical Sciences > Applied Mathematics
Language:English
Date:2018
Deposited On:08 Mar 2018 09:11
Last Modified:29 Jul 2020 07:02
Publisher:Springer
ISSN:0925-1022
Funders:Schweizerischer Nationalfonds
OA Status:Green
Publisher DOI:https://doi.org/10.1007/s10623-017-0343-7

Download

Green Open Access

Download PDF  'Extension of Overbeck’s attack for Gabidulin-based cryptosystems'.
Preview
Content: Accepted Version
Language: English
Filetype: PDF
Size: 282kB
View at publisher