Randomized Decoding of Gabidulin Codes Beyond the Unique Decoding Radius

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

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 $$q^{m(n-k)-w(n+m)+w^2+\min \{2\xi (\frac{n+k}{2}-\xi ),wk\} }$$, 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 $$\xi := w-\tfrac{n-k}{2}$$. It improves upon generic rank-metric decoders by an exponential factor.
BibTeX
@inproceedings{renner2020randomized,
  author = {Julian Renner and Thomas Jerkovits and Hannes Bartz and Sven Puchinger and Pierre Loidreau and Antonia Wachter-Zeh},
  title = {{Randomized Decoding of Gabidulin Codes Beyond the Unique Decoding Radius}},
  booktitle = {PQCrypto},
  year = {2020},
  doi = {10.1007/978-3-030-44223-1\_1},
}

Loading related content...

Figure