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

126 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 - Jussieu Campus, Paris, France
Duration: 21 Sept 202023 Sept 2020
Conference number: 11
https://pqcrypto2020.inria.fr/

Conference

Conference11th International Conference on Post-Quantum Cryptography
Number11
LocationJussieu Campus
Country/TerritoryFrance
CityParis
Period21/09/202023/09/2020
Internet address
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

Fingerprint

Dive into the research topics of 'Randomized Decoding of Gabidulin Codes Beyond the Unique Decoding Radius'. Together they form a unique fingerprint.

Cite this