Decoding supercodes of Gabidulin codes and applications to cryptanalysis

Maxime Bombar; Alain Couvreur

Paper 2021/348

Decoding supercodes of Gabidulin codes and applications to cryptanalysis

Maxime Bombar and Alain Couvreur

Abstract

This article discusses the decoding of Gabidulin codes and shows how to extend the usual decoder to any supercode of a Gabidulin code at the cost of a significant decrease of the decoding radius. Using this decoder, we provide polynomial time attacks on the rank–metric encryption schemes Ramesses and Liga.

Note: The Sage code is available on Github: https://github.com/mbombar/Attack_on_LIGA

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published elsewhere. PQCrypto 2021
Keywords: Code–based cryptography Gabidulin codes decoding rank–metric cryptanalysis
Contact author(s): maxime bombar @ inria fr
History: 2021-06-14: revised; 2021-03-17: received; See all versions
Short URL: https://ia.cr/2021/348
License: CC BY

BibTeX

@misc{cryptoeprint:2021/348,
      author = {Maxime Bombar and Alain Couvreur},
      title = {Decoding supercodes of Gabidulin codes and applications to cryptanalysis},
      howpublished = {Cryptology {ePrint} Archive, Paper 2021/348},
      year = {2021},
      url = {https://eprint.iacr.org/2021/348}
}