1
Subcodes of Lambda-Gabidulin Codes for Compact-Ciphertext Cryptography Freddy Lendé Metouké, Hervé Talé Kalachi, Hermann Tchatchiem Kamche, Ousmane Ndiaye, Sélestin Ndjeya
arXiv:2604.18282v1 [cs.CR] 20 Apr 2026
Abstract This paper investigates subcodes of lambda-Gabidulin codes, viewed as rank-metric analogues of generalized Reed–Solomon codes, and their applications to compact-ciphertext cryptosystems. We first analyze subspace and generalized subspace subcodes of lambda-Gabidulin codes and relate them to corresponding subcodes of classical Gabidulin codes through coordinate-wise scaling. This relation yields cardinality bounds and structural properties for these families. When the extension degree equals the code length, we further characterize Gabidulin subspace subcodes in terms of linearized polynomials, which gives an explicit description of their encoding and dimension. We also study the matrix images of these subcodes over the base field through their stabilizer and annihilator algebras, showing that subspace restrictions may preserve nontrivial algebraic invariants despite the loss of extension-field linearity. Motivated by these results, we propose a generator-matrix-based construction of random subcodes designed to avoid such invariants. This construction is then used to design McEliece-like and Niederreiter-like encryption schemes in the MinRank setting. Among the parameter sets considered in this work, the most compact ciphertexts are obtained from random subcodes of classical Gabidulin codes. At the 128-, 192-, and 256-bit security levels, the resulting LGS-Niederreiter instances achieve the smallest ciphertext sizes among the compared schemes, while maintaining competitive public-key sizes. Index Terms Code-based cryptography, rank-metric codes, Gabidulin codes, lambda-Gabidulin codes, subcodes, MinRank problem, public-key encryption.
I. I NTRODUCTION The rank metric was first introduced by Delsarte in 1978 in the setting of matrix codes over finite fields [1]. A few years later, Gabidulin developed the extension-field viewpoint and introduced the family now known as Gabidulin codes, together with their main structural properties and a decoding algorithm [2]. These codes are maximum rank distance codes, since they attain the Singleton bound in the rank metric. Shortly thereafter, Gabidulin, Paramonov, and Tretjakov proposed the GPT cryptosystem [3], the first public-key cryptosystem based on rank-metric codes and a rank-metric analogue of the McEliece construction [4]. One of the main attractions of the rank metric in code-based cryptography is that the best known generic decoding attacks remain significantly harder in practice than their counterparts in the Hamming metric for comparable parameters [5]. As a result, rank-metric cryptosystems can operate with much smaller code parameters and often achieve substantially smaller public keys in practice [6], [7]. In principle, rank-metric codes therefore offer an appealing route toward compact code-based encryption. These advantages, however, can only be realized if the algebraic structure of the secret code is sufficiently well hidden in the public key, and this masking problem turned out to be the main obstacle for early Gabidulin-based proposals. Freddy Lendé Metouké is with the Department of Mathematics, Faculty of Science, University of Yaounde I, Cameroon email : [email protected]. Hervé Talé Kalachi is with the Department of Computer Engineering, National Advanced School of Engineering of Yaoundé, University of Yaounde I, Cameroon e-mail: [email protected]. Hermann Tchatchiem Kamche is with the Centre for Cybersecurity and Mathematical Cryptology, The University of Bamenda, Bamenda, Cameroon e-mail: [email protected]. Ousmane Ndiaye is with the Université Cheikh Anta Diop de Dakar, FST, DMI, LACGAA, Senegal e-mail: [email protected]. Sélestin Ndjeya is with the Department of Mathematics, Higher Teacher Training College, University of Yaounde I, Cameroon e-mail : [email protected].
This difficulty was already visible in the original GPT cryptosystem. Its main weakness was precisely the challenge of hiding the strong algebraic structure of the underlying Gabidulin code. Gibson’s attack [8] showed that this structure could already be exploited in the original proposal, and most subsequent variants were later broken by Overbeck’s attacks [9], [10] and their extensions [11]–[13]. In retrospect, this vulnerability is perhaps not entirely surprising. Gabidulin codes are rank-metric analogues of Reed–Solomon codes, and McEliece-type cryptosystems based on Reed–Solomon-like structures have also been shown to admit powerful structural attacks [14]. By contrast, the original McEliece cryptosystem based on binary Goppa codes has largely resisted efficient structural cryptanalysis for several decades in practical parameter ranges, even though Goppa codes can be viewed as subfield subcodes of generalized Reed–Solomon codes [15], [16]. This contrast naturally suggests investigating subcodes of Gabidulin codes as possible rank-metric counterparts of the passage from generalized Reed–Solomon codes to Goppa codes. This perspective has already motivated several works on subcodes of Gabidulin codes. Gabidulin and Loidreau initiated the study of subspace and subfield subcodes in the rank metric [17], [18]. Their work was later continued by Gabidulin and Pilipchuk, who emphasized the relevance of subspace subcodes to network coding [19]. More recently, Liu et al. studied random Gabidulin subcodes from the point of view of list decoding and showed that they can, with overwhelming probability, achieve list-decodability behavior close to that of random rank-metric codes near the relevant Gilbert–Varshamov bound [20]. Subcodes have also been considered directly for cryptographic design. Berger et al. [21] proposed a cryptosystem based on matrix Gabidulin subcodes and highlighted the possibility of obtaining very short ciphertexts, an especially desirable feature in communication-constrained settings. Later, Guo et al. [22] introduced Loidreau-type variants based on Gabidulin subcodes. Taken together, these contributions indicate that subcodes are a natural way to weaken visible algebraic structure while retaining efficient decoding, and they also show that compact ciphertexts can be a decisive advantage in practical rank-metric cryptography. In 2019, Lau and Tan introduced lambda-Gabidulin codes as a generalized Gabidulin family, which may be viewed as rank-metric analogues of generalized Reed–Solomon codes, and proposed a McEliece-type cryptosystem based on them [23]. These codes enlarge the design space beyond classical Gabidulin codes and were proposed to mitigate the structural weaknesses exploited by known attacks. More recently, however, several parameter sets of such constructions were shown to be vulnerable to structural cryptanalysis [24]. Although some parameters still resist the attacks currently known, these developments naturally raise the question of whether one should study subcodes of lambda-Gabidulin codes rather than the full family itself. From this viewpoint, subcodes of lambda-Gabidulin codes may provide a more plausible rankmetric analogue of the transition from generalized Reed–Solomon codes to Goppa codes. This question is particularly appealing because it combines two objectives: weakening visible algebraic structure while preserving the practical efficiency advantages that make rank-metric cryptography attractive. In this paper, we investigate subcodes of lambda-Gabidulin codes from both a structural and a cryptographic viewpoint. On the structural side, we relate generalized subspace subcodes of lambdaGabidulin codes to suitable subcodes of classical Gabidulin codes, derive cardinality bounds, and introduce a simple generator-matrix-based construction of random Fq -linear subcodes. We also study the matrix images of these subcodes through their stabilizer and annihilator algebras, leading to structural distinguishers and to criteria for identifying restricted subcode families that remain algebraically visible. On the cryptographic side, we use random Fq -linear subcodes of lambda-Gabidulin codes and of their classical Gabidulin specialization to design McEliece-like and Niederreiter-like encryption schemes in the MinRank setting. Among the resulting instantiations, the best ciphertext-size tradeoffs are obtained in the classical Gabidulin case, while the broader lambda-Gabidulin framework provides additional design flexibility. In particular, the proposed Niederreiter-like construction achieves very compact ciphertexts together with competitive public-key sizes, improving the ciphertext-size tradeoff of previous rank-metric subcode-based proposals such as those of Berger et al. [21] and Guo et al. [22], and comparing favorably with the enhanced matrix-code framework of Aragon et al. [25]. The remainder of the paper is organized as follows. Section II recalls the necessary background on rank2
metric codes, subcodes, and lambda-Gabidulin codes. Section III studies subcodes of lambda-Gabidulin and Gabidulin codes and establishes their main structural properties. Section IV investigates the stabilizer and annihilator algebras of matrix images of subcodes and derives the corresponding structural distinguishers. Section V presents the proposed cryptographic constructions. Section VI analyzes structural and decoding attacks. Section VII provides parameter sets and comparisons with related schemes. Finally, Section VIII concludes the paper. II. P RELIMINARIES This section is structured as follows. We begin with a brief overview of the rank metric, followed by a presentation of Gabidulin and λ-Gabidulin codes. We conclude with some properties of subcodes in the rank metric. A. Matrix and Vector Representations of Rank-Metric Codes The rank metric was originally introduced by Delsarte [1] in the study of matrix codes over finite fields. Let q be a power of a prime, let Fq be the finite field with q elements, and let Fqm be its extension of degree m. Throughout this subsection, we fix an Fq -basis B = (b1 , . . . , bm ) of Fqm . Definition 2.1 (Matrix code): A matrix code is an Fq -linear subspace Cmat of the Fq -vector space Fm×n q of all m × n matrices over Fq . The rank weight of a matrix M ∈ Fm×n is defined by q wtR (M) := rank(M), and the associated rank distance on Fm×n is q d(M, N) := rank(M − N)
for all M, N ∈ Fm×n . q
The dual matrix code of Cmat is ⊥ Cmat := A ∈ Fm×n Tr(AB⊤ ) = 0 for all B ∈ Cmat , q where Tr(·) denotes the ordinary trace of a square matrix over Fq and B⊤ the transpose of the matrix B. Definition 2.2 (Vector rank-metric code): A vector rank-metric code of length n over Fqm is an Fqm -linear subspace C ⊆ Fnqm . For a vector c = (c1 , . . . , cn ) ∈ Fnqm , its rank weight is rankwt (c) := dimFq ⟨c1 , . . . , cn ⟩Fq , where ⟨c1 , . . . , cn ⟩Fq denotes the Fq -subspace of Fqm generated by the coordinates of c. The associated rank distance on Fnqm is d(c, c′ ) = rankwt (c − c′ )
for all c, c′ ∈ Fnqm .
The dual code of C is ( ⊥
C :=
c ∈ Fnqm
n X
) ci c′i = 0 for all c′ = (c′1 , . . . , c′n ) ∈ C
i=1
3
.
a) Expansion Maps: Every element x ∈ Fqm can be written uniquely as x=
m X
xj ∈ Fq .
x j bj ,
j=1
This defines the Fq -linear map ϕB : Fqm −→ Fm q ,
x 7−→ (x1 , . . . , xm ).
Extending componentwise, we obtain the vector expansion map n mn ϕvec B : Fq m −→ Fq ,
(x1 , . . . , xn ) 7−→ ϕB (x1 ), . . . , ϕB (xn ) ,
and the matrix expansion map (x1 , . . . , xn ) 7−→ ϕB (x1 )⊤ , . . . , ϕB (xn )⊤ ,
ϕmat : Fnqm −→ Fm×n , B q
whose columns are the q-ary expansions of the coordinates. Remark 2.3: For every x ∈ Fnqm , one has rank ϕmat B (x) = rankwt (x). In the sequel, we often write rank(x) in place of rankwt (x) when no confusion is possible. Let C ⊆ Fnqm be an Fqm -linear code generated by {g1 , . . . , gk }. Since every coefficient in Fqm expands uniquely on the basis B = (b1 , . . . , bm ), the code C, viewed as an Fq -linear space, is generated by { bi gj | 1 ⩽ i ⩽ m, 1 ⩽ j ⩽ k }. mat mat Since ϕvec are Fq -linear isomorphisms, the codes ϕvec B and ϕB B (C) and ϕB (C) are generated by
{ϕvec B (bi gj )}1⩽i⩽m, 1⩽j⩽k
and
{ϕmat B (bi gj )}1⩽i⩽m, 1⩽j⩽k ,
respectively. b) Fold and Unfold: Since the Fq -vector spaces Fmn and Fm×n are canonically isomorphic, we q q freely switch between vector and matrix representations depending on the context. For v = (v11 , . . . , v1m , v21 , . . . , v2m , . . . , vn1 , . . . , vnm ) ∈ Fmn q , its folding is v11 v21 · · · vn1 .. .. ∈ Fm×n . .. Fold(v) = ... . . . q v1m v2m · · · vnm
The inverse map is denoted by Unfold and, one can notice that for every x ∈ Fnqm , mat vec Fold ϕvec Unfold ϕmat B (x) = ϕB (x), B (x) = ϕB (x). m×n Figure 1 summarizes the connections between Fnqm , Fmn . q , Fq
Fnqm
ϕvec B
Fmn q Unfold
ϕmat B
Fm×n q Fig. 1. Relation between the vector and matrix representations over Fq .
4
Fold
Remark 2.4: Let M, N ∈ Fm×n , and let vec(·) denote the usual vectorization map. By definition of q Unfold, one has vec(M) = Unfold(M)⊤ . Using the classical identity vec(M)⊤ vec(N) = Tr(M⊤ N), see [26], it follows that Unfold(M) Unfold(N)⊤ = Tr(MN⊤ ). B. Gabidulin Codes and λ-Gabidulin Codes Gabidulin codes are rank-metric analogues of Reed–Solomon codes in the Hamming metric. They were introduced by Gabidulin in the extension-field setting and form a family of maximum rank distance codes [2]. We recall their standard definition. Definition 2.5 (Gabidulin code): Let n, m, k be positive integers such that n ⩽ m and k ⩽ n, and let g = (g1 , . . . , gn ) ∈ Fnqm be a vector whose coordinates are linearly independent over Fq . The Gabidulin code G(g, k) is the Fqm -linear code of length n and dimension k generated by the rows of g1 g2 · · · gn [1] [1] g [1] g2 · · · gn 1 G = .. (1) .. , .. . . . . . . [k−1]
g1
[k−1]
g2
[k−1]
· · · gn
i
where x[i] := xq denotes the i-th Frobenius power of x. Gabidulin codes are maximum rank distance (MRD) codes: their minimum rank distance is d = n − k + 1. Moreover, the dual of a Gabidulin code is again a Gabidulin code [2]. Inspired by the role of diagonal multipliers in generalized Reed–Solomon codes, Lau and Tan introduced the family of λ-Gabidulin codes [23]. Definition 2.6 (λ-Gabidulin code): Let g = (g1 , . . . , gn ) ∈ Fnqm be a vector whose coordinates are linearly independent over Fq , and let λ = (λ1 , . . . , λn ) ∈ (F∗qm )n . The λ-Gabidulin code Gλ (g, k) is the Fqm -linear code generated by the rows of λ1 g1 λ2 g2 · · · λn gn [1] [1] λ1 g [1] λ2 g2 · · · λ n gn 1 (2) Gλ = .. = G∆, .. .. . . . . . . [k−1]
λ1 g1
[k−1]
λ2 g2
[k−1]
· · · λn gn
where G is given by (1) and ∆ = Diag(λ1 , . . . , λn ). If λ = (λ, . . . , λ) for some λ ∈ F∗qm , then Gλ (g, k) = G(g, k). Thus classical Gabidulin codes appear as a special case of λ-Gabidulin codes. Lau and Tan showed that the dual of a λ-Gabidulin code is again a λ-Gabidulin code [23, Proposition 1]. Moreover, decoding a λ-Gabidulin code reduces to decoding the associated Gabidulin code after multiplication by ∆−1 . More precisely, if the Gabidulin code G(g, k) corrects up to t rank-metric errors and if −1 δ = rank(λ−1 ) with λ−1 = (λ−1 1 , . . . , λn ), t then the code Gλ (g, k) can correct up to δ rank errors [23, Proposition 4]. 5
C. Subcodes in the Rank Metric In this subsection, we recall several notions of subcodes in the rank metric that will be used throughout the paper. Definition 2.7 (Subcode): Let C ⊆ Fnqm be an Fqm -linear code, and let D ⊆ Fnqm be an Fq -linear code. We say that D is a subcode of C if D ⊆ C. The above definition is equivalent to say that, an Fq -linear code D ⊆ Fnqm is a subcode of C ⊆ Fnqm if and only if there exists an Fq -linear code C ′ ⊆ Fnqm such that D = C ∩ C ′ . Indeed, one may simply take C ′ = D. This observation motivates the study of subcodes obtained by intersecting C with suitable Fq -linear subspaces of Fnqm . Definition 2.8 (Subfield, subspace, and generalized subspace subcodes): Let C ⊆ Fnqm be an Fqm -linear code. 1) The intersection C ∩ Fnq is called the subfield subcode of C over Fq [27], [28]. 2) Let V ⊆ Fqm be an Fq -vector subspace. Then C ∩ V n is called the subspace subcode of C over V , where V n = |V × ·{z · · × V} [18], [29], [30]. n times
3) Let V1 , . . . , Vn be Fq -vector subspaces of Fqm , and set W = V1 × · · · × Vn . Then C ∩ W is called a generalized subspace subcode of C [30], [31]. Remark 2.9: The restriction to Fnq is of limited interest from the rank-metric viewpoint, since every nonzero vector of Fnq has rank weight equal to 1. More generally, if V ⊆ Fqm is an Fq -subspace of dimension s, then every word c ∈ V n satisfies rank(c) ⩽ s. Consequently, if C has minimum rank distance d, then the subspace subcode C ∩ V n is trivial whenever s < d. This motivates the consideration of generalized subspace restrictions, where different coordinates may be restricted to different subspaces. Another classical way to construct subcodes is through the vertical concatenation of parity-check matrices, as in [21], [22]. Let C, C ′ ⊆ Fnq be linear codes with parity-check matrices H and H′ , respectively. By standard duality arguments [32], (C ∩ C ′ )⊥ = C ⊥ + C ′⊥ . Therefore, the dual of C ∩ C ′ is generated by the rows of ′ e = H . H H This viewpoint underlies subcode constructions based on parity-check matrices. III. G ENERALIZED S UBSPACE S UBCODES OF λ-G ABIDULIN C ODES In this section, we study generalized subspace subcodes of λ-Gabidulin codes. We first derive cardinality bounds for such subcodes and then, in the special case where the extension degree equals the code length, we give an algebraic characterization of subspace subcodes of Gabidulin codes. A. Cardinality Bounds for Generalized Subspace Subcodes of λ-Gabidulin Codes We begin by relating generalized subspace subcodes of λ-Gabidulin codes to suitable generalized subspace subcodes of classical Gabidulin codes. Throughout this subsection, let n, m, k be positive integers such that n ⩽ m, and let G(g, k) ⊆ Fnqm be a Gabidulin code with minimum rank distance d = n − k + 1. Let λ = (λ1 , . . . , λn ) ∈ (F∗qm )n and define ∆ = Diag(λ1 , . . . , λn ), so that Gλ (g, k) = G(g, k)∆. For each i ∈ {1, . . . , n}, let Vi ⊆ Fqm be an Fq -subspace of dimension si , and set W :=
n Y
Vi ⊆ Fnqm .
i=1
6
We have the following lemma. Lemma 3.1: Let ψ be the Fq -linear map defined by c 7→ c∆−1 .
ψ : Fnqm → Fnqm , Then ψ restricts to an Fq -linear bijection
ψ|Gλ ∩W : Gλ ∩ W −→ G ∩
n Y
(λ−1 i Vi ).
i=1
Proof. Since ∆ ∈ GLn (Fqm ), the map ψ is a bijection on Fnqm . Moreover, ψ(Gλ ) = G, because Gλ = G∆. Finally, for c = (c1 , . . . , cn ) ∈ W , we have −1 ψ(c) = (λ−1 1 c1 , . . . , λ n cn ) ∈
n Y
(λ−1 i Vi ),
i=1
and conversely ψ
−1
maps
Qn
−1 i=1 (λi Vi ) back to W . Hence the restriction of ψ yields the claimed bijection.
Theorem 3.2: Assume that max1⩽i⩽n {si } − d + 1 > 0. Then the generalized subspace subcode Gλ ∩ W satisfies Pn q i=1 si −m(n−k) ⩽ Gλ ∩ W ⩽ q m(max1⩽i⩽n {si }−d+1) . Moreover, if s1 = · · · = sn = s and m = n, then the two bounds coincide, and the code Gλ (g, k) ∩ W has Fq -dimension k ′ = km + sm − m2 . Proof. By Lemma 3.1, n Y Gλ ∩ W = G ∩ (λ−1 i Vi ) . i=1
The announced bounds then follow directly from [31, Theorem 3] applied to the Gabidulin code G. Remark 3.3: If V1 = · · · = Vn = V and dimFq (V ) = s, then the previous theorem specializes to q ns−m(n−k) ⩽ |Gλ ∩ V n | ⩽ q m(s−d+1) , which recovers the corresponding bound for Gabidulin codes [18]. B. q-Polynomials and Subspace Subcodes We now recall some basic facts on q-polynomials and use them to study subspace subcodes. Definition 3.4 ( [33]): A q-polynomial (or linearized polynomial) over Fqm is a polynomial of the form P (x) =
d X
i
ai x q ,
ai ∈ Fqm .
i=0
Such a polynomial induces an Fq -linear map on Fqm . If P (x) = q-degree is degq (P ) = d.
Pd
i=0 ai x
qi
is nonzero with ad ̸= 0, its
By convention, degq (0) = −∞. Let Lqm denote the set of q-polynomials over Fqm , equipped with addition and composition ◦. The next lemma collects the properties of q-polynomials that will be needed later in the analysis of stabilizer algebras. Lemma 3.5: Let V be an Fq -subspace of Fqm of dimension s, with 0 < s < m. Then the following properties hold. 7
(i) There exists a nonzero q-polynomial P ∈ Lqm of q-degree s such that for all v ∈ V.
P (v) = 0
Moreover, P is unique up to multiplication by a nonzero scalar in Fqm . (ii) Let P be as in (i). Then there exists a q-polynomial Q ∈ Lqm of q-degree m − s such that m
Q ◦ P = xq − x. Moreover, P ◦ Q = Q ◦ P. Proof. (i) The existence of such a polynomial follows from [34]. m (ii) Since P vanishes on V and xq − x vanishes on all of Fqm , [34] implies that there exists a q-polynomial Q ∈ Lqm of q-degree m − s such that m
Q ◦ P = xq − x. m
Now, xq − x is a central element of Lqm (see [35, Theorem II-18]), that is, m
m
(xq − x) ◦ R = R ◦ (xq − x)
for all R ∈ Lqm .
Applying this with R = P gives (Q ◦ P ) ◦ P = P ◦ (Q ◦ P ). By associativity, (Q ◦ P ) ◦ P = (P ◦ Q) ◦ P. Since Lqm is an integral domain and P ̸= 0, we may cancel the right factor P and obtain Q ◦ P = P ◦ Q. The evaluation of q-polynomials on a support vector gives an equivalent description of Gabidulin codes: G(g, k) = P (g1 ), . . . , P (gn ) P ∈ Lqm , degq (P ) < k . The next proposition specializes this description to subspace subcodes in the case m = n. Proposition 3.6: Assume that m = n. Let G = G(g, k) be a Gabidulin code with support g = (g1 , . . . , gn ) ∈ Fnqm , whose coordinates are linearly independent over Fq , and let V ⊆ Fqm be an Fq subspace of dimension s. Then there exists a q-polynomial Q ∈ Lqm of q-degree m − s such that G ∩ V n = (Q ◦ A)(g1 ), . . . , (Q ◦ A)(gn ) A ∈ Lqm , degq (A) < k − (m − s) . Proof. By Lemma 3.5, there exist P, Q ∈ Lqm such that m
V = ker(P ), Q ◦ P = xq − x, degq (P ) = s, degq (Q) = m − s. Let c ∈ G ∩ V n . Then there exists a q-polynomial F ∈ Lqm with degq (F ) < k such that c = (F (g1 ), . . . , F (gn )). Since c ∈ V n = ker(P )n , we have P (F (gi )) = 0
for all i = 1, . . . , n.
Hence (P ◦ F )(gi ) = 0 for all i. Because m = n and the coordinates of g are Fq -linearly independent, they form an Fq -basis of Fqm . Therefore P ◦ F vanishes on all of Fqm . By [34], there exists A ∈ Lqm such that m
P ◦ F = A ◦ (xq − x). 8
m
Since xq − x is central in Lqm , m
m
A ◦ (xq − x) = (xq − x) ◦ A = (Q ◦ P ) ◦ A. Using Lemma 3.5, we also have P ◦ Q = Q ◦ P , hence P ◦ F = P ◦ (Q ◦ A). Since Lqm is an integral domain and P ̸= 0, we get F = Q ◦ A. Moreover, degq (A) = degq (F ) − degq (Q) < k − (m − s). This proves one inclusion. Conversely, let A ∈ Lqm satisfy degq (A) < k − (m − s). Then degq (Q ◦ A) < k, so (Q ◦ A)(g1 ), . . . , (Q ◦ A)(gn ) ∈ G. Furthermore,
m
P ((Q ◦ A)(gi )) = (P ◦ Q ◦ A)(gi ) = ((xq − x) ◦ A)(gi ) = 0 for all i, so this word belongs to V n . Hence it lies in G ∩ V n . Remark 3.7: 1) Proposition 3.6 provides a direct description of the Gabidulin subspace subcode G ∩ V n in terms of the original support g and q-polynomials, without passing through the parent-code framework of [18, Section B]. 2) Moreover, if k − m + s > 0, then the above parametrization shows that |G ∩ V n | = q m(k−m+s) , and therefore dimFq (G ∩ V n ) = m(k − m + s). This recovers the corresponding dimension formula in [18]. 3) Although G ∩ V n is in general only Fq -linear, Proposition 3.6 shows that it still retains a strong algebraic structure inherited from the extension field through the q-polynomial parametrization. In particular, the codewords are described by evaluations of compositions Q ◦ A with A ∈ Lqm , which reveals a residual extension-field structure behind the subspace restriction. This makes the existence of nontrivial structural invariants, and hence of potential distinguishers, less surprising. IV. S TABILIZER AND A NNIHILATOR A LGEBRA OF S UBSPACE S UBCODES OF G ABIDULIN C ODES When an Fqm -linear code is expanded into a matrix code over Fq , its hidden Fqm -linear structure may be revealed through non-trivial algebraic invariants, such as stabilizer [25]. This observation underlies the distinguisher of [25] for Gabidulin matrix codes. To study this stabilizer algebra on the subcodes, we will first give a method to compute a dimension of this stabilizer algebra. Then, we will study the stabilizers of subspace subcodes and random subcodes.
9
A. Stabilizer and Annihilator Algebras In this subsection, we recall the relevant definitions and derive a linear-algebraic characterization of the left stabilizer and left annihilator of a matrix code. Definition 4.1: Let Cmat ⊆ Fm×n be a matrix code. q 1) The left stabilizer algebra of Cmat is StabL (Cmat ) := P ∈ Fm×m PC ∈ Cmat for all C ∈ Cmat . q 2) The left annihilator algebra of Cmat is AnnL (Cmat ) := A ∈ Fm×m AC = 0 for all C ∈ Cmat . q 3) The right stabilizer algebra and right annihilator algebra are defined similarly, and are denoted by StabR (Cmat ) and AnnR (Cmat ). Remark 4.2: 1) One always has AnnL (Cmat ) ⊆ StabL (Cmat ). Thus, the annihilator may be viewed as a substructure of the stabilizer algebra, consisting of linear transformations that act trivially on all codewords. 2) As observed in [25], the existence of an Fqm -linear structure may be detected through a nontrivial right stabilizer algebra. Although subspace subcodes lose global Fqm -linearity, such codes may still exhibit nontrivial stabilizer algebras. 3) For a random matrix code, one typically expects the annihilator algebras to be trivial, namely reduced to {0}, and the stabilizer algebras to be minimal, namely reduced to the scalar matrices: StabL (Cmat ) = {αIm | α ∈ Fq },
StabR (Cmat ) = {αIn | α ∈ Fq },
with overwhelming probability. Proposition 4.3 (Left stabilizer and annihilator via linear systems): Let Cmat ⊆ Fm×n be an Fq -linear q ′ matrix code of dimension k , with ordered basis (G1 , . . . , Gk′ ). ⊥ Let (H1 , . . . , Hmn−k′ ) be a basis of the dual code Cmat . m×m 1) A matrix A ∈ Fq belongs to StabL (Cmat ) if and only if, for all i = 1, . . . , mn − k ′ and ′ j = 1, . . . , k , Unfold(Hi )(G⊤ j ⊗ Im ) vec(A) = 0.
Furthermore, let MS be the matrix obtained by stacking all row vectors Unfold(Hi )(G⊤ j ⊗ Im ),
1 ⩽ i ⩽ mn − k ′ , 1 ⩽ j ⩽ k ′ ,
Then dimFq StabL (Cmat ) = m2 − rank(MS ). 2) A matrix A ∈ Fm×m belongs to AnnL (Cmat ) if and only if, for all j = 1, . . . , k ′ , q (G⊤ j ⊗ Im ) vec(A) = 0. Additionally, if we define G⊤ 1 ⊗ Im .. k′ mn×m2 , M′S = ∈ Fq .
G⊤ k ′ ⊗ Im 10
Then dimFq AnnL (Cmat ) = m2 − rank(M′S ). Proof. We first consider the stabilizer. By definition, A ∈ StabL (Cmat )
⇐⇒
AGj ∈ Cmat , for all j = 1, . . . , k ′ .
⊥ is the dual of Cmat , this is equivalent to Since Cmat Tr Hi (AGj )⊤ = 0 for all i = 1, . . . , mn − k ′ , j = 1, . . . , k ′ .
By Remark 2.4, Tr Hi (AGj )⊤ = Unfold(Hi ) Unfold(AGj )⊤ . Using the vectorization identity vec(AGj ) = (G⊤ j ⊗ Im ) vec(A)
(see [26, Lemma 4.3.1]),
we obtain Tr Hi (AGj )⊤ = Unfold(Hi )(G⊤ j ⊗ Im ) vec(A). Hence the stabilizer is exactly the solution space of the corresponding homogeneous linear system. The dimension formula follows from the rank–nullity theorem. For the annihilator, A ∈ AnnL (Cmat )
⇐⇒
AGj = 0 for all j = 1, . . . , k ′ .
Vectorizing gives (G⊤ j ⊗ Im ) vec(A) = 0
for all j = 1, . . . , k ′ ,
which yields the matrix M′S . The dimension formula again follows from the rank–nullity theorem. Proposition 4.3 shows that both the left stabilizer and the left annihilator of a matrix code can be computed through explicit homogeneous linear systems. Analogous constructions apply to the right stabilizer and right annihilator algebras. B. Stabilizer Algebra of Subspace Subcodes Subspace subcodes are only Fq -linear, since restricting to an Fq -subspace V ⊆ Fqm breaks the ambient Fqm -linearity. One might therefore expect the algebraic invariants associated with the extension-field structure to disappear. The next theorem shows that this is not necessarily the case. In particular, subspace subcodes of Gabidulin codes, and more generally subspace restrictions of linear codes over Fqm , may still retain large stabilizer or annihilator algebras after expansion to matrix form. Theorem 4.4 (Structural properties of stabilizer and annihilator algebras): Let g ∈ Fnqm be a support vector, let G(g, k) be a Gabidulin code, and let V ⊆ Fqm be an Fq -subspace of dimension s, with 0 < s < m. Let B be a fixed Fq -basis of Fqm . Then the following properties hold. 1) If m = n, then the expanded subspace subcode ϕmat G(g, k) ∩ V n ⊆ Fm×n B q admits a right stabilizer algebra containing an Fq -subalgebra isomorphic to Fqm . In particular, n dimFq StabR ϕmat (G(g, k) ∩ V ) ⩾ m. B 2) For every Fq -linear code C ⊆ Fnqm , mat n dimFq AnnL ϕB (C ∩ V ) ⩾ m(m − s). 11
Consequently, n dimFq StabL ϕmat (C ∩ V ) ⩾ m(m − s) + 1. B Proof. 1) By Proposition 3.6, there exists a q-polynomial Q ∈ Lqm of q-degree m − s such that codewords of G(g, k) ∩ V n are precisely the vectors of the form (Q ◦ A)(g1 ), . . . , (Q ◦ A)(gn ) , A ∈ Lqm , degq (A) < k − (m − s). Since m = n and the coordinates of g are Fq -linearly independent, the tuple (g1 , . . . , gn ) is an Fq -basis of Fqm . For each α ∈ Fqm , let Nα ∈ Fn×n be the matrix of the Fq -linear map q Lα : Fqm −→ Fqm ,
x 7−→ αx
with respect to the basis (g1 , . . . , gn ). Let c = (Q ◦ A)(g1 ), . . . , (Q ◦ A)(gn ) ∈ G(g, k) ∩ V n . Since Q ◦ A is Fq -linear, one has cNα = (Q ◦ A)(αg1 ), . . . , (Q ◦ A)(αgn ) = (Q ◦ A ◦ Lα )(g1 ), . . . , (Q ◦ A ◦ Lα )(gn ) . Moreover, degq (A ◦ Lα ) = degq (A) < k − (m − s), so cNα ∈ G(g, k) ∩ V n . Since Nα ∈ Fn×n , this implies q mat G(g, k) ∩ V n . ϕmat B (c)Nα ∈ ϕB Hence n Nα ∈ StabR ϕmat B (G(g, k) ∩ V )
for every α ∈ Fqm .
Finally, the map Fqm −→ Fn×n , q
α 7−→ Nα
is an injective Fq -algebra morphism. Therefore, {Nα | α ∈ Fqm } is an Fq -subalgebra of
n StabR ϕmat B (G(g, k) ∩ V )
isomorphic to Fqm . In particular, n dimFq StabR ϕmat (G(g, k) ∩ V ) ⩾ m. B 2) Let TV := T ∈ EndFq (Fqm ) V ⊆ Ker(T ) , where EndFq (Fqm ) denotes the Fq -algebra of Fq -linear endomorphisms of Fqm . Choose an Fq -basis (e1 , . . . , em ) of Fqm adapted to V , namely such that V = ⟨e1 , . . . , es ⟩Fq . Then an endomorphism T ∈ EndFq (Fqm ) belongs to TV if and only if the first s columns of its matrix in the basis (e1 , . . . , em ) are zero. Hence dimFq (TV ) = m(m − s). 12
For each T ∈ TV , let MT ∈ Fm×m be the matrix of T with respect to the fixed basis B. Let q c = (c1 , . . . , cn ) ∈ C ∩ V n . Since ci ∈ V for all i, one has T (ci ) = 0
for all i = 1, . . . , n.
mat ⊤ Now, by definition of ϕmat B , the i-th column of ϕB (c) is ϕB (ci ) . Since MT is the matrix of the mat Fq -linear map T in the basis B, the i-th column of MT ϕB (c) is
MT ϕB (ci )⊤ = ϕB (T (ci ))⊤ = 0. Therefore every column of MT ϕmat B (c) is zero, and thus MT ϕmat B (c) = 0. Hence n MT ∈ AnnL ϕmat B (C ∩ V ) . Since the map TV −→ Fm×m , q
T 7−→ MT
is injective and Fq -linear, its image is an Fq -subspace of n AnnL ϕmat B (C ∩ V )
of dimension m(m − s). Therefore, n dimFq AnnL ϕmat (C ∩ V ) ⩾ m(m − s). B Let n Cmat := ϕmat B (C ∩ V ).
Since AnnL (Cmat ) ⊆ StabL (Cmat ), it remains to prove that dimFq StabL (Cmat ) ⩾ dimFq AnnL (Cmat ) + 1. If Cmat ̸= {0}, then Im ∈ StabL (Cmat ) but Im ∈ / AnnL (Cmat ), so dimFq StabL (Cmat ) ⩾ dimFq AnnL (Cmat ) + 1 ⩾ m(m − s) + 1. If Cmat = {0}, then StabL (Cmat ) = Fm×m , q so dimFq StabL (Cmat ) = m2 ⩾ m(m − s) + 1, because 0 < s < m. Corollary 4.5 (Generalized coordinate restrictions): Let V1 , . . . , Vn ⊆ Fqm be Fq -subspaces, and set W := V1 × · · · × Vn ,
V := V1 + · · · + Vn .
Assume that V ̸= Fqm , and let r := dimFq (V ). Then, for every Fq -linear code C ⊆ Fnqm , mat dimFq AnnL ϕB (C ∩ W ) ⩾ m(m − r). Consequently, dimFq
StabL ϕmat B (C ∩ W ) 13
⩾ m(m − r) + 1.
Proof. Since each Vi is contained in V , one has W ⊆ V n. Hence C ∩ W ⊆ C ∩ V n. By Item (2) of Theorem 4.4, n dimFq AnnL ϕmat (C ∩ V ) ⩾ m(m − r), B n mat because dimFq (V ) = r < m. Now every matrix that annihilates ϕmat B (C ∩ V ) also annihilates ϕB (C ∩ W ), since mat n ϕmat B (C ∩ W ) ⊆ ϕB (C ∩ V ).
Therefore, n mat AnnL ϕmat B (C ∩ V ) ⊆ AnnL ϕB (C ∩ W ) , and thus
dimFq AnnL ϕmat (C ∩ W ) ⩾ m(m − r). B
The bound on the stabilizer follows from the inclusion AnnL (Cmat ) ⊆ StabL (Cmat ) for every matrix code Cmat . The final claim is immediate. Theorem 4.4 and Corollary 4.5 show that some natural classes of restricted subcodes retain quantitatively large stabilizer or annihilator algebras after expansion to matrix form. Therefore, these families remain algebraically visible from the viewpoint of structural distinguishers. V. A PPLICATIONS IN C RYPTOGRAPHY The structural results obtained in the previous section have direct implications for cryptographic constructions based on rank-metric codes. In particular, the presence of non-trivial stabilizer or annihilator algebras provides potential distinguishers that must be avoided when designing public codes. In this section, we exploit these observations to construct encryption schemes based on λ-Gabidulin codes, using carefully chosen Fq -linear subcodes. A. Selection of Public Subcodes A central design requirement for the public code is to avoid residual algebraic structure that could be exploited by structural distinguishers. In the present setting, the results of the previous section show that this issue is naturally captured by the stabilizer and annihilator algebras of the matrix image of the chosen subcode. Consequently, the main objective is to select Fq -linear subcodes of Gλ (g, k) whose expansion behaves as much as possible like a random matrix code. Recall that any Fq -linear subcode D of Gλ (g, k) can be written in the form D = K ∩ Gλ (g, k), for some Fq -linear code K ⊆ Fnqm . From a cryptographic viewpoint, the choice of K is therefore crucial: depending on this choice, the resulting subcode may either retain detectable algebraic invariants after expansion to matrix form or resemble a generic Fq -linear rank-metric code. Several natural choices of K lead to families that remain too structured for cryptographic use. First, if K is Fqm -linear, then D is itself Fqm -linear, and its matrix image inherits the stabilizer phenomenon classically associated with extension-field linearity. Second, if K = V n for some Fq -subspace V ⊆ Fqm , then D is a subspace subcode, and Theorem 4.4 shows that its matrix image retains explicit algebraic 14
invariants after expansion. More precisely, its right stabilizer remains large in the Gabidulin case, while its left annihilator and left stabilizer admit quantitative lower bounds in the general Fq -linear setting. Third, if K = V1 × · · · × Vn is a generalized subspace restriction and r := dimFq (V1 + · · · + Vn ) < m, then Corollary 4.5 implies that the corresponding matrix code has a left annihilator algebra of dimension at least m(m − r), and hence a nontrivial left stabilizer algebra as well. In all these cases, the public code remains algebraically distinguishable after expansion. These observations suggest excluding such structured families from the public code design. By contrast, random Fq -linear subcodes are not forced a priori to exhibit the stabilizer or annihilator patterns induced by extension-field linearity or coordinate-wise subspace restrictions. They therefore constitute the most promising candidates for constructing public codes that are both cryptographically less distinguishable and flexible enough for practical instantiation. This motivates the generator-matrix approach developed in the next subsection, whose purpose is precisely to produce Fq -linear subcodes with a more random-looking matrix image. B. Toward Random-Looking Fq -Linear Subcodes The discussion of the previous subsection shows that some natural families of subcodes of λ-Gabidulin codes remain algebraically visible after q-ary expansion. This motivates the search for a more flexible construction of Fq -linear subcodes, with fewer a priori structural constraints. To this end, we describe a simple generator-matrix-based construction derived from the q-ary image of an Fqm -linear code. Let C ⊆ Fnqm be an Fqm -linear code of dimension k. Since ϕvec B (C) is an Fq -linear code of dimension vec km, any Fq -linear subcode D ⊆ C gives rise, via ϕB , to an Fq -linear subspace of ϕvec B (C). The next proposition shows that all such subcodes can be obtained by left-multiplying a generator matrix of ϕvec B (C) by a full-rank matrix over Fq . Proposition 5.1: Let B be an Fq -basis of Fqm , C ⊆ Fnqm be an Fqm -linear code of dimension k, and n ′ Gvec ∈ Fkm×mn be a generator matrix of ϕvec q B (C). Let D ⊆ Fq m be an Fq -linear code of dimension k ⩽ km, ′ e ∈ Fk ×mn be a generator matrix of ϕvec (D). Then D is a subcode of C if and only if there exists and let G q B ′ e = P Gvec . a full-rank matrix P ∈ Fkq ×km such that G Proof. Since ϕvec B is an Fq -linear isomorphism, one has D⊆C
⇐⇒
vec ϕvec B (D) ⊆ ϕB (C).
e and Gvec are generator matrices of ϕvec (D) and ϕvec (C), respectively. Therefore, the inclusion Now G B B vec e is an Fq -linear combination of the rows of Gvec . ϕvec (D) ⊆ ϕ (C) holds if and only if each row of G B B ′ Equivalently, there exists a matrix P ∈ Fqk ×km such that e = P Gvec . G e has rank k ′ , the matrix P must also have rank k ′ . Since G Proposition 5.1 provides a convenient parametrization of Fq -linear subcodes of C through the q-ary image ′ ϕvec B (C). In particular, it allows one to prescribe any subcode dimension 1 ⩽ k ⩽ km. This flexibility is useful in comparison with parity-check-based constructions, for which the achievable dimensions are typically more constrained and may depend on additional rank conditions [21], [22]. From a cryptographic viewpoint, this construction is attractive because it makes it possible to avoid, at least at the design level, the structured families discussed in the previous subsection. Indeed, if m does not divide k ′ , then the resulting subcode cannot be Fqm -linear, since every Fqm -linear code has Fq -dimension divisible by m. Moreover, unlike subspace subcodes or generalized subspace restrictions, the present approach does not impose any explicit coordinate-wise restriction pattern. For this reason, choosing P at random yields natural candidates for public codes whose q-ary images may behave more like generic 15
′
matrix codes. More precisely, for a fixed value of k ′ , one may sample a full-rank matrix P ∈ Fkq ×km e = P Gvec . This produces an Fq -linear subcode of C whose matrix uniformly at random and define G image can then be analyzed using Proposition 4.3. Our experiments further support this design choice. For several parameter sets, we fixed a parent λGabidulin code and generated 500 subcodes using the proposed construction. For each generated subcode, we computed the dimensions of the left and right stabilizer algebras of its matrix image. In almost all tested instances, both stabilizers were trivial, that is, of dimension 1. More precisely, this occurred in all tested cases over q ∈ {8, 16} and in all but two tested cases over q = 2, where the empirical probability that the left stabilizer is trivial remained 0.998. Although these experiments were restricted to moderate parameter sizes, they nevertheless provide strong evidence that the proposed construction yields subcodes whose matrix images behave much more like random matrix codes than the structured subcode families discussed above. The SageMath codes used for our simulations are publicly available at https://github.com/Freddy-Lende/Lambda-Gabidulin-and-LGS-Niederreiter-cryptosystem. C. Instantiating the MinRank Encryption Frameworks We now instantiate the McEliece and Niederreiter encryption frameworks in the MinRank setting introduced in [25, Sections 4 and 5], using public codes derived from random-looking Fq -linear subcodes of λ-Gabidulin codes. In both constructions, the secret key is based on a λ-Gabidulin code Gλ (g, k) together with a chosen Fq -basis B of Fqm . The public key is obtained from an Fq -linear subcode D ⊆ Gλ (g, k) ′
of dimension k ′ , constructed through Proposition 5.1 by selecting a full-rank matrix P ∈ Fkq ×km and forming e = P Gvec , G λ vec where Gvec λ is a generator matrix of the expanded code ϕB (Gλ (g, k)). A distinctive feature of our instantiations is that, once the public subcode D has been constructed, no additional masking transformation is applied to derive the public key. In contrast with subcode-based constructions that rely on extra disguising mechanisms or enhanced matrix-code transformations [21], [25], our public key is simply a direct representation of the chosen subcode. More precisely, in the McEliece-like variant, the public key is given by a basis of the matrix code ϕmat B (D), whereas in the Niederreiter-like variant, it is given by a parity-check matrix of the vector code ϕvec B (D). In this respect, the proposed approach is closer in spirit to the original McEliece paradigm, where the public matrix directly describes a Goppa code [4]. We now describe these two instantiations in detail. 1) The LGS-McEliece Cryptosystem: In what follows, we specialize the general construction described above to the McEliece-like MinRank framework of [25, Fig. 2]. We refer to the resulting scheme as the Lambda-Gabidulin Subcode McEliece-like cryptosystem, abbreviated as LGS-McEliece. In this variant, the public code is represented directly by a basis of the matrix code ϕmat B (D), where D ⊆ Gλ (g, k) is an Fq -linear subcode constructed as in Proposition 5.1. a) Key generation: The key generation starts from a secret λ-Gabidulin code Gλ (g, k) and an ′ Fq -basis B of Fqm . A full-rank matrix P ∈ Fkq ×km is then sampled in order to define an Fq -linear subcode D of prescribed dimension k ′ . The public key is obtained by computing a basis of the matrix image ϕmat B (D), while the secret key keeps the compact description of the underlying λ-Gabidulin code together with the basis B. The public rank-weight bound is chosen so as to remain within the decoding capability of the λ-Gabidulin code. The corresponding procedure is summarized in Algorithm 1.
16
Algorithm 1: Key Generation for LGS-McEliece Input: n = m, integers k ⩾ 1 and q a prime power. Output: A public key P K and a secret key SK. ′ ′ 1 Choose an integer k not divisible by m and such that 1 ⩽ k < km. k×n 2 Construct a generator matrix Gλ ∈ Fq m of the λ-Gabidulin code Gλ (g, k). 3 Set n−k −1 , δ = rank(λ ), tpub = 2δ −1 where λ−1 = (λ−1 1 , . . . , λn ). 4 Choose a random Fq -basis B of Fq m . vec vec 5 Compute a generator matrix Gλ of ϕB (Gλ (g, k)). k′ ×km and set 6 Sample a uniformly random full-rank matrix P ∈ Fq
e = P Gvec . G λ vec This matrix generates the Fq -linear subcode ϕvec B (D) ⊆ ϕB (Gλ (g, k)). mat 7 Compute a basis (G1 , . . . , Gk′ ) of ϕB (D). 8 Set P K = (G1 , . . . , Gk′ , tpub ), SK = (B, g, λ, k).
b) Encryption: Encryption follows the standard McEliece paradigm in matrix-code form. The plaintext is viewed as a coefficient vector ′
x = (x1 , . . . , xk′ ) ∈ Fkq , which selects a codeword in the public matrix code generated by (G1 , . . . , Gk′ ). A low-rank error matrix is then generated at random and added to the resulting codeword in order to hide it. Since the public code is given directly by a basis of ϕmat B (D), encryption is particularly simple and amounts to a linear combination in the public basis followed by the addition of a rank-bounded perturbation. This is summarized in Algorithm 2. Algorithm 2: Encryption for LGS-McEliece ′ Input: A plaintext x = (x1 , . . . , xk′ ) ∈ Fkq and P K = (G1 , . . . , Gk′ , tpub ). Output: A ciphertext Y ∈ Fm×n . q m×n 1 Generate an error matrix E ∈ Fq such that rank(E) ⩽ tpub . 2 Compute k′ X Y= xi Gi + E. i=1 3
return Y.
c) Decryption: Decryption uses the secret information of the ambient λ-Gabidulin code rather than the public subcode itself. More precisely, the received matrix is first mapped back to a vector of Fnqm through the inverse expansion map with respect to the secret basis B. The resulting word is then decoded in the secret code Gλ (g, k), whose decoding algorithm corrects up to tpub rank-weight errors, thereby recovering the transmitted codeword of the subcode D. Finally, the plaintext is obtained by expressing the recovered matrix codeword in the public basis (G1 , . . . , Gk′ ). The procedure is given in Algorithm 3. 17
Algorithm 3: Decryption for LGS-McEliece Input: A ciphertext Y ∈ Fm×n , the public basis (G1 , . . . , Gk′ ), and SK = (B, g, λ, k). q ′ Output: A plaintext x = (x1 , . . . , xk′ ) ∈ Fkq . 1 Compute −1 n y = (ϕmat B ) (Y) ∈ Fq m . Decode y in the code Gλ (g, k) and recover the nearest codeword c ∈ Gλ (g, k). Compute C = ϕmat B (c). 4 Recover x = (x1 , . . . , xk′ ) by solving the linear system 2
3
′
C=
k X
xi Gi
i=1
over Fq . 5 return x.
2) The LGS-Niederreiter Cryptosystem: We now specialize the general construction described above to the Niederreiter-like MinRank framework of [25, Fig. 3]. We refer to the resulting scheme as the Lambda-Gabidulin Subcode Niederreiter-like cryptosystem, abbreviated as LGS-Niederreiter. In this variant, the public code is represented directly by a parity-check matrix of the vector code ϕvec B (D), where D ⊆ Gλ (g, k) is an Fq -linear subcode constructed as in Proposition 5.1. a) Key generation: Key generation starts from a secret λ-Gabidulin code Gλ (g, k) and an Fq -basis ′ B of Fqm . A full-rank matrix P ∈ Fkq ×km is then sampled in order to define an Fq -linear subcode D of prescribed dimension k ′ . The public key is obtained by computing a parity-check matrix of the vector image ϕvec B (D), while the secret key keeps the compact description of the underlying λ-Gabidulin code together with the basis B. The public rank-weight bound is chosen so as to remain within the decoding capability of the λ-Gabidulin code. The corresponding procedure is summarized in Algorithm 4. b) Encryption: Encryption follows the standard Niederreiter paradigm in vector form. The information to be transmitted is represented by an error vector e ∈ Fmn whose folded matrix representation has rank q at most tpub . The ciphertext is then obtained as the syndrome of e with respect to the public parity-check e Since the public code is given directly through a parity-check description of ϕvec (D), encryption matrix H. B reduces to a single syndrome computation. This is summarized in Algorithm 5. c) Decryption: Decryption combines the public syndrome description with the secret decoding algorithm of the ambient λ-Gabidulin code. Given a ciphertext s, one first computes any vector y ∈ Fmn q e This vector is then mapped back having syndrome s with respect to the public parity-check matrix H. to Fnqm using the inverse expansion map associated with the secret basis B. Decoding in the secret code Gλ (g, k) yields the nearest codeword c, and the transmitted error is finally recovered by subtracting c and expanding back over Fq . The corresponding procedure is summarized in Algorithm 6. VI. S ECURITY A NALYSIS In this section, we formalize the computational problems underlying the security of the proposed schemes and discuss their cryptographic relevance. We distinguish two main attack directions. Structural attacks aim at recovering the secret key, or an equivalent one, by exploiting residual algebraic properties of the public code. By contrast, decoding attacks treat the public code as essentially random and attempt to recover plaintexts through generic algebraic techniques, which in our setting reduce to solving instances of the MinRank problem.
18
Algorithm 4: Key Generation for LGS-Niederreiter Input: n = m, integers k ⩾ 1 and q a prime power. Output: A public key P K and a secret key SK. ′ ′ 1 Choose an integer k not divisible by m and such that 1 ⩽ k < km . k×n 2 Construct a generator matrix Gλ ∈ Fq m of the λ-Gabidulin code Gλ (g, k). 3 Set n−k −1 , δ = rank(λ ), tpub = 2δ −1 where λ−1 = (λ−1 1 , . . . , λn ). 4 Choose a random Fq -basis B of Fq m . vec vec 5 Compute a generator matrix Gλ of ϕB (Gλ (g, k)). k′ ×km and set 6 Sample a uniformly random full-rank matrix P ∈ Fq
e = P Gvec . G λ vec This matrix generates the Fq -linear subcode ϕvec B (D) ⊆ ϕB (Gλ (g, k)). 7 Compute a parity-check matrix e ∈ F(mn−k′ )×mn H q
of ϕvec B (D). 8 Set e tpub ), P K = (H,
SK = (B, g, λ, k).
Algorithm 5: Encryption for LGS-Niederreiter e tpub ) and an error vector e ∈ Fmn such that rank(Fold(e)) ⩽ tpub . Input: P K = (H, ′
q
. Output: A ciphertext s ∈ Fmn−k q ⊤ e . 1 Compute s = e H 2 return s. Algorithm 6: Decryption for LGS-Niederreiter ′
e and SK = (B, g, λ, k). Input: A ciphertext s ∈ Fmn−k , the public parity-check matrix H, q mn Output: An error vector e ∈ Fq . mn e ⊤ = s. 1 Find any y ∈ Fq such that y H 2 Compute −1 n y′ = (ϕvec B ) (y) ∈ Fq m . Decode y′ in the code Gλ (g, k) and recover the nearest codeword c ∈ Gλ (g, k). ′ ′ 4 Set e = y − c. vec ′ 5 Return e = ϕB (e ). 3
A. Structural Attacks Structural attacks aim at exploiting residual algebraic properties of the public code in order to distinguish it from a random matrix code or to recover the secret key, or an equivalent one. Following the viewpoint of [25, Definitions 17 and 18], we distinguish between a distinguishing task and a search task adapted to the present setting. 19
Definition 6.1 (LGS–Distinguishing Problem): Let Cmat ⊆ Fm×n be a matrix code of dimension k ′ . q The LGS–Distinguishing Problem consists in deciding, with non-negligible advantage, whether Cmat is a subcode of the matrix image of a λ-Gabidulin code or a uniformly random matrix code of the same dimension. Definition 6.2 (LGS–Search Problem): Let m, n, k ′ be positive integers with n ⩽ m, and Cmat ⊆ Fm×n q be a matrix code of dimension k ′ . The LGS–Search Problem consists in recovering, if possible, an Fq -basis B of Fqm and vectors g, λ ∈ Fnqm such that Cmat ⊆ ϕmat B (Gλ (g, k)) . More generally, one may also regard the LGS–Search Problem as that of recovering any equivalent secret ∗ ∗ key tupple (B ∗ , g∗ , λ∗ , k) yielding the same public code. That is to say Cmat ⊆ ϕmat B ∗ (Gλ (g , k)). A successful structural attack would then reveal the hidden λ-Gabidulin structure underlying the public subcode, together with the expansion map induced by the secret basis B, or at least enough information to derive an equivalent secret representation. This motivates the following attack scenarios. a) Stabilizer-Based Attacks and Design Choices: Stabilizer-based techniques provide efficient distinguishers between structured matrix codes of Gabidulin type and generic random matrix codes. Their effectiveness stems from the presence of non-trivial stabilizer algebras, which typically do not occur for random matrix codes but naturally arise in several highly structured families [25], [36]. Although subspace subcodes are only Fq -linear, Theorem 4.4 shows that they may nevertheless admit a non-trivial stabilizer algebra. Likewise, Corollary 4.5 establishes that certain generalized subspace restrictions also possess detectable stabilizers. These observations indicate that a non-trivial stabilizer algebra should be viewed as a structural weakness. For this reason, the public subcodes used in our cryptosystem are chosen so as to avoid such configurations. More precisely, Proposition 4.3 provides an effective test to detect whether a subcode generated at random through Proposition 5.1 admits a non-trivial stabilizer algebra. Whenever such a stabilizer is detected, the subcode is discarded and regenerated. This simple filtering step prevents stabilizer-based distinguishing attacks against the proposed construction. b) Overbeck-Like Distinguisher: When Cpub is an Fq -linear subcode of ϕmat B (G(g, k)), that is, when the ambient secret code is a classical Gabidulin code, the Overbeck-like argument of [25, Sec. 6.1.4] applies. More precisely, using [25, Lemma 2], one obtains, as in [25, Proposition 7 and Corollary 1], a matrix code U ⊆ Fm×m such that q dim Cpub + UCpub ⩽ m(n − 1), for all U ∈ U. By contrast, if Cpub is a random matrix code of dimension k ′ , one expects dim Cpub + UCpub = min(mn, 2k ′ ) with high probability, and in particular mn when mn ⩽ 2k ′ . This yields a structural distinguisher in the Gabidulin case. However, as explained in [25, pp. 22–23], turning this property into an explicit algebraic attack leads to a bilinear system with roughly Θ(m2 ) unknowns and Θ(m2 ) equations, which remains out of reach for the parameter ranges considered in this work. Therefore, although this Overbeck-like property provides a formal structural distinguisher when Cpub ⊆ ϕmat B (G(g, k)), it does not currently lead to a practical attack. The general λ-Gabidulin case is not covered by this argument. c) Generator-Completion Attack: We now formalize a structural attack in which the adversary attempts to complete a generator matrix of the public subcode into a generator matrix of the hidden expanded code. We first record the following lemma. Lemma 6.3: Let C ⊆ Fnqm be an Fqm -linear code of dimension k, and let I ⊆ {1, . . . , n} be an information set of C. Then the km q-ary coordinate positions corresponding to the expansion of the mn coordinates indexed by I form an information set of the expanded code ϕvec B (C) ⊆ Fq . 20
Proof. Let πI : C −→ Fkqm denote the projection onto the coordinates indexed by I. Since I is an information set of C, the map πI is an Fqm -linear isomorphism. Let k km ϕvec B,I : Fq m −→ Fq be the coordinatewise q-ary expansion map with respect to the basis B. This is an Fq -linear isomorphism. Therefore, the composition km ϕvec B,I ◦ πI : C −→ Fq is an Fq -linear isomorphism. This means exactly that the km positions corresponding to the coordinates of the q-ary expansion of the coordinates indexed by I form an information set of ϕvec B (C). vec mn Theorem 6.4: Let Csec = ϕB (Gλ (g, k)) ⊆ Fq and F ⊆ Csec be an Fq -linear subcode of Gλ (g, k), with dimension k ′ . 1) There exist a permutation matrix Q ∈ Fkm×km , q and matrices
′
′
′
A1 ∈ Fkq ×(km−k ) ,
A2 ∈ Fkq ×(mn−km)
such that F admits a generator matrix of the form e = (Ik′ A1 ) Q A2 . G e there exists a unique matrix 2) For any fixed such normal form of G, ′
)×(mn−km) A3 ∈ F(km−k q
such that
b = G
(Ik′ A1 ) Q A2 (0 Ikm−k′ ) Q A3
is a generator matrix of Csec . Proof. Since {1, . . . , k} is an information set of Gλ (g, k), Lemma 6.3 implies that {1, . . . , km} is an information set of Csec . Therefore, if we denote by π : Fmn −→ Fkm the projection onto the first km q q km coordinates, then π|Csec : Csec −→ Fq is an Fq -linear isomorphism. It follows that its restriction to F is injective and we have dimFq π(F) = k ′ . Therefore, π(F) admits a generator matrix of the form (Ik′ A1 ) Q, k′ ×(km−k′ ) for some permutation matrix Q ∈ Fkm×km and some A1 ∈ Fq . Lifting back to F yields q e = (Ik′ A1 ) Q A2 , G k′ ×(mn−km)
where A2 ∈ Fq , which proves the first claim. For the second claim, let 1 ⩽ j ⩽ km − k ′ ,
uj = (0 ej ) Q ∈ Fkm q , ′
where ej is the jth standard basis vector of Fkm−k . Since π|Csec : Csec −→ Fkm is bijective, each uj has a q q unique preimage cj ∈ Csec . Let the last mn − km coordinates of cj form the jth row of a matrix ′
)×(mn−km) A3 ∈ F(km−k . q
Then all rows of
b = G
(Ik′ A1 ) Q A2 (0 Ikm−k′ ) Q A3 21
belong to Csec . b formed by its first km columns has rank km. Hence the rows of G b are Moreover, the submatrix of G b linearly independent. Since dimFq (Csec ) = km, G generates Csec . Uniqueness follows again from the bijectivity of π|Csec . Once e = (Ik′ A1 ) Q A2 G is fixed, each vector (0 ej )Q has a unique preimage in Csec , hence each row of A3 is uniquely determined. Theorem 6.4 shows that, once a normal form of the public subcode has been fixed, recovering the hidden expanded code amounts to recovering the unique matrix A3 . e = (Ik′ A1 ) Q A2 of the public subcode The attack therefore consists in fixing a generator matrix G e in the normal form of Theorem 6.4, and then do an exhaustive search on′ A3 in order to complete G ′ )(mn−km) (km−k )×(mn−km) (km−k b Note that the number of candidate matrices for A3 ∈ Fq to have G. is q . Consequently, an exhaustive completion-search attack requires ′
q (km−k )(mn−km) candidate tests, up to polynomial factors and the cost of the distinguisher used to validate each candidate. This generator-completion attack primarily recovers the hidden expanded code Csec , and therefore already distinguishes the public subcode from a random code. Combined with a reconstruction procedure for q-ary images, such as those considered in [21], it may also lead to an equivalent secret description. For distinguishing purposes, however, one can reduce the cost of the completion search by puncturing the public subcode and keeping only k + 1 extension-field coordinates. This is in the same spirit as the puncturing-based dimension reduction used in [25] in the context of structural distinguishers. vec ′ Corollary 6.5: Let F = ϕvec B (D) ⊆ Csec = ϕB (Gλ (g, k)) be the public subcode, of dimension k . Let m(k+1) F pun ⊆ Fq be the puncturing of F obtained by keeping only the first k + 1 extension-field coordinates, i.e., the first m(k + 1) q-ary coordinates. Then dimFq (F pun ) = k ′ , and F pun is an Fq -linear subcode of ′ ′ ′ ϕvec B (Gλ′ (g , k)), where g and λ denote the truncations of g and λ to their first k + 1 entries. Consequently, Theorem 6.4 applies with n replaced by k + 1, so that the completion search space drops to ′ Cdist = q m(km−k ) . Proof. By Lemma 6.3, the first km q-ary coordinates form an information set of Csec = ϕvec B (Gλ (g, k)) . Hence the projection onto the first m(k + 1) q-ary coordinates is injective on Csec , and therefore also on its subcode F. It follows that dimFq (F pun ) = dimFq (F) = k ′ . Moreover, puncturing Gλ (g, k) on the last n − k − 1 extension-field coordinates yields the λ′ -Gabidulin ′ code Gλ′ (g′ , k) of length k+1. Thus F pun is an Fq -linear subcode of ϕvec B (Gλ′ (g , k)). Applying Theorem 6.4 with length k + 1 gives an unknown block A3 of size (km − k ′ ) × m(k + 1) − km = (km − k ′ ) × m, ′
hence q m(km−k ) candidates. Thus, while the full completion attack is naturally viewed as a recovery attack for the hidden expanded code, its punctured version provides a strictly cheaper structural distinguisher.
22
B. Decoding Attacks We begin by recalling the MinRank problem. Definition 6.6 (MinRank problem): Let q be a prime power and let m, n, K, r ∈ N. Given matrices , A1 , . . . , AK ∈ Fm×n q the MinRank(q, m, n, K, r) problem consists in finding scalars x1 , . . . , xK ∈ Fq such that ! K X rank xi Ai ⩽ r. i=1
Decoding a matrix code can be reduced to an instance of the MinRank problem [37]. The corresponding decision problem was shown to be NP-complete in [38]. The MinRank problem is therefore commonly used as a hardness assumption in code-based cryptography [25], [39], [40]. In the present setting, once the public code is assumed to behave like a random matrix code, message recovery attack reduces to solving a generic instance of the MinRank(q, m, n, K, r) problem, with r = tpub
and
K = k ′ + 1.
We now review the main generic attacks considered in our estimates. a) The Kernel Attack: The kernel attack introduced in [41] is one of the standard generic approaches for solving MinRank instances. Its principle is to sample vectors in the right ambient space and to retain those that lie in the kernel of the unknown matrix K X
xi A i
i=1
of rank at most r. Each such vector yields a linear equation in the unknown coefficients, and once sufficiently many of them have been found, one obtains a solvable linear system. Its complexity is Cker = O q r⌈K/m⌉ K ω , where ω denotes the linear algebra constant. In our estimates, we take ω = 2.38, which is a convenient rounded value for the Coppersmith–Winograd matrix-multiplication exponent [42]. b) The Support Minors Attack: The support-minors approach, introduced in [43], provides an algebraic system for solving MinRank instances. The complexity expression is taken under the rank assumption on the corresponding Macaulay matrix given in [43], [44]. It is then given by Calg = O min Eb (q, m, n, K, r) Ub (q, m, n, K, r)ω−1 , K(r + 1) Eb (q, m, n, K, r) Ub (q, m, n, K, r) where b is the smallest positive integer such that 1⩽b<r+2
and
Ub (q, m, n, K, r) − 1 ⩽ Eb (q, m, n, K, r),
b X
i+1
and where: If q > 2, then Eb (q, m, n, K, r) :=
i=1
and
(−1)
n m+i−1 K +b−i−1 , r+i i b−i
K +b−1 n Ub (q, m, n, K, r) := . b r 23
,
If q = 2, then j b X X n m+i−1 K i+1 , (−1) Eb (q, m, n, K, r) := r+i i j−i j=1 i=1 and
b X n K Ub (q, m, n, K, r) := . r j j=1
Here, ab denotes the binomial coefficient. c) The Hybrid Approach: To improve the efficiency of attacks against the MinRank problem, a generic hybrid strategy was proposed in [45]. The idea is to reduce the original instance to several smaller sub-instances that can be solved more efficiently. Let A be an algorithm for solving the MinRank problem, and let T CA(q,m,n,K,r) denote its time complexity on an instance with parameters (q, m, n, K, r). Using the hybrid technique of [45], the resulting complexity becomes T CA-hybrid(q,m,n,K,r) = min q ar · T CA(q,m,n−a,K−am,r) . 0⩽a<⌈K/m⌉
d) A Subsupport-Reduction Hybrid Approach: A recent idea, introduced in [46] in the context of the Rank Decoding problem, is to use subsupport reduction as a preprocessing step. We combine this reduction with the generic hybrid strategy recalled above. The main idea is to guess a subsupport, that is, an h-dimensional subspace contained in the rank support of the unknown low-rank solution. This guess reduces the MinRank instance from parameters (q, m, n, K, r) to (q, m, n − h, K, r − h) before applying a solver to the reduced instance. Let A be an algorithm for solving the MinRank problem, and let T CA(q,m,n,K,r) denote its time complexity on an instance with parameters (q, m, n, K, r). In our MinRank adaptation, we model the average cost of the subsupport-reduction step by Csub-red = O q h(n−r) · T CA(q,m,n−h,K,r−h) . Combining this reduction with the hybrid strategy of [45] yields the complexity Cnew-hyb =
min
(a,h)∈B ′ (q,m,n,K,r)
q h(n−r)+a(r−h) · T CA(q,m,n−h−a,K−am,r−h) ,
where we set B ′ (q, m, n, K, r) = {0, . . . , ⌈K/m⌉ − 1} × {0, . . . , r − 1}. When A is instantiated with the support-minors attack SM, by letting 0 ⩽ a < K , 0 ⩽ h < r, and m 1 ⩽ b < r − h + 2, we define n B(q, m, n, K, r) := (a, b, h) ; Ub (q, m, n − a − h, K − am, r − h) − 1 o ⩽ Eb (q, m, n − a − h, K − am, r − h) . Then, Cnew-hyb-SM = O(min{Cnew-hyb-SM1 , Cnew-hyb-SM2 }) , where Cnew-hyb-SM1 = O
min
q h(n−r)+a(r−h)
(a,b,h)∈B(q,m,n,K,r)
· Eb (q, m, n − h − a, K − am, r − h) ω−1
· Ub (q, m, n − h − a, K − am, r − h) 24
,
and Cnew-hyb-SM2 = O
q h(n−r)+a(r−h) (K − am)(r − h + 1)
min
(a,b,h)∈B(q,m,n,K,r)
· Eb (q, m, n − h − a, K − am, r − h) · Ub (q, m, n − h − a, K − am, r − h) . When A is instantiated with the kernel attack ker, the resulting complexity is h(n−r)+a(r−h) (r−h)⌈(K−am)/m⌉ ω Cnew-hyb-ker = O min q q (K − am) . ′ (a,h)∈B (q,m,n,K,r)
Finally, taking into account the distinguishing complexity Cdist given in Corollary 6.5, the overall work factor is Cf = min Cnew-hyb-SM , Cnew-hyb-ker , Cdist , (3) where r = tpub and K = k ′ + 1. VII. P ROPOSED PARAMETERS In this section, we propose parameter sets for the LGS-Niederreiter cryptosystem. Let G(g, k) denote the Gabidulin code associated with the λ-Gabidulin code Gλ (g, k), and let δ = rank(λ−1 ), Then
−1 λ−1 = (λ−1 1 , . . . , λn ).
n−k tpub = . 2δ
The proposed parameter sets are selected according to the attack complexities discussed in the previous section. A. Parameters for the LGS-Niederreiter Cryptosystem As in [25], we focus on the Niederreiter variant in order to minimize the ciphertext size. The public key consists mainly of a systematic parity-check matrix of the public code, and can therefore be stored using k ′ (mn − k ′ ) log2 (q) bits. The ciphertext size is (mn − k ′ ) log2 (q) bits. Tables I, II, and III provide some parameter sets for 128-, 192-, and 256-bit security levels, together with the corresponding values of Cf from (3). The two last columns of the tables contains the public key and ciphertext sizes. TABLE I LGS-N IEDERREITER : 128 BITS SECURITY q
δ
m=n
k
k′
tpub
Cf
pk (kB)
ct (B)
2 8 2 16 2 2 8
1 1 1 1 1 2 2
38 20 34 17 32 46 30
30 14 24 11 18 30 18
1125 270 800 183 564 1360 528
4 3 5 3 7 4 3
131 135 131 142 137 132 145
44.86 13.16 35.60 9.70 32.43 128.52 73.66
40 49 45 53 58 95 140
25
TABLE II LGS-N IEDERREITER : 192 BITS SECURITY q
δ
m=n
k
k′
tpub
Cf
pk (kB)
ct (B)
8 16 2 16 2 8
1 1 1 1 2 2
27 23 39 21 62 37
21 17 23 11 46 25
557 381 880 221 2822 910
3 3 8 5 4 3
199 213 195 213 196 203
35.93 28.19 70.51 24.31 360.51 156.63
65 74 81 110 128 173
TABLE III LGS-N IEDERREITER : 256 BITS SECURITY q
δ
m=n
k
k′
tpub
Cf
pk (kB)
ct (B)
2 2 2 8 16 8
1 1 1 1 1 2
59 47 49 27 24 44
49 31 35 17 14 32
2881 1434 1695 447 324 1388
5 8 7 5 5 3
259 260 257 265 276 269
216.07 138.92 149.58 47.27 40.82 285.23
75 97 89 106 126 206
B. Comparison with Other Schemes In the following, we compare the public key and ciphertext sizes of our scheme with those of other encryption schemes. The comparisons are summarized in tables IV, V, and VI where we compare representative instances of LGS-Niederreiter with several related cryptosystems such as EGMC-Niederreiter Cryptosystem [25] based on expanded codes, MinRankPKE [47], Modification I of Loidreau’s cryptosystem [22] and Cryptosystem Based on Equivalent of Subcodes of Gabidulin Matrix Codes (Cryptosystem BESG) [48] at 128-, 192-, and 256-bit security levels. TABLE IV C OMPARISON WITH OTHER CRYPTOSYSTEMS , SECURITY: 128 BITS Cryptosystems
pk (kB) ct (B)
LGS-Niederreiter LGS-Niederreiter Cryptosystem BESG [21] EGMC-Niederreiter [49] Classic McEliece [50] Modification I of Loidreau’s cryptosystem [22] RQC-Block-NH-MS-AG [51] BIKE [52] RQC-NH-MS-AG [53] MinRankPKE [47]
44.86 40 9.70 53 11.30 54 97.82 65 261.12 96 3.67 105 0.31 1118 1.54 1572 0.42 2288 14.70 14158
For all parameter sets considered here, LGS-Niederreiter achieves the smallest ciphertext size among the compared schemes. Moreover, some of the proposed parameter sets provide a favorable public-key/ciphertext trade-off compared with MinRankPKE, EGMC-Niederreiter, BESG cryptosystem, and Classic McEliece. These results indicate that LGS-Niederreiter is a promising option for communication-constrained settings.
26
TABLE V C OMPARISON WITH OTHER CRYPTOSYSTEMS , SECURITY: 192 BITS Cryptosystems
pk (kB)
ct (B)
LGS-Niederreiter LGS-Niederreiter EGMC-Niederreiter [49] Classic McEliece [50] Modification I of Loidreau’s cryptosystem [22] RQC-Block-NH-MS-AG [51] BIKE [52] RQC-NH-MS-AG [53] MinRankPKE [47]
35.93 28.19 267.80 524.16 5.48 0.62 3.08 0.98 35.37
65 74 89 156 457 2278 3024 3753 35365
TABLE VI C OMPARISON WITH OTHER CRYPTOSYSTEMS , SECURITY: 256 BITS Cryptosystems
pk (kB)
ct (B)
LGS-Niederreiter 216.07 LGS-Niederreiter 47.27 EGMC-Niederreiter [49] 274.29 Classic McEliece [50] 1 044.99 Cryptosystem BESG [21] 136.58 Modification I of Loidreau’s cryptosystem [22] 8.70 BIKE [52] 5.12 MinRankPKE [47] 62.89
75 106 139 208 265 622 5153 62700
VIII. C ONCLUSION In this paper, we studied subcodes of λ-Gabidulin codes and analyzed their suitability for cryptographic use. We showed that several natural families of subcodes may retain visible algebraic invariants after q-ary expansion, which makes them poor candidates for public-key design. This led us to focus on random-looking Fq -linear subcodes obtained through a simple generator-matrix construction. Using this construction, we proposed McEliece-like and Niederreiter-like encryption schemes in the MinRank setting. We then analyzed their security against structural and generic decoding attacks, including stabilizer-based distinguishers, an Overbeck-like distinguisher, generator-completion attacks, and the best currently known MinRank attacks. This analysis allowed us to derive concrete parameters for the LGS-Niederreiter cryptosystem. The resulting scheme achieves very compact ciphertexts while keeping public-key sizes competitive with those of related proposals. Overall, our results suggest that Fq -linear subcodes of λ-Gabidulin codes provide a promising framework for rank-metric encryption. Several questions remain open. In particular, it would be valuable to obtain sharper structural criteria for random Fq -linear subcodes, especially to better understand when their matrix images behave like random matrix codes. Another important direction is to clarify the complexity of recovering a hidden parent expanded code, or an equivalent description, from a public subcode. More broadly, it would be interesting to determine whether the same approach can be extended to other structured rank-metric primitives.
R EFERENCES [1] P. Delsarte, “Bilinear forms over a finite field, with applications to coding theory,” J. Comb. Theory, Ser. A, vol. 25, no. 3, pp. 226–241, 1978. [2] È. M. Gabidulin, “Theory of codes with maximum rank distance,” Problemy Peredachi Informatsii, vol. 21, no. 1, pp. 3–16, 1985. [3] E. M. Gabidulin, A. V. Paramonov, and O. V. Tretjakov, “Ideals over a non-commutative ring and their applications to cryptography,” in Advances in Cryptology - EUROCRYPT’91, ser. Lecture Notes in Comput. Sci., no. 547, Brighton, Apr. 1991, pp. 482–489.
27
[4] R. J. McEliece, A Public-Key System Based on Algebraic Coding Theory. Jet Propulsion Lab, 1978, pp. 114–116, dSN Progress Report 44. [5] S. Puchinger, J. Renner, and J. Rosenkilde, “Generic decoding in the sum-rank metric,” IEEE Transactions on Information Theory, vol. 68, no. 8, pp. 5075–5097, 2022. [6] M. Gadouleau and Z. Yan, “Properties of codes with the rank metric,” in Proceedings of IEEE Global Telecommunications Conference (GLOBECOM), 2006. [7] H. Bartz, L. Holzbaur, H. Liu, S. Puchinger, J. Renner, and A. Wachter-Zeh, “Rank-metric codes and their applications,” Foundations and Trends in Communications and Information Theory, vol. 19, no. 3, pp. 390–546, 2022. [8] J. K. Gibson, “Severely denting the Gabidulin version of the McEliece public key cryptosystem,” Designs, Codes and Cryptography, vol. 6, no. 1, pp. 37–45, 1995. [9] R. Overbeck, “A new structural attack for GPT and variants,” in Mycrypt, ser. Lecture Notes in Comput. Sci., vol. 3715, 2005, pp. 50–63. [10] ——, “Structural attacks for public key cryptosystems based on Gabidulin codes,” J. Cryptology, vol. 21, no. 2, pp. 280–301, 2008. [11] A. Otmani, H. T. Kalachi, and S. Ndjeya, “Improved cryptanalysis of rank metric schemes based on Gabidulin codes,” Designs, Codes and Cryptography, vol. 86, no. 9, pp. 1983–1996, 2018. [12] A.-L. Horlemann-Trautmann, K. Marshall, and J. Rosenthal, “Extension of Overbeck’s attack for Gabidulin-based cryptosystems,” Designs, Codes and Cryptography, vol. 86, pp. 319–340, 2018. [13] H. T. Kalachi, “On the failure of the smart approach of the GPT cryptosystem,” Cryptologia, vol. 46, no. 2, pp. 167–182, 2022. [14] A. Couvreur, P. Gaborit, V. Gauthier-Umaña, A. Otmani, and J.-P. Tillich, “Distinguisher-based attacks on public-key cryptosystems using Reed-Solomon codes,” Des. Codes Cryptogr., vol. 73, no. 2, pp. 641–666, 2014. [Online]. Available: http://dx.doi.org/10.1007/s10623-014-9967-z [15] P. Delsarte, “On subfield subcodes of modified Reed–Solomon codes,” IEEE Transactions on Information Theory, vol. 21, no. 5, pp. 575–576, 1975. [16] V. Weger, N. Gassner, and J. Rosenthal, “A survey on code-based cryptography,” 2022. [17] E. M. Gabidulin and P. Loidreau, “On subcodes of codes in rank metric,” in Proceedings. International Symposium on Information Theory, 2005. ISIT 2005. IEEE, 2005, pp. 121–123. [18] ——, “Properties of subspace subcodes of Gabidulin codes,” Advances in Mathematics of Communications, vol. 2, no. 2, p. 147, 2008. [19] E. M. Gabidulin and N. I. Pilipchuk, “Rank subcodes in multicomponent network coding,” Problems of information transmission, vol. 49, no. 1, pp. 40–53, 2013. [20] S. Liu, C. Xing, and C. Yuan, “List decodability of random subcodes of Gabidulin codes,” IEEE Transactions on Information Theory, vol. 63, no. 1, pp. 159–163, 2016. [21] T. P. Berger, P. Gaborit, and O. Ruatta, “Gabidulin matrix codes and their application to small ciphertext size cryptosystems,” in Progress in Cryptology–INDOCRYPT 2017: 18th International Conference on Cryptology in India, Chennai, India, December 10-13, 2017, Proceedings 18. Springer, 2017, pp. 247–266. [22] W. Guo and F.-W. Fu, “Two modifications for Loidreau’s code-based cryptosystem,” Applicable Algebra in Engineering, Communication and Computing, vol. 35, no. 5, pp. 647–665, 2024. [23] T. S. C. Lau and C. H. Tan, “A new Gabidulin-like code and its application in cryptography,” in International Conference on Codes, Cryptology, and Information Security. Springer, 2019, pp. 269–287. [24] É. Burle, H. T. Kalachi, F. L. Metouke, and A. Otmani, “Security assessment of the LG cryptosystem,” Applicable Algebra in Engineering, Communication and Computing, vol. 37, no. 1, pp. 187–198, 2026. [25] N. Aragon, A. Couvreur, V. Dyseryn, P. Gaborit, and A. Vinçotte, “MinRank Gabidulin encryption scheme on matrix codes,” in International Conference on the Theory and Application of Cryptology and Information Security. Springer, 2024, pp. 68–100. [26] R. Horn and C. R. Johnson, “Topics in matrix analysis cambridge university press cambridge,” UK Google Scholar, 1991. [27] P. Delsarte, “On subfield subcodes of modified Reed-Solomon codes (corresp.),” IEEE Transactions on Information Theory, vol. 21, no. 5, pp. 575–576, 2003. [28] H. Stichtenoth, “Subfield subcodes and trace codes,” Algebraic Function Fields and Codes, pp. 311–326, 2009. [29] M. Hattori, R. J. McEliece, and G. Solomon, “Subspace subcodes of Reed-Solomon codes,” IEEE Transactions on Information Theory, vol. 44, no. 5, pp. 1861–1880, 2002. [30] A. Couvreur and M. Lequesne, “On the security of subspace subcodes of Reed–Solomon codes for public key encryption,” IEEE Transactions on Information Theory, vol. 68, no. 1, pp. 632–648, 2021. [31] O. Ndiaye, P. A. Kidoudou, and H. T. Kalachi, “Generalized subspace subcodes in the rank metric,” arXiv preprint arXiv:2301.12523, 2023. [32] S. Lang, Algebra. Springer Science & Business Media, 2012, vol. 211. [33] O. Ore, “Theory of non-commutative polynomials,” Annals of mathematics, vol. 34, no. 3, pp. 480–508, 1933. [34] ——, “On a special class of polynomials,” Transactions of the American Mathematical Society, vol. 35, no. 3, pp. 559–584, 1933. [35] B. R. McDonald, “Finite rings with identity,” (No Title), 1974. [36] A. Porwal, A. Wachter-Zeh, and P. Loidreau, “Improved key attack on the minrank encryption scheme based on matrix codes,” Cryptology ePrint Archive, 2025. [37] J.-C. Faugere, F. Levy-dit Vehel, and L. Perret, “Cryptanalysis of minrank,” in Annual International Cryptology Conference. Springer, 2008, pp. 280–296. [38] J. F. Buss, G. S. Frandsen, and J. O. Shallit, “The computational complexity of some problems of linear algebra,” Journal of Computer and System Sciences, vol. 58, no. 3, pp. 572–596, 1999. [39] A. Petzoldt, M.-S. Chen, B.-Y. Yang, C. Tao, and J. Ding, “Design principles for HFEv-based multivariate signature schemes,” in Advances in Cryptology–ASIACRYPT 2015: 21st International Conference on the Theory and Application of Cryptology and Information Security, Auckland, New Zealand, November 29–December 3, 2015, Proceedings, Part I 21. Springer, 2015, pp. 311–334.
28
[40] W. Beullens, “Improved cryptanalysis of uov and rainbow,” in Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, 2021, pp. 348–373. [41] L. Goubin and N. T. Courtois, “Cryptanalysis of the TTM cryptosystem,” in Advances in Cryptology—ASIACRYPT 2000: 6th International Conference on the Theory and Application of Cryptology and Information Security Kyoto, Japan, December 3–7, 2000 Proceedings 6. Springer, 2000, pp. 44–57. [42] D. Coppersmith and S. Winograd, “Matrix multiplication via arithmetic progressions,” in Proceedings of the nineteenth annual ACM symposium on Theory of computing, 1987, pp. 1–6. [43] M. Bardet and M. Bertin, “Improvement of algebraic attacks for solving superdetermined minrank instances,” in International Conference on Post-Quantum Cryptography. Springer, 2022, pp. 107–123. [44] M. Bros, “Algebraic cryptanalysis and contributions to post-quantum cryptography based on error-correcting codes in the rank-metric,” Ph.D. dissertation, Université de Limoges, 2022. [45] M. Bardet, P. Briaud, M. Bros, P. Gaborit, and J.-P. Tillich, “Revisiting algebraic attacks on minrank and on the rank decoding problem,” Designs, Codes and Cryptography, vol. 91, no. 11, pp. 3671–3707, 2023. [46] H. Beeloo-Sauerbier Couvée, A. Wachter-Zeh, and V. Weger, “Hybrid subsupport guessing: A new hybrid technique for the rank decoding problem,” in Post-Quantum Cryptography, M. Bardet and R. Niederhagen, Eds. Cham: Springer Nature Switzerland, 2026, pp. 130–155. [47] T. Debris-Alazard, P. Gaborit, R. Neveu, and O. Ruatta, “A minrank-based encryption scheme\a la alekhnovich-regev,” arXiv preprint arXiv:2510.07584, 2025. [48] T. P. Berger, C. T. Gueye, and J. B. Klamti, “A NP-complete problem in coding theory with application to code based cryptography,” in International Conference on Codes, Cryptology, and Information Security. Springer, 2017, pp. 230–237. [49] A. Vinçotte, “Protocoles cryptographiques basés sur les codes correcteurs d’erreur en métrique rang,” Ph.D. dissertation, Université de Limoges, 2025. [50] D. J. Bernstein, T. Chou, T. Lange, I. von Maurich, R. Misoczki, R. Niederhagen, E. Persichetti, C. Peters, P. Schwabe, N. Sendrier et al., “Classic McEliece: conservative code-based cryptography,” NIST submissions, vol. 1, no. 1, pp. 1–25, 2017. [51] N. Aragon, P. Briaud, V. Dyseryn, P. Gaborit, and A. Vinçotte, “The blockwise rank syndrome learning problem and its applications to cryptography,” in International Conference on Post-Quantum Cryptography. Springer, 2024, pp. 75–106. [52] C. A. Melchor, N. Aragon, P. Barreto, S. Bettaieb, L. Bidoux, O. Blazy, J.-C. Deneuville, P. Gaborit, S. Gueron, T. Güneysu et al., “Bike,” First round submission to the NIST post-quantum cryptography call, 2017. [53] L. Bidoux, P. Briaud, M. Bros, and P. Gaborit, “RQC revisited and more cryptanalysis for rank-based cryptography,” IEEE Transactions on Information Theory, 2023.
29