TY - GEN
T1 - Randomized Decoding of Gabidulin Codes Beyond the Unique Decoding Radius
AU - Renner, Julian
AU - Jerkovits, Thomas
AU - Bartz, Hannes
AU - Puchinger, Sven
AU - Loidreau, Pierre
AU - Wachter-Zeh, Antonia
N1 - Publisher Copyright:
© 2020, Springer Nature Switzerland AG.
PY - 2020
Y1 - 2020
N2 - 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.
AB - 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.
KW - Code-based cryptography
KW - Decoding
KW - Gabidulin codes
KW - Rank metric
UR - http://www.scopus.com/inward/record.url?scp=85083980486&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-44223-1_1
DO - 10.1007/978-3-030-44223-1_1
M3 - Conference contribution
AN - SCOPUS:85083980486
SN - 9783030442224
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 3
EP - 19
BT - Post-Quantum Cryptography - 11th International Conference, PQCrypto 2020, Proceedings
A2 - Ding, Jintai
A2 - Tillich, Jean-Pierre
PB - Springer
T2 - 11th International Conference on Post-Quantum Cryptography, PQCrypto 2020
Y2 - 15 April 2020 through 17 April 2020
ER -