Constant-time decoding of Gabidulin codes and their generalizations with application to RQC
Abstract
Gabidulin codes are a rank metric analog of Reed-Solomon codes. They are of great importance in rank-metric cryptography, as they are employed in highly efficient rank-based schemes, such as RQC and the Loidreau cryptosystem. However, until now, there has been no constant-time implementation of these codes, even though such an implementation is crucial for real-life development of cryptosystems. In this paper, we propose the first constant-time decoding algorithm of augmented Gabidulin (AG) codes, a simple variation of Gabidulin codes, in which columns of zeros are added to the end of a Gabidulin code. AG codes are used in the most efficient variants of the RQC cryptosystem. We prove that AG codes decoding can be achieved with quadratic complexity by reducing the decoding of an AG code to the decoding of a shorter standard Gabidulin code. In addition to the description of the complete AG codes decoding procedure, we present a constant-time algorithm for the left division of q-polynomials that can be used in every constant-time implementation of Gabidulin code variants. These algorithms are integrated into the RQC-Block-MS-AG scheme, and we evaluate the performance of our implementation through benchmarks. Our results show that our constant-time implementation outperforms the original RQC, though it remains approximately four to five times slower than HQC. However, it achieves ciphertext and key sizes about four times smaller, highlighting an appealing trade-off between performance and compactness.
Related
- Maximum-Likelihood Decoding of Gabidulin Codes Is NP-Hard Even in Dimension One
- Breaking ACDGV MinRank Gabidulin encryption schemes over matrix codes
- Proximity Gaps for Gabidulin Codes and Applications
- Algorithmic List Decoding of Reed-Solomon Codes up to Capacity
- Reed-Solomon Codes at Capacity: Algorithmic List-Decoding and Proximity Gaps
BibTeX
@misc{aragon2026constanttime,
title = {{Constant-time decoding of Gabidulin codes and their generalizations with application to RQC}},
author = {Nicolas Aragon and Chloé Baïsse and Anthony Fraga and Philippe Gaborit and Ilaria Zappatore},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2607.20305},
eprint = {2607.20305},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2607.20305},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Constant-time decoding of Gabidulin codes and their generalizations with application to RQC
AU - Nicolas Aragon
AU - Chloé Baïsse
AU - Anthony Fraga
AU - Philippe Gaborit
AU - Ilaria Zappatore
PY - 2026
DA - 2026/10/04
PB - arXiv
DO - 10.48550/arxiv.2607.20305
UR - https://arxiv.org/abs/2607.20305
AB - Gabidulin codes are a rank metric analog of Reed-Solomon codes. They are of great importance in rank-metric cryptography, as they are employed in highly efficient rank-based schemes, such as RQC and the Loidreau cryptosystem. However, until now, there has been no constant-time implementation of these codes, even though such an implementation is crucial for real-life development of cryptosystems. In this paper, we propose the first constant-time decoding algorithm of augmented Gabidulin (AG) codes, a simple variation of Gabidulin codes, in which columns of zeros are added to the end of a Gabidulin code. AG codes are used in the most efficient variants of the RQC cryptosystem. We prove that AG codes decoding can be achieved with quadratic complexity by reducing the decoding of an AG code to the decoding of a shorter standard Gabidulin code. In addition to the description of the complete AG codes decoding procedure, we present a constant-time algorithm for the left division of q-polynomials that can be used in every constant-time implementation of Gabidulin code variants. These algorithms are integrated into the RQC-Block-MS-AG scheme, and we evaluate the performance of our implementation through benchmarks. Our results show that our constant-time implementation outperforms the original RQC, though it remains approximately four to five times slower than HQC. However, it achieves ciphertext and key sizes about four times smaller, highlighting an appealing trade-off between performance and compactness.
ER -