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 language | English |
---|---|
Title of host publication | Proceedings of the 11th International Conference on Post-Quantum Cryptography |
Editors | Jintai Ding, Jean-Pierre Tillich |
Publisher | Springer |
Publication date | 1 Jan 2020 |
Pages | 3-19 |
ISBN (Print) | 9783030442224 |
DOIs | |
Publication status | Published - 1 Jan 2020 |
Event | 11th International Conference on Post-Quantum Cryptography - Jussieu Campus, Paris, France Duration: 21 Sept 2020 → 23 Sept 2020 Conference number: 11 https://pqcrypto2020.inria.fr/ |
Conference
Conference | 11th International Conference on Post-Quantum Cryptography |
---|---|
Number | 11 |
Location | Jussieu Campus |
Country/Territory | France |
City | Paris |
Period | 21/09/2020 → 23/09/2020 |
Internet address |
Series | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
Volume | 12100 LNCS |
ISSN | 0302-9743 |
Keywords
- Code-based cryptography
- Decoding
- Gabidulin codes
- Rank metric