Search papers, labs, and topics across Lattice.
This paper introduces the first constant-time decoding algorithm for Augmented Gabidulin (AG) codes, a variant of Gabidulin codes crucial for efficient rank-based cryptosystems like RQC. The authors demonstrate that AG code decoding can be performed with quadratic complexity while also providing a constant-time algorithm for left division of $q$-polynomials. Their implementation achieves smaller ciphertexts and key sizes compared to existing methods, offering a compelling trade-off between performance and compactness despite being slower than HQC.
Constant-time decoding of Augmented Gabidulin codes could revolutionize the efficiency and security of rank-based cryptosystems like RQC.
Gabidulin codes are a rank metric analog of Reed-Solomon codes. Although these codes are used in different very efficient rank-based cryptosystems like the RQC cryptosystem or the Loidreau cryptosystem, there was no constant-time implementation of Gabidulin codes, when having a constant-time 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 on Gabidulin codes where one adds zero columns to Gabidulin codes, and which contains the case of Gabidulin codes. These AG codes are used in practice in the most efficient variations of the RQC cryptosystem. We prove that AG code decoding can be achieved with quadratic complexity. We further present a constant-time algorithm for the left division of $q$-polynomials along with a complete description of the AG code decoding procedure. 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 implementation outperforms the original RQC, though it remains approximately four times slower than HQC. However, it achieves ciphertexts and key sizes about four times smaller, highlighting an appealing trade-off between performance and compactness.
