### 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, PQCrypto 2020 - Paris, France Duration: 15 Apr 2020 → 17 Apr 2020 |

### Conference

Conference | 11th International Conference on Post-Quantum Cryptography, PQCrypto 2020 |
---|---|

Country | France |

City | Paris |

Period | 15/04/2020 → 17/04/2020 |

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

## Cite this

*Proceedings of the 11th International Conference on Post-Quantum Cryptography*(pp. 3-19). Springer. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol.. 12100 LNCS https://doi.org/10.1007/978-3-030-44223-1_1