arXiv CSopen access

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

Constant-time decoding of Gabidulin codes and their generalizations with application to RQC Nicolas Aragon, Chloé Baïsse, Anthony Fraga, Philippe Gaborit, and Ilaria Zappatore

arXiv:2607.20305v1 [cs.CR] 22 Jul 2026

XLIM, CNRS UMR 7252, Université de Limoges 123, avenue Albert Thomas 87060 Limoges Cedex, (France) {nicolas.aragon, chloe.baisse, anthony.fraga, philippe.gaborit, ilaria.zappatore}@unilim.fr Abstract. 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-BlockMS-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.

1

Introduction

Code-based cryptography was first introduced by McEliece [16] in 1978. For many years, code-based cryptography was not considered mainstream since number theory-based cryptography permitted very efficient cryptosystems. Things changed with the development of the quantum threat related to Shor’s algorithm [21] in 1994. With the emergence of quantum computers in the 2010s, the NIST, many years later, organized a post-quantum competition in 2017 in order to propose quantum-resistant cryptographic standards for the future. After 8 years of competition, two encryption schemes were chosen: first, KYBER [19], based on lattices, and HQC in 2025 [17], based on coding theory and Hamming

distance, introducing a new era for cryptographic paradigms. Most well-known code-based systems like BIKE, HQC, or the McEliece cryptosystem are based on coding problems for the Hamming distance. However, it is also possible to use another metric: the rank metric. This metric, introduced in 1985 by Gabidulin [12], is very different from the Hamming distance. In the 2000s, the rank metric gained significant attention from the coding community due to its relevance to network coding, but this metric can also be used for cryptography. Indeed, it is possible to construct rank-analogues of Reed-Solomon codes: the Gabidulin codes. These codes were used in early cryptosystems, like the GPT cryptosystem [11], which consists of an instance of the McEliece cryptosystem using Gabidulin codes. Because of the hardness of decoding random codes in rank metric, sizes of parameters hold the promise of being far smaller than parameters obtained in Hamming metric. Somehow, problems in rank metric are harder than problems in Hamming metric in the same spirit that the discrete logarithm problem is harder for elliptic curves than for Z/pZ. At first, due to the difficulty of masking the very structured Gabidulin codes, many systems in the spirit of the original McEliece in rank metric were broken and repaired and broken again, so that rank-based cryptography, although holding clear potential, did not seem secure enough. Things began to change in 2013 with the introduction of LRPC codes and the LRPC cryptosystem [13] which, in contrast to previous systems, was not based on a masking of Gabidulin codes. Then later, in 2016 in the same paper as HQC [1], the RQC cryptosystem was proposed. The RQC cryptosystem is an analog of the HQC cryptosystem in rank metric and benefits from the same very nice feature that no masking is necessary; indeed, one has to decode eventually, but the decoding code is public and no masking is needed. For the first time, it was possible to use Gabidulin codes in cryptography without fearing that the masking would be broken. Later in 2017, a special masking for Gabidulin codes, mixing them with LRPC-like codes, was also proposed in [15] and seems to be resistant, and was moreover improved in [4]. Rank metric-based systems like RQC and LRPC were submitted to the NIST competition and reached the second round, but eventually did not make it to the third round since generic algebraic attacks were improved for rank metric in [7], attacking parameters proposed to the NIST for these schemes. However, since that time in 2020, many improvements were obtained for the RQC cryptosystem: first, algebraic attacks in rank metric have become better understood and stabilized, which was not the case at the time of the NIST competition; moreover, some improvements were obtained for the RQC cryptosystem in particular: the use of augmented Gabidulin codes (Gabidulin codes to which one adds columns of zeros) and the use of multiple syndromes [10] and also more recently the use of blockwise errors [23,3]. Eventually, all these improvements led to parameters for RQC very close to parameters obtained for KYBER and hence far smaller than parameters for BIKE or HQC. Constant-time implementation in rank metric. At the beginning of the NIST standardization process, things were different between the diverse post-quantum 2

communities. For instance, since lattice-based cryptography had been stabilized for some years, researchers had begun to consider constant-time implementations, which was a requirement for the NIST competition, and more than anything, a requirement for the security of practical development of cryptosystems in real life. For the coding community, cryptosystems were less stabilized and, for instance, the HQC team only proposed a constant-time implementation for the third round of competition. Regarding rank metric, implementations in ’almost’ constant-time were proposed for the RQC cryptosystem, almost in the sense that the decoding of Gabidulin codes was not fully constant-time (the Euclidean division step in [9] is still implemented in variable time for example), but overall, since RQC did not reach the third round, all the work done during the competition was gathered in the RBC public library [5] and nothing more was done on constant-time implementation of Gabidulin codes. When these codes are used in the RQC cryptosystem (and its recent variations) as well as in the recent Loidreau’s cryptosystem and its variations, there is currently no constant-time implementation of Gabidulin codes even if a constanttime implementation for rank-based cryptography is essential. Our contributions. In this paper, we present a reduction of the augmented Gabidulin decoding problem to the decoding problem of standard Gabidulin codes. This allows us to use the decoding algorithm of Loidreau [14] and thus reach quadratic decoding complexity, instead of the exponential from linear algebra. We also provide a constant-time implementation of the decoding of AG codes. For this purpose, we modify the core functions of the RBC library for the arithmetic of q-polynomials to make them constant-time. In particular, we propose a constant-time algorithm for the left division of q-polynomials, a required step in Loidreau’s decoding algorithm. While our work focuses on AG codes, these modifications in the RBC library can be useful for other variants of Gabidulin codes. We integrate our decoding algorithm into the RQC-Block-MSAG scheme [3] and show promising performance: our implementation is faster than the original RQC, and although about four times slower than HQC, it achieves ciphertext and key sizes roughly four times smaller. Organization of this paper. Section 2 presents the background on rank metric, Gabidulin codes and decoding algorithms, and Gabidulin code generalizations. Section 3 describes the reduction of the augmented Gabidulin code decoding problem to the reconstruction problem. Section 4 gives details on the implementation of the decoding algorithm and the left Euclidean division in a constanttime context. We describe the structure of the RBC library and our modifications and optimizations aimed at maintaining constant-time. Section 5 presents the complexity of the augmented Gabidulin code decoding implementation. Section 6 shows different results of our experiments, including constant-time analysis, comparison over Gabidulin generalizations, and RQC performance. 3

2

Preliminaries

In this section we introduce the basic notions we will be using throughout this paper, starting with the notations. Then, we introduce the Gabidulin codes and their decoding. We also briefly present one of their extension, the augmented Gabidulin codes. Finally, we give an overview of the last version of the Rank Quasi-Cyclic (RQC) scheme using augmented Gabidulin codes. 2.1

Notation

Let q be a prime power, Fq be a finite field of order q, and Fqm the extension field of Fq of degree m. In this paper, we represent vectors by lowercase bold letters x, y and matrices by uppercase bold letters G, H. Polynomials and qpolynomials (see Section 2.3) are denoted by capital letters A(X), B(X), and sometimes we omit the indeterminate for simplicity. 2.2

Background on rank-metric codes

Given x = (x1 , . . . , xn ) ∈ Fnqm , we define its support as, def

Supp(x) = ⟨x1 , . . . , xn ⟩Fq , where ⟨x1 , . . . , xn ⟩Fq denotes the Fq -linear span of the xi ’s, viewed as vectors in Fm q . The rank weight of x is defined as, def

∥x∥ = dim(Supp(x)) and the rank distance of two vectors x, y ∈ Fnqm is, def

d(x, y) = ∥x − y∥.

Remark 1. If we fix an Fq -basis B = {β1 , . . . , βm } of Fqm , any vector x = , by representing (x1 , . . . , xn ) ∈ Fnqm can be written as a matrix M B (x) ∈ Fm×n q any element xi ∈ Fqm as a column vector whose entries are its coefficients in the basis B. Under this point of view, the rank of x is the rank of M B (x). We can now introduce the following, Definition 1 (Fqm -linear code) An Fqm -linear code C of length n and dimension k is an Fqm -vector subspace of Fnqm whose minimum distance is defined as, def dmin (C) = min {∥x∥}. x∈C\{0}

It is referred to as a [n, k]qm code. 4

Such codes can be represented by: – a full-rank generator matrix G ∈ Fk×n q m , i.e. a matrix whose rows form a basis of C, (n−k)×n

– a full-rank parity check matrix H ∈ Fqm , i.e. a generator matrix of the dual code C ⊥ of C, which is the orthogonal of C with respect to the standard inner product in Fqm . We now recall a formal statement of the decoding problem of rank metric codes, that will be useful later. Definition 2 (Decoding(y, C, t)) Let y ∈ Fnqm , C an Fqm -linear code and t a positive integer. Find, if it exists, a codeword c ∈ C and an error vector e ∈ Fnqm such that, y = c + e and ∥e∥ ≤ t. 2.3

The ring of q-polynomials and Gabidulin codes

In rank metric cryptography, a central notion is that of q-polynomials, a special class of polynomials introduced by Ore in [20]. They are defined as Fqm -linear 2 i combinations of the monomials X, X q , X q , . . . , X q , . . . respectively denoted by X, X [1] , X [2] , . . . , X [i] , . . .. In fact, these monomials are the successive iterations of the Frobenius automorphism θ : Fqm → Fqm x 7→ xq A nonzero q-polynomial P is defined as, P (X) =

dP X

pi X [i]

i=0

with pi ∈ Fqm , pdP ̸= 0 and dP ̸= 0. The integer dP is called q-degree of P and it is denoted degq (P ). We equip the space of q-polynomials with a non-commutative ring structure, denoted Fqm ⟨X q ⟩, where addition is defined termwise as in classical polynomial rings, and the multiplication is defined by composition and extended by Fqm linearity as follows: ∀i, j ∈ N, ∀a ∈ Fqm ,

X [i] X [j] = X [i+j] ,

i

X [i] a = aq X [i] .

The ring Fqm ⟨X q ⟩ is a left and right Euclidean domain. In this paper, we will focus on the left division, which will be used later in the decoding of Gabidulin codes. 5

Given A, B ∈ Fqm ⟨X q ⟩ with B ̸= 0, we aim to find unique Q, R ∈ Fqm ⟨X q ⟩ such that: A = BQ + R with degq (R) < degq (B). We can now define Gabidulin codes, a family of Fqm -linear codes introduced in [12]. These are the rank-metric analogue of Reed-Solomon codes. Definition 3 (Gabidulin codes) Given two positive integers k, n, with k < n ≤ m and g = (g1 , . . . , gn ) ∈ Fnqm such that ∥g∥ = n, the Gabidulin code of length n and dimension k is defined as, def  Gg (n, k, m) = F (g) = (F (g1 ), . . . , F (gn )) | F (X) ∈ Fqm ⟨X q ⟩, degq (F ) < k ,

The vector g is called evaluation vector. Gabidulin codes are a family of Maximum Rank Distance (MRD) codes, i.e. they achieve the largest possible minimum rank distance for given parameters, namely dmin (Gg (n, k, m)) = n − k + 1. They also admit efficient decoding algorithms correcting up to half of the minimum distance (see Section 2.4). 2.4

On the Decoding of Gabidulin codes

Several decoding algorithms have been proposed for Gabidulin codes (for instance [24,14,6]). Similarly to Reed-Solomon codes in the Hamming metric, all these algorithms reduce the decoding problem to a reconstruction problem, or equivalently, to the resolution of a key equation. Definition 4 (Reconstruction(y, g, n, k, t)) Let y = (y1 , . . . , yn ) ∈ Fnqm , g = (g1 , . . . , gn ) ∈ Fnqm and k, t be two positive integers. Find a pair of qpolynomials (V, N ) such that,   V (yi ) = N (gi ), 1 ≤ i ≤ n degq (V ) ≤ t   degq (N ) ≤ k + t − 1 In [14], Loidreau showed the following fundamental result, Theorem 1. If (V, N ) is a solution of Reconstruction(y, g, k, t) and t ≤ ⌊ n−k 2 ⌋, then the codeword c = F (g) and the error vector e = y − c form a solution of Decoding(y, Gg , t), where F is the quotient of the left euclidean division of N by V . def

Therefore, if the number of errors is at most τ0 = ⌊ n−k 2 ⌋, decoding a Gabidulin code reduces to solving the Reconstruction problem with t = τ0 . Once the pair (V, N ) is found, the transmitted codeword can be recovered via left Euclidean division. 6

This result holds because any pair (V, N ) of q-polynomials satisfying the Reconstruction(y, g, n, k, t) degree constraints captures the interpolation relations between the received symbols and the evaluation sequence. When the rank of the error is t ≤ ⌊ n−k 2 ⌋, then the solution (V, N ) of the reconstruction is unique up to a scalar factor. In this case, V is the annihilator q-polynomial of the error support, and N = V ◦ F where F is the q-polynomial defining the transmitted codeword c. Hence, performing the left Euclidean division of N by V retrieves F , and evaluating F at g reconstructs the original codeword. Finally, decoding Gabidulin codes involves applying the steps described in Algorithm 1. Algorithm 1 Decoding algorithm for Gabidulin codes n−k Require: Gg (n, k, m), y ∈ Fn q m , the received word with error of rank t ≤ ⌊ 2 ⌋ Ensure: (c, e) a solution of Decoding(y, Gg (n, k, m), t) 1: (V, N ) ← SolveReconstruction(y, g, n, k, ⌊ n−k ⌋) 2 2: F ← LeftEuclideanDivision(N ,V ) 3: return (F (g1 ), . . . , F (gn )), y − (F (g1 ), . . . , F (gn ))

A natural approach to solve the Reconstruction problem is to set up a linear system where the unknowns are the coefficients of the q-polynomials (V, N ). This can be solved using linear algebra in time O(nω ), where ω is the exponent of matrix multiplication. In contrast, in [14], Loidreau proposed a more efficient algorithm for solving the Reconstruction problem, later improved by Augot et al. [6], leading to a quadratic complexity. In the next section, we summarize this algorithm, as it will play a central role in the remainder of this paper. Loidreau’s algorithm for the Reconstruction problem. The decoding algorithm proposed by Loidreau [14] and later refined in [6] finds a solution to the Reconstruction problem in quadratic time. The idea is to iteratively construct two pairs of q-polynomials (N0 , V0 ) and (N1 , V1 ), such that for any i ≤ n,  N0 (gj ) − V0 (yj ) = 0 ∀j ≤ i, (1) N1 (gj ) − V1 (yj ) = 0 In other terms, after the i-th iteration, both pairs satisfy the interpolator conditions on the first i evaluation points. At the end of the process, step n, at least one of the two pairs also satisfies the degree constraints imposed by the Reconstruction problem. The algorithm starts by defining the following initial pairs : (N0 (X), V0 (X)) = (A⟨g1 ,...,gk ⟩ (X), 0) (N1 (X), V1 (X)) = (Ig,y (X), X) thus guaranteeing that (1) is satisfied. Note that, – A⟨g1 ,...,gk ⟩ (X) is the annihilator q-polynomial of the Fq - subspace ⟨g1 , . . . , gk ⟩, i.e. , A⟨g1 ,...,gk ⟩ (v) = 0 for any v in this subspace; 7

– Ig,y (X) is the interpolation q-polynomial satisfying I(gi ) = yi for 1 ≤ i ≤ k. This initialization guarantees that property (1) holds for the first k positions. At each step, the algorithm checks how far the current polynomials are from fulfilling the interpolation property. This is done by computing the discrepancy vectors : u0 = (u0,1 , . . . , u0,n ) = N0 (g) − V0 (y) (2) u1 = (u1,1 , . . . , u1,n ) = N1 (g) − V1 (y) At the end of step i, the first i components of the discrepancy vectors must be zero. From step k + 1 to step n, both pairs of q-polynomials (V0 , V1 ) and (N0 , N1 ) are updated using the ith -coordinate of the discrepancy vectors u0 and u1 , so that property (1) continues to hold at each iteration. For convenience, we now denote by (P0 , P1 ) either the pair (V0 , V1 ) or (N0 , N1 ). The same update rule applies to both pairs. In the original Loidreau algorithm [14,6], at each iteration i, three possible cases are distinguished : 1. u1,i ̸= 0: interpolation step. In this case, the pair (N1 , V1 ) detects a nonzero discrepancy component: the current point (gi , yi ) is not yet correctly interpolated. To fix this, both pairs of polynomials are updated so that the new ones also satisfy the constraint at index i : uq1,i P1 (X) P1′ (X) = P1q (X) − u1,i u P0′ (X) = P0 (X) − u0,i P1 (X) 1,i This is the interpolation step since in the end u′0,i = u′1,i = 0. 2. u1,i = 0 and u0,i = 0 : no discrepancy case. In this case, both pairs already interpolate the current point (gi , yi ) correctly. In this case, the algorithm simply performs a dummy interpolation, applying a Frobenius to maintain the structure of the q-polynomials. P1′ (X) = P1q (X) P0′ (X) = P0 (X) 3. u1,i = 0 and u0,i ̸= 0: discrepancy exchange. In this case, the pair (N1 , V1 ) cannot be used to eliminate the discrepancy at index i. To overcome this, the algorithm searches for the smallest position j > i where u1,j ̸= 0 or u0,j = 0. If such a position exists, the ith and the j th -coordinates of both discrepancy vectors are swapped, and the procedure continues as in case 1 or 2. Otherwise the algorithm stops. After each iteration, the pairs (V0 , N0 ) and (V1 , N1 ) are swapped, and the discrepancy vectors are recomputed. At the end of the algorithm, one of the two pairs satisfies both the interpolation property (1) and the degree constraints, thus providing a valid solution to the Reconstruction problem. The proof of the correctness of the algorithm can be found in [14,6]. 8

In [9], a simplified version of the original Loidreau’s algorithm is proposed. This modification removes the dummy interpolation (case 2) while keeping the swap step (case 3). In this version, the algorithm only checks whether u1,i is zero or non-zero: if u1,i ̸= 0, an interpolation step is performed; if u1,i = 0 and u0,i ̸= 0, a swap is executed as in case 3; and if both u1,i and u0,i are zero, no action is required since the interpolation property already holds. As a result, all effective updates are handled immediately, and the positions corresponding to the former dummy case remain automatically satisfied. Bettaieb et al. prove in [9] that there exists a correlation between the weight of the error to be corrected and the number of interpolation steps. They also show that this correlation can be exploited to build two theoretical timing attacks against RQC. As a countermeasure, they provide a constant-time version of the Loidreau’s algorithm. 2.5

Augmented Gabidulin Codes

Gabidulin codes have given rise to several generalizations tailored to meet specific cryptographic requirements. In this paper, we focus on one of them, the augmented Gabidulin (AG) codes [10], which, as we will see later, play a central role in the RQC cryptosystem. Definition 5 (Augmented Gabidulin codes) Let k ≤ n′ < m < n be posi′ tive integers, g = (g1 , . . . , gn′ ) ∈ Fnqm such that ∥g∥ = n′ , and g ∈ Fnqm the vector g completed by n − n′ zeros on the right. The AG code Gg+ (n, n′ , k, m) is the [n, k]qm code defined as  Gg+ (n, n′ , k, m) = F (g) | F (X) ∈ Fqm ⟨X q ⟩, degq (F ) < k . Clearly, the minimum distance of these codes is n′ − k + 1, as they are obtained by augmenting a Gabidulin code Gg (n′ , k, m) with zero coordinates. Contrary to the Hamming metric case, appending zeros in this rank metric setting increases thenumber of correctable errors : in particular, it allows unique decoding up to n−k+ε , where ε denotes the dimension of the erasure support, i.e. the 2 dimension of the support corresponding to the known part of the error [10, Proposition 1]. In section 3 we discuss about the decoding of such codes. 2.6

The RQC cryptosystem using augmented Gabidulin codes

In this part, we present the last improved version of the RQC cryptosystem [3]. Compared to the original RQC scheme, three novel approaches are employed. As proposed in [10], AG codes are used instead of Gabidulin codes, resulting in a smaller parameter m. Furthermore, again following the proposal in [10], the last RQC variant applies the multiple syndromes (MS) strategy [2]. Finally, the scheme uses blockwise structured errors, a principle introduced in [23]. 9

Definition 6 (Blockwise ℓ-error) Let n = (n1 , . . . , nℓ ), r = (r1 , . . . , rℓ ) and Pℓ n = i=1 ni . An ℓ-error e with parameters n and r is an error e = (e1 , . . . , eℓ ) ∈ i with ∥ei ∥ = ri and for i ̸= j, Supp(ei )∩ Fnqm such that for any 1 ≤ i ≤ ℓ, ei ∈ Fnqm Supp(ej ) = {0}. The RQC scheme that embedded the above-mentioned improvements is called to RQC-Block-MS-AG [3]. To describe the cryptosystem in Figure 1, we use the following notations: – Srn (Fqm ), the set of blockwise errors of parameters n and r. – SrN ×n (Fqm ), the set of N × n block matrices of the form M = (M 1 | . . . |M ℓ ) where for all 1 ≤ i ≤ ℓ, the M i are N ×ni matrices such that dim(Supp(M i )) = ri . 2 ×n1 2 is given and a matrix M ∈ Fnqm – The product between a vector v ∈ Fnqm T T by v · M = ((v · m1 ) , . . . , (v · mn1 ) ), where for 1 ≤ i ≤ n1 , mi is the ith column of M .

– P is an irreducible polynomial of degree n2 . We also define the procedure Fold :

2 ×n1 2 n1 ) → Fnqm (Fnqm T (v 1 , . . . , v n1 ) 7→ (v 1 , . . . , v Tn1 )

whose inverse is denoted by Unfold.

KeyGen(1λ ) $

$

$

(n ,n )

m 2 1. g ← − Sm (Fqm ), h ← − Fn − S(rx2,ry2) (Fqm ) q m , (x, y) ← 2. s ← x + h · y mod P 3. return pk = (g, h, s), sk = (x, y)

Encrypt(pk, m) 1 n2 1. Compute G ∈ Fk×n a generator matrix of Gg+ (n1 n2 , m, k, m) where g = qm (g, 0n1 n2 −m )

$

n ×(n ,n ,n )

2. (R1 , R2 , E) ← − S(r21 ,r2 ,r1e ) 1 1 (Fqm ) 3. U ← R1 + h · R2 4. V ← Fold(mG) + s · R2 + E 5. return C = (U , V ) Decrypt(sk, C) 1. return Decode(Unfold(V − y · U ))

Fig. 1: The RQC-Block-MS-AG cryptosystem 10

Parameters for 128-bit security of the RQC-Block-MS-AG cryptosystem [3]are given Table 1.

q m n2 k ε rx ry r1 r2 re n1 DFR pk + ct (in kB) 2 43 52 3 32 4 4 4 4 4 2 -145 1.43

Table 1: Parameters for RQC-Block-MS-AG-128

3

Decoding Augmented Gabidulin codes

In this section, we discuss further the decoding of augmented Gabidulin codes. We explicitly reduce this problem to a reconstruction problem (see Definition 4) and show how Loidreau’s algorithm [14] can be used to solve it efficiently. The main idea behind the decoding algorithm is to exploit the structure of AG codes : since the last n − n′ positions of each codeword are zero by construction, the corresponding components of the received vector provide partial information about the error. By recovering this information, we can transform the Decoding problem of an AG code into the decoding of a standard Gabidulin code with shorter length, increased dimension, and reduced error rank. Let Gg+ (n, n′ , k, m) be an AG code as in Definition 5. def

Recall that g = (g1 , . . . , gn′ , 0, . . . , 0), so denote by g 1 = (g1 , . . . , gn′ ) the sequence of nonzero evaluation points. Let y = (y 1 , 0, . . . , 0) + (0, . . . , 0, y 2 ) ∈ Fnqm , where y 1 = (y1 , . . . , yn′ ) and y 2 = (yn′ +1 , . . . , yn ). We consider the Decoding problem Decoding(y, Gg+ (n, n′ , k, m), t) where the error rank satisfies  t≤

n′ − k + ε 2



and ε, denotes the dimension of the support erasure E2 , i.e. the Fq -space generated by the components of y 2 . We observe that 1 ≤ ε ≤ min{n − n′ , n′ − k}. Let (c, e) be a solution of the above Decoding problem, i.e. y = c + e, with c the transmitted codeword and ∥e∥ ≤ t. Denoting by E = Supp(e) the error support, let V ∈ Fqm ⟨X q ⟩ be its annihilator q-polynomial. We have that, V (y) = V (F (g)), where, F ∈ Fqm ⟨X q ⟩, degq (F ) < k is the q-polynomial corresponding to the sent word c. Hence, (V, V ◦ F ) satisfies the interpolation constraints of the problem 11

Reconstruction(y, g, n, k, t), i.e.   V (yi ) = N (gi ), 1 ≤ i ≤ n degq (V ) ≤ t   degq (N ) ≤ k + t − 1 j ′ k Moreover, to be precise, we can also observe that since n −k+ε is the unique 2 decoding radius of the above AG code, any solution of this Reconstruction problem coincides with (V, V ◦ F ). Therefore, without loss of generality, we can restrict our attention to this Reconstruction problem, which fully characterizes the decoding of AG codes. Now, we consider V2 , the annihilator polynomial of the support erasure E2 . Then, since E2 ⊆ E and the ring of q-polynomials is left Euclidean, there exists a unique monic polynomial W ∈ Fqm ⟨X q ⟩ of degq (W ) ≤ t − ε such that V = W ◦ V2 . def

If V2 is known, we can compute y ′1 = V2 (y 1 ) and reformulate the previous Reconstruction equations as,  ′ ′  W (y1,i ) = N (gi ), 1 ≤ i ≤ n (3) degq (W ) ≤ t − ε   degq (N ) ≤ k + t − 1 This defines a restricted Reconstruction problem which can be interpreted as an instance of Reconstruction(y 1 , g, n′ , k + ε, t − ε), since degq (N ) ≤ (k + ε) + (t − ε) − 1. Now, according to Theorem 1, we can conclude the following result. Theorem 2. The Decoding problem Decoding(y, Gg+ (n, n′ , k, m), t) can be reduced to a standard Gabidulin Decoding problem Decoding(y ′ , Gg (n′ , k + ′ ε, m), t − ε), where y ′ ∈ Fnqm and ε denotes the dimension of the support erasure. This means the initial Decoding problem for AG can be reduced to the decoding of a standard Gabidulin code with shorter length n′ , larger dimension k + ε, and reduced error rank t−ε. We can now resume how the algorithm (see Algorithm 2) works. Step 1. Retrieving the support erasure and its annihilator. The first step of the decoding algorithm consists in retrieving ε elements of the error support def E = Supp (e), We consider y 2 , which directly exposes the last n−n′ components of the error. If these n − n′ elements span an Fq -subspace of dimension ε, we can successfully recover the erasure support E2 . However, this condition is not always satisfied, as the components of y 2 do not necessarily contain ε linearly independent elements. The decryption failure rate (DFR) [10] quantifies this 12

event – it represents the probability that a random matrix of size (n − n′ ) × t over Fq , whose rows correspond to the last error components, has rank smaller than ε. It is upper bounded by, 1−

δ ε−1 X Y (q δ − q j )(q n−n′ − q j ) 1 δ(n − n′ ) i=ε j=0 qε − qj

Once E2 is found, we can recover its annihilator polynomial V2 , for instance using the iterative process described in [20] [6]. Step 2. Decoding a shorter Gabidulin code. Given V2 , we can compute V2 (y 1 ) and by Theorem 2, we can just apply the Loidreau’s algorithm to solve the corresponding Reconstruction(y 1 , g, n′ , k + ε, t − ε) problem as in (3) and find (W, N ). Step 3. Recovering the codeword and its associate q-polynomial Since N = W ◦ V2 ◦ F , where F is the q-polynomial corresponding to the codeword, we can compute left Euclidean divisions to recover it. Algorithm 2 Decoding algorithm of the augmented Gabidulin codes n−k+ε Require: Gg+ (n, n′ , k, m), y ∈ Fn ⌋, q m the received word with error of rank t ≤ ⌊ 2 ε the dimension of the support erasure Ensure: (c, e) solution of Decoding(y, Gg+ (n, n′ , k, m), t), or ⊥ if algorithm fails 1: E2 ← Echelonize(y 2 ) ▷ i.e. basis of Supp(y 2 ), supposed to have size ε 2: if dim(E2 ) < ε then 3: return ⊥ ▷ Decoding failure: dimension of support erasure is too low 4: end if 5: V2 (X) ← A⟨E2,1 ,...,E2,ε ⟩ (X) 6: for i = 1 to n′ do 7: yi′ ← V2 (yi ) 8: end for 9: W, N ← SolveReconstruction(y ′ , (g1 , . . . , gn′ ), n′ , k + ε, t − ε) ▷ Step 2. 10: N2 ← LeftEuclideanDivision(N, W ) 11: F ← LeftEuclideanDivision(N2 , V2 ) 12: c ← F (g) 13: return c, y − c

Difference with the AG decoding algorithm of [10]. In [10], the authors introduced a decoding algorithm for AG codes based on solving a linear system over Fqm . Their method solves the reconstruction equations in (3) using linear algebra techniques. However, the Decoding problem is not explicitly formulated as a Reconstruction problem. In this work, we explicitly reduce the Decoding problem to a Reconstruction problem by leveraging the decoding of a standard Gabidulin code. This formulation allows us to directly apply Loidreau’s 13

algorithm to solve it, leading to a more efficient and structured decoding procedure with quadratic time complexity instead to the complexity of linear algebra computations.

4

Implementation details

We implement the RQC-Block-MS-AG scheme (Figure 1) using the RBC library, employing Algorithm 2 for decoding. We target a constant-time implementation. For the SolveReconstruction procedure (see line 9 of Algorithm 2), we rely on the decoding algorithm for Gabidulin codes already available in the RBC library. It is an implementation of Loidreau’s algorithm largely inspired by the constant-time version described in [10]. This implementation, although the number of iterations is fixed, is not fully constant-time, since some of the operations on q-polynomials are still executed in variable time. So, to achieve a complete constant-time implementation of RQC-Block-MS-AG, we need to implement all the required q-polynomial operations in constant-time. This constitute a part of the contributions of this paper. To provide some background on the RBC library in the context of rank metric operations, the field extension considered is F2m , defined as F2 [X]/(P ), where P is a sparse irreducible polynomial of degree m. The elements and the arithmetic operations defined on this field form the core layer of the RBC library. An element x of F2m is represented as a vector (x0 , . . . , xm−1 ) in Fm 2 , in a data structure called rbc_elt. Arithmetic operations on rbc_elt are carried out through polynomial arithmetic modulo P . A vector of elements in F2m is represented by the rbc_vec structure, consisting of a pointer to fixed size array of rbc_elt. Finally, the rbc_qpoly structure, which represents q-polynomials, is composed of three components: max_degree, the upper bound of the q-degree; degree, the current q-degree; and values, an rbc_vec of size max_degree + 1 containing the coefficients of the polynomial. 4.1

Basic arithmetic operations

For many operations on q-polynomials implemented in the RBC library, the number of iterations depends on the q-degree of the input q-polynomials. Consequently, most of our modifications aim to make this number of iterations depend on the upper bound of the q-degree rather than on the q-degree itself. Instead of relying on the max_degree component of a q-polynomial as this upper bound, we choose to make it an explicit input parameter of each function. This approach allows the user to select a custom upper bound that may be smaller than the actual max_degree of the q-polynomial. This feature is, for example, particularly useful in the decoding algorithm for AG codes. Indeed, in the Loidreau’s algorithm, it has been shown that in the interpolation steps i ∈ {k +1, · · · , n}, the q-degrees of the polynomials V0 , N0 , V1 and N1 are upper bounded by values that depend on the the step index i (see 14

Proposition 11 in [14]). For AG codes, the same bounds hold if we replace the parameter k by k + ε, as explained Section 3. This modification to the handling of q-degrees was the only change required to make the following q-polynomial operations constant-time: – addition of q-polynomials, – left multiplication of a q-polynomial by a scalar, – product of two q-polynomials, – evaluation of a q-polynomial, and – the q-exponentiation of a q-polynomial. At the end of each of these functions, the q-degree of the resulting q-polynomial must be updated. To ensure this step is performed in constant-time, we implement a dedicated constant-time function for computing the q-degree of a q-polynomial. In this function, the coefficients of the input q-polynomial are scanned sequentially, starting from the coefficient corresponding to the highest possible q-degree (max_degree). A variable storing the resulting degree is updated at every iteration using masks (Algorithm 3) : when a nonzero coefficient is encountered, the mask preserves the current value of the variable, preventing further changes. Since the loop always iterates over all the coefficients, regardless the actual q-degree, the execution time remains constant. We use the same technique in the function that retrieves the leading coefficient of a q-polynomial. Algorithm 3 constant-time q-degree computation Require: A(X) ∈ Fqm ⟨X q ⟩ of q-degree upper bounded by max Ensure: degq (A) 1: d ← max 2: mask ← 0 3: for i = max to 0 do 4: mask ← mask ∨ (Ai ̸= 0) 5: d ← (1 − mask) · (i − 1) + mask · d 6: end for 7: return d

4.2

The annihilator and interpolator q-polynomials

The decoding of the AG codes involves computing both annihilator and interpolator q-polynomials. In the second step of Algorithm 2, the annihilator q-polynomial V2 – which vanishes on E2 , the subspace spanned by the support erasures – is computed. Moreover, at the beginning of Loidreau’s algorithm, 15

the q-polynomials N0 and N1 are initialized respectively as an annihilator qpolynomial and an interpolator q-polynomial (see Equation (2.4)). To compute V2 , we develop a constant-time version of the RBC library function that computes the annihilator q-polynomial of a given subspace. For the initialization of N0 and N1 , we keep the choice of the RBC Library, which uses a function to compute and return both the annihilator and the interpolator qpolynomials. We adapted this function to a constant-time version as well. Both constant-time variants of these functions follow exactly the same computational steps as their original algorithms, but employ the constant-time arithmetic operations on q-polynomials.

4.3

The left division on q-polynomials

To decode AG codes, q-polynomials Euclidean left divisions are required (see Steps 7 and 8 of Algorithm 2). These divisions are performed by using an adaptation of the Euclidean algorithm to the ring of q-polynomials. PdB Let us consider the left division of a q-polynomial A(X) by B(X) = i=0 bi X [i] , where dB = degq (B). The goal is to find the unique pair (Q, R) of q-polynomials satisfying A(X) = B(X)Q(X) + R(X) with degq (R) < dB . Initially, Q(X) and R(X) are set to 0 and A(X), respectively. Euclidean left division algorithm for q-polynomials. At each iteration i, the Euclidean algorithm cancels the leading coefficient of the current remainder Ri , denoted lc(Ri ), by computing Ri+1 (X) = Ri (X) − B(X) ◦ cX [degq (Ri )−dB ] The term c is chosen so that lc(Ri ) matches the leading coefficient of B(X) × cX [degq (Ri )−dB ] . Since, bdB X [dB ] ◦ cX [degq (Ri )−dB ] = bdB c[dB ] X [degq (Ri )] c satisfies

Thus,

bdB c[dB ] = lc(Ri )

[−dB ] c = (lc(Ri )b−1 dB )

where the notation x[−t] denotes the inverse of the Frobenius automorphism −1 θ−1 : x 7→ xq , iterated t times. The monomial cX [degq (Ri )−dB ] is also added to the current quotient Q(X). The algorithm terminates when it finds a remainder Ri satisfying degq (Ri ) < dB . The total number of iterations depends on the gap between the q-degrees of A and B, as well as on the possible degree drops of Ri between two successive iterations. 16

Constant-time left division algorithm for q-polynomials We propose a constant-time version of the Euclidean algorithm for the left division of qpolynomials. In the standard Euclidean algorithm, the number of iterations is upper bounded by degq (A) + 1. This bound is reached in the worst case, when degq (B) = 0 and the q-degree of the remainder R decreases by exactly one at each iteration. Thus, our constant-time algorithm has to execute at least degq (A) + 1 iterations. Since the q-degree of A must remain secret, we design our algorithm to always perform maxA + 1 iterations, where maxA denotes the value of the max_degree parameter chosen when initializing A. The core idea is to update Q and R as in the classical Euclidean algorithm explained above, while performing dummy operations whenever no real update should occur. Let i be a loop variable, decreasing by 1 from maxA down to 0. In the classical Euclidean algorithm, the monomial used to update Q and R is cX [degq (R)−dB ] . In our constant-time version, it is replaced with cX [i] and dummy operations are performed whenever i ̸= degq (R) − dB . This situation occurs in two cases: – Before the first valid update. In the classical algorithm, the first meaningful update occurs when i = degq (A) − dB . Since our constant-time loop starts from i = maxA , all iterations such that maxA ≥ i > degq (A) − dB do not correspond to real updates and must therefore be replaced by dummy operations. Valid updates start only when i ≤ degq (A) − dB . – When the remainder’s degree drops by more than one. During the execution of the algorithm, the q-degree of the remainder R may decrease by more than one, between two consecutive iterations. When such “degree jumps” occur, some iterations of the loop no longer correspond to a valid update, because the remainder has already lost the term that would normally be canceled at that position. In these cases, the algorithm must perform dummy operations for the number of iterations to remain constant. Formally, this happens whenever i > degq (R) − dB . Moreover, when dR < dB at the beginning of a loop iteration, the target qpolynomials Q and R have already been completely determined, and therefore must not be modified. So, degq (R) − dB < 0 and since i ≥ 0, this also implies that dR − dB − i < 0. Note that this situation is encountered when we check for degree jumps of R. Finally, legitimate operations on Q and R occur only when both degq (A) − dB − i ≥ 0 and degq (R) − dB − i ≥ 0 are simultaneously satisfied. This can be easily handled by using a flag variable that determines whether the current iteration should execute a valid or a dummy operation. In order to maintain a constant number of steps, we have implemented several algorithmic optimizations, described in the following sections. Each of them 17

targets a specific computational bottleneck of the constant-time left division algorithm for q-polynomials. Combined computation of q-degree and leading coefficient. The first optimization consists in computing both the q-degree and the leading coefficient of B and R within a single constant-time function inspired by Algorithm 3. It is straightforward to observe that these two values can be retrieved in a single loop. For the q-polynomial R, which is recomputed at each iteration, this improvement saves up to maxA · maxR iterations, where maxR denotes the upper bound of the q-degree of R. Inverse of the iterated Frobenius. A second optimization concerns the computation of the inverse of the Frobenius iterated a number of times equal to the q-degree of a q-polynomial (see Algorithm 4). This operation is required at each [−dB ] step i to compute c = (lc(Ri )b−1 . Let m = (lc(Ri )b−1 dB ) dB ) and maxB denote the upper bound of the q-degree of B The following equality holds: m[−dB ] = (m[−maxB ] )[maxB −dB ]

(4)

Our implementation exploits this property by first computing m[−maxB ] , followed by (maxB − dB ) Frobenius iterations and dB dummy iterations to keep the number of steps unrelated to dB , resulting in a total of 2maxB Frobenius computations. Algorithm 4 Constant-time inverse of the iterated Frobenius Require: e ∈ Fqm , A(X) ∈ Fqm ⟨X q ⟩ of q-degree upper bounded by max Ensure: e[− degq (P )] 1: f ← e[−max] 2: tmp ← f 3: mask = 0 4: for i = max to 0 do 5: tmp ← tmpq 6: mask ← mask ∨ (ai ̸= 0) 7: f ← (1 − mask) · f + mask · tmp 8: end for 9: return f

Product with a monomial. The third optimization is the implementation of a dedicated function to multiply a q-polynomial with a monomial (see Algorithm 5). This operation, used to compute B(X) ◦ cX [i] at each step i, would otherwise require scanning all coefficients of B(X). However, since a monomial contains only a nonzero coefficient, the product can be simplified as, B(X) ◦ cX [i] =

max XB j=0

18

bj · c[j] X [i+j]

(5)

This formulation avoids unnecessary iterations and makes it possible to perform the multiplication through a single pass over the coefficients of B(X). We define a monomial by its coefficient and corresponding q-degree, which serve as inputs of our function. Algorithm 5 constant-time product of q-polynomial by a monomial Require: A(X) ∈ Fqm ⟨X q ⟩ of q-degree upper bounded by max, c ∈ Fqm , i ∈ N Ensure: A(X) · cX [i] 1: P ← 0 2: pi ← a0 · c 3: for j = 1 to max do 4: c ← cq 5: pi+j mod m ← pi+j mod m + aj · c 6: end for 7: return P

Update of the quotient. The last optimization concerns the update of the quotient Q. At step i, instead of performing the operation Q ← Q + f lag × cX [i] on the full q-polynomials, we directly update the i-th coefficient of Q as follows: qi ← qi + f lag · c. This optimization avoids unnecessary assignments and thus eliminates up to maxQ coefficient updates per step, where maxQ is the upper bound on the q-degree of Q. Furthermore, if we denote maxM as the q-degree upper bound of cX [i] , representing it only by its coefficient and q-degree–rather than as a q-polynomial – we save maxM elements of Fqm in memory, as well as maxM initializations and de-allocations maxM . Finally, combining all the proposed optimizations leads to our constant-time left-division algorithm of q-polynomials presented in Algorithm 6. In the next section, we will focus on the arithmetic costs of these functions and of the decoding algorithm.

5

Complexity analysis

In order to perform the complexity analysis of the decoding algorithm of the AG codes, we first establish the arithmetic costs of the basic operations on qpolynomials over Fqm . We denote by Cadd , Cmul and CFro the unit cost of an addition, multiplication and Frobenius map in Fqm , respectively. 5.1

Complexity analysis of q-polynomials arithmetic.

Given A(X), B(X), two q-polynomials of q-degree dA and dB . We consider the following operations on Fqm ⟨X q ⟩: 19

Algorithm 6 constant-time left division algorithm Require: A(X), B(X) ∈ Fqm ⟨X q ⟩, with degq (A) ≥ degq (B), and degrees upper bounded by max Ensure: Q(X), R(X) such that A(X) = B(X)Q(X) + R(X) and degq (R) < degq (B) 1: R ← A 2: Q ← 0 3: dA ← deg_ct(A) ▷ From 3 4: dB , bdB ← deg_lc_ct(B) ▷ Same idea as 3 5: ibdb ← b−1 dB 6: s ← dA − dB − max ▷ prevent leaks on degree gaps 7: for i = max to 0 do 8: dR , bdR ← deg_lc_ct(R) ▷ Same idea as 3 9: jump ← dR − dB − i ▷ prevent leaks on degree falls
10: f lag ← 1 − (s < 0) ∨ (jump < 0) 11: m ← ibdB · rdR 12: c ← inverse_frobenius_ct(m, dB ) ▷ Compute m[−dB ] with 4 13: qi ← qi + f lag · c 14: P ← qpoly_monomial_mul_ct(B, c, i) ▷ Compute B(X) × cX [i] with 5 15: R ← R + f lag · P 16: s←s+1 17: end for 18: return (Q, R)

– Cost A(X) + B(X) = (max{dA , dB } + 1) Cadd = O(max{dA , dB }),
– Cost Aq (X) = (dA + 1) CFro = O(dA ),
– Cost A ◦ B = (dA + 1)(dB + 1) (Cadd + Cmul + CFro ) = O(dA dB ),
– Cost A(α) = (dA + 1) (Cadd + Cmul + CFro ) = O(dA ), for α ∈ Fqm . For the computation of the annihilator q-polynomial, we will only consider the case q = 2, since its simplifies calculations and it is parameters used in practice. Let V = {v1 , . . . , vn } be a basis of a F2m -vector space. Following [6], we can compute the sequence Ai (X), for any 1 ≤ i ≤ n, defined by A0 (X) = X Ai (X) = (X + Ai−1 (vi )) ◦ Ai−1 (X) = A2i−1 (X) + Ai−1 (vi ) · Ai−1 (X). The last q-polynomial An (X) is the annihilator polynomial AV (X). Proposition 1. The computation of the annihilator polynomial requires O(n2 ) operations over F2m , where n is the dimension of the corresponding subspace. Proof. For each 1 ≤ i < n any Ai−1 has q-degree i − 1 and hence i coefficients. From the recurrence, computing Ai from Ai−1 requires one Frobenius, one evaluation, one scalar multiplication (costing i Cmul ) and one addition. Thus the i-th iteration costs at most 2i (Cadd + Cmul + CFro ). Summing up the above costs for 20

all iterations we get an overall cost of n(n + 1)(Cadd + Cmul + CFro ) leading to a complexity of order O(n2 ). We now compute the cost of the left Euclidean division of the q-polynomial A(X) by the q-polynomial B(X). To remain consistent with the constant-time implementation, we analyze the complexity of Algorithm 6. Proposition 2. The left Euclidean division of A(X) by B(X) where dA ≥ dB , i.e. A(X) = Q(X) ◦ B(X) + R(X) with degq (R) < degq (B), can be performed in O(dA (dA + dB )) field operations. Proof. Note that the most expensive operations in Algorithm 6 are steps 12, 14, and 15. Step 12 is Algorithm 4 (Frobenius inverse), which requires dB (Cmul + CFro ) operations. Step 14 is Algorithm 5 (product over q-polynomial and monomial), which requires dB Cmul operations. Step 15 consists of the sum of two q-polynomials of degree upper bounded by dB +i, where 0 ≤ i ≤ dA ; it requires (dB +dA +1) Cadd operations. Since these operations are applied over dA + 1 iterations of the for loop, the overall cost is O(dA (dA + dB )) field operations. For the sake of simplicity, we consider that the cost of the left Euclidean division is O(d2A ). In practice, this simplification it does not significantly affect the results. We now have all the costs of the q-polynomials operations used in the decoding algorithm, we can now discuss the complexity of this one. 5.2

Complexity analysis of the decoding Algorithm 2

Among all the operations over Fqm of the decoding algorithm, the most significant in terms of complexity is the computation of a basis of a vector support, since it is equivalent to performing Gaussian elimination over Fq . Proposition 3. Computing a Fqm -basis of Supp(v) from a vector v ∈ Fnqm requires O(n2 ) operations over Fqm . as the matrix representaProof. Let v ∈ Fnqm be a vector. We define V ∈ Fm×n q tion of v over a fixed Fq -basis B. Computing a basis of the vector space spanned by Supp(v) is equivalent to performing Gaussian elimination on V , which requires O(mn2 ) operations over Fq . We observe that columns operations on V can be performed as operations over Fqm . Thus, we conclude that computing a basis of Supp(v) requires O(n2 ) operations over Fqm . Lemma 1. The reduction of the Decoding problem of AG codes to an instance of the Reconstruction problem (steps 1 to 8 of Algorithm 2) requires O(max{(n − n′ )2 , ε(n′ + ε)}) operations over Fqm . 21

Proof. Step 1 is calculation of a Fqm -basis of a vector of size n−n′ , which requires O((n − n′ )2 ) operations. Step 5 is a computation of the annihilator polynomial of q-degree ε, which requires O(ε2 ) operations from Proposition 1. Step 7 is a q-polynomial evaluation over the n′ coordinates of y 1 , it thus requires O(n′ ε). The next part of the decoding Algorithm 2 (step 9) consists of solving the Reconstruction problem for a standard Gabidulin code. Following [6], the divisionfree variant of SolveReconstruction requires O(max{n′2 , (k + ε)2 }) operations over Fqm . The final part of the decoding (steps 10 and 11) involves two left Euclidean divisions. From Proposition 2, these operations require O((k + t)2 ) and O(ε2 ) operations over Fqm , respectively. From the Table 1, we observe that n − n′ ≥ n′ ≥ k + ε, and (n − n′ )2 ≥ ε(n′ + ε). Thus, the next theorem follows. Theorem 3. Algorithm 2 performs O((n − n′ )2 ) operations over Fqm . This constitutes a significant reduction compared to previous approaches, which rely on solving large linear systems and exhibit higher asymptotic cost. In the following section, we also compare this result with other generalizations of Gabidulin codes and show that our method achieves better performance in practice.

6

Results

In this section, we will present and discuss on experimental results that we have observed. Firstly, we will compare decoding algorithms for the AG codes and another Gabidulin code generalization. Secondly, we will compare the RQCBlock-MS-AG implementation with others KEM implementations. Thirdly and lastly, we will provide some results regarding the constant-time analysis of the decoding algorithm. The benchmarks have been performed on a machine equipped with an Intel® Core™ I7-13700 CPU for which the Turbo Boost feature has been disabled during the tests. Programs were compiled using gcc and use the openssl library as a provider for hash functions. 6.1

Comparison of the complexity of AG and EG decoding algorithms

There exists another generalization of Gabidulin codes called extended Gabidulin (EG) codes. These codes were first introduced by Berger and Ourivski in 2009 [8], originally with the aim of constructing new MDS codes derived from classical Gabidulin codes. 22

Definition 7 (Extended Gabidulin codes) Let k, n′ , n, m be positive integers such as k ≤ n′ ≤ min{n, m}, and g = (g1 , . . . , gn ) ∈ Fnqm with ∥g∥ = n′ . The EG code EG g (n, n′ , k, m) is the [n, k]qm -code defined as 
EG g (n, n′ , k, m) = F (g) = F (g1 ), . . . , F (gn ) | F (X) ∈ Fqm ⟨X q ⟩, degq (F ) < k . We can observe that if m ≥ n and n′ = n, the coordinates of the evaluation vector g are linearly independent, and EG codes reduce to Gabidulin codes. The key difference between these two codes is that, in the case of EG codes, the evaluation vector is allowed to be linearly dependent, i.e. n′ ≤ min{m, n}. This relaxation weakens the algebraic structure of the code, which is a desirable property in certain cryptographic contexts. Also, AG codes are a particular case of EG codes; indeed, Gg+ (n, n′ , k, m) ⊂ EG g (n, n′ , k, m). This viewpoint highlights that AG codes inherit the algebraic framework of EG codes, while introducing additional structure – namely, evaluation on partially zero-padded vectors – which plays a central role in their decoding strategy with support erasures. This property is especially relevant in cryptographic settings such as RQC, where controlling the support of errors is crucial (see Section 2.4). In [22], Song et al. suggest that EG codes are of interest to be used in RQC. They prove that their decoding can be reduced to the Reconstruction(y, g, n, k, t) problem, and thus, propose to apply Loidreau’s algorithm to solve it. With this method, the complexity of decoding EG codes is O(n2 ). In the case of AG codes, we showed in section 3 that their decoding reduced to a restricted version of the Reconstruction problem, thanks to the recovery of the support erasure. The decoding algorithm resulting from this restriction has a complexity O((n − n′ )2 ), as proven in section 5. In the end, the decoding appears faster for AG codes than for EG codes for the same parameters. Indeed, both theoretical and practical complexity shown in Table 2 confirm this proposal: decoding EG codes requires three times more multiplications and Frobenius than equivalent AG code, and two times more CPU cycles. Overall comparison between AG and EG codes. EG codes were introduced in 2009 [8] but no decoding algorithm was proposed for these codes at that time, later in 2024 [3] AG codes were introduced and a decoding algorithm was proposed. AG codes and EG codes are equivalent codes, so that in terms of distance property there is no difference between these two families. However in practice having additional zero columns in AG codes rather than additional random combinations of columns of the Gabidulin code for EG codes, is clearly an advantage in terms of decoding, as explained in this section. So that, in practice the specific subfamily of AG codes of EG codes seems to be 23

the most relevant to use in terms of efficiency for the decryption of the RQC cryptosystem and its variations. Code Additions Multiplications Frobenius CPU cycles AG code 12400 9200 5800 675K EG code 12500 32600 14600 1.50M

Table 2: Theoretical and practical complexity of decoding generalized Gabidulin with parameters [104, 3] over F243 and ∥g∥ = 43

AG decoding complexity distribution. Figure 2 describes the practical distribution of each key step of the decoding algorithm of the AG codes. Recalling subsection 2.4, the SolveReconstruction function can be split into two steps. The initialization consists in the calculation of both A⟨g1 ,...,gk ⟩ (X) and I⟨g1 ,...,gk ⟩,⟨y1 ,...,yk ⟩ , where k denotes the code dimension. The interpolation consists in the calculation of the sequence of q-polynomials pairs verifying the Equation (1), for k ≤ i ≤ n, where n denotes the code length. We observe that the initialization of the SolveReconstruction procedure takes a third of the time. This is caused by the reduction of the Reconstruction problem: the Gabidulin code involved has high dimension, which means that there are not many steps for the interpolation part. An alternative to interpolation decoding is syndrome decoding, which is more convenient where the Gabidulin codes are high-dimensional. If a constant-time implementation of such a decoding algorithm can be effective, it may be more efficient than today’s decoding algorithm. step 1 (Gauss) 12.5% 7.5% steps 2 to 8

step 10 (N \ W )

step 9 (Init.) 32%

6.5%

16.5%

step 9 (Interp.)

25% step 11 (N2 \ V2 )

Fig. 2: Execution time distribution for Algorithm 2 using RQC-Block-MS-AG parameters 1

6.2

Performances

We now compare our work to other KEMs: the previous RQC implementation from the NIST proposal [18], the latest HQC implementation [17], and the MLKEM implementation available in the liboqs library. Our proposal is labeled as RQC-Block-MS-AG in the results table. Files required to reproduce these benchmarks will be made publicly available on GitHub soon. 24

Algorithm (128 bits) Keygen Encaps Decaps Size pk + ct (B) RQC-Block-MS-AG 300K 580K 1.65M 1432 RQC (NIST proposal) 595K 685K 2.75M 5486 HQC 77K 145K 325K 6674 ML-KEM 26K 28.5K 34K 1568

Table 3: Average CPU cycles for performing the Keygen, Encaps and Decaps operations for different KEMs (128 bits of security).

Table 3 presents the performance of RQC-Block-MS-AG compared to standardized KEMs and the previous version of RQC. In addition to providing a fully constant-time implementation for the RQC cryptosystem, our implementation outperforms the previous implementation from the NIST standardization process for every operation. When compared to HQC, we observe a performance trade-off: while our implementation is approximately four to five times slower, it compensates with significantly more compact parameters. Specifically, RQCBlock-MS-AG achieves public key and ciphertext sizes roughly four times smaller than HQC. Further optimizations of the implementation could reduce the execution time gap with HQC while maintaining constant-time properties. 6.3

Constant-time

It was shown in [9] that there exists a correlation between the weight of the error and the decoding time for Loidreau’s algorithm, and hence the same holds for our AG decoding algorithm. To verify that our new implementation removes this dependency, we ran the decoding algorithm for each error weight up to the code’s correction capacity. We then analyzed our implementation using the Valgrind debugging tool. Timing analysis over error weight. The Figure 3 shows the average decoding time of AG codes as a function of the error weight, ranging from 0 to 36, which is the decoding capacity of the code used in the RQC-Block-MS-AG scheme. The experiments show that the number of CPU cycles for the decoding operation now varies very slightly when the input weight changes: the relative difference between the minimum and maximum observed values is less than 0.2%. Constant-time analysis. We used Valgrind’s memcheck tool to check from datadependent branching and memory accesses in our program. The analysis process consists in marking variables as uninitialized and running the program, which is called data poisoning. If any such variable is used in a conditional branch, Valgrind raises a warning. In our case, the degrees of the q-polynomials V and N correlate with this value. We decided to poison these variables, as well as all other degrees that may influence the value. To prevent any leakage from the degrees of q-polynomials in the left Euclidean division, we poisoned the degrees of all q-polynomials in this function too. 25

Average CPU Cycles (×104 )

68 67.5 67 66.5 66 65.5 65 64.5 64

0

4

8

12

16

20

24

28

32

36

Error weight

Fig. 3: Average CPU cycles of AG decoding, over the weight of the error Observations. As discussed in Section 4, some q-polynomial functions of the RBC library use the degree in conditional branches, in particular for the range of for loops. Thanks to the constant-time analysis configuration, we modify the program and achieve with a decoding algorithm that does not use any degree as a variable anymore. Indeed, from Figure 3, the experiments show that there exists no more correlation between secret values and elapsed time.

7

Conclusion

In this paper, we present the first constant-time implementation of a decoding algorithm of AG codes. This decoding algorithm achieves a better complexity compared to [3], exploiting the Loidreau’s reconstruction. This theoretical improvement allows us to show that AG codes outperforms EG codes for the same parameters, making them more relevant for decryption in the RQC cryptosystem and its variations. We develop a constant-time implementation of the decoding algorithms for both Gabidulin and AG codes, as well as the left Euclidean division operation. Through extensive timing analysis and validation with Valgrind, we demonstrated that our implementation satisfies constant-time requirements, eliminating vulnerabilities to timing attacks. Our RQC-Block-MS-AG implementation significantly outperforms the previous RQC implementation. While it is approximately 4 times slower than the optimized HQC implementation, this performance difference is compensated by a fourfold reduction in public key and ciphertext sizes, offering an attractive trade-off. Furthermore, additional optimizations of the im26

plementation could reduce the execution time gap while maintaining constanttime properties. The techniques developed for AG code decoding can be directly applied to optimize Gabidulin code decoding, since AG decoding generalizes the Gabidulin case. Future works could explore syndrome decoding approaches for high-dimensional Gabidulin codes, which may offer substantial performance improvements while preserving the compact parameter sizes that make rank metric-based cryptography particularly promising for resource-constrained environments.

References 1. Carlos Aguilar, Olivier Blazy, Jean-Christophe Deneuville, Philippe Gaborit, and Gilles Zémor. Efficient encryption from random quasi-cyclic codes, 2016. 2. Carlos Aguilar-Melchor, Nicolas Aragon, Victor Dyseryn, Philippe Gaborit, and Gilles Zémor. LRPC codes with multiple syndromes: near ideal-size KEMs without ideals. In International Conference on Post-Quantum Cryptography, pages 45–68. Springer, 2022. 3. Nicolas Aragon, Pierre Briaud, Victor Dyseryn, Philippe Gaborit, and Adrien Vinçotte. The blockwise rank syndrome learning problem and its applications to cryptography. In International Conference on Post-Quantum Cryptography, pages 75–106. Springer, 2024. 4. Nicolas Aragon, Victor Dyseryn, Philippe Gaborit, Pierre Loidreau, Julian Renner, and Antonia Wachter-Zeh. Lowms: a new rank metric code-based kem without ideal structure. Designs, Codes and Cryptography, 92(4):1075–1093, 2024. 5. Nicolas Aragon, Bettaieb Slim, Loic Bidoux, Yann Connan, Jérémie Coulaud, Philippe Gaborit, and Anais Kominiarz. Rbc library, 2021. 6. Daniel Augot, Pierre Loidreau, and Gwezheneg Robert. Generalized Gabidulin codes over fields of any characteristic. Designs, Codes and Cryptography, 86:1807– 1848, 2018. 7. Magali Bardet, Pierre Briaud, Maxime Bros, Philippe Gaborit, Vincent Neiger, Olivier Ruatta, and Jean-Pierre Tillich. An Algebraic Attack on Rank Metric Code-Based Cryptosystems, page 64–93. Springer International Publishing, 2020. 8. Thierry P Berger and Alexei Ourivski. Construction of new MDS codes from Gabidulin codes. In Proceedings of ACCT, pages 40–47. Citeseer, 2009. 9. Slim Bettaieb, Loïc Bidoux, Philippe Gaborit, and Etienne Marcatel. Preventing timing attacks against RQC using constant time decoding of Gabidulin codes. In Post-Quantum Cryptography: 10th International Conference, PQCrypto 2019, Chongqing, China, May 8–10, 2019 Revised Selected Papers 10, pages 371–386. Springer, 2019. 10. Loïc Bidoux, Pierre Briaud, Maxime Bros, and Philippe Gaborit. RQC revisited and more cryptanalysis for rank-based cryptography. IEEE Transactions on Information Theory, 70(3):2271–2286, 2023. 11. E. M. Gabidulin, A. V. Paramonov, and O. V. Tretjakov. Ideals over a noncommutative ring and their application in cryptology. In Donald W. Davies, editor, Advances in Cryptology — EUROCRYPT ’91, pages 482–489, Berlin, Heidelberg, 1991. Springer Berlin Heidelberg. 12. Ernest Mukhamedovich Gabidulin. Theory of codes with maximum rank distance. Problemy peredachi informatsii, 21(1):3–16, 1985.

27

13. Philippe Gaborit, Gaétan Murat, Olivier Ruatta, and Gilles Zemor. Low Rank Parity Check codes and their application to cryptography. In Lilya Budaghyan, Tor Helleseth, and Matthew G. Parker, editors, PREPROCEEDINGS The International Workshop on Coding and Cryptography WCC 2013, page 13 p., Bergen, Norway, April 2013. ISBN 978-82-308-2269-2. 14. Pierre Loidreau. A Welch–Berlekamp like algorithm for decoding Gabidulin codes. In International Workshop on Coding and Cryptography, pages 36–45. Springer, 2005. 15. Pierre Loidreau. A new rank metric codes based encryption scheme. In International Workshop on Post-Quantum Cryptography, pages 3–17. Springer, 2017. 16. Robert J. McEliece. A public key cryptosystem based on algebraic coding theory. 1978. 17. Carlos Aguilar Melchor, Nicolas Aragon, Slim Bettaieb, Loïc Bidoux, Olivier Blazy, Jean-Christophe Deneuville, Philippe Gaborit, Edoardo Persichetti, and Gilles Zémor. Hamming Quasi-Cyclic (HQC). Submission to the NIST PQC standardization process, 2017. 18. Carlos Aguilar Melchor, Nicolas Aragon, Slim Bettaieb, Loïc Bidoux, Olivier Blazy, Jean-Christophe Deneuville, Philippe Gaborit, and Gilles Zémor. Rank QuasiCyclic (rqc). Submission to the NIST PQC standardization process, 2017. 19. National Institute of Standards and Technology. Fips 203: Module-lattice-based key-encapsulation mechanism (ml-kem). Technical Report FIPS 203, U.S. Department of Commerce, August 2024. Available at https://doi.org/10.6028/NIST. FIPS.203. 20. Oystein Ore. On a special class of polynomials. Transactions of the American Mathematical Society, 35(3):559–584, 1933. 21. P.W. Shor. Algorithms for quantum computation: discrete logarithms and factoring. In Proceedings 35th Annual Symposium on Foundations of Computer Science, pages 124–134, 1994. 22. Yongcheng Song, Rongmao Chen, Fangguo Zhang, Xinyi Huang, Jian Weng, and Huaxiong Wang. (Interleaved) Extended Gabidulin Codes and Their Applications to RQC. Cryptology ePrint Archive, 2025. 23. Yongcheng Song, Jiang Zhang, Xinyi Huang, and Wei Wu. Blockwise rank decoding problem and LRPC codes: cryptosystems with smaller sizes. IEEE Transactions on Information Theory, 2025. 24. Antonia Wachter-Zeh, Valentin Afanassiev, and Vladimir Sidorenko. Fast decoding of Gabidulin codes. Designs, Codes and Cryptography, 66:57–73, 2012.

28