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 cryptographyGabidulin codesdecodingrank–metriccryptanalysis
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
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2021/348}},
      url = {https://eprint.iacr.org/2021/348}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.