Randomized Decoding of Gabidulin Codes Beyond the Unique Decoding Radius

Julian Renner*, Thomas Jerkovits, Hannes Bartz, Sven Puchinger, Pierre Loidreau, Antonia Wachter-Zeh

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

10 Downloads (Pure)

Abstract

We address the problem of decoding Gabidulin codes beyond their unique error-correction radius. The complexity of this problem is of importance to assess the security of some rank-metric code-based cryptosystems. We propose an approach that introduces row or column erasures to decrease the rank of the error in order to use any proper polynomial-time Gabidulin code error-erasure decoding algorithm. The expected work factor of this new randomized decoding approach is a polynomial term times (Formula Presented), where n is the code length, q the size of the base field, m the extension degree of the field, k the code dimension, w the number of errors, and (Formula Presented). It improves upon generic rank-metric decoders by an exponential factor.

Original languageEnglish
Title of host publicationProceedings of the 11th International Conference on Post-Quantum Cryptography
EditorsJintai Ding, Jean-Pierre Tillich
PublisherSpringer
Publication date1 Jan 2020
Pages3-19
ISBN (Print)9783030442224
DOIs
Publication statusPublished - 1 Jan 2020
Event11th International Conference on Post-Quantum Cryptography, PQCrypto 2020 - Paris, France
Duration: 15 Apr 202017 Apr 2020

Conference

Conference11th International Conference on Post-Quantum Cryptography, PQCrypto 2020
CountryFrance
CityParis
Period15/04/202017/04/2020
SeriesLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12100 LNCS
ISSN0302-9743

Keywords

  • Code-based cryptography
  • Decoding
  • Gabidulin codes
  • Rank metric

Cite this

Renner, J., Jerkovits, T., Bartz, H., Puchinger, S., Loidreau, P., & Wachter-Zeh, A. (2020). Randomized Decoding of Gabidulin Codes Beyond the Unique Decoding Radius. In J. Ding, & J-P. Tillich (Eds.), Proceedings of the 11th International Conference on Post-Quantum Cryptography (pp. 3-19). Springer. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol.. 12100 LNCS https://doi.org/10.1007/978-3-030-44223-1_1