Distinguishers for Skew and Linearized Reed–Solomon Codes Felicitas Hörmann1,2
and Anna-Lena Horlemann2
1
arXiv:2604.12954v1 [cs.CR] 14 Apr 2026
Institute of Communications and Navigation, German Aerospace Center (DLR), Oberpfaffenhofen–Wessling, Germany [email protected] 2 Institute of Computer Science, University of St.Gallen, St. Gallen, Switzerland [email protected]
Abstract. Generalized Reed–Solomon (GRS) and Gabidulin codes have been proposed for various code-based cryptosystems, though most such schemes without elaborate disguising techniques have been successfully attacked. Both code classes are prominent examples of the isometric families of (generalized) skew and linearized Reed–Solomon ((G)SRS and (G)LRS) codes which are obtained as evaluation codes from skew polynomials. Both GSRS and GLRS codes share the advantage of achieving the maximum possible error-decoding radius and thus promise smaller key sizes than e.g. Classic McEliece. We investigate whether these generalizations can avoid the known structural attacks on GRS and Gabidulin codes. In particular, we prove that both GSRS and GLRS codes decompose into GRS subcodes and are thus efficiently distinguishable from random codes with a square code method. This applies to all parameters for which the code length n and its dimension k over the field Fqm satisfy m + 1 < k < n − 21 (m2 + 3m). The distinguishability extends to GSRS and GLRS codes with Hammingisometric disguising. We further relate these findings to existing distinguishers for GRS, Gabidulin, and LRS codes, and extend known results on duals of SRS and LRS codes to the generalized setting allowing nonzero column multipliers. Finally, we provide explicit transformations between GSRS and GLRS codes, clarifying the algebraic relationship between the skew and linearized frameworks. Keywords: code-based cryptography, evaluation codes, skew polynomials, distinguishers
1
Introduction
Post-quantum cryptography. We have known for decades that quantum computers pose a threat for current public key cryptography based on integer factorization or variants of the discrete logarithm problem. This awareness lead to the emergence of the field of post-quantum cryptography (PQC), which studies alternative security assumptions and develops cryptographic algorithms that resist
both classical and quantum attacks. Since there has been tremendous progress in quantum computing and store-now-decrypt-later attacks constitute an additional risk, the transition to PQC is not only a crucial but also a time-pressing matter. For instance, Germany’s Federal Office for Information Security (BSI) conservatively estimates in its 2024 status report on quantum computing that cryptographically relevant quantum computers will become available by around 2040 [55]. The U.S. National Institute of Standards and Technology (NIST) started a PQC standardization project by publishing a call for quantum-resistant algorithms in late 2016. While the branch for standardizing digital signature algorithms (DSAs) is still ongoing, the part dealing with key-encapsulation mechanisms (KEMs) recently came to an end. There, NIST selected the lattice-based CRYSTALS-Kyber after three rounds in 2022 and the code-based HQC after the fourth round in 2025 [1]. Code-based cryptography. McEliece pioneered the field of code-based cryptography with his seminal paper [38] in 1978. There, Alice picks a linear code with an efficient decoding algorithm and publishes a random-looking generator matrix of an equivalent code as public key. Bob then encrypts a message by encoding it and adding a random correctable error. Since Alice knows an efficient decoder for the secret code, she can decrypt successfully, while the adversary Eve faces the hard problem of decoding in a seemingly random code. Note that Eve’s problem is in fact NP-complete if the input code is arbitrary and gets decoded by means of a maximum-likelihood decoder [6,5]. Niederreiter followed a somewhat dual approach when he proposed another cryptosystem based on algebraic codes in [40]. In his framework, the public key is a random-looking parity-check matrix of the secret code and the ciphertexts are syndromes. Both formulations were shown to be equivalent from a security point of view [28] and we usually include both variants when referring to McEliece-like schemes for simplicity. The major shortcoming of McEliece-like systems are their large keys, and the literature recorded numerous suggestions to improve upon this in the last decades. Most proposals use strategies like more advanced disguising techniques or alternative decoding metrics, or they employ other code families. While the original McEliece system guarantees correct decryption, proposals such as HQC and BIKE use decoders with decoding failures. The resulting decryption failures require a careful analysis and potentially lead to side-channel vulnerabilities. Unfortunately, most of the systems employing algebraic codes with non-failing decoders and isometric disguising were broken by structural attacks which allow to recover the secret code structure from the public key. Cryptosystems using generalized Reed–Solomon and Gabidulin codes. Prominent choices for algebraic code families are generalized Reed–Solomon (GRS) codes in the Hamming metric and their rank-metric analogs, that is, Gabidulin codes. Both classes of codes exhibit the highest possible unique decoding radius and have efficient decoders. As a consequence, the public keys of respective cryptosystems are expected to be small due to the rising cost of information-set 2
decoding (ISD) for a growing error weight. Another argument for GRS and Gabidulin codes is their compact algebraic representation as evaluation codes which yields small secret keys. In the following, we focus on schemes based on the unique decoding of GRS and Gabidulin codes, and exclude proposals using e.g. interleaved codes, subcode constructions, or list-decoding problems. Structural attacks on GRS codes. Niederreiter developed the first McEliece-like scheme based on GRS codes [40] but Sidelnikov and Shestakov showed that the secret code parameters can be recovered from the isometrically disguised generator matrix, i.e., from the public key [51]. Wieschebrink introduced additional random columns in the public scrambled generator matrix to mitigate this attack [53], yet the system was broken by the square code distinguisher [54,11]. Indeed, the distinguisher allows to extract the GRS columns from the public key and thus makes the scheme susceptible to Sidelnikov–Shestakov’s attack. The BBCRS scheme [4] mitigates structural attacks with a special disguising technique which amplifies the Hamming weight of the error for the attacker but keeps it decodable for the legitimate receiver. Its updated parameter sets appear to be still secure after the attack from [12] broke all initial parameter suggestions. Structural attacks on Gabidulin codes. The GPT system [15] was the start of a series of cryptosystems based on Gabidulin codes [16,49]. Unfortunately, the attacking side was strong and many of these proposals were broken by Gibsons’s attacks [17,18] as well as by Overbeck’s attack [46,45,47] and its extensions [19,20,44]. In contrast to these schemes, Loidreau’s cryptosystem [32,33] employs Gabidulin codes but hides their structure by means of rank amplifiers. Some of the originally chosen parameter sets were broken by the Coggia– Couvreur attack [10] but new parameter choices fixed the vulnerability. Recently, a generalization of the system was presented in [42]. Skew evaluation codes. GRS and Gabidulin codes are special cases of the isometric families of generalized skew Reed–Solomon (GSRS) and generalized linearized Reed–Solomon (GLRS) codes (see [35] for example), which are both obtained as evaluation codes from skew polynomial rings. The efficient decoding of these codes was showcased by means of various decoding techniques in e.g. [8,30,37]. GSRS and GLRS codes are maximum distance separable (MDS) and thus promising for reducing the key size in cryptographic applications while potentially being resistant against the known structural attacks against GRS and Gabidulin codes. Within this research direction, e.g. the distinguishing of GLRS codes under isometric disguising was studied in [22]. The main result was an Overbeck-like distinguisher whose complexity is polynomial-time only for trivial column multipliers and partial knowledge of the secret code parameters. Further, a cryptosystem based on GLRS codes with trivial column multipliers was introduced recently [41]. The proposal does not use isometric disguising but hides the secret code structure by means of low-dimensional subspaces similar to Loidreau’s idea for Gabidulin codes. 3
Contributions. We study the algebraic structure and the distinguishability of skew evaluation codes with the goal of understanding if they are promising candidates for McEliece-like cryptosystems with isometric disguising. In particular, we show that generalized skew Reed–Solomon (GSRS) codes and generalized linearized Reed–Solomon (GLRS) codes can be expressed as the direct sum of GRS codes and thus have a predictable square code dimension. This structural perspective yields a polynomial-time distinguisher for GSRS and GLRS codes over Fqm , as long as their dimension k and length n satisfy m + 1 < k < n − 12 (m2 + 3m). The results also carry over to codes disguised by Hamming-metric isometries. We try to give a comprehensive overview of the connections between the isometric GSRS and GLRS codes as well as the relations to their special cases of GRS and Gabidulin codes. Thus, we compare our results to known distinguishers and also enhance known results on the duals of GSRS and GLRS codes for trivial column multipliers to the general setting. Outline. After this introduction, we start the paper by collecting useful preliminaries about codes and skew polynomials in Section 2. Section 3 introduces GSRS and GLRS codes, gives results about their duals, and highlights GRS and Gabidulin codes as special cases. The end of the section explains the connection between the distinguishing problem and security in code-based cryptography. In Section 4, we show that GSRS and GLRS codes can be decomposed into GRS subcodes. This implies the existence of a square code distinguisher which we present in Section 5. We discuss connections to known distinguishers for GRS, Gabidulin, and linearized Reed–Solomon (LRS) codes in Section 6 and showcase experimental results in Section 7. Finally, we give a summary and mention interesting open research questions in Section 8. In addition to the main part of the paper, Appendix A introduces the cryptosystem ReSkew based on Reed–Solomon codes in a skew setting. It is a straightforward instantiation of the McEliece system with respect to the Hamming metric and isometric disguising and thus showcases a system for which the presented distinguisher is relevant. Further, it quantifies the potential of GSRS codes in a McEliece-like setting by providing key and ciphertext sizes for parameter sets adhering to the NIST security levels. In fact, the size of the public key is reduced by a factor of at least three compared to Classic McEliece.
2
Preliminaries
We mainly work in finite extension fields and denote by Fq and Fqm the fields of prime-power order q and q m , respectively. Field elements are usually denoted by lowercase letters, and bold lowercase and uppercase letters represent vectors and matrices, respectively. Further, 0 denotes the all-zero vector or the all-zero matrix, and 1 represents the all-one vector or the all-one matrix, both of suitable dimensions depending on the context. 4
We interpret vectors as row vectors and write e.g. v = (v1 , . . . , vn ) ∈ Fnqm . If we want to highlight that v is divided into ℓ blocks whose lengths are the entries of the vector n = (n1 , . . . , nℓ ) ∈ Nℓ , we denote it as (i) (i) i = v1 , . . . , vn(i)i ∈ Fnqm v = (v (1) | · · · | v (ℓ) ) ∈ Fn for i = 1, . . . , ℓ. q m with v n This notation carries over to matrices M ∈ Fk×n q m . For two vectors v, w ∈ Fq m , we define their star product, which is also known as the Schur product, as
v ⋆ w := (v1 w1 , . . . , vn wn ) ∈ Fnqm . Moreover, we use the shorthand F∗qm = Fqm \ {0} to denote the multiplicative group of Fqm . Recall that F∗qm is cyclic and ζ ∈ F∗qm is called a primitive element if it generates F∗qm . 2.1
Skew polynomials and their evaluation
A skew polynomial ring Fqm [x; θ] contains all formal polynomials with finitely many nonzero coefficients from Fqm . The addition in Fqm [x; θ] is the same as for the conventional polynomial ring Fqm [x]. However, the multiplication in Fqm [x; θ] is determined by the rule xa = θ(a)x which allows to swap the indeterminate x with a field element a ∈ Fqm [43]. Here, θ : Fqm → Fqm denotes a field automorphism of Fqm , i.e., it satisfies the properties θ(a + b) = θ(a) + θ(b) and θ(a · b) = θ(a) · θ(b) for any a, b ∈ Fqm . Note that the notion of degree from Fqm [x] carries over naturally to Fqm [x; θ] and is denoted by deg(·). Further, skew polynomial rings are left and right Euclidean domains, which means that the least common left multiple and the greatest common right divisor of two skew polynomials f, g ∈ Fqm [x; θ] exist and are denoted by lclm(f, g) and gcrd(f, g), respectively. Remark 1. Note that Øre [43] defined skew polynomials for potentially infinite division rings instead of finite fields and also included a θ-derivation in addition to the automorphism θ. However, the finite setting is more appropriate for coding theory and finite division rings are fields due to Wedderburn’s theorem [34]. In this case, nonzero derivations do not really change the setup since skew polynomial rings with nonzero derivation are isomorphic to the one with zero derivation as detailed in [35, Prop. 40]. This means that our setting is barely a restriction from a coding-theoretic perspective. Automorphism choices. Each automorphism θ : Fqm → Fqm has a fixed field and we choose θ such that this is precisely Fq . In other words, θ has the form s θ(x) = xq for an s with gcd(s, m) = 1. In particular, θ is the s-th power of the Frobenius automorphism σ which is the q-powering map x 7→ xq for all x ∈ Fqm . Similar to [29], we introduce the notations [i]θ = q is
and
JiKθ =
i−1 X j=0
5
q js = q (i−1)s + · · · + q s + 1
for θ = σ s with an arbitrary s = 0, . . . , m − 1 and for all i ∈ N. In particular, is −1 θi (x) = x[i]θ applies and JiKθ = qqs −1 for s ̸= 0. Remainder evaluation. One approach to skew polynomial evaluation is enforcing a remainder theorem [24,25]. Namely, the evaluation of f ∈ Fqm [x; θ] at a point a ∈ Fqm is defined as the remainder of the right division of f by x − a. We will denote it by f [a] to visually distinguish it from other function evaluations. In fact, remainder evaluation can be expressed similarly to usual polynomial evaluation, namely [25, Lem. 2.4] yields X f [a] = fi aJiKθ i
for any a ∈ Fqm and f ∈ Fqm [x; θ] having the form f (x) = a ∈ Fnqm , we write f [a] = (f [a1 ] , . . . , f [an ]) ∈ Fnqm .
i i fi x . For vectors
P
Generalized operator evaluation. Another way of evaluating skew polynomials is based on the operator Dθ (b)a := θ(b)a for all a, b ∈ Fqm and its powers Dθi (b)a = θ θi (b) · aJiK P for all i > 0 (see e.g. [27,35]). The generalized operator evaluation of f (x) = i fi xi ∈ Fqm [x; θ] at b ∈ Fqm with respect to the evaluation parameter a ∈ Fqm is then X X f (b)a := fi Dθi (b)a = fi θi (b)aJiKθ . i
i
Observe that there is the useful relation f (b)a b−1 = f Dθ (b)a b−1
for any a, b ∈ Fqm
(1)
between remainder and generalized operator evaluation [35, Lem. 24]. For simplicity, we generalize the notations Dθi (·)· and f (·)· to vectors a, b ∈ Fnqm via elementwise application and understand Dθi (b)a = (Dθi (b1 )a1 , . . . , Dθi (bn )an ) ∈ Fnqm and f (b)a = (f (b1 )a1 , . . . , f (bn )an ) ∈ Fnqm , respectively. Conjugacy and norm. For any two elements a ∈ Fqm and c ∈ F∗qm , we define γθ (a, c) := θ(c)ac−1 . Two elements a, b ∈ Fqm are called θ-conjugates, if there exists an element c ∈ F∗qm such that b = γθ (a, c) holds [24]. The notion of θ-conjugacy defines an equivalence relation on Fqm and thus a partition of Fqm into θ-conjugacy classes [25]. We use the shorthand γθ (a, c) for two vectors a, c ∈ Fnqm with c having nonzero entries to denote (γθ (a1 , c1 ), . . . , γθ (an , cn )) ∈ Fnqm . Qm−1 The norm of b ∈ Fqm with respect to θ is Nθ (b) = j=0 θj (b) = bJmKθ . It follows from Hilbert’s Theorem 90 that two field elements have the same norm if and only if they belong to the same θ-conjugacy class [26, Eq. (1.2)]. We extend the notation Nθ (·) elementwise to vectors and write Nθ (b) = (Nθ (b1 ), . . . , Nθ (bn )) for any b ∈ Fnqm . 6
P-independence. We call a vector α ∈ Fnqm Pθ -independent if lclmi=1,...,n (x − αi ) ∈ Fqm [x; θ] has degree n [7]. Interestingly, P-independence can be expressed in terms of Fq -linear independence when α is represented in a particular form. Namely, we group the entries by θ-conjugacy class and express each of them as a conjugate of a selected class representative. When a1 , . . . , aℓ ∈ Fqm belong to distinct conjugacy classes and n ∈ Nℓ is a block partition, let us define the vector (i) i of a contains precisely ni copies of a ∈ Fn ∈ Fnqm q m such that the i-th block a ai . This will allow us to keep the notation as simple as possible and we refer to a as the n-vector corresponding to a1 , . . . , aℓ in the following. Lemma 2. Consider an arbitrary vector α ∈ Fnqm whose entries belong to ℓ distinct θ-conjugacy classes. Pick representatives a1 , . . . , aℓ ∈ Fqm of the respective conjugacy classes and denote the corresponding n-vector by a ∈ Fn q m . Then there exist a permutation π ∈ Sn and a vector b ∈ Fn with nonzero entries such that m q π(α) = γθ (a, b) holds. Further, the following statements are equivalent: 1. α ∈ Fnqm is Pθ -independent. 2. a contains only nonzero entries and each block of b contains Fq -linearly independent elements. Proof. Recall that θ-conjugacy is an equivalence relation and each element α ∈ Fqm can thus be represented as a conjugate γθ (a, b) of a class representative a ∈ Fqm with a nonzero b ∈ Fqm . When we fix a set of representatives of the conjugacy classes and let π group the entries of α by their class membership, we arrive at the claimed representation π(α) = γθ (a, b). The equivalence of 1. and 2. follows from [31, Lem. 1] and [35, Lem. 29]. ⊓ ⊔ Remark 3. We only introduced the permutation π in Lemma 2 to simplify the notation. π rearranges the entries of α by θ-conjugacy class and allows to reflect this structure also in the block partition n of the vector b ∈ Fn q m . This will be beneficial later in the context of GLRS codes and the related sum-rank weight that depends on the block partition n. However, there is no mathematical problem if the entries of the representation γθ (a, b) are not sorted by class. 2.2
Linear codes
An Fqm -linear code C of length n and dimension k is a k-dimensional Fqm -linear subspace of Fnqm . We call the ratio nk its rate. C can be represented as the Fqm linear row space of a full-rank generator matrix G ∈ Fk×n q m or as the kernel of (n−k)×n
a full-rank parity-check matrix H ∈ Fqm . Remark that GH ⊤ = 0 applies to any pair consisting of a generator and a parity-check matrix, and that both representations are not unique. The dual code of C is the code generated by H. It has length n and dimension n − k, and is denoted by C ⊥ . Puncturing and shortening. We will need two ways of deriving a shorter code from a given one (see e.g. in [21, Sec. 1.5]). First, we puncture a linear code 7
C ⊆ Fnqm at position i = 1, . . . , n by removing the i-th coordinate from each codeword. In other words, Cpun,i := {(c1 , . . . , ci−1 , ci+1 , . . . , cn ) | (c1 , . . . , cn ) ∈ C} ⊆ Fn−1 qm . We obtain a generating matrix of Cpun,i from a generator matrix of C by removing the i-th column. Second, we shorten C at the i-th coordinate when we consider the subcode that vanishes at position i and puncture it at position i. More precisely, Csho,i := {(c1 , . . . , ci−1 , ci+1 , . . . , cn ) | (c1 , . . . , ci−1 , 0, ci+1 , . . . , cn ) ∈ C} ⊆ Fn−1 qm . Both notions can be extended from one index to a set of coordinates in a straightforward manner. Further, it is worth noting that puncturing and shortening are dual operations in the sense that (Cpun,i )⊥ = (C ⊥ )sho,i and (Csho,i )⊥ = (C ⊥ )pun,i apply according to [21, Thm. 1.5.7]. Different decoding metrics. Codes can be endowed with different decoding metrics which measure e.g. the distance of an erroneous received vector from the closest codeword or the error weight. Classically, the Hamming weight wtH (v) of a vector v ∈ Fnqm is the number of its nonzero entries. For the rank weight, we use the fact that Fqm is an m-dimensional vector space over its subfield Fq . We define wtR (v) as the maximum number of Fq -linearly independent entries of v and note that this is precisely the rank of the matrix representation of v over Fq . The sum-rank weight is a mixture between the Hamming weight and the rank weight. It is defined for vectors v ∈ Fn q m which are divided into ℓ blocks of lengths n1 , . . . , nℓ and is given as wtΣR (v) =
ℓ X
wtR (v (i) ).
i=1
Note that the sum-rank weight depends on the chosen block partition but we omit that fact from the notation for simplicity. The case n1 = n results in one block and recovers the rank metric, whereas the case of n length-one blocks, i.e., n1 = · · · = nn = 1, corresponds to the Hamming metric [35]. The skew weight depends on θ and on a Pθ -independent vector α ∈ Fnqm . Its definition can be found in e.g. [7] and reads wtθ,α S (v) = deg lclm i=1,...,n (x − γθ (αi , vi )) . vi ̸=0
Each of the above discussed weights allows to obtain a metric on Fnqm by letting the distance between two vectors v, w ∈ Fnqm equal the weight of their difference v − w. The minimum distance d of a linear code C with respect to a certain metric is the minimum weight of a nonzero codeword in the corresponding metric. It determines the error-correction capability d−1 for unique decoding 2 with respect to errors in the respective metric. The Singleton bound relates the 8
length n, the dimension k, and the minimum Hamming distance dH of a linear code via d ≤ n − k + 1. Every code with minimum distance precisely n − k + 1 is called maximum distance separable (MDS). There are analog bounds for the minimum distances dR , dΣR , and dSθ,α with respect to rank, sum-rank, and skew metric. For Fqm -linear codes, the upper bound is n−k +1 in each case, and linear codes achieving these bounds have maximum rank distance (MRD), maximum sum-rank distance (MSRD), and maximum skew distance (MSD) with respect to θ and α, respectively [35]. Later, we will consider Fqm -linear isometries for the Hamming metric, i.e., bijective linear maps that preserve the Hamming weight of vectors in Fnqm . The application of any such mapping to a code C ⊆ Fnqm yields a monomially equivalent code C ′ . The transition from C to C ′ corresponds to multiplying a generator matrix of C by a monomial matrix from the right. Recall that a monomial matrix n×n M ∈ Fn×n q m can be expressed as the product of a diagonal matrix diag(d) ∈ Fq m with nonzero diagonal entries d ∈ Fnqm and a permutation matrix P ∈ Fn×n q m containing precisely one one in each column and in each row and zeros elsewhere [21, Sec. 1.7].
3
Skew evaluation codes
This section contains definitions and basic properties of GSRS and GLRS codes and their special cases. Both code families are obtained as evaluation codes from skew polynomial rings with respect to remainder and generalized operator evaluation, respectively. That is why we use the term skew evaluation codes to represent all these code classes. Note however that the same or a similar term was used in the literature for slightly different codes [8,30,29]. We will discuss the differences after we have given the necessary background to understand them.
3.1
Generalized skew Reed–Solomon codes and their duals
We start with the definition of generalized skew Reed–Solomon (GSRS) codes, which were e.g. studied in [8,30,29]. Definition 4 (GSRS codes). Consider a Pθ -independent vector α ∈ Fnqm and column multipliers λ ∈ Fnqm with only nonzero entries. Then, the generalized skew Reed–Solomon (GSRS) code of length n and dimension k is defined as GSRS[α, λ; n, k]θ := f [α] ⋆ λ : f ∈ Fqm [x; θ] with deg(f ) < k ⊆ Fnqm . We call α its code locators and λ its column multipliers. Further, trivial column multipliers λ = 1 yield a skew Reed–Solomon (SRS) code which we denote by SRS[α; n, k]θ . 9
GSRS codes have a generator matrix of a particularly nice form. Namely, J0K J0K α1 θ · · · αn θ J1Kθ J1K α1 · · · αn θ k G = Vθ (α) · diag(λ) := . .. .. · diag(λ) .. . . α1
Jk−1Kθ
· · · αn
Jk−1Kθ
generates GSRS[α, λ; n, k]θ , where diag(λ) denotes the diagonal matrix having λ1 , . . . , λn on the diagonal. In general, we call Vθk (α) a skew Vandermonde matrix and it has full rank k ≤ n if the entries of α are Pθ -independent (see [25, Thm. 4.5] and Lemma 2). It is known that GSRS codes have minimum Hamming distance d = n − k + 1 and are thus MDS codes [29, Thm. 4.1.4]. Particular parameter choices result in properties with respect to the skew metric, as was shown in [7, Thm. 2]: Lemma 5 (Skew-metric GSRS codes). Let α, λ ∈ Fnqm be GSRS parameters according to Definition 4. Assume further that γθ (α, λ) ∈ Fnqm is Pθ independent. Then, the GSRS code GSRS[γθ (α, λ), λ; n, k]θ is MSD with respect to θ and α. Recently, a formula for the dual of an SRS code was given in [7, Thm. 3]. We can extend this result to generalized codes with column multipliers as follows: Lemma 6 (GSRS duals). Consider GSRS parameters α, λ ∈ Fnqm as in Definition 4. Moreover, let v ∈ Fnqm be a nonzero vector in GSRS[α, λ; n, n − 1]⊥ θ and assume that γθ−1 (θ−1 (α), v ⋆ λ) is Pθ−1 -independent. Then, −1 (α), v ⋆ λ), v; n, n − k]θ−1 . GSRS[α, λ; n, k]⊥ θ = GSRS[γθ −1 (θ
Proof. The codes GSRS[α, λ; n, k]θ and GSRS[γθ−1 (θ−1 (α), v ⋆λ), v; n, n−k]θ−1 have generator matrices of the form G = Vθk (α) · diag(λ) ∈ Fk×n q m and H = (n−k)×n
−1 , respectively. We first show that Vθn−k (α), v ⋆ λ)) · diag(v) ∈ Fqm −1 (γθ −1 (θ ⊤ GH = 0 holds, i.e., that the GSRS code on the right-hand side is a subcode of the wanted dual. This is the case if and only if for all g = 1, . . . , k and all h = 1, . . . , n − k
⊤ αJg−1Kθ ⋆ λ · γθ−1 (θ−1 (α), v ⋆ λ)Jh−1Kθ−1 ⋆ v = 0 applies. This equality can be rephrased as 0=
n X
Jg−1Kθ −1
αj
θ
Jh−1Kθ−1 vj λ j (αj )Jh−1Kθ−1 θ−1 (vj λj )Jh−1Kθ−1 (vj−1 λ−1 j )
j=1
=
n X
θ−(h−1) αj
Jg+h−2Kθ −(h−1)
θ
(vj λj ) = θ−(h−1)
j=1
n X j=1
10
αj
Jg+h−2Kθ
vj λ j
Pn Je−1Kθ vj λj = 0 holds for all e = 1, . . . , n − 1. and is satisfied if and only if j=1 αj In other words, it holds for any v ∈ GSRS[α, λ; n, n − 1]⊥ θ as assumed in the statement. The equality of the two codes follows from the assumption that the entries of γθ−1 (θ−1 (α), v ⋆ λ) are Pθ−1 -independent which is sufficient for the skew −1 Vandermonde matrix Vθn−k (α), v ⋆ λ)) to have rank n − k. Further, it −1 (γθ −1 (θ can be shown with a similar argument as in [37, Thm. 4] and [7, Lem. 2] that every v ∈ GSRS[α, λ; n, n − 1]⊥ θ contains only nonzero elements. This ensures that any generator matrix of GSRS[γθ−1 (θ−1 (α), v ⋆ λ), v; n, n − k]θ−1 has rank n − k, i.e., the code on the right-hand side has dimension n − k. ⊔ ⊓ 3.2
Generalized linearized Reed–Solomon codes and their duals
LRS codes were introduced in [35, Def. 31] and generalized to block multipliers in [22]. We extend the definition to arbitrary nonzero column multipliers: Definition 7 (GLRS codes). Consider a vector b ∈ Fn q m with wtΣR (b) = n contain only nonzero elements. Further, let a1 , . . . , aℓ ∈ Fqm and let λ ∈ Fn qm belong to distinct nontrivial θ-conjugacy classes of Fqm and let a ∈ Fn q m be the corresponding n-vector as defined above Lemma 2. Then, the generalized linearized Reed–Solomon (GLRS) code of length n and dimension k is GLRS[b, a, λ; n, k]θ := f (b)a ⋆ λ : f ∈ Fqm [x; θ] with deg(f ) < k ⊆ Fn qm . We call b its code locators, a its evaluation parameters, and λ its column multipliers. If λ = 1, we obtain an LRS code and denote it by LRS[b, a; n, k]θ . The code GLRS[b, a, λ; n, k]θ has a generator matrix of the form G = Mkθ (b)a · diag(λ)
(2)
where the blocks of the generalized Moore matrix Mkθ (b)a ∈ Fk×n q m are defined as (i) (i) b1 ... bni (i) (i) Dθ (b1 )ai . . . Dθ (bni )ai k (i) Mθ (b )ai = .. .. . ... . k−1 (i) k−1 (i) Dθ (b1 )ai . . . Dθ (bni )ai
for all i = 1, . . . , ℓ.
Since the multiplication of each block of a code with a nonzero Fqm -element or with a full-rank Fq -matrix is a sum-rank isometry [36,3], GLRS codes with the following parameter restrictions are MSRD: Lemma 8 (Sum-rank-metric GLRS codes). Consider GLRS parameters (i) (i) a, b, λ ∈ Fn q m as in Definition 7. If λ1 = · · · = λni applies for all i = 1, . . . , ℓ n or if λ ∈ Fq , the code GLRS[b, a, λ; n, k]θ is MSRD. 11
We can now derive a statement about GLRS duals similar to Lemma 6 in the GSRS setting. We obtain the following: Lemma 9 (GLRS duals). Let a, b, λ ∈ Fn q m be GLRS parameters according to Definition 7. Further, choose any nonzero vector v ∈ GLRS[b, a, λ; n, n − 1]⊥ θ and assume that λ ⋆ v has sum-rank weight n. Then, it holds −1 GLRS[b, a, λ; n, k]⊥ (a), λ−1 ; n, n − k]θ−1 . θ = GLRS[v ⋆ λ, θ
Proof. This proof is an adaptation of the one of [37, Thm. 4] and follows the same strategy as the proof of Lemma 6. For the orthogonality of the codes, −1 −1 we show that G = Mkθ (b)a · diag(λ) and H = Mn−k ) θ −1 (v ⋆ λ)θ (a) · diag(λ ⊤ satisfy GH = 0. In other words, we require that for all g = 1, . . . , k and all h = 1, . . . , n − k −1 ⊤ Dθg−1 (b)a ⋆ λ · Dθh−1 =0 −1 (v ⋆ λ)θ −1 (a) ⋆ λ holds. With similar steps as in Lemma 6, we rephrase this equivalently as θh−1
n X
Dθg+h−2 (bj )aj vj λj = 0
j=1
Pn
and finally as j=1 Dθe−1 (bj )aj vj λj = 0 for all e = 1, . . . , n − 1. By definition, this is true for any v ∈ GLRS[b, a, λ; n, n − 1]⊥ θ and we hence proved that GLRS[v ⋆ λ, θ−1 (a), λ−1 ; n, n − k]θ−1 ⊆ GLRS[b, a, λ; n, k]⊥ θ applies. Since θ−1 (a) contains representatives of distinct nontrivial θ−1 -conjugacy −1 classes and we assumed that wtΣR (v ⋆λ) = n applies, Mn−k θ −1 (v ⋆λ)θ (a) has full Fqm -rank n−k according to [35, Thm. 2] and [25, Thm. 4.5]. Further, λ and thus −1 also λ−1 contains only nonzero entries and consequently H = Mn−k θ −1 (v ⋆λ)θ (a) has full rank. This shows that the GLRS code on the right-hand side of the statement has dimension n − k, which finishes the proof. ⊔ ⊓ The nonzero vector v that is arbitrarily chosen from GLRS[b, a, λ; n, n − 1]⊥ θ in the above theorem actually satisfies wtΣR (v) = n, which follows from an adaptation of the proof of [37, Thm. 4]. Thus, the condition wtΣR (v ⋆ λ) = n from the theorem statement is automatically satisfied when λ ∈ Fnqm satisfies any of the two conditions given in Lemma 8. This means that the sum-rank-metric GLRS codes defined in Lemma 8, i.e., the ones with Fqm -block multipliers or Fq column multipliers, are closed under duality. In particular, this holds for LRS codes and generalizes the known results on LRS duals from [37, Thm. 4]. 3.3
Connections between GSRS, GLRS, GRS, and Gabidulin codes
It is well-known that there is an isometry which maps GSRS codes in the realm of the skew metric to GLRS codes in the sum-rank world [35]. We now give equalities between codes of the two families which are independent of the considered metrics. We believe that the resulting explicit transformations of the code parameters make the results more accessible. 12
Lemma 10 (From GLRS to GSRS codes). For GLRS parameters a, b, λ ∈ Fn q m as in Definition 7, it holds GLRS[b, a, λ; n, k]θ = GSRS[γθ (a, b), λ ⋆ b; n, k]θ . Proof. Recall that each codeword c ∈ GLRS[b, a, λ; n, k]θ corresponds to a skew polynomial f ∈ Fqm [x; θ] of degree less than k via c = f (b)a ⋆ λ. Since equation (1) implies λf (b)a = λf [γθ (a, b)] b for any a, b, λ ∈ F∗qm , the statement follows. ⊔ ⊓ Lemma 11 (From GSRS to GLRS codes). Consider GSRS parameters α, λ ∈ Fnqm satisfying the conditions of Definition 4. Let further a, b ∈ Fn q m be the outcome of Lemma 2 such that π(α) = γθ (a, b) applies. Then, GSRS[π(α), λ; n, k]θ = GLRS[b, a, λ ⋆ b−1 ; n, k]θ . Proof. This follows from the same argument as Lemma 10.
⊔ ⊓
The permutation π in the above Lemma 11 is no restriction for the choice of code locators α of the GSRS code that is transformed. In fact, recall from Remark 3 that π only groups the entries of α by conjugacy class which is convenient for the GLRS representation and the related sum-rank metric. It is however not necessary: the permuted GLRS code with code locators π −1 (b) and evaluation parameters π −1 (a) has the same Hamming-metric properties. Further, its sumrank properties carry over if the sum-rank weight is defined in terms of suitable index sets instead of a block partition n. Next, we deal with prominent special cases of GSRS and GLRS codes: GRS and Gabidulin codes. We state comprehensively how they can be obtained from the GSRS and the GLRS framework and thus give a good starting point to compare our distinguishing results to known distinguishers for these code families later. GRS codes. Let us first recall the definition of a generalized Reed–Solomon (GRS) code of length n and dimension k, which reads GRS[b, λ; n, k] := {f (b) ⋆ λ : f ∈ Fqm [x] with deg(f ) < k} ⊆ Fnqm for distinct code locators b ∈ Fnqm and nonzero column multipliers λ ∈ Fnqm . Observe that this definition employs conventional polynomials from Fqm [x] and their standard evaluation. We can express GRS[b, λ; n, k] as a GSRS and as a GLRS code with block partition n = 1 ∈ Fnqm as follows: GRS[b, λ; n, k] = GSRS[b, λ; n, k]id = GLRS[1, b, λ; n, k]id .
(3)
The chosen automorphism is the identity and the equalities follow from expressing the P remainder evaluation and the generalized operator evaluation of any f (x) = i fi xi ∈ Fqm [x; id] as X X f [b] = fi bJiKid = f i bi i
i
13
and
f (1)b =
X i
fi Di (b)1 =
X i
fi idi (1)bJiKid =
X i
fi bi
for any b ∈ Fqm , respectively. The code locators b of the GRS code and its GSRS representation actually become the evaluation parameters in its GLRS representation. In contrast, the code locators of Gabidulin codes stay code locators also in the GLRS representation, as we will see shortly. Observe also that the distinctness of b1 , . . . , bn translates to the required conditions in the GSRS and the GLRS case: Since the identity creates q m − 1 nontrivial conjugacy classes of cardinality one, every vector with distinct nonzero entries such as b is Pid -independent. Further, b1 , . . . , bn are used as evaluation parameters in the GLRS setting where they represent different nontrivial conjugacy classes due to the reasoning above. In addition, the all-one vector has sum-rank weight n as required because each block has length precisely one. Gabidulin codes. In the classical definition of Gabidulin codes, we pick Fq -linearly independent code locators b ∈ Fnqm and define the respective code of length n and dimension k as Gab[b; n, k] := f (b) : f ∈ Lqm[x] with degq (f ) < k ⊆ Fnqm , where Lqm[x] is the ring of linearized polynomials. A linearized polynomial has P P i the form f (x) = i fi xq = i fi x[i]σ with finitely P many Fqm -coefficients, and its evaluation at any b ∈ Fqm is given as f (b) = i fi b[i]σ . The q-degree degq (f ) equals the maximum i for which fi ̸= 0 applies and −∞ if f = 0. We use the Frobenius automorphism σ to express Gab[b; n, k] as GSRS and as GLRS code with block partition n = (n) ∈ Fqm . Namely, Gab[b; n, k] = GSRS[bq−1 , b; n, k]σ = GLRS[b, (1), 1; n, k]σ .
(4)
Similar to the case of GRS codes above, the equalities follow from the following facts about P remainder and generalized operator evaluation of a skew polynomial f (x) = i fi xi ∈ Fqm [x; σ] at any b ∈ Fqm : X X X i bf bq−1 = b fi b(q−1)·JiKσ = fi bbq −1 = fi b[i]σ i i i X X X and f (b)1 = fi Di (1)b = fi σ i (b)1JiKσ = fi b[i]σ . i
i
i
Observe that the column multipliers in the GSRS representation cannot be chosen freely in the Gabidulin scenario but they depend heavily on the code locators. The condition wtR (b) = n implies that the column multipliers of the GSRS representation are nonzero. Further, bq−1 = γσ (1, b) applies and thus bq−1 is Pσ -independent according to Lemma 2 as demanded. The requirements for the respective GLRS parameters are clearly satisfied. Remark 12. Note that other works in the literature use the term skew evaluation codes slightly differently. In [30,29], generalized skew evaluation (GSE) codes are a superclass of GSRS codes. The relaxation lies in the fact that the code locators 14
α ∈ Fnqm do not need to be Pθ -independent but only have to ensure that Vθk (α) has full rank. In [8], remainder evaluation skew codes are the same as the GSE codes from [30,29] but without column multipliers. There, also operator evaluation skew codes are studied. They are related to generalized operator evaluation but are not exactly the same as LRS codes. In particular, their generator matrix is the Wronskian matrix and not the generalized Moore matrix. 3.4
Code distinguishability and McEliece-like cryptosystems
In this work, we study the algebraic structure of skew evaluation codes with a particular focus on understanding if these code families are efficiently distinguishable from random codes. A distinguisher for GSRS/GLRS codes is an algorithm that is capable of correctly answering the following question with a higher success probability than random guessing: Was a given matrix G ∈ Fk×n qm drawn randomly from the set of all full-rank matrices in Fk×n or from the set m q of all generator matrices of GSRS/GLRS codes of length n and dimension k? Remark that the notion of a distinguisher can be formalized in the form of a game, and put into relation with attackers of the underlying McEliece-like problem. But since the formalism seems not to be beneficial for the presentation of the present work, we point the interested reader to [14, Sec. II], for example. Our motivation clearly comes from code-based cryptography where the indistinguishability assumption for the code class used in the McEliece-like setting is commonly seen as a requirement for security. To be more precise, system designers usually aim for indistinguishability under adaptive chosen-ciphertext attacks (IND-CCA2) in accordance with the standard requirements from NIST’s PQC standardization for general-use KEMs. This can be achieved, as in the case of Classic McEliece, by applying an IND-CCA2 conversion to a public-key encryption (PKE) which is one-way under chosen-plaintext attacks (OW-CPA). For example, Kobara and Imai investigate the applicability of several known generic transformations and derive alternatives tailored to the McEliece setting in the random oracle model (ROM) in [23]. Up to our knowledge, there are two ways in which the OW-CPA security of McEliece-like cryptosystems can be attacked: by means of key-recovery attacks, in which the adversary retrieves an equivalent secret key from the sheer knowledge of the public key, or by means of generic decoding, in which the adversary ignores the secret code structure and tries to decode an obtained ciphertext as if it originated from a random code. The latter can be formalized as the syndrome-decoding problem (SDP) whose decisional version was shown to be NP-complete in [6] for the binary field and in [5] for arbitrary finite fields. The former structural attacks correspond to the distinguishability problem for the used code family. The hardness of these two problems implies OW-CPA security but is however not equivalent to it. It is nevertheless common to study them instead of the OW-CPA security itself. Observe that a McEliece-like system can remain secure even if an efficient distinguisher breaks the indistinguishability assumption. This only turns into a 15
security risk if the distinguisher can be extended to a key-recovery attack. In contrast, every successful break of the OW-CPA security yields a distinguisher for the public keys or solves the SDP.
4
GRS subcodes of skew evaluation codes
In addition to their inherent algebraic structure arising from being evaluation codes of skew polynomials, generalized skew and linearized Reed–Solomon codes also exhibit a rich compositional property: they can be expressed as a direct product of several classical generalized Reed–Solomon (GRS) codes. We establish this decomposition in the following and also explore its shape in the special case of Gabidulin and GRS codes. For the ease of notation, let us first define ( k for i = 1, . . . , (k mod m) (5) ki := m k for i = (k mod m) + 1, . . . , m. m Theorem 13 (GRS subcodes of GSRS codes). Let α, λ ∈ Fnqm be GSRS parameters according to Definition 4. Then, it applies GSRS[α, λ; n, k]θ =
m M
GRS[Nθ (α), αJi−1Kθ ⋆ λ; n, ki ]
i=1
with k1 , . . . , km from (5). Note that the code locators Nθ (α) of the GRS codes might not all be distinct. Proof. For simplicity we assume that θ = σ is the Frobenius automorphisms, and note that the same arguments in the proof can be used for general θ. Moreover, we can take the column mutlipliers λ out, prove the statement for trivial column multipliers, and multiply the component codes by them again in the end. Consider the basis of GSRS[α, 1; n, k]θ consisting of αJxKθ for x = 0, . . . , k −1 and note that for 0 < x < k αj
JxKθ
= αjq
x−1
+···+q+1 x−1
(x−1) mod m (1+q+···+q m−1 )⌊ x−1 m ⌋+1+q+···+q
= αj
Jx mod mKθ
= Nθ (αj )⌊ m ⌋ αj
.
For x = 0 we get that αj
J0Kθ
= 1 = Nθ (αj )0 αj
J0Kθ
.
k ⌋, the basis vectors with exponents JiKθ , Ji + mKθ , . . . , Hence, for 0 ≤ i < k−m⌊ m k Ji + m(⌈ m ⌉ − 1)Kθ generate the code
GRS[Nθ (α), αJiKθ ; n,
k m
].
k Similarly, the basis vectors with exponents JiKθ , Ji + mKθ , . . . , Ji + m(⌊ m ⌋ − 1)Kθ k for k − m⌊ m ⌋ ≤ i < m generate k GRS[Nθ (α), αJiKθ ; n, m ].
16
This proves that all claimed GRS subcodes are contained in GSRS[α, λ; n, k]θ . Finally, we show that the sum of the m distinct GRS codes is direct since their dimensions sum up precisely to k. This is easy to see in case k divides m since Pm P m k k = split up the sum in the i i=1 i=1 m = k. If k does not divide m, we can k to obtain spirit of (5) and use the fact that k mod m = k − m m m X
ki = (k mod m) ·
k m
+ (m − k mod m) ·
k m
i=1
= k−m
k m
·
k m
k k +1 + m−k+m m · m = k. ⊔ ⊓
This finishes the proof.
As mentioned in Theorem 13, the resulting GRS subcodes are not always proper classical GRS codes as their code locators might not all be distinct. In fact, we can easily see how many distinct elements Nθ (α) contains: Recall therefore that members of the same θ-conjugacy class have the same norm according to Hilbert’s Theorem 90. Thus, apply Lemma 2 to obtain a representation π(α) = γθ (a, b) with a, b ∈ Fn q m . Since α is Pθ -independent, a1 , . . . , aℓ belong to distinct nontrivial conjugacy classes and Nθ (a1 ), . . . , Nθ (aℓ ) are distinct. This means that Nθ (α) = Nθ (a) contains precisely ni copies of Nθ (ai ) for each i = 1, . . . , ℓ. As a consequence, this fact ensures that each of the GRS subcodes in Theorem 13 attains the claimed dimension. The Vandermonde part of their k k generator matrices is Vθki (Nθ (a)) for ki ∈ {⌈ m ⌉, ⌊ m ⌋} and has rank min(ℓ, ki ). k n The minimum is ensured to always be ki since m ≤ m ≤ ℓm m ≤ ℓ. Remark 14. In the case k ≤ m, the decomposition presented above has exactly k GRS components, all of which have dimension one. In the decomposition above, the component GRS codes share a common set of code locators, all contained in the base field Fq , but differ in their respective sets of column multipliers. From a cryptographic perspective, the presence of these particular column multipliers inhibits straightforward recovery attacks of the Sidelnikov–Shestakov type. On the other hand, this structural regularity also has implications for the behavior of the code under the coordinate-wise (or star) product, particularly with respect to its square. Specifically, the structured nature of the component codes causes the dimension of the square code to deviate from that of a random linear code of the same length and dimension for many code parameters, as we will analyze in the next section. Theorem 15 (GRS subcodes of GLRS codes). Let a, b, λ ∈ Fn q m be GLRS parameters according to Definition 7. Then, it applies GLRS[b, a, λ; n, k]θ =
m M
GRS[Nθ (a), aJi−1Kθ ⋆ λ ⋆ θi−1 (b); n, ki ]
i=1
with k1 , . . . , km being defined as in (5). Note that the code locators Nθ (a) of the GRS codes might not all be distinct. 17
Proof. Recall that Dθi (b)a = θi (b)aJiKθ applies for i > 0 and for all a, b ∈ Fqm , and that the code GLRS[b, a, λ; n, k]θ has a generator matrix of the form G = Mkθ (b)a · diag(λ) ∈ Fk×n q m defined in (2). Thus, we can express the i-th block of the Moore part Mkθ (b)a as (i) (i) b1 ··· bni (i) (i) Dθ (b1 )ai · · · Dθ (bni )ai k (i) Mθ (b )a(i) = .. .. . ··· . k−1 (i) k−1 (i) Dθ (b1 )ai · · · Dθ (bni )ai (i) (i) b1 · ai J0Kθ ··· bni · ai J0Kθ (i) (i) θ(b1 ) · ai J1Kθ ··· θ(bni ) · ai J1Kθ . = .. .. . ··· . (i)
(i)
θk−1 (b1 ) · ai Jk−1Kθ · · · θk−1 (bni ) · ai Jk−1Kθ
Ignoring the parts depending on b(i) , this matrix looks like the skew Vandermonde matrix Vθk (a(i) ), i.e., similar to the GSRS case. Recall that Theorem 13 combines the rows whose indices coincide modulo m into one GRS subcode. Since (i) θm = id holds, the factor in the j-th row and l-th column is θj mod m (bl ). In other words, this factor is the same for a fixed column and for rows with indices coinciding modulo m. It can thus be moved into the column multipliers of the respective GRS subcode and we obtain the theorem’s statement with the same strategy that we used in the GSRS setting in Theorem 13. ⊔ ⊓ Gabidulin codes. Let us next look at how the decompositions behave for the special cases of Gabidulin codes. Note therefore that the required Fq -linear independence of the n code locators from Fqm implies that k ≤ n ≤ m holds. Corollary 16 (GRS subcodes of Gabidulin codes). Let all entries of the vector b ∈ Fnqm be Fq -linearly independent. Then, Gab[b; n, k] =
k M
GRS[1, σ i−1 (b); n, 1].
i=1
Proof. If we express Gab[b; n, k] as GSRS code as in (4) and apply Theorem 13, we obtain m M Gab[b; n, k] = GRS[Nθ (bq−1 ), (bq−1 )Ji−1Kσ ⋆ b; n, ki ] i=1
=
k M
GRS[Nθ (bq−1 ), (bq−1 )Ji−1Kσ ⋆ b; n, 1].
i=1
Similarly, the GLRS representation of Gab[b; n, k] from (4) and Theorem 15 yield Gab[b; n, k] =
m M
GRS[Nθ (1), σ i−1 (b); n, ki ] =
i=1
k M i=1
18
GRS[Nθ (1), σ i−1 (b); n, 1].
The resulting subcodes are indeed the same since bq−1 = σ(b)b−1 = γσ (1, b) applies to any b ∈ Fqm and the norm of all conjugates of 1 equals 1. Further, every b ∈ Fqm satisfies (bq−1 )Ji−1Kσ b = bq
i−1
−1
b = σ i−1 (b). ⊔ ⊓
GRS codes. In the case of GRS codes, the automorphism θ equals the identity map. Thus, we are automatically in the case m = 1, that is Fqm = Fq , and our results about GSRS and GLRS decompositions become trivial: we only obtain the GRS code itself. More precisely, the application of Theorem 13 and Theorem 15 to the GSRS and the GLRS representations of GRS[b, λ; n, k] as given in (3) both yield GRS[b, λ; n, k] =
1 M
GRS[Nθ (b), bJi−1Kid ⋆ λ; n, ki ]
i=1
for distinct code locators b ∈ Fnqm and nonzero column multipliers λ ∈ Fnqm . Clearly, k1 = k and bJi−1Kid = 1 for all b ∈ Fq since i = 1 is the only valid option. Further, the norm Nθ (b) satisfies bJmKid = b for every b ∈ Fq . The combination of these insights yields precisely GRS[b, λ; n, k] on the right-hand side of the equation.
5
Square code distinguishers
We now exploit the decomposition of GSRS and GLRS codes we have seen in the last section to analyze the behavior of the squares of such codes. Recall therefore that the star product (also called the Schur product) of two vectors is their coordinate-wise product, i.e., x ⋆ y := (x1 y1 , . . . , xn yn ) for any x, y ∈ Fnqm . For two linear codes C1 , C2 ⊆ Fnqm , we define their star product C1 ⋆ C2 as the code spanned by all pairwise star products c1 ⋆ c2 of codewords c1 ∈ C1 and c2 ∈ C2 . If C1 = C2 = C, we call C ⋆ C the square (code) of C and denote it by C ⋆2 . Let us first state how the square code of random codes behaves. Lemma 17 (Squares of random codes [9, Thm. 2.2 and Thm. 2.3]). −n . Consider a random linear code C ⊆ Fnqm of dimension k and let δ := k(k+1) 2 Then, there exists a positive γ ∈ R such that for all large enough k the equality k+1 k(k + 1) dim(C ⋆2 ) = min , n = min ,n 2 2 is satisfied with probability at least 1 − 2δγ . 19
Using the fact that GSRS and GLRS codes contain GRS codes as subcodes, we can deduce the following theorem: Theorem 18 (Squares of GSRS and GLRS codes). Let α, λ ∈ Fnqm be GSRS parameters as given in Definition 4 and consider the outcome of Lemma 2 such that a, b ∈ Fn q m satisfy π(α) = γθ (a, b). Then, the dimensions of the squares ⋆2 GSRS[α, λ; n, k]⋆2 θ and GLRS[b, a, λ; n, k]θ are equal and at most n o min k(k+1) , n if k ≤ m 2 n o min k(m + 1) − m(m+1) , n otherwise. 2 Proof. We first note that the dimensions of the squares of the GSRS and the GLRS code must be equal due to Lemma 10 and Lemma 11. If k ≤ m, then the GSRS code constitutes the direct sum of k one-dimensional GRS codes with the same evaluation parameters according to Theorem 13 and Remark 14. Then the square code consists of k(k+1) star products of one2 dimensional codes. We ignore potential nontrivial intersections to arrive at the on the square code dimension of the GSRS code. upper bound k(k+1) 2 In the case k > m, the decomposition of Theorem 13 consists of m GRS k k subcodes of dimension ki ∈ ⌈ m ⌉, ⌊ m ⌋ for i = 1, . . . , m. The square code decomposes into the sum of m squares of GRS codes of dimensions k1 , . . . , km , and m(m−1) Schur products of two different GRS codes with the same evaluation 2 parameters. Each of the former has an expected dimension of 2ki −1, respectively, and we expect that each of the latter has dimension ki + kj − 1 where ki and kj denote the dimensions of the codes in the star product. Let us now obtain an upper bound on the dimension of GSRS[α, λ; n, k]⋆2 θ by summing up the square code dimensions of all parts. In other words, we assume that all GRS squares and Schur products intersect only trivially. We denote k r := k mod m = k − m m with 0 ≤ r < m and express the sum of the dimensions for the square parts as r m m X X X k k (2 m (2ki − 1) = (2 m − 1) + − 1) i=1
i=1
i=r+1
and the sum of the dimensions for the mixed star products as m X m X
(ki + kj − 1) =
i=1 j=i+1
r r X X
(2
k m
i=1 j=i+1 m m X X
+
− 1) +
r m X X
(2
k m )
i=1 j=r+1
(2
k m
− 1).
i=r+1 j=i+1
Together with the fact 2 obtain the upper bound
k m
−1 = 2
k m
+ 1, we can combine the above and
k r(r + 1) k (m − r)(m − r + 1) k (2 m + 1) + (2 m − 1) + r(m − r)2 m 2 2 20
= (2
k m
− 1) · 21 r(r + 1) + (m − r)(m − r + 1) + 2r(m − r)
+ r(r + 1) + r(m − r) m(m + 1) k = 2 m − 1 + r (m + 1) 2 = k(m + 1) − m(m+1) 2 on dim(GSRS[α, λ; n, k]⋆2 θ ) as long as this is at most n. Note that, if k divides m, we get r = 0 and the sums with upper limit r vanish. ⊔ ⊓ Theorem 18 gives hope to distinguish GSRS and GLRS codes for the case k > m. Since k = m + 1 implies m(m + 1) (m + 2)(m + 1) k+1 m(m + 1) = (m + 1)2 − = = , k(m + 1) − 2 2 2 2 we restrict to k > m + 1 in the following. McEliece-like cryptosystems need to disguise the secret code in order to hide the algebraic structure which can be used to decrypt messages. We study an isometric disguising strategy for GSRS and GLRS codes and the Hamming metric: Lemma 19 (Squares of disguised GSRS and GLRS codes). Let C be a code obtained from applying a Hamming-metric isometry to a GSRS or GLRS code with parameters adhering to Definition 4 and Definition 7, respectively. Then, the square C ⋆2 behaves as described in Theorem 18. Proof. Hamming-metric isometries correspond to multiplication of a generator matrix with a monomial matrix from the right. We can decompose any monomial matrix into the product of a diagonal matrix with nonzero entries on the diagonal and a permutation matrix. The first part can be combined with the code’s column multipliers, resulting in another GSRS/GLRS code. The second part only scrambles the columns which does not change the fact that the code is a GSRS or GLRS code. This implies the statement. ⊓ ⊔ Note that the above results yield an efficient distinguisher for GLRS and GSRS codes as long as their square code dimension differs from the expectancy for a random code. More precisely, we obtain the following statement: Lemma 20 (Naive square code distinguisher). Let C ⊆ Fnqm be a GSRS or GLRS code as defined in Definition 4 and Definition 7. Assume that its din + m mension k satisfies m + 1 < k < m+1 2 and disguise C by means of a Hamming-metric isometry. Then, the disguised version of C can be distinguished from a random code with the same length and dimension with high probability by means of its square code dimension. Proof. In order to obtain distinguishability, the expected square code dimension for random and for GSRS/GLRS codes needs to deviate by at least one. Thus, it is possible to distinguish when the following two inequalities are satisfied: k(m + 1) − m(m+1) <n 2 21
⇐⇒
n k < m+1 +m 2,
k(m + 1) − m(m+1) < k(k+1) 2 2
⇐⇒
k∈ / {m, m + 1}.
As mentioned above, k needs to be larger than m+1 to get a different formula for the expected dimension. Therefore, the second condition above is obsolete. ⊔ ⊓ As with classical generalized Reed–Solomon codes, designers of cryptosystems may attempt to choose parameters for GSRS or GLRS codes such that their square code dimensions are indistinguishable from those of random linear codes. However, when shortening is taken into account, the supposed advantage of the extension parameter m in the square code dimension estimate becomes negligible. Theorem 21 (Square code distinguisher). Let C ⊆ Fnqm be a GSRS or a GLRS code with respect to Definition 4 and Definition 7, respectively. Assume that its dimension k satisfies m + 1 < k < n − 12 (m2 + 3m) and disguise C by means of a Hamming-metric isometry. Then we can distinguish the disguised version of C from a random code by means of its square code dimension with high probability. Proof. We want to shorten C such that we end up in the naive case of Lemma 20. Let us denote the number of shortened coordinates by s and note that the shortened code is a GSRS code of length n − s and dimension k − s. Hence, we need to find an integer s that satisfies both k−s>m+1
n−s and k − s < m+1 +m 2.
While the first inequality is equivalent to s ≤ k − m − 2, the second can be simplified to 1 (k − m s> m 2 )(m + 1) − n . A valid s thus exists if 1 k−m−2> m (k − m 2 )(m + 1) − n
⇐⇒
k < n − 21 (m2 + 3m)
and Lemma 20 then ensures that the square code dimension successfully distinguishes the shortened code from random ones with high probability. In fact, s = k − m − 2 is always a viable choice if the necessary conditions from above are satisfied. ⊔ ⊓ Remark 22. The restriction k < n − 12 (m2 + 3m) in Theorem 21 can also be interpreted as a condition on the redundancy n − k or on the code length n. While the latter reads n > 12 (m2 + 3m) + k, the naive approach from Lemma 20 n implicitly assumes n > 12 (m2 + 5m) + 2 since m + 1 < k < m+1 +m 2 cannot be satisfied otherwise. Observe that the computation of the square code of a k-dimensional code in Fnqm takes O(k 2 n2 ) operations [11, Prop. 5]. Since its dimension can be derived via Gaussian elimination, the above distinguisher is clearly polynomial-time. 22
6
Connections to known distinguishers
We use this section to recall distinguishers for special classes of skew evaluation codes from the literature to give context for our results. We discuss them by code family: first GRS codes, then Gabidulin codes, and finally LRS codes. GRS codes. The behavior of GRS under the Schur product was studied e.g. in [54,11]. It holds dim(GRS[b, λ; n, k]⋆2 ) = min{2k − 1, n} due to the code equality GRS[b, λ; n, k]⋆2 = GRS[b, λ⋆2 ; n, 2k−1]. We obtain the resulting known distinguisher as a special case of Theorem 21, as the GRS setting with m = 1 = 2k − 1. In particular, both distinguishers share the yields k(m + 1) − m(m+1) 2 restriction k ̸= 2 since k = 2 results in squares of dimension 3 both for random and GRS codes. Remark that there are efficient key-recovery attacks for GRS codes [51,11] whose analogs for GSRS and GLRS codes are interesting open research questions. Gabidulin codes. We first note that our square code distinguisher in the GSRS (or GLRS) representation cannot be applied, since Gabidulin codes require m ≥ n, which in turn implies that m ≥ k. By Remark 14 we thus expect the square code to have the same dimension as the square of a random code. Many McEliece-like cryptosystems using Gabidulin codes without advanced disguising strategies have been broken with attacks based on the following behavior related to the Frobenius automorphism σ (see e.g. [46,45,20,19]): Consider a code C ⊆ Fnqm of dimension k over a large enough field Fqm . Then, with high probability, the dimension of the vector space C + σ(C) equals min{2k, n} if C is a random code but min{k + 1, n} for C being a Gabidulin code. In fact, it is true that Gab[b; n, k] + σ(Gab[b; n, k]) = Gab[b; n, k + 1]. The property that the dimension increases by exactly one makes it easy to iteratively apply it until a code of codimension one is achieved. This can then be used to derive (equivalent) code locators b via the known duality relation for Gabidulin codes. Observe that this behavior does not carry over to all GSRS and GLRS codes. Nevertheless, we have a look at how C + σ(C) behaves for a GSRS code C as it is interesting to see how the pieces fall into place for Gabidulin codes. The i-th row of the generator matrix Vθk (α) · diag(λ) of GSRS[α, λ; n, k]θ is αJi−1Kθ · diag(λ), and applying σ to it yields σ(αJi−1Kθ · diag(λ)) = αq·Ji−1Kθ · diag(λq )
for i = 1, . . . , k.
(6)
If we want to achieve the analog GSRS[α, λ; n, k]θ + σ(GSRS[α, λ; n, k]θ ) = GSRS[α, λ; n, k + 1]θ of the equality that holds for Gabidulin codes, each row in (6) needs to be an Fqm -linear combination of rows of Vθk+1 (α) · diag(λ). In other words, we would need coefficients µi,1 , . . . , µi,k+1 ∈ Fqm for every i = 1, . . . , k such that for each column j = 1, . . . , n it holds q·Ji−1Kθ
αj
λqj =
k+1 X l=1
23
µi,l αj
Jl−1Kθ
λj .
This is only true for very particular column multipliers such as the ones of 1 Gabidulin codes which satisfy Gab[α; n, k] = GSRS[α, α q−1 ; n, k]σ in the setting θ = σ according to (4). LRS codes. There is an Overbeck-like distinguisher for LRS codes which runs in polynomial time if the evaluation parameters, i.e., the vector a in Definition 7, are known [22]. The respective operator for a vector a ∈ Fn q m and any j ∈ N is defined as M Dθ (M )a (j+1)k×n → F , M → 7 Γaj : Fk×n m m . .. q q . Dθj (M )a
of the LRS code LRS[b, a; n, k]θ yields While a generator matrix G ∈ Fk×n qm j rk(Γa (G)) = k + j for j = 0, . . . , n − k, a random full-rank matrix R ∈ Fk×n qm whose blocks have full column rank over Fq likely satisfies rk(Γaj (R)) = min{(j + 1)k, n}. In fact, the code generated by Γaj (G) is precisely LRS[b, a; n, k + j]θ for j = 0, . . . , n − k. The next lemma shows that we can translate this distinguisher from [22] into the GSRS setting and that it behaves conceptually similar. While Γaj (·) applied to a LRS generator matrix in generalized Moore form basically adds j additional rows, the respective GSRS counterpart adds j rows to the generator matrix of the corresponding GSRS code in skew Vandermonde form multiplied by the diagonal matrix containing the particularly chosen column multipliers. Lemma 23. Let α ∈ Fnqm be a Pθ -independent vector with the representation π(α) = γθ (a, b) from Lemma 2. The Overbeck-like distinguisher Γaj (·) with j = 0, . . . , n − k for LRS codes can be applied to the GSRS code GSRS[α, b; n, k]θ via the transformations between GSRS and GLRS codes. Then, the resulting code in the GSRS setting is GSRS[α, b; n, k + j]θ . Proof. Choose a, b ∈ Fn q m appropriately for Lemma 11 and assume π = id without loss of generality such that GSRS[α, λ; n, k]θ = GLRS[b, a, λ ⋆ b−1 ; n, k]θ . Then, we can apply the Overbeck-like distinguisher Γaj (·) to the right-hand side if the column multipliers are trivial, i.e., if λ = b. The output is a generator matrix of LRS[b, a; n, k + j]θ and can be translated back into the GSRS setting via Lemma 10. We obtain GSRS[α, b; n, k + j]θ , which concludes the proof. ⊓ ⊔
7
Experimental results
We ran simulations in SageMath [52] to verify our results experimentally. Since GSRS and GLRS codes can be transformed into each other (see Section 3.3), 24
we only simulated the square code distinguisher for GSRS codes. Further, we did not showcase the shortening mechanism from Theorem 21 which makes the naive distinguisher from Lemma 20 applicable to a wider range of parameters. We picked several parameter sets (q, m, n, k) and observed 100 iterations for each of them. In every run, we chose a code GSRS[α, λ; n, k]θ ⊆ Fnqm with respect to a randomly chosen automorphism θ with fixed field Fq , with random nonzero block multipliers λ ∈ Fnqm , and with random Pθ -independent code locators α ∈ Fnqm . Even though Theorem 21 shows that Hamming-isometric disguising does not affect the applicability of the square code distinguisher, we decided to disguise the code nevertheless for illustrative purposes. As a consequence, we computed the square code dimension of the code generated by Vθk (α)·diag(λ)·M where M denotes a random monomial matrix, i.e., a Hamming-metric isometry. We also determined the dimension of the squares of random codes with the same parameters to show when the square code dimension differs and allows to distinguish. Our experimental results are showcased in Table 1. Since the right-hand side n +m of the condition k < m+1 2 from Lemma 20 and thus the range of distinguishable codes grows for fixed q and m, we picked the maximum possible code length n = m(q − 1) in all cases. Recall that the upper bound n ≤ m(q − 1)comes from the need for P-independent code locators for GSRS codes and Lemma 2. Note that we included in each case the largest k for which the distinguishing conditions are satisfied and the smallest one for which they are not. Additionally, we picked another k for which the codes are distinguishable to also collect some data points that are not directly at the breaking point. The expected square code dimension for both GSRS and random codes coincided precisely with the predicted bounds in all our experiments: squares of GSRS codes have dimension min k(m + 1) − m(m+1) , n (see Theorem 18), and 2 k(k+1) the dimension of squares of random codes is min , n (see Lemma 17). 2
8
Conclusion
In this work, we studied the algebraic structure and distinguishability of generalized skew Reed–Solomon (GSRS) and generalized linearized Reed–Solomon (GLRS) codes in the context of code-based cryptography. We first establish explicit transformations between the GLRS and GSRS settings, showing that structural properties of one family can be transferred to the other. Using these transformations, we prove that the dual of a GSRS code is itself a GSRS code under certain conditions. Some of these results generalize previously known statements, while others are new contributions, providing a rigorous algebraic framework for further analysis of these code families. We then prove that both GSRS and GLRS codes admit a decomposition into direct sums of classical GRS subcodes. As a consequence, we determine bounds on the dimension of the square code for these codes and construct a polynomial-time distinguisher capable of separating them from random linear codes for large parameter regimes. The distinguisher remains valid under 25
Table 1: Experimental results for the square code dimension of GSRS and random codes with different parameters. Code parameters
Square code dimension
q
m
n
k
GSRS codes
Random codes
4
2 24 24
4 4 4
60 60 60
10 13 14
40 55 60
55 60 60
24 24 24
6 6 6
90 90 90
12 15 16
63 84 90
78 90 90
26 26 26
2 2 2
126 126 126
32 42 43
93 123 126
126 126 126
26 26 26
4 4 4
252 252 252
42 52 53
200 250 252
252 252 252
26 26 26
6 6 6
378 378 378
44 56 57
287 371 378
378 378 378
Hamming-metric isometries, and, through shortening operations, applies to a well-defined range of code parameters. Finally, we emphasize that the existence of a distinguisher does not immediately yield key recovery or a complete cryptographic break of a McEliece-like cryptosystem based on the respective code family. While the distinguisher identifies GSRS and GLRS codes among random linear codes, constructing efficient attacks that recover secret keys from the public code remains an open problem. Addressing this problem requires new techniques beyond the square code criterion, and it constitutes an important direction for future research. Altogether, our results provide precise algebraic insights into GSRS and GLRS codes and establish a framework for assessing their security in post-quantum cryptographic schemes.
References 1. Alagic, G., Bros, M., Ciadoux, P., Cooper, D., Dang, Q., Dang, T., Kelsey, J., Lichtinger, J., Liu, Y.K., Miller, C., Moody, D., Peralta, R., Perlner, R., Robinson, A., Silberg, H., Smith-Tone, D., Waller, N.: Status report on the fourth round of the NIST post-quantum cryptography standardization process, NIST IR 8545. Tech. rep., National Institute of Standards and Technology (2025). https://doi. org/10.6028/NIST.IR.8545 2. Albrecht, M.R., Bernstein, D.J., Chou, T., Cid, C., Gilcher, J., Lange, T., Maram, V., von Maurich, I., Misoczki, R., Niederhagen, R., Paterson, K.G., Persichetti,
26
E., Peters, C., Schwabe, P., Sendrier, N., Szefer, J., Tjhai, C.J., Tomlinson, M., Wang, W.: Classic McEliece: conservative code-based cryptography: cryptosystem specification. Tech. rep., Round-4 submission to the NIST PQC standardization project (2022), https://classic.mceliece.org/mceliece-spec-20221023.pdf 3. Alfarano, G.N., Lobillo, F., Neri, A., Wachter-Zeh, A.: Sum-rank product codes and bounds on the minimum distance. Finite Fields and Their Applications 80, 102013 (2022). https://doi.org/10.1016/j.ffa.2022.102013 4. Baldi, M., Bianchi, M., Chiaraluce, F., Rosenthal, J., Schipani, D.: Enhanced public key security for the McEliece cryptosystem. Journal of Cryptology 29(1), 1–27 (2014). https://doi.org/10.1007/s00145-014-9187-8 5. Barg, S.: Some new NP-complete coding problems. Problemy Peredachi Informatsii 30(3), 23–28 (1994) 6. Berlekamp, E., McEliece, R., van Tilborg, H.: On the inherent intractability of certain coding problems. IEEE Transactions on Information Theory 24(3), 384– 386 (1978). https://doi.org/10.1109/TIT.1978.1055873 7. Boucher, D., Nouetowa, K.E.: A decoding algorithm for skew cyclic generalized skew Reed–Solomon codes. In: 2025 IEEE International Symposium on Information Theory (ISIT 2025) (2025), https://hal.science/hal-04893716 8. Boucher, D., Ulmer, F.: Linear codes using skew polynomials with automorphisms and derivations. Designs, Codes and Cryptography 70(3), 405–431 (2014). https: //doi.org/10.1007/s10623-012-9704-4 9. Cascudo, I., Cramer, R., Mirandola, D., Zémor, G.: Squares of random linear codes. IEEE Transactions on Information Theory 61(3), 1159–1173 (2015). https://doi. org/10.1109/TIT.2015.2393251 10. Coggia, D., Couvreur, A.: On the security of a Loidreau rank metric code based encryption scheme. Designs, Codes and Cryptography 88(9), 1941–1957 (2020). https://doi.org/10.1007/s10623-020-00781-4 11. Couvreur, A., Gaborit, P., Gauthier-Umaña, V., Otmani, A., Tillich, J.P.: Distinguisher-based attacks on public-key cryptosystems using Reed–Solomon codes. Designs, Codes and Cryptography 73(2), 641–666 (2014). https://doi. org/10.1007/s10623-014-9967-z 12. Couvreur, A., Otmani, A., Tillich, J.P., Gauthier-Umaña, V.: A polynomial-time attack on the BBCRS scheme. In: Public-Key Cryptography (PKC 2015). pp. 175– 193 (2015). https://doi.org/10.1007/978-3-662-46447-2_8 13. Esser, A., Verbel, J., Zweydinger, F., Bellini, E.: SoK: CryptographicEstimators – a software library for cryptographic hardness estimation. In: Proceedings of the 19th ACM Asia Conference on Computer and Communications Security (ASIA CCS ’24). pp. 560–574 (2024). https://doi.org/10.1145/3634737.3645007 14. Faugère, J.C., Gauthier-Umaña, V., Otmani, A., Perret, L., Tillich, J.P.: A distinguisher for high-rate McEliece cryptosystems. IEEE Transactions on Information Theory 59(10), 6830–6844 (2013). https://doi.org/10.1109/TIT.2013.2272036 15. Gabidulin, E.M., Paramonov, A.V., Tretjakov, O.V.: Ideals over a noncommutative ring and their application in cryptology. In: Advances in Cryptology (EUROCRYPT ’91). vol. 547, pp. 482–489 (1991). https://doi.org/10.1007/ 3-540-46416-6_41 16. Gabidulin, E.M.: Attacks and counter-attacks on the GPT public key cryptosystem. Designs, Codes and Cryptography 48(2), 171–177 (2008). https://doi.org/ 10.1007/s10623-007-9160-8 17. Gibson, J.K.: Severely denting the Gabidulin version of the McEliece public key cryptosystem. Designs, Codes and Cryptography 6(1), 37–45 (1995). https://doi. org/10.1007/bf01390769
27
18. Gibson, K.: The security of the Gabidulin public key cryptosystem. In: Advances in Cryptology (EUROCRYPT ’96). pp. 212–223 (1996). https://doi.org/10.1007/ 3-540-68339-9_19 19. Horlemann-Trautmann, A.L., Marshall, K., Rosenthal, J.: Considerations for rankbased cryptosystems. In: 2016 IEEE International Symposium on Information Theory (ISIT 2016). pp. 2544–2548 (2016). https://doi.org/10.1109/ISIT.2016. 7541758 20. Horlemann-Trautmann, A.L., Marshall, K., Rosenthal, J.: Extension of Overbeck’s attack for Gabidulin based cryptosystems. Designs, Codes and Cryptography 86, 319–340 (2018). https://doi.org/10.1007/s10623-017-0343-7 21. Huffman, W.C., Pless, V.: Fundamentals of Error-Correcting Codes. Cambridge University Press (2003). https://doi.org/10.1017/cbo9780511807077 22. Hörmann, F., Bartz, H., Horlemann, A.L.: Distinguishing and recovering generalized linearized Reed–Solomon codes. In: Code-Based Cryptography (CBCrypto 2022). pp. 1–20 (2023). https://doi.org/10.1007/978-3-031-29689-5_1 23. Kobara, K., Imai, H.: Semantically secure McEliece public-key cryptosystems: conversions for McEliece PKC. In: Public-Key Cryptography (PKC 2001). pp. 19–35 (2001). https://doi.org/10.1007/3-540-44586-2_2 24. Lam, T.Y.: A general theory of Vandermonde matrices. Expositiones Mathematicae 4, 193–215 (1986) 25. Lam, T., Leroy, A.: Vandermonde and Wronskian matrices over division rings. Journal of Algebra 119(2), 308–336 (1988). https://doi.org/10.1016/ 0021-8693(88)90063-4 26. Lam, T., Leroy, A.: Hilbert 90 theorems over division rings. Transactions of the American Mathematical Society 345(2), 595–622 (1994) 27. Leroy, A.: Pseudo linear transformations and evaluation in Ore extensions. Bulletin of the Belgian Mathematical Society - Simon Stevin 2(3), 321–347 (1995) 28. Li, Y.X., Deng, R., Wang, X.M.: On the equivalence of McEliece’s and Niederreiter’s public-key cryptosystems. IEEE Transactions on Information Theory 40, 271–273 (1994). https://doi.org/10.1109/18.272496 29. Liu, S.: Generalized skew Reed–Solomon codes and other applications of skew polynomial evaluation. Ph.D. thesis, University of Toronto (Canada) (2016) 30. Liu, S., Manganiello, F., Kschischang, F.R.: Construction and decoding of generalized skew-evaluation codes. In: 2015 IEEE 14th Canadian Workshop on Information Theory (CWIT 2015). pp. 9–13 (2015). https://doi.org/10.1109/CWIT. 2015.7255141 31. Liu, S., Manganiello, F., Kschischang, F.R.: Matroidal structure of skew polynomial rings with application to network coding. Finite Fields and Their Applications 46, 326–346 (2017). https://doi.org/10.1016/j.ffa.2017.04.007 32. Loidreau, P.: An evolution of GPT cryptosystem. In: International Workshop on Algebraic and Combinatorial Coding Theory (ACCT) (2016) 33. Loidreau, P.: A new rank metric codes based encryption scheme. In: Post-quantum cryptography (PQCrypto 2017). pp. 3–17 (2017). https://doi.org/https://doi. org/10.1007/978-3-319-59879-6_1 34. Maclagan-Wedderburn, J.H.: A theorem on finite algebras. Transactions of the American Mathematical Society 6(3), 349–352 (1905) 35. Martínez-Peñas, U.: Skew and linearized Reed–Solomon codes and maximum sum rank distance codes over any division ring. Journal of Algebra 504, 587–612 (2018). https://doi.org/https://doi.org/10.1016/j.jalgebra.2018.02.005
28
36. Martínez-Peñas, U.: Hamming and simplex codes for the sum-rank metric. Designs, Codes and Cryptography 88(8), 1521–1539 (2020). https://doi.org/10.1007/ s10623-020-00772-5 37. Martínez-Peñas, U., Kschischang, F.R.: Reliable and secure multishot network coding using linearized Reed–Solomon codes. IEEE Transactions on Information Theory 65(8), 4785–4803 (2019). https://doi.org/10.1109/TIT.2019.2912165 38. McEliece, R.J.: A public-key cryptosystem based on algebraic coding theory. The Deep Space Network Progress Report 42-44, 114–116 (1978) 39. National Institute of Standards and Technology (NIST): Submission requirements and evaluation criteria for the post-quantum cryptography standardization process (2016), https://csrc.nist. gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/ call-for-proposals-final-dec-2016.pdf 40. Niederreiter, H.: Knapsack-type cryptosystems and algebraic coding theory. Problems of Control and Information Theory 15, 159–166 (1986) 41. Nouetowa, K.E.: A post-quantum encryption scheme based on linearized ReedSolomon codes. Preprint: HAL science ouverte, hal-05441609 (2026), https:// hal.science/hal-05441609 42. Nouetowa, K.É., Loidreau, P.: An analysis of a generalization of Loidreau’s encryption scheme. Preprint: HAL science ouverte, hal-04894873 (2025), https: //hal.science/hal-04894873 43. Ore, O.: Theory of non-commutative polynomials. The Annals of Mathematics 34(3), 480–508 (1933). https://doi.org/10.2307/1968173 44. Otmani, A., Kalachi, H.T., Ndjeya, S.: Improved cryptanalysis of rank metric schemes based on Gabidulin codes. Designs, Codes and Cryptography 86(9), 1983– 1996 (2017). https://doi.org/10.1007/s10623-017-0434-5 45. Overbeck, R.: Structural attacks for public key cryptosystems based on Gabidulin codes. Journal of Cryptology 21(2), 280–301 (2007). https://doi.org/10.1007/ s00145-007-9003-9 46. Overbeck, R.: A new structural attack for GPT and variants. In: Progress in Cryptology (Mycrypt 2005). pp. 50–63 (2005). https://doi.org/10.1007/11554868_5 47. Overbeck, R.: Public key cryptography based on coding theory. Ph.D. thesis, Technische Universität Darmstadt (2007) 48. Prange, E.: The use of information sets in decoding cyclic codes. IRE Transactions on Information Theory 8(5), 5–9 (1962). https://doi.org/10.1109/TIT.1962. 1057777 49. Rashwan, H., Gabidulin, E.M., Honary, B.: A smart approach for GPT cryptosystem based on rank codes. In: 2010 IEEE International Symposium on Information Theory (ISIT 2010). pp. 2463–2467 (2010). https://doi.org/10.1109/isit. 2010.5513549 50. Roth, R.: Introduction to coding theory. Cambridge University Press, Cambridge (2006). https://doi.org/10.1017/CBO9780511808968 51. Sidelnikov, V.M., Shestakov, S.O.: On insecurity of cryptosystems based on generalized Reed–Solomon codes. Discrete Mathematics and Applications 2(4), 439–444 (1992). https://doi.org/10.1515/dma.1992.2.4.439 52. The Sage Developers: SageMath, the Sage Mathematics Software System (Version 10.5) (2024), https://www.sagemath.org 53. Wieschebrink, C.: Two NP-complete problems in coding theory with an application in code based cryptography. In: 2006 IEEE International Symposium on Information Theory (ISIT 2006). pp. 1733–1737 (2006). https://doi.org/10.1109/isit. 2006.261651
29
54. Wieschebrink, C.: Cryptanalysis of the Niederreiter public key scheme based on GRS subcodes. In: Post-Quantum Cryptography (PQCrypto 2010). pp. 61–72 (2010). https://doi.org/10.1007/978-3-642-12929-2_5 55. Wilhelm, F.K., Steinwandt, R., Zeuch, D., Lageyre, P., Kirchhoff, S.: Status of quantum computer development, version 2.1. Tech. rep., Federal Office for Information Security (BSI) (2024), https://www.bsi.bund.de/dok/study_status_ quantum_computer
A
The ReSkew cryptosystem
We use this appendix to introduce the ReSkew cryptosystem which is built on Reed–Solomon codes in a skew setting and uses Hamming-isometric disguising. It allows us to showcase the cryptographic potential of GSRS codes by selecting parameter sets adhering to NIST’s security levels and providing their key and ciphertext sizes for comparison with state-of-the-art schemes. Moreover, ReSkew is a straightforward example of a code-based cryptosystem whose public keys are susceptible to the square code distinguisher presented in the main paper. As pointed out in Section 3.4, efficient distinguishing does not directly break a McEliece-like cryptosystem but we understand the skepticism the community usually shows for systems based on distinguishable algebraic codes. In the design of the scheme, we closely follow Classic McEliece [2] which advanced to the fourth and last round of NIST’s standardization project for post-quantum KEMs [1]. In particular, ReSkew employs the Niederreiter framework [40], which is equivalent to McEliece’s original approach to code-based cryptography [38] according to [28]. We also adopt systematic public keys, that (n−k)×n but only the nonis, we do not use a whole parity-check matrix H ∈ Fqm identity part T of its systematic form (In−k | T ). As in the main part of the paper, we work with the Hamming metric even though many GSRS codes have good properties with respect to the skew metric as well (see Lemma 5). Our approach has the advantage that we can employ well-established estimators for the complexity of generic decoding when selecting parameters [13]. Nevertheless, an adaptation of ReSkew to the skew metric probably allows to reduce the public key size even further. It is also possible to translate the system to the sum-rank metric by switching to GLRS codes. A.1
System description
We present ReSkew as a PKE scheme and thus describe it by means of the three algorithms for key generation, encryption, and decryption in the following. We start with a parameter set of the form (q, m, s, n, k, t) containing the following: – A prime power q and an integer m > 1 which determine the considered field extension Fqm over Fq . s – An integer 0 < s < m which chooses the Fqm -automorphism θ as θ(x) = xq for x ∈ Fqm and thus decides on the skew-polynomial ring Fqm [x; θ]. – Three integers n, k, and t which define the code’s length n ≤ m(q − 1), its dimension k < n, and a decodable error weight t ≤ 12 (n − k) .
30
Algorithm 1: ReSkew key generation. Input : ReSkew parameter set with params = (q, m, s, n, k, t). Output : ReSkew key pair (pk, sk). Function KeyGen(params): Set up the GSRS generator matrix Gsec = Vθk (b) · diag(λ) ∈ Fk×n q m for random Pθ -independent code locators b ∈ Fn q m and random nonzero column multipliers λ ∈ Fn qm . 3 Compute the systematic form (U | Ik ) of Gsec . (n−k)×n 4 Set up the GSRS parity-check matrix Hpub = (In−k | −U ⊤ ) ∈ Fqm . ⊤ 5 return public key pk = (T ) with T = −U , secret key sk = (b, λ).
1
2
Key generation. Algorithm 1 displays the ReSkew key generation and starts from a selected parameter set. After suitable code locators b and column multipliers λ are drawn uniformly at random, the generator matrix Gsec is constructed as the Vandermonde-like matrix Vθk (b)·diag(λ). Then, its systematic form is computed to disguise the secret parameters b and λ, and to derive the parity-check matrix Hpub . Since the identity part of Hpub can be restored easily, only T is used as public key pk. Thus, the k(n − k) entries of T determine ReSkew’s public key size, which is k(n − k) · ⌈log2 (q m )⌉ bits. The secret key sk consists of the two length-n vectors b and λ. As a consequence, 2n field elements need to be stored and the secret-key size amounts to 2n · ⌈log2 (q m )⌉ bits. Note that the insecure subclasses of GRS and Gabidulin codes can be filtered out easily in the third line of Algorithm 1. However, the probability of sampling such a code is negligible and we therefore omit the check. Further, notice that GSRS codes are MDS and thus naturally admit a parity-check matrix in systematic form [50, Prop. 11.4]. This ensures that Algorithm 1 always succeeds.
Algorithm 2: ReSkew encryption. Input : ReSkew public key pk = (T ), message m ∈ Fn q m of weight t. Output : Ciphertext c. Function Encrypt(pk, m): Set up Hpub = (In−k | T ). ⊤ 3 Compute c = mHpub ∈ Fn−k qm . 4 return ciphertext c.
1
2
Encryption. Algorithm 2 depicts the encryption process whose inputs are a public key T and a message m of weight t to be encrypted. After the parity⊤ . Since the check matrix Hpub = (In−k | T ) is set up, m is encrypted as mHpub m ciphertext has length n − k, it can be stored in (n − k) · ⌈log2 (q )⌉ bits. 31
Algorithm 3: ReSkew decryption. Input : ReSkew secret key sk = (b, λ), ciphertext c ∈ Fn−k qm . Output : Decrypted message m. Function Decrypt(sk, c): Set up Gsec = Vθk (b) · diag(λ). 3 Obtain c0 = (c | 0) ∈ Fn q m by appending k zeros to c. 4 Use Gsec to find a codeword cb with distance at most t from c0 . 5 Recover m = c0 − cb. 6 return decrypted message m.
1
2
Decryption. ReSkew’s decryption is displayed in Algorithm 3 and starts from a ciphertext c and the corresponding secret key sk = (b, λ). First, the secret generator matrix Gsec is constructed as Vθk (b) · diag(λ) and a length-n vector c0 is obtained by appending k zeros to the ciphertext c. Then, Gsec is used to perform bounded-distance decoding with radius t on the vector c0 , that is, the GSRS decoder finds a codeword cb whose distance to c0 is at most t. The decrypted message m is then retrieved as the difference c0 − cb, which we prove in Lemma 24 below. The main idea is to exploit the systematic form of the public key to derive a vector c0 for which the unique codeword cb with distance at most t can be determined explicitly. The lemma adapts the decryption strategy used in Classic McEliece and described in [2, Sec. 4.4] from binary extension fields to arbitrary finite fields. Lemma 24. When c = Encrypt(pk, m) is a faithfully generated ReSkew ciphertext and (pk, sk) is a valid key pair, then Decrypt(sk, c) from Algorithm 3 correctly recovers the original message m. Proof. First observe that the vector c0 = (c | 0) ∈ Fnqm satisfies ⊤ c0 Hpub = (c | 0) · (In−k | T )⊤ = c.
This implies that c0 − m is a codeword of the GSRS code defined by the paritycheck matrix Hpub because ⊤ ⊤ ⊤ (c0 − m) · Hpub = c0 Hpub − mHpub =c−c=0
applies. Further, c0 −m has distance t from c0 , as dH (c0 , c0 −m) = wtH (m) = t. Note that the considered GSRS code has length n and dimension k, and thus a minimum distance of n − k + 1. Since t is chosen as t = 21 (n − k) , at most one codeword can lie within a distance of t of a given point. Therefore, c0 − m is the unique codeword of distance at most t from c0 and the GSRS decoder in Algorithm 3 recovers it as cb. As a consequence, we can recover m as c0 − cb = c0 − (c0 − m) = m. ⊓ ⊔ Remark that the decryption algorithm relies on unique decoding of GSRS codes up to half the Singleton bound. This can be achieved efficiently by a Berlekamp–Welch-like approach in cubic complexity [30], for example. 32
A.2
Parameter sets
In the following, we present ReSkew parameter sets for each of the security levels that NIST defined for their PQC standardization process. Security levels one, three, and five refer to any break of the system requiring at least as many computational resources as a brute-force key search on AES-128, AES-192, or AES-256, respectively [39, Sec. 4.A.5]. Their security-bit equivalents are estimated as 143, 207, and 272 bits in [39, Sec. 4.A.5]. We take a conservative path and add a security margin of five bits on top of NIST’s bit estimates and thus arrive at target security levels of 148, 212, and 277 security bits, respectively. Information-set decoding. Assuming that we choose GSRS codes with parameters for which no efficient structural attacks are known, the selection of suitable parameter sets boils down to estimating the complexity of the best known attacks on the underlying hard problem. The fastest known strategy for the computational SDP is information-set decoding (ISD), which Prange coined in 1962 [48]. The main idea is to introduce a permutation matrix P ∈ Fn×n and alter the qm equality eH ⊤ = s to obtain eP −1 P H ⊤ = s. This step is equivalent to switching to another SDP instance with parity-check matrix HP ⊤ and weight-t error eP −1 . The hope is that now all t nonzero entries of eP −1 are condensed in the first n − k coordinates because this special case allows to recover e efficiently by means of linear algebra. It can be easily checked if the new SDP instance has the desired property and thus the process can be repeated for random permutations until it successfully recovers e. The expected number of permutations to try until succeeding is n t n−k t
and this is the dominating factor of the computational complexity of Prange’s algorithm [13, Sec. 4.3]. The literature contains many improvements and variants of ISD procedures and most of them allow that a constant predefined share of the error weight is still located in the last k entries of the permuted error. This reduces the expected number of trials but increases the cost of each iteration since the enumeration of valid second parts of e takes longer than assuming it being equal to 0. Note that a series of improvements in terms of the enumeration are tailored to binary fields and not applicable to q-ary fields with q > 2 [13, Sec. 4.3]. Thus, these variants are no threat for ReSkew due to its need for a nontrivial field extension. We employ the CryptographicEstimators library [13] to obtain complexity estimates for ISD algorithms, which let us assess the security of potential parameter sets and reach good tradeoffs between efficiency and security. We aim for conservative estimates and stick to the widely adopted random access machine (RAM) model, which neglects memory-access costs. We use the library’s SDP estimator for nonbinary finite fields for which the ISD variants by Prange, by Lee–Brickell, and by Stern are implemented. Note that this estimator counts additions in the respective finite field but neglects multiplications because the latter are assumed to be implemented via lookup tables [13, Sec. 4.3]. 33
Parameter constraints. Observe that ReSkew parameters need to satisfy certain properties. In particular, we need to choose a nontrivial automorphism θ to exclude the GRS case and thus prohibit efficient key-recovery attacks. This s implies that s with θ(x) = xq can take values from 1 to m − 1 and therefore m > 1 is necessary. Additionally, the code locators of a GSRS code need to be P-independent which yields the restriction n ≤ m(q − 1). We further fix t = 12 (n − k) as the maximal Hamming weight for which the chosen nontrivial GSRS code of dimension k < n can decode errors uniquely. This is reasonable since a larger error weight does not increase key and ciphertext sizes but tends to result in higher ISD costs.
Table 2: ReSkew parameter sets. q
m
s
n
k
t
Level 1 Level 1
233 256
2 2
1 1
427 427
325 325
51 51
ReSkew-3 ReSkew-3-bin
Level 3 Level 3
331 512
2 2
1 1
627 626
465 464
81 81
ReSkew-5 ReSkew-5-bin
Level 5 Level 5
457 512
2 2
1 1
842 842
624 624
109 109
parameter set
NIST level
ReSkew-1 ReSkew-1-bin
Table 3: Key and ciphertext sizes for the ReSkew parameter sets from Table 2, rounded up to full bytes. parameter set
NIST level
public key (bytes)
secret key (bytes)
ciphertext (bytes)
ReSkew-1 ReSkew-1-bin
1 1
66,300 66,300
1,708 1,708
204 204
ReSkew-3 ReSkew-3-bin
3 3
160,077 169,128
2,665 2,817
345 365
ReSkew-5 ReSkew-5-bin
5 5
306,072 306,072
3,789 3,789
491 491
Parameter sets. Since public key size is the major drawback of Classic McEliece, we decided to optimize the ReSkew parameter sets for small public keys. We iterated over many possibilities with the above discussed parameter restrictions in mind and analyzed the bit-security level by means of the SDP estimator from the CryptographicEstimators library. Then, we picked the parameter set 34
with the smallest public key for each of the target security levels of 148, 212, and 277 bits and named them ReSkew-1, ReSkew-3, and ReSkew-5, respectively. In addition, we provide the parameter sets ReSkew-1-bin, ReSkew-3-bin, and ReSkew-5-bin based on binary extension fields to simplify the implementation and to avoid storage overhead. All proposed ReSkew parameter sets are depicted in Table 2 and the resulting system properties are displayed in Table 3. Remark that all sets use extension fields of degree two and thus the only valid choice for a nontrivial automorphism, namely the Frobenius automorphism σ defined by σ(x) = xq . The code rates for the three security levels are about 0.76, 0.74, and 0.74, which aligns with the rates between 0.7 and 0.8 employed in Classic McEliece. The resulting public key sizes are about 66.3 kB, 0.17 MB, and 0.31 MB for the security categories one, three, and five, respectively. In particular, this means an improvement of the public key size by at least a factor three compared to Classic McEliece for each security level.
35