Constant-time decoding of Gabidulin codes and their generalizations with application to RQC

Title: Constant-time decoding of Gabidulin codes and their generalizations with application to RQC

Authors: Nicolas Aragon, Chloé Baïsse, Anthony Fraga, Philippe Gaborit, and Ilaria Zappatore (XLIM, CNRS UMR 7252, Université de Limoges)

1. Problem Statement

Gabidulin codes are the rank-metric analog of Reed-Solomon codes and serve as the foundation for several efficient rank-based cryptosystems, including the RQC (Rank Quasi-Cyclic) and Loidreau cryptosystems. Despite their cryptographic utility, a critical gap existed in their practical deployment: there was no constant-time implementation of Gabidulin code decoding.

In the context of post-quantum cryptography, particularly following the NIST standardization process, constant-time execution is a mandatory requirement to prevent timing side-channel attacks. Previous implementations of RQC were "almost" constant-time; specifically, the decoding of Gabidulin codes relied on variable-time operations, such as the Euclidean division step in Loidreau's algorithm. Furthermore, recent improvements to RQC utilize Augmented Gabidulin (AG) codes (Gabidulin codes with added zero columns) and blockwise errors to achieve smaller parameter sizes. However, no constant-time decoding algorithm existed for these specific AG codes, hindering the secure real-world development of these cryptosystems.

2. Methodology

The authors propose a comprehensive solution involving algorithmic reduction and low-level implementation optimization to achieve constant-time decoding for AG codes.

Algorithmic Reduction:
The core theoretical contribution is the reduction of the AG code decoding problem to a standard Gabidulin decoding problem.

• Support Erasure Recovery: AG codes are constructed by appending zero columns to standard Gabidulin codes. The authors exploit the structure of the received vector, where the last $n-n'$ components correspond to the error on the zero-padded positions. By recovering the "support erasure" (the subspace spanned by these error components), they can transform the AG decoding problem into a standard Gabidulin decoding problem with a shorter length ($n'$), increased dimension ($k+\varepsilon$), and reduced error rank ($t-\varepsilon$).
• Complexity Reduction: This reduction allows the use of Loidreau's algorithm for the reconstruction step. While previous approaches for AG codes relied on solving large linear systems (exponential or high polynomial complexity), this method achieves quadratic complexity ($O((n-n')^2)$).

Constant-Time Implementation:
To ensure the implementation is resistant to timing attacks, the authors modified the RBC (Rank-Based Cryptography) library, focusing on $q$-polynomial arithmetic:

• Fixed Iteration Bounds: Operations that previously depended on the actual degree of the $q$-polynomials (which is secret) were modified to depend on a fixed upper bound ($max\_degree$).
• Constant-Time Left Division: A significant portion of the work involved creating a constant-time version of the left Euclidean division of $q$-polynomials. The standard algorithm's iteration count varies based on the degree of the remainder. The authors implemented a loop that always executes a fixed number of steps ($max\_A + 1$), performing "dummy" operations when no real update is required to mask the actual degree.
• Optimizations: Several optimizations were introduced to maintain efficiency while ensuring constant-time execution, including:
  • Combined computation of $q$-degree and leading coefficient.
  • Constant-time inverse of the iterated Frobenius automorphism.
  • Dedicated functions for multiplying a $q$-polynomial by a monomial.
  • Direct coefficient updates for the quotient to avoid unnecessary assignments.

3. Key Contributions

1. First Constant-Time AG Decoding: The paper presents the first constant-time decoding algorithm for Augmented Gabidulin codes, a critical component of modern RQC variations.
2. Quadratic Complexity Proof: The authors prove that AG code decoding can be achieved with quadratic complexity by reducing it to a standard Gabidulin reconstruction problem solvable via Loidreau's algorithm, avoiding the higher complexity of linear algebra approaches.
3. Constant-Time $q$-Polynomial Arithmetic: The paper provides a complete description and implementation of constant-time operations for $q$-polynomials, specifically the left division, which is a bottleneck in rank-metric decoding.
4. Integration and Benchmarking: The algorithms are integrated into the RQC-Block-MS-AG scheme. The implementation is validated against timing attacks and compared against other post-quantum candidates.

4. Results

The authors evaluated their implementation on an Intel Core i7-13700 CPU.

• Performance vs. Original RQC: The new constant-time implementation of RQC-Block-MS-AG outperforms the original RQC implementation (from the NIST proposal) in all operations (KeyGen, Encapsulation, Decapsulation).
• Performance vs. HQC: When compared to HQC (a Hamming-metric based KEM that was selected by NIST), the RQC-Block-MS-AG implementation is approximately 4 to 5 times slower in terms of CPU cycles.
• Size Trade-off: Despite the performance gap, the RQC-Block-MS-AG scheme achieves public key and ciphertext sizes roughly four times smaller than HQC.
• Comparison with Extended Gabidulin (EG) Codes: The authors compared their AG decoding approach with decoding Extended Gabidulin (EG) codes. Results show that AG decoding is significantly faster (requiring ~3 times fewer multiplications and Frobenius operations and ~2 times fewer CPU cycles) than EG decoding for equivalent parameters, confirming that the specific structure of AG codes is more efficient for decryption.
• Constant-Time Verification:
  • Timing Analysis: The average decoding time varies by less than 0.2% across different error weights (0 to 36), eliminating the correlation between error weight and execution time found in previous algorithms.
  • Valgrind Analysis: Using Valgrind's memcheck tool with data poisoning, the authors verified that no secret-dependent branches or memory accesses remain in the implementation.

5. Significance and Claims

The paper claims to solve a critical security bottleneck in rank-metric cryptography. By providing the first constant-time decoding for AG codes, the authors enable the secure, real-world deployment of the RQC cryptosystem and its variations.

The significance of the work lies in the trade-off it offers: while the implementation is slower than the leading Hamming-metric candidate (HQC), it provides a fourfold reduction in key and ciphertext sizes. The authors argue this is an "appealing trade-off" for environments where bandwidth or storage is constrained.

Furthermore, the paper highlights that the techniques developed for AG codes (specifically the constant-time left division and the reduction strategy) are directly applicable to optimizing standard Gabidulin code decoding, as AG decoding generalizes the Gabidulin case. The authors suggest that future work could explore syndrome decoding for high-dimensional Gabidulin codes to further improve performance while maintaining compact parameters.