Randomized Decoding of Gabidulin Codes Beyond the Unique Decoding Radius
Preprint
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. This approach improves on generic rank-metric decoders by an exponential factor.Keywords
All Related Versions
This publication has 25 references indexed in Scilit:
- An Algebraic Attack on Rank Metric Code-Based Cryptosystems2020
- Polynomial-time key recovery attack on the Faure–Loidreau scheme based on Gabidulin codesDesigns, Codes and Cryptography, 2017
- A basis for all solutions of the key equation for Gabidulin codes2010
- Error and erasure correcting algorithms for rank codesDesigns, Codes and Cryptography, 2008
- A New Public-Key Cryptosystem Based on the Problem of Reconstructing p–PolynomialsLecture Notes in Computer Science, 2006
- A Public Key Encryption Scheme Based on the Polynomial Reconstruction Problem2003
- Improved decoding of Reed-Solomon and algebraic-geometry codesIEEE Transactions on Information Theory, 1999
- The intractability of computing the minimum distance of a codeIEEE Transactions on Information Theory, 1997
- Maximum-rank array codes and their application to crisscross error correctionIEEE Transactions on Information Theory, 1991
- Bilinear forms over a finite field, with applications to coding theoryJournal of Combinatorial Theory, Series A, 1978