Randomized Decoding of Gabidulin Codes Beyond the Unique Decoding Radius
Preprint
Abstract
We address the problem of decoding Gabidulin codes beyond their error-correcting 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 columns 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 24 references indexed in Scilit:
- An Algebraic Attack on Rank Metric Code-Based Cryptosystems2020
- A New Algorithm for Solving the Rank Syndrome Decoding Problem2018
- Repairing the Faure-Loidreau Public-Key Cryptosystem2018
- 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
- 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
- On the inherent intractability of certain coding problems (Corresp.)IEEE Transactions on Information Theory, 1978