Maximum-Likelihood Decoding of Gabidulin Codes Is NP-Hard Even in Dimension One

Maximum-Likelihood Decoding of Gabidulin Codes Is NP-Hard Even in Dimension One Philippe Gaborit

arXiv:2610.34404v1 [cs.CR] 25 Oct 2026

XLIM, Université de Limoges, France gaborit@unilim.fr

Abstract. Fix a prime power q. We prove that deciding whether a received word y ∈ Fn q m lies at rank distance at most n − 2 from the one-dimensional Gabidulin code {λg : λ ∈ Fqm } is NP-complete. Thus maximum-likelihood decoding of Gabidulin codes is NP-hard even for k = 1, an analogue of the Guruswami–Vardy theorem for Reed–Solomon codes. In the Hamming metric, by contrast, hardness at this radius requires the dimension to grow with the length, as in the Guruswami–Vardy theorem. The reduction is deterministic; consequently Rank Syndrome Decoding (RSD) and Rank Minimum Distance (RMD) for Fqm -linear codes are NP-complete under deterministic polynomial reductions, whereas the previously known reduction was randomized. The proof goes through a pivot problem that we introduce, Twisted Square Membership (TSM): given Fq -subspaces U, W ⊂ FqN , decide whether some non-zero a ∈ U satisfies aq+1 ∈ W . Quadratic systems in d unknowns are encoded into TSM, then TSM into Gabidulin decoding. The last step views the received word as an Fq -linear map and decoding at radius n − 2 as the search for an Fq -plane on which it acts as a scalar. With support U ⊕ τ W in a 2 cubic extension and map a + τ b 7→ aq + τ bq , two Frobenius twists force solution planes to encode the relation aq+1 ∈ W . All constructions are explicit and polynomial, with N = O(qd2 ), n ≤ N + d, and m = 3N . Keywords: Rank metric · Gabidulin codes · NP-completeness · maximumlikelihood decoding · MinRank

1

Introduction

1.1

Context and motivation

Gabidulin codes [11, 16] are the rank-metric analogues of Reed–Solomon codes. They are maximum rank distance codes and can be decoded in polynomial time up to ⌊(n − k)/2⌋ errors. Beyond half the minimum distance, however, the picture changes sharply: no analogue of the Guruswami–Sudan algorithm is known, and for many parameters no efficient worst-case list decoder can exist because some received words have exponentially many nearby codewords [36, 32]. The complexity of maximum-likelihood decoding for Gabidulin codes themselves has remained open, to the best of our knowledge. Our main result closes this gap in

2

P. Gaborit

a particularly rigid case: for every fixed prime power q, decoding is NP-complete already for dimension-one Gabidulin codes at radius n − 2 (Theorem 1). This result fits into a longer line of hardness results for decoding. In the Hamming metric, Berlekamp, McEliece and van Tilborg proved that decoding a general linear code is NP-complete [5]; Vardy settled the corresponding minimumdistance problem [35], and Dumer, Micciancio and Sudan proved hardness of approximation [12]. Structured algebraic codes require separate arguments. Reed– Solomon codes admit polynomial-time decoding up to half the minimum distance, and the Guruswami–Sudan algorithm reaches the Johnson radius [23]; nevertheless, Guruswami and Vardy proved maximum-likelihood decoding NP-hard at radius n − k − 1 over fields of exponential size [26]. Further hardness results connect bounded-distance decoding to discrete logarithms [8], cover algebraicgeometry codes under randomized reductions [7], and lower the NP-hard radius for Reed–Solomon codes to n − k − c log n/ log log n [20]. In the rank metric, a vector in Fnqm is weighted by the Fq -dimension of the space spanned by its coordinates rather than by the number of non-zero coordinates. Besides their coding-theoretic role, Gabidulin codes underlie error control in random linear network coding [27, 34] and have found applications in theoretical computer science, from explicit hitting sets for low-rank matrices [14] to list decoding via subspace designs [24, 22]; random Gabidulin codes achieve list decoding capacity [25]. On the complexity side, MinRank is NP-complete [6], and decoding an Fq -linear code is an instance of MinRank. The Fqm -linear case is substantially more rigid. Gaborit and Zémor proved hardness for such rank-metric decoding problems through a randomized reduction from Hamming decoding [19], but no hardness result was known for maximum-likelihood decoding of Gabidulin codes themselves, to the best of our knowledge. The question also matters in rank-based cryptography. The first rank-metric encryption scheme, due to Gabidulin, Paramonov and Tretjakov [18], is a McEliecetype construction based on a disguised Gabidulin code; Overbeck’s structural attacks [30] motivated repaired variants, including Loidreau’s scheme [29] and its subsequent cryptanalysis [9]. More directly related to this work, the Faure– Loidreau scheme [13] and its repaired version LIGA [31] rely on decoding Gabidulin codes beyond the unique-decoding radius. Our result concerns worstcase complexity only and does not address the particular parameters or instance distributions used by these cryptosystems; it places the underlying worst-case decoding problem on a firmer complexity-theoretic footing. Other rank-based constructions rely on rank syndrome decoding for random or quasi-cyclic Fqm -linear codes, including LRPC-based schemes [17, 1], the ROLLO and RQC candidates to the NIST post-quantum standardization process [3, 4], and rank-based signatures such as Durandal [2]. 1.2

The idea of the method

The proof rests on three elementary observations whose combination is the key. First, decoding becomes an eigenplane problem. For a dimension-one Gabidulin code {λg}, the received word y can be viewed as an Fq -linear map ỹ on the

ML decoding of Gabidulin codes is NP-hard

3

Fq -space spanned by the coordinates of g, while the codeword λg corresponds to multiplication by λ. Decoding at radius n − 2 is therefore equivalent to finding an Fq -plane on which ỹ acts as a scalar, which we call an eigenplane. Second, the eigenplane equation produces a twisted square. Because the received word is part of the constructed instance, we let ỹ act by different Frobenius 2 twists on different parts of the support. Comparing a 7→ aq and b 7→ bq along an eigenplane yields b ∈ F∗q aq+1 . Thus the only non-linearity that must be encoded is the map a 7→ aq+1 = a · aq . This leads to the pivot problem Twisted Square Membership (TSM): given subspaces U, W ⊂ FqN , decide whether there exists a non-zero a ∈ U with aq+1 ∈ W . The linear membership constraints are built into the support, while the eigenplane equation supplies the non-linear relation. Third, twisted squares encode homogeneous quadratic systems. The element a · aq is quadratic in the Fq -coordinates of a. With a suitable basis of U , every homogeneous quadratic system can be represented by linear conditions on aq+1 . Since such systems encode 3-SAT, TSM is NP-complete. The complete reduction is therefore 3-SAT −→ HomMQ −→ TSM −→ GabDec1 , with TSM separating the finite-field encoding of quadratic forms from the Gabidulin decoding construction. 1.3

Contributions and organization

Theorem 1 proves that, for every fixed prime power q, deciding whether a received word lies at rank distance at most n − 2 from a dimension-one Gabidulin code is NP-complete. Radius n − 1 is always reachable, so n − 2 is the first nontrivial radius. Maximum-likelihood decoding is therefore NP-hard as soon as the problem ceases to be trivial, already for k = 1. This is a rank-metric analogue of the Guruswami–Vardy theorem, with the notable difference that its Hamming-metric counterpart requires growing dimension; see Section 7. The reduction is deterministic. As a consequence, rank syndrome decoding and rank minimum distance for general Fqm -linear codes are NP-complete under deterministic polynomial reductions, with rank minimum distance already hard for dimension-two codes (Corollaries 3 and 4). The previously known reduction for these problems was randomized [19]. A further contribution is the pivot problem TSM, a compact NP-complete problem over finite fields that may be of independent interest. The construction is fully explicit: the encoding exponents are given by a closed formula obtained by interleaving base-q expansions, and a quadratic system in d unknowns leads to parameters N = O(qd2 ), n ≤ N + d, and m = 3N . Organization. Section 2 recalls the necessary background and develops the eigenplane formulation and TSM. Section 3 states the main theorem and gives the complete reduction at a high level. Sections 4–6 prove its three steps. Section 7 derives the complexity consequences, and Section 8 discusses open questions and suggests some directions.

4

2

P. Gaborit

Background and preliminaries

This section gathers what the reduction needs. The first part recalls standard material: the rank metric, Gabidulin codes, the two decoding problems of rankmetric coding theory, and the two classical NP-complete problems, 3-SAT and homogeneous quadratic systems, from which we start. The second part contains the two ingredients specific to this paper: the reformulation of decoding in dimension one as the search for an eigenplane, and the pivot problem TSM. 2.1

Background: known problems

Throughout, q is a fixed prime power. For v = (v1 , . . . , vn ) ∈ Fnqm , the rank rk(v) is the dimension over Fq of ⟨v1 , . . . , vn ⟩Fq ; equivalently it is the rank of the m × n matrix over Fq whose j-th column is the vector of coordinates of vj in a fixed basis of Fqm /Fq . The rank distance is d(u, v) = rk(u − v). For instance, with α ∈ Fqm \ Fq , the vector (α, α, α + 1) has Hamming weight 3 but rank 2, its coordinates spanning ⟨1, α⟩: vanishing coordinates in the Hamming metric are replaced by Fq -linear dependencies in the rank metric. An Fqm -linear code of length n ≤ m and dimension k has minimum rank distance at most n − k + 1; this is the Singleton bound for the rank metric [11, 16], and codes meeting it are called maximum rank distance (MRD) codes. Let g ∈ Fnqm with rk(g) = n. The Gabidulin code of dimension k is Gab(g, k) = P i {(f (g1 ), . . . , f (gn ))} where f runs over the q-polynomials i<k fi X q with fi ∈ Fqm ; it is MRD, with minimum rank distance n − k + 1. For k = 1 one has f (X) = λX, so Gab(g, 1) = {λg : λ ∈ Fqm } has minimum distance n and unique decoding radius ⌊(n − 1)/2⌋. At the other end, decoding Gab(g, 1) at radius n − 1 is easy: every received word lies at rank distance at most n − 1 from the code, since for any coordinate yj the scalar λ = yj /gj makes the j-th coordinate of y − λg vanish, so that its coordinates span a space of dimension at most n − 1. The first radius at which decoding is a non-trivial question is therefore n − 2. We shall decode this code, but our conclusions concern the two general problems of rank-metric coding theory, which we recall now. An Fqm -linear code of length n and dimension k is given by a generator matrix G ∈ Fk×n q m or by a (n−k)×n

parity-check matrix H ∈ Fqm the codeword as certificate.

. Both problems below are in NP, with e or (n−k)×n

Definition 1 (rank syndrome decoding, RSD). Given H ∈ Fqm , a n−k n syndrome s ∈ Fqm and an integer t, decide whether there exists e ∈ Fqm with He⊤ = s and rk(e) ≤ t. Definition 2 (rank minimum distance, RMD). Given G ∈ Fk×n and an qm integer w, decide whether the code generated by G contains a non-zero codeword of rank at most w. RSD is equivalent to bounded-distance decoding, with input (G, y, t) and question whether some codeword lies at rank distance at most t from y, since e = y − c and H, s = Hy ⊤ are computed from G and y in polynomial time.

ML decoding of Gabidulin codes is NP-hard

5

Remark 1 (relation with MinRank). Identifying a vector of Fnqm with its m × n matrix of coordinates over Fq , the codewords of an Fqm -linear code form an Fq -space of matrices, and RSD asks for a matrix of rank at most t in an affine space of matrices: this is an instance of MinRank. It is a structured one, since the matrix space is stable under multiplication by Fqm ; for the code {λg}, for instance, every non-zero matrix of the space has full rank n. This gives RSD ≤ MinRank and not the converse, so the hardness of MinRank [6] does not transfer and a dedicated reduction is needed. The source of our reduction is the satisfiability problem for formulas in 3-conjunctive normal form. Definition 3 (3-SAT). An instance consists of Boolean variables b1 , . . . , bv and a formula Φ = C1 ∧· · ·∧Cc . Each clause Cj is a disjunction ℓj,1 ∨ℓj,2 ∨ℓj,3 of three literals, a literal being either a variable bi or its negation ¬bi . An assignment is a map σ : {b1 , . . . , bv } → {true, false}; it makes the literal bi true if σ(bi ) = true, the literal ¬bi true if σ(bi ) = false, a clause true if at least one of its three literals is true, and Φ true if all clauses are true. The question is whether there exists an assignment making Φ true, in which case Φ is satisfiable. For instance Φ = (b1 ∨ ¬b2 ∨ b3 ) ∧ (¬b1 ∨ b2 ∨ b3 ) is satisfiable, by σ(b3 ) = true, whatever the values of b1 and b2 . 3-SAT is the NP-complete problem of Cook and Levin [21]; the size of an instance is polynomial in v + c. Its first translation is into quadratic systems, whose NP-completeness is classical as well [15, 21]; we use the homogeneous version. Definition 4 (HomMQ). Given homogeneous quadratic forms Q1 , . . . , Qs in d unknowns over Fq , decide whether there exists x = (x1 , . . . , xd ) ∈ Fdq , x = ̸ 0, with Q1 (x) = · · · = Qs (x) = 0. 2.2

Preliminaries: the eigenplane formulation and the TSM pivot problem

We next specialize to the problem studied in this paper: decoding dimension-one Gabidulin codes at the first nontrivial radius. Definition 5 (GabDec1 ). Given g, y ∈ Fnqm with rk(g) = n, decide whether there exists λ ∈ Fqm such that rk(y − λg) ≤ n − 2. This is RSD for k = 1, G = g and t = n − 2; it is in NP with λ as certificate. Radius n − 1 is always reachable, as shown below, so n − 2 is the first non-trivial radius. The key to everything that follows is to read vectors as linear maps. Throughout the paper, g = (g1 , . . . , gn ) ∈ Fnqm has Fq -linearly independent coordinates, and we call G = ⟨g1 , . . . , gn ⟩Fq ⊂ Fqm the support of the code Gab(g, 1); it is an Fq -space of dimension n, of which g is a basis.

6

P. Gaborit

Definition 6 (the map ỹ). For y = (y1 , . . . , yn ) ∈ Fnqm , we denote by ỹ : G → Fqm the unique Fq -linear map such that ỹ(gj ) = yj for j = 1, . . . , n, that is, ỹ

n X j=1



cj gj =

n X

cj yj

(cj ∈ Fq ).

j=1

Lemma 1 (vectors as linear maps). The map y 7→ ỹ is a bijection between Fnqm and the set of Fq -linear maps G → Fqm , whose inverse is ỹ 7→ (ỹ(g1 ), . . . , ỹ(gn )). Under this bijection, the codeword λg corresponds to the multiplication by λ on G, and y − λg corresponds to ỹ − λ. Proof. An Fq -linear map on G is determined by the images of the basis g, and these images can be prescribed arbitrarily. The map attached to λg sends gj to λgj , hence is x 7→ λx by linearity; the last assertion follows since y 7→ ỹ is Fq -linear. In particular, choosing a received word is the same as choosing an Fq -linear map on the support; this is how received words will be constructed in Section 6. Lemma 2. rk(y − λg) = n − dimFq Ker(ỹ − λ). Proof. The coordinates of y − λg are the images (ỹ − λ)(gj ) of a basis of G, so they span Im(ỹ − λ); conclude with the rank theorem. Lemma 3 (eigenplane). There exists λ with rk(y − λg) ≤ n − 2 if and only if there exist Fq -linearly independent x1 , x2 ∈ G with ỹ(x1 ) x2 = ỹ(x2 ) x1 . Proof. If dim Ker(ỹ − λ) ≥ 2, two independent vectors x1 , x2 of this kernel satisfy ỹ(xi ) = λxi , whence ỹ(x1 )x2 = λx1 x2 = ỹ(x2 )x1 . Conversely put λ = ỹ(x1 )/x1 ; the equation gives ỹ(x2 ) = λx2 , and since ỹ − λ is Fq -linear the whole plane ⟨x1 , x2 ⟩ lies in its kernel. For a single vector the condition is empty: any x = ̸ 0 gives λ = ỹ(x)/x, which is why radius n − 1 is trivial. In Lemma 3 the equation is written for one basis (x1 , x2 ) of the plane; in Section 6 we shall apply it to other pairs of vectors of the same plane, which the following lemma allows. Lemma 4 (eigenplane equation for all pairs). Let L ⊂ G be an Fq -plane. The following are equivalent: (i) ỹ(x1 )x2 = ỹ(x2 )x1 for one basis (x1 , x2 ) of L; (ii) L ⊂ Ker(ỹ − λ) for some λ ∈ Fqm ; (iii) ỹ(x) x′ = ỹ(x′ ) x for all x, x′ ∈ L. Proof. (i)⇒(ii) is the second half of the proof of Lemma 3, with λ = ỹ(x1 )/x1 . (ii)⇒(iii): every x ∈ L satisfies ỹ(x) = λx, hence for x, x′ ∈ L, ỹ(x)x′ = λxx′ = ỹ(x′ )x. (iii)⇒(i) is a special case. We call a plane satisfying these conditions a solution plane; by Lemma 2, the decoding instance is a yes-instance if and only if a solution plane exists. The eigenplane formulation tells us what has to be encoded: a plane on which ỹ acts as a scalar. The reduction will be organized around an intermediate problem tailored to this, which we introduce now. Let E = FqN . For a ∈ E we call aq+1 = a · aq the twisted square of a: it is a square twisted by the Frobenius, and for a ∈ Fq2 it would be the norm to Fq , but here N will be odd.

ML decoding of Gabidulin codes is NP-hard

7

Definition 7 (Twisted Square Membership, TSM). Given an integer N ≡ ±1 (mod 6) and two Fq -subspaces U, W of E = FqN by bases, decide whether there exists a ∈ U \ {0} whose twisted square aq+1 lies in W . The problem is in NP, with a as certificate. Since a 7→ aq is Fq -linear, the twisted square is a quadratic form in the coordinates of a, which is what allows TSM to encode HomMQ (Section 5); and it is the non-linear operation computed by an eigenplane equation, which is what allows TSM to embed into GabDec1 (Section 6). The condition on N combines two constraints of the latter step: N odd, so that Fq2 ∩ FqN = Fq , and N prime to 3, so that a cubic extension of Fq stays cubic over FqN . We are not aware of TSM having been studied before.

3

Main result and overview of the reduction

We can now state the main result. It concerns the simplest Gabidulin codes, those of dimension one, at the first radius beyond which decoding is not trivial, n − 2; in particular it does not depend on any special structure of the received word, which is part of the input. The field size q is fixed, while the length n and the extension degree m are part of the input and are polynomial in the size of the source formula. Theorem 1. For every fixed prime power q, GabDec1 is NP-complete. More precisely, a 3-SAT formula with v variables and c clauses is mapped in deterministic polynomial time to an instance with m = 3N and n ≤ N + d, where d = 1 + v + c, N ≡ ±1 (mod 6) and N = O(q d2 ). Membership in NP was noted in Section 2. NP-hardness is proved by a reduction from 3-SAT in three steps, §4

§5

§6

3-SAT −−→ HomMQ −−→ TSM −−→ GabDec1 , each step being an equivalence between a yes-instance of one problem and a yes-instance of the next (Propositions 1, 2 and 3). Before giving the details, we describe the three steps once in a row, following the same object along the chain: a satisfying assignment of the formula becomes a non-zero solution x of a quadratic system, then a field element a, and finally a plane ⟨a, τ aq+1 ⟩ on which the received word acts as a scalar. From 3-SAT to HomMQ. Given a formula Φ with variables b1 , . . . , bv and clauses C, we write a system of quadratic equations in d = 1 + v + c unknowns over Fq : an unknown h which stands for the constant 1, one unknown zi per variable, which stands for its truth value, and one auxiliary unknown wC per clause. The equations say that zi ∈ {0, 1} and that at least one literal of each clause is true. The unknown h is there to make all equations homogeneous: a satisfying assignment gives a solution with h = 1, and conversely homogeneity and the equations zi2 = hzi force any non-zero solution to have h = ̸ 0, hence to come from a satisfying assignment. This yields homogeneous quadratic forms Q1 , . . . , Qs such that Φ is satisfiable if and only if the Qk have a common zero x ̸= 0.

8

P. Gaborit

From HomMQ to TSM. We encode the d coordinates of x into a single field element so that all the quadratic forms become linear conditions on its twisted square. We take E = FqN with a generator α, choose exponents e1 < · · · < ed , and encode x as a = ϕ(x) = x1 αe1 + · · · + xd αed ; this identifies Fdq with the e1 ed subspace ̸ 0 with a = ̸ 0. Expanding aq+1 = a · aq P U = ⟨α , . . . , α ⟩, and x = gives i≤j xi xj µij with µij ∈ E; the exponents are chosen so that the µij are linearly independent, which means that aq+1 "remembers" every monomial xi xj separately. Trace duality then provides, for each k, an element tk ∈ E with Tr(tk aq+1 ) = Qk (x) for all x. Putting W = {z ∈ E : Tr(tk z) = 0 for all k}, the conditions Qk (x) = 0 become aq+1 ∈ W . This gives an instance (U, W ) of TSM that is a yes-instance if and only if the system has a non-zero solution. From TSM to GabDec1 . From (U, W ) we build a code and a received word, i.e. a support G and an Fq -linear map ỹ on it, so that the eigenplanes of ỹ are exactly the planes ⟨a, τ aq+1 ⟩ with a a solution of TSM. Three things must be imposed on a plane: its shape, and the two conditions of TSM. The linear conditions are placed in the support: G = U ⊕ τ W inside a cubic extension K = E(τ ), so that every vector of G is a + τ b with a ∈ U , b ∈ W . The eigenplane equation, one equality in K, is then three equalities in E, one per coefficient on 1, τ, τ 2 , and this 2 is what the cubic extension is for. We take ỹ(a + τ b) = aq + τ bq , two Frobenius twists with different exponents. Two of the three equalities force the plane to be ⟨a, τ b⟩; the third compares the two twists and forces b to be the twisted square aq+1 , up to a scalar of Fq , so that aq+1 ∈ W . Conversely a solution a of TSM gives the eigenplane ⟨a, τ aq+1 ⟩. Thus (g, y) is a yes-instance exactly when (U, W ) is; the details are in Section 6. The sizes are summarized in Table 1 at the end of Section 6. The three steps are now treated in turn, each in a self-contained section.

4

From 3-SAT to HomMQ

This first step is classical, and we include it because its two features, homogeneity and the special unknown h, are used later. We start from a 3-SAT instance as in Section 2, with variables b1 , . . . , bv and c clauses C = ℓ1 ∨ ℓ2 ∨ ℓ3 . We may assume v + c ≥ 1, so that d = 1 + v + c ≥ 2; the trivial formula with no variable and no clause is satisfiable and is mapped to a fixed yes-instance. From such an instance we construct an instance of HomMQ: homogeneous quadratic forms Q1 , . . . , Qs in d unknowns over Fq such that the formula is satisfiable if and only if the forms have a common zero x ̸= 0. The translation is the natural one. A truth value becomes an element of {0, 1} ⊂ Fq , encoded by the equation z 2 = z. A literal is represented by a linear expression which vanishes exactly when the literal is true, and a clause is true when the product of the three expressions of its literals vanishes; since this product has degree three, an auxiliary unknown is introduced per clause to split it into equations of degree two. Finally, the constant 1 is replaced by an unknown h, for the reason explained below.

ML decoding of Gabidulin codes is NP-hard

9

The role of the unknown h for homogenization. We recall here the standard technique of homogenization [10], and explain why it is needed. The unknown h is imposed by the pivot problem TSM (Twisted Square Membership) to which the quadratic system will be reduced in Section 5. The twisted square aq+1 = a · aq is a homogeneous quadratic form in the coordinates of a: every monomial is a product xi xj , with no constant and no linear term. Through trace duality, only homogeneous equations of degree two can therefore be encoded into TSM. The natural equations are not homogeneous: a Boolean value z satisfies z 2 − z = 0, which has a linear term, and a clause involves the constant 1. We therefore homogenize: the constant 1 is replaced by a new unknown h and every linear term z by hz, which turns an equation f (z) = 0 of degree at most two into the homogeneous equation h2 f (z/h) = 0; geometrically, this passes from an affine variety to its projective closure [10, Ch. 8]. Its effect on solutions is the following. If h = ̸ 0, every equation can be divided by h2 , and the solution divided by h is a solution of the original system with h = 1. If h = 0, the equations zi2 − hzi = 0 become zi2 = 0, so zi = 0, and likewise for the auxiliary unknowns, so that the solution is zero. Thus the homogenization creates no spurious solution, provided one asks for a non-zero solution, which is exactly what HomMQ does. For instance, consider the single clause b1 ∨ ¬b2 ∨ b3 . Without h, it is encoded by the equations zi2 − zi = 0 and (1 − z1 )z2 (1 − z3 ) = 0, which cannot be fed to TSM. With h, the equations become zi2 −hzi = 0, w2 −hw = 0, hw−(h−z1 )z2 = 0 and w(h − z3 ) = 0, all homogeneous of degree two. The assignment b1 = true, b2 = b3 = false gives the solution (h, z1 , z2 , z3 , w) = (1, 1, 0, 0, 0). Over F3 , the vector (2, 2, 0, 0, 0) = 2 · (1, 1, 0, 0, 0) is also a solution; it describes the same assignment, recovered by dividing by h = 2. Setting h = 0 forces z1 = z2 = z3 = w = 0. Concretely, the unknowns are h, one unknown zi per variable bi , and one auxiliary unknown wC per clause C, so that d = 1+v +c. To a literal we associate the linear form u(bi ) = h − zi , u(¬bi ) = zi , which, for h = 1, vanishes exactly when the literal is true. For a clause C = ℓ1 ∨ ℓ2 ∨ ℓ3 we write uj = u(ℓj ). The system consists of the following equations, v of the first kind and 3c of the other three, so that s = v + 3c: zi2 − hzi = 0,

2 wC − hwC = 0,

hwC − u1 u2 = 0,

wC u3 = 0.

The first family says that zi is a truth value, the third defines wC as u1 u2 , and the last one then says u1 u2 u3 = 0, i.e. that one literal of C is true; the second family only normalizes wC . Before proving that this system does what we want, let us see it on a small case. As a running example, take the formula consisting of the single clause C = b1 ∨ ¬b2 ∨ b3 , so that v = 3, c = 1 and d = 5. The unknowns are h, z1 , z2 , z3 , wC , the literal forms are u1 = h − z1 , u2 = z2 , u3 = h − z3 , and the system consists of the s = v + 3c = 6 equations z12 − hz1 ,

z22 − hz2 ,

z32 − hz3 ,

2 wC − hwC ,

hwC − (h − z1 )z2 ,

wC (h − z3 ).

10

P. Gaborit

The assignment b1 = true, b2 = b3 = false gives the solution (h, z1 , z2 , z3 , wC ) = (1, 1, 0, 0, 0), and indeed u1 = 0. In the notation of Section 5, where the unknowns are numbered x1 = h, x2 = z1 , x3 = z2 , x4 = z3 , x5 = wC , the fifth equation reads x1 x5 − x1 x3 + x2 x3 , with coefficients c15 = 1, c13 = −1, c23 = 1 and all others zero. It remains to verify that satisfying assignments correspond exactly to non-zero solutions. The only point requiring care is that a non-zero solution must have h ̸= 0. Proposition 1. The formula is satisfiable if and only if the system has a nonzero solution in Fdq . Proof. Given a satisfying assignment, set h = 1, zi ∈ {0, 1} its value and wC = u1 u2 ; the last equation holds since one literal of C is true, so u1 u2 u3 = 0. Conversely let x be a non-zero solution. If h = 0 the first two equations give zi = wC = 0, hence x = 0; so h = ̸ 0, and by homogeneity we may take h = 1. Then zi ∈ {0, 1} defines an assignment, wC = u1 u2 , and u1 u2 u3 = 0 says that a literal of each clause is true. The output of this step, the list Q1 , . . . , Qs of the left-hand sides above, read as forms in the d unknowns h, z1 , . . . , zv , (wC )C , is the input of Section 5.

5

From HomMQ to TSM

We start from an instance of HomMQ, that is, homogeneous quadratic forms Q1 , . . . , Qs in d unknowns over Fq , for instance those produced in Section 4, and we construct an instance (N, U, W ) of TSM, that is, a field E = FqN with N ≡ ±1 (mod 6) and two subspaces U, W ⊂ E given by bases, such that the forms have a common zero x = ̸ 0 if and only if some a ∈ U \ {0} has aq+1 ∈ W (Proposition 2). The plan is to encode the unknown vector x ∈ Fdq by a single element a of a field E = FqN , chosen so that every form Qk (x) can be read off aq+1 by a linear operation. Two tools make this possible. Trace duality (Section 5.1) expresses every Fq -linear form on E as z 7→ Tr(tz) and lets us prescribe the values of such a form on independent elements. An explicit choice of exponents (Section 5.2) P ensures that, when a = i xi αei is raised to the power q + 1, each monomial xi xj comes with its own independent coefficient in E, so that the forms can be prescribed freely. The encoding itself and the proof of the equivalence are in Section 5.3. 5.1

Trace duality N −1

Let E = FqN and Tr(z) = z + z q + · · · + z q , an Fq -linear map E → Fq which is not identically zero, being a polynomial of degree q N −1 < |E|. Lemma 5. Every Fq -linear form on E is z 7→ Tr(tz) for a unique t ∈ E. Consequently, if µ1 , . . . , µr ∈ E are Fq -linearly independent and c1 , . . . , cr ∈ Fq , there exists t ∈ E with Tr(tµj ) = cj for all j, computable by linear algebra.

ML decoding of Gabidulin codes is NP-hard

11

Proof. If t ̸= 0, z 7→ tz is a bijection of E, so z 7→ Tr(tz) is not zero. Hence t 7→ Tr(t ·) is an injective linear map between two spaces of dimension N , thus bijective. For the second claim, complete the µj into a basis and prescribe a linear form on it. 5.2

Choice of exponents

Let us first see what is needed. The unknown x ∈ Fdq will be encoded as a = Pd ei i=1 xi α , where α generates E over Fq and e1 < · · · < ed are integers to be chosen. Since xqi = xi for xi ∈ Fq , the twisted square expands as X X  X aq+1 = a · aq = x i α ei xj αqej = xi xj αei +qej . i

j

i,j

So the twisted square is the sum, over all ordered pairs (i, j), of the monomial xi xj times the power αei +qej . We want to recover each monomial from aq+1 by a linear operation, and this is possible as soon as the powers αei +qej are linearly independent over Fq , which holds when the exponents ei + qej are pairwise distinct and smaller than N , since 1, α, . . . , αN −1 is a basis. The condition on the exponents is thus (⋆)

the d2 integers ei + qej (1 ≤ i, j ≤ d) are pairwise distinct,

the case i = j giving (q + 1)ei ; and the size of the largest of them will dictate N , hence the size of the whole construction. We therefore want integers satisfying (⋆) which are as small as possible. The idea of the construction is that ei + qej should display i and j side by side, without interference. Write i − 1 in base q and dilate its expansion, placing its coefficients on the even positions; the odd positions are then free, and multiplying by q shifts a number by one position. Thus ei occupies the even positions and qej the odd ones, and the sum ei + qej is simply the interleaving of the two base-q expansions, from which P i and j are read off. Formally, for an integer t ≥ 0 with base-q expansion t = k tk q k , with coefficients 0 ≤ tk < q, put X δq (t) = tk q 2k , k

and set ei = δq (i − 1). For q = 2, t = 5 = 1012 gives δ2 (5) = 100012 = 17, and the first exponents are 0, 1, 4, 5, 16. Lemma 6. The integers ei = δq (i − 1) are strictly increasing, satisfy (⋆), and ed ≤ (d − 1)2 . Hence all integers of (⋆) are at most (q + 1)(d − 1)2 . Proof. δq is strictly increasing, since it preserves the lexicographic comparison of coefficients. PLet (tk ) and P (sk ) be the base-q coefficients of i − 1 and j − 1. Then ei +qej = k tk q 2k + k sk q 2k+1 : the coefficients of ei sit on even positions, those of qej on odd positions, and all are smaller than q, so the two expansions interleave

12

P. Gaborit

and this is the base-q expansion of the sum, with coefficients t0 , s0 , t1 , s1 , . . . By uniqueness of the expansion, the even positions give back i − 1 and the odd positions j − 1, so the ordered pair (i, j) is recovered and (⋆) holds. For instance, for q = 2 and (i, j) = (2, 3), e2 + 2e3 = 1 + 8 = 9 = 10012 , whose even positions 1=i− positions read 2 = j − 1. Finally t2k ≥ tk gives Pread P1 andk odd 2 2k 2 δq (t) ≤ k tk q ≤ ( k tk q ) = t2 , whence ed ≤ (d − 1)2 . 5.3

The encoding and the reduction

We now fix the field and encode the unknown. Let N be the smallest integer with N ≡ ±1 (mod 6) and N > (q + 1)(d − 1)2 , so N = O(qd2 ); the congruence will be used in Section 6. We build E = Fq [X]/(P ) with P irreducible of degree N , found in deterministic polynomial time by Shoup’s algorithm [33], and let α be the class of X. Since P is the minimal polynomial of α, the powers 1, α, . . . , αN −1 form an Fq -basis of E: a non-trivial relation would give a non-zero polynomial of degree less than N vanishing at α. The quadratic-system unknown is encoded as follows. The unknown is a single vector x = (x1 , . . . , xd ) ∈ Fdq : its coordinate xi ∈ Fq is the value given to the i-th unknown of the system, with the numbering x1 = h, x2 , . . . , xv+1 the values of z1 , . . . , zv and the last c coordinates the values of the wC , as in the example of Section 4; Qk (x) ∈ Fq is the value of the k-th equation at this point, and we look for x = ̸ 0 with Qk (x) = 0 for all k. The aim of this step is to replace the d coordinates of x by one element of the field E. Let U = ⟨αe1 , . . . , αed ⟩Fq , a subspace of dimension d since the αei are distinct elements of a basis, and define ϕ : Fdq −→ U,

x = (x1 , . . . , xd ) 7−→ a = x1 αe1 + · · · + xd αed .

Thus the xi are the coordinates of a in the basis (αei ) of U , and ϕ is an Fq linear bijection: looking for x or looking for a ∈ U is the same thing, and a ̸= 0 if and only if x ̸= 0. For q = 2 and d = 2 one has a = x1 + x2 α, and a3 = a · a2 = (x1 + x2 α)(x1 + x2 α2 ) = x21 + x1 x2 (α + α2 ) + x22 α3 : each monomial of the system comes out with its own coefficient in E, which is the point of the encoding. In general, since xqi = xi , aq+1 = a·aq =

X

xi xj µij ,

µii = α(q+1)ei ,

µij = αei +qej +αej +qei (i < j).

i≤j

By Lemma 6 and N > (q + 1)(d − 1)2 , the elements µij involve pairwise disjoint sets of basis vectors αe , e < N , and are therefore linearly independent over Fq . P (k) (k) Write Qk (x) = i≤j cij xi xj , where cij ∈ Fq is the coefficient of the monomial xi xj in the k-th equation; the coordinates of x are the values of h, of the zi and of the wC , in this order, as in the example of Section 4. For instance the equation z12 − hz1 reads x22 − x1 x2 , so that c22 = 1, c12 = −1 and all other coefficients vanish. Since the µij are independent, Lemma 5 lets us prescribe a (k) linear form on them: we choose tk ∈ E with Tr(tk µij ) = cij for all i ≤ j. Since

ML decoding of Gabidulin codes is NP-hard

xi xj ∈ Fq and the trace is Fq -linear, X Tr(tk aq+1 ) = xi xj Tr(tk µij ) = Qk (x)

13

for all x ∈ Fdq .

i≤j

Finally put W = {z ∈ E : Tr(tk z) = 0, k = 1, . . . , s}, a subspace computed by linear algebra. Proposition 2. The quadratic system has a non-zero solution if and only if (U, W ) is a yes-instance of TSM. Proof. Let x ∈ Fdq and a = ϕ(x) ∈ U . Since ϕ is a linear bijection, a ̸= 0 if and only if x ̸= 0. By definition of W , aq+1 ∈ W if and only if Tr(tk aq+1 ) = 0 for all k, and by the choice of the tk this reads Qk (x) = 0 for all k. Hence if x = ̸ 0 is a common zero of the Qk , then a = ϕ(x) is a non-zero element of U with aq+1 ∈ W ; conversely, if a ∈ U \ {0} satisfies aq+1 ∈ W , then x = ϕ−1 (a) is non-zero and Qk (x) = Tr(tk aq+1 ) = 0 for all k. Corollary 1. For every fixed prime power q, TSM is NP-complete under deterministic polynomial-time reductions. Proof. TSM is in NP: a certificate is a, and the conditions a ∈ U \ {0} and aq+1 ∈ W are checked by linear algebra over Fq . NP-hardness follows from Propositions 1 and 2, whose composition is a deterministic polynomial-time reduction from 3-SAT to TSM. This completes the second step. Its output is the instance (N, U, W ) of TSM, with U given by the basis αe1 , . . . , αed and W by a basis computed from the tk ; all the non-linearity of the quadratic system is now carried by the single operation a 7→ aq+1 , and the two remaining conditions, a ∈ U and aq+1 ∈ W , are linear. The next section shows how a Gabidulin decoding instance can impose exactly these three things.

6

From TSM to GabDec1

6.1

What has to be shown

Section 5 turned a homogeneous quadratic system into an instance (N, U, W ) of TSM: a field E = FqN with N ≡ ±1 (mod 6), and two subspaces U, W ⊂ E given by bases, such that the system has a non-zero solution if and only if some a ∈ U \ {0} has aq+1 ∈ W . All the non-linearity of the original problem is now carried by the twisted square a 7→ aq+1 , while the conditions a ∈ U and aq+1 ∈ W are linear. In this last step we start from such an instance and construct an instance (g, y) of GabDec1 , that is, a field K = Fqm , a vector g ∈ K n of rank n and a received word y ∈ K n , such that some λ ∈ K satisfies rk(y − λg) ≤ n − 2 if and only if some a ∈ U \ {0} has aq+1 ∈ W . The received word is not given, it is designed.

14

P. Gaborit

By Lemma 3, the decoding instance is a yes-instance exactly when some plane of the support satisfies the eigenplane equation. One direction consists in exhibiting such a plane from a solution of TSM. The converse is the heart of the proof: we show that every solution plane is necessarily of the form ⟨a, τ aq+1 ⟩ with a ∈ U \ {0} and aq+1 ∈ W . The construction and the proof are organized as follows. In Section 6.2 we build a cubic extension K = E(τ ) of E, in which one equality splits into three independent equalities in E, one per coefficient on 1, τ, τ 2 ; this is what allows a single eigenplane equation to impose several conditions. In Section 6.3 we choose the code, through its support G = U ⊕ τ W , so that the two linear conditions of TSM are built into the code itself. In Section 6.4 we choose the 2 received word, ỹ(a + τ b) = aq + τ bq , made of two Frobenius twists with different exponents, and check that it is a legitimate received word. Finally, in Section 6.5, we read the eigenplane equation coefficient by coefficient: the coefficients on 1 and τ 2 force the shape ⟨a, τ b⟩, the coefficient on τ forces b ∈ F∗q aq+1 , and this proves the equivalence (Proposition 3) and the main theorem. 6.2

The field K

We first build the field in which the code will live. Fix once and for all an irreducible polynomial R ∈ Fq [Y ] of degree 3; it depends only on q, and it exists since the field Fq3 exists and the minimal polynomial over Fq of a generator of its cyclic multiplicative group is irreducible of degree 3 (for q = 2, Y 3 + Y + 1); it is found by exhaustive search in constant time. Put K = E[Y ]/(R) and let τ be the class of Y . Lemma 7. K is a field, K = Fq3N , and 1, τ, τ 2 is a basis of K over E. Proof. An irreducible polynomial of degree 3 over Fq factors over FqN into gcd(3, N ) irreducible factors of equal degree, and gcd(3, N ) = 1 since N ≡ ±1 (mod 6). Hence R stays irreducible over E, [K : E] = 3, and 1, τ, τ 2 is a basis by the argument used for α. Every z ∈ K is thus written uniquely z = z0 + z1 τ + z2 τ 2 with zi ∈ E, and an equality in K is equivalent to three equalities in E, one for each power of τ ; we call zi the component of z on τ i . 6.3

The code

With K in hand we choose the code, that is, its support. Recall from Section 2 that a code Gab(g, 1) is determined by the vector g = (g1 , . . . , gn ), whose coordinates are Fq -linearly independent, and that its support is the Fq -space G = ⟨g1 , . . . , gn ⟩Fq ⊂ Fqm of dimension n spanned by these coordinates: g is a basis of G, a received word is an Fq -linear map ỹ : G → Fqm , and decoding asks for a plane of G on which ỹ acts as a scalar. Choosing the code thus amounts to choosing G together with a basis. Since the expected plane contains a vector a ∈ U and a vector τ b with b ∈ W , we take G = U ⊕ τ W = {a + τ b : a ∈ U, b ∈ W } ⊂ K.

ML decoding of Gabidulin codes is NP-hard

15

The sum is direct, because 1 and τ are linearly independent over E, so, writing r = dim W (with N − s ≤ r ≤ N , since W is cut out by s linear conditions), n := dimFq G = dim U + dim W = d + r ≤ d + N . We choose the extension field Fqm = K with m = 3N , and for g ∈ K n the concatenation of the basis αe1 , . . . , αed of U and of τ w1 , . . . , τ wr for a basis w1 , . . . , wr of W (computed by linear algebra from the tk ); this is an Fq -basis of G, so rk(g) = n. Note that n ≥ d ≥ 2, so that radius n − 2 makes sense. Moreover N > (q + 1)(d − 1)2 ≥ d since d ≥ 2, hence n ≤ d + N ≤ 2N < 3N = m, so that the code satisfies the length constraint n ≤ m of Gabidulin codes. 6.4

The received word

The code being fixed, it remains to choose the received word; this is where the twisted square is produced. Since (g, y) is ours to choose, and since by Section 2 received words correspond exactly to Fq -linear maps G → K, we define the map ỹ and deduce y from it. Every element of G is uniquely a + τ b with a ∈ U , b ∈ W , so it suffices to give ỹ(a + τ b). We set (∗)

2

ỹ(a + τ b) = aq + τ bq .

Lemma 8. The map (∗) is Fq -linear. The corresponding received word yj = ỹ(gj ) 2 is yj = αei q for gj = αei and yj = τ wlq for gj = τ wl , and is computed in polynomial time. 2

Proof. The map a + τ b 7→ (a, b) is linear; a 7→ aq and b 7→ bq are additive and 2 2 satisfy (λa)q = λaq for λ ∈ Fq ; the multiplication by τ is linear. The two Frobenius twists have distinct exponents on purpose: equal exponents on a and b would force the plane to be ⟨a, τ b⟩ as well, but would only give b ∈ F∗q a, whereas the exponents q 2 and q produce b ∈ F∗q aq+1 . For x = a + τ b and x′ = a′ + τ b′ in G, the components of ỹ(x)x′ on 1, τ, τ 2 are 2

aq a′ ,

2

aq b′ + bq a′ ,

bq b′ ,

of degree at most 2 in τ , so no reduction modulo R occurs. 6.5

The shape of solution planes

We prove the converse direction by showing that every solution plane has the form ⟨a, τ b⟩. The first lemma is the elementary fact that makes the coefficients on 1 and τ 2 useful. 2

2

Lemma 9. Let a, a′ ∈ E be non-zero with aq a′ = a′q a. Then a′ ∈ Fq a. 2

2

Proof. Put u = a′ /a. Dividing by aq a gives uq = u. Since u ∈ FqN , also N 2 2k uq = u. Write N = 2k + 1; applying k times u 7→ uq gives uq = u, hence N 2k u = uq = (uq )q = uq , and u ∈ Fq .

16

P. Gaborit

This is the only place where the parity of N is used. Lemma 10. If a plane L ⊂ G satisfies L ⊂ Ker(ỹ − λ) for some λ ∈ K, then L = ⟨a, τ b⟩ with a ∈ U \ {0} and b ∈ W \ {0}. Proof. By Lemma 4, for all x = a + τ b and x′ = a′ + τ b′ in L we have ỹ(x)x′ = 2 2 ỹ(x′ )x, and the components on 1 and τ 2 give aq a′ = a′q a and bq b′ = b′q b. Let A = {a ∈ U : ∃b, a + τ b ∈ L}, the image of L under the linear map a + τ b 7→ a; it is a subspace of U . If dim A ≥ 2, take a, a′ ∈ A linearly independent and x, x′ ∈ L realizing them: the first relation and Lemma 9 give a′ ∈ Fq a, a contradiction. Hence dim A ≤ 1, and likewise dim B ≤ 1 for B = {b ∈ W : ∃a, a + τ b ∈ L}, using (b′ /b)q = b′ /b. The map L → A × B, a + τ b 7→ (a, b), is linear and injective, so 2 = dim L ≤ dim A + dim B ≤ 2. Thus A = Fq a, B = Fq b with a, b = ̸ 0, the map is bijective, and a and τ b belong to L. Note that the argument never assumes that a particular basis of L has nonzero components: it works on the projections A and B of the whole plane. With the shape of solution planes in hand, the coefficient on τ finishes the job, and the converse direction is a direct computation. Proposition 3. There exists λ ∈ K with rk(y − λg) ≤ n − 2 if and only if there exists a ∈ U \ {0} with aq+1 ∈ W . Proof. Assume the decoding instance is a yes-instance. By Lemmas 2 and 10, some plane ⟨a, τ b⟩ with a ∈ U \ {0} and b ∈ W \ {0} lies in Ker(ỹ − λ). The 2 component on τ of the equality ỹ(a) τ b = ỹ(τ b) a reads aq b = abq . Dividing 2 2 by ab gives aq −1 = bq−1 , and since aq −1 = (aq+1 )q−1 , the element γ = b/aq+1 satisfies γ q−1 = 1, so γ ∈ F∗q ; this is where the exponent q + 1 of TSM arises. Since W is an Fq -subspace, aq+1 = γ −1 b ∈ W . Conversely let a ∈ U \ {0} with aq+1 ∈ W , put b = aq+1 , so that τ b ∈ G, and 2 2 2 λ = aq −1 . Then ỹ(a) = aq = λa and ỹ(τ b) = τ aq +q = λτ b. By linearity ⟨a, τ b⟩, a plane since the sum U ⊕ τ W is direct, lies in Ker(ỹ − λ), and Lemma 2 gives rk(y − λg) ≤ n − 2. 6.6

Proof of Theorem 1

All three steps are now established, and we can prove the main theorem, which we recall. Theorem 1. For every fixed prime power q, GabDec1 is NP-complete. More precisely, a 3-SAT formula with v variables and c clauses is mapped in deterministic polynomial time to an instance with m = 3N and n ≤ N + d, where d = 1 + v + c, N ≡ ±1 (mod 6) and N = O(q d2 ). Proof. Membership in NP. Given (g, y), a certificate is λ ∈ Fqm ; the rank of y − λg is computed by Gaussian elimination over Fq on its m × n matrix of coordinates, in polynomial time.

ML decoding of Gabidulin codes is NP-hard

17

NP-hardness. Let Φ be a 3-SAT formula with v variables and c clauses, and d = 1 + v + c. Section 4 produces homogeneous quadratic forms Q1 , . . . , Qs in d unknowns, with s = v + 3c, such that Φ is satisfiable if and only if they have a common zero x ̸= 0 (Proposition 1). Section 5 produces from them an instance (N, U, W ) of TSM, with N ≡ ±1 (mod 6) and N = O(qd2 ), such that the forms have a common zero x ̸= 0 if and only if some a ∈ U \ {0} has aq+1 ∈ W (Proposition 2). Section 6 produces from (N, U, W ) an instance (g, y) of GabDec1 over K = Fq3N , of length n = dim U + dim W ≤ d + N , such that some λ satisfies rk(y − λg) ≤ n − 2 if and only if (N, U, W ) is a yes-instance (Proposition 3). Composing the three equivalences, Φ is satisfiable if and only if (g, y) is a yes-instance of GabDec1 . Polynomial time. Each object of the construction is computed deterministically in time polynomial in v + c, with the sizes of Table 1: the exponents ei are given by a closed formula (Lemma 6); the irreducible polynomial of degree N defining E is found by Shoup’s algorithm [33]; the polynomial R of degree 3 defining K depends only on q; the elements tk , the basis of W , the vector g and the received word y are obtained by linear algebra over Fq in dimension O(m) = O(qd2 ) (Lemmas 5 and 8). Since q is fixed, m, n = O(d2 ), and the 2n elements of Fqm forming g and y have m coordinates each over Fq , so that the output instance has size |(g, y)| = O(nm) = O(d4 ) symbols of Fq , polynomial in the size of the formula. Remark 2 (representation of finite fields). The answer does not depend on how finite fields are represented. We take E = Fq [X]/(P ), with P found by Shoup’s deterministic algorithm [33] in time polynomial in N for fixed q, and K = E[Y ]/(R). If the input must give Fqm by a single irreducible polynomial Q of degree m, one computes Q by the same algorithm and an explicit isomorphism ψ : K → Fq [Z]/(Q) by Lenstra’s deterministic algorithm [28], and outputs (ψ(g), ψ(y)). Since ψ restricts to an automorphism of Fq , it is semilinear over Fq and preserves rank weights; as ψ(y − λg) = ψ(y) − ψ(λ)ψ(g), the two instances have the same answer.

Table 1. Sizes in the reduction, for a formula with v variables and c clauses, d = 1+v +c, and fixed q. Object

Size

Construction

exponents ei ed ≤ (d − 1) δq (i − 1) (Lemma 6) field E = FqN N = O(qd2 ), N ≡ ±1 (mod 6) irreducible polynomial [33] field K = E(τ ) m = 3N fixed degree-3 polynomial tk , W, g, y polynomial linear algebra code n = d + r ≤ N + d with r = dim W ; k = 1; Gab(g, 1) radius n − 2 2

18

P. Gaborit

7

Consequences

7.1

Complexity consequences

We first derive the consequence for Gabidulin codes, then turn to the general problems RSD and RMD from Section 2. Maximum-likelihood decoding of a code consists in finding, for a received word, a closest codeword. Corollary 2. For every fixed prime power q, maximum-likelihood decoding of Gabidulin codes is NP-hard under deterministic polynomial reductions, already for codes of dimension k = 1. Proof. For k = 1, a maximum-likelihood decoder applied to (g, y) returns some λ0 with rk(y − λ0 g) = minλ rk(y − λg). Comparing this rank with n − 2 decides GabDec1 , which is NP-complete by Theorem 1. This holds for the simplest codes of the family, which have dimension one and minimum distance n. We next consider RSD and RMD. Corollary 3. RSD, the rank syndrome decoding problem for Fqm -linear codes, is NP-complete under deterministic polynomial reductions. Proof. From an instance (g, y) of GabDec1 , compute a parity-check matrix H of Gab(g, 1) and s = Hy ⊤ . The solutions e of He⊤ = s are exactly the vectors y − λg, so a solution of rank at most n − 2 exists if and only if the instance of GabDec1 is a yes-instance. Corollary 4. RMD, the rank minimum distance problem for Fqm -linear codes, is NP-complete under deterministic polynomial reductions, already for codes of dimension 2. Proof. From (g, y) consider C ′ = {µy + λg : µ, λ ∈ Fqm } and w = n − 2. If y ∈ Fqm g, which is tested by linear algebra, the instance of GabDec1 is a yesinstance and we output any fixed yes-instance; otherwise C ′ has dimension 2. Multiplication by a non-zero scalar is an Fq -linear bijection of Fqm , hence preserves rank. A codeword with µ = 0 and λ ̸= 0 therefore has rank rk(g) = n, while a codeword with µ ̸= 0 equals µ(y − λ′ g) with λ′ = −λ/µ and has rank rk(y − λ′ g). Hence C ′ has a non-zero codeword of rank at most n − 2 if and only if the instance of GabDec1 is a yes-instance. These problems underlie rank-based cryptography. Gaborit and Zémor [19] established their hardness through a randomized reduction from Hamming decoding; Corollaries 3 and 4 give NP-completeness under deterministic reductions. Their reduction covers constant rate and small weight, ours is restricted to dimension one or two and to large radius; the two results are complementary. The result can also be seen as the rank-metric counterpart of the Guruswami–Vardy theorem [26].

ML decoding of Gabidulin codes is NP-hard

7.2

19

Comparison with the Hamming metric

It is instructive to compare with the Hamming metric. There, any linear code of fixed dimension k is decoded at radius n − k − 1 in polynomial time: a codeword at that distance agrees
with the received word on k + 1 positions, and one may n enumerate the k+1 candidate position sets and solve a linear system for each. For k = 1 the Reed–Solomon code is the repetition code and the problem is trivial; this is why the Guruswami–Vardy theorem needs a growing dimension. In the rank metric the agreement set is an Fq -subspace rather than a subset, there are q Θ(kn) candidates, and Theorem 1 shows that the problem is hard already for k = 1. The same contrast explains why the Guruswami–Vardy reduction does not transfer: it encodes a subset-sum instance into the freedom of choosing which positions to keep, a freedom which does not exist for subspaces, so that the hard constraints must be written, as here, into the field structure of ỹ. Several questions remain open and are discussed in Section 8.

8

Discussion and open questions

The reduction proves hardness in a specific regime: dimension one, radius n − 2, and an extension degree m ≈ 3n. Each of these three parameters raises a natural question, namely how far the radius can be lowered, whether the extension degree can be brought down to the values used in cryptography, and whether the dimension can be increased. We discuss them in turn, together with directions that seem interesting to explore. Below radius n−2. For k = 1, radius n−r −1 asks for an eigenspace of dimension r + 1 instead of a plane. One might try P to use r + 1 summands in the support, P 2 G = U ⊕ ω1 W ⊕ · · · ⊕ ωr W , with ỹ(a + i ωi bi ) = aq + i ωi bqi , where the ωi would be powers of τ whose pairwise products are linearly independent over E; a Sidon set of exponents could provide this with an extension of moderate degree. If the coefficientwise reading of the eigenplane equation were to go through as in Section 6, the same pivot problem might give hardness at radius n − r − 1, at the price of a larger extension degree. Whether this works, down to which radius, and with which trade-off between the radius and m, remains to be investigated. Square codes. The parameters produced by the reduction are not those most often used in practice: our instances have m ≈ 3n, whereas rank-based cryptosystems frequently work with square or nearly square codes, m = n or m close to n, which also give the smallest extension field for a given length. The complexity of decoding in this regime is open. A heuristic count suggests that radius n − 2 may not be the right place to look for it: a random word has on average about q 2(n−2)−m scalars λ within that distance, which is large when m < 2(n − 2). If yes-instances are indeed typical in this regime, which the expectation alone does not prove and which would not exclude worst-case hardness, the natural question for square codes would be at smaller radius.

20

P. Gaborit

Higher dimensions. Decoding Gab(g, k) at radius n − k − 1 asks for a (k + 1)dimensional space on which ỹ agrees with a q-polynomial of q-degree less than k. A direction that seems promising is to compose a dimension-one instance with linearized polynomials of q-degree one, such as P (x) = xq − δ q−1 x: when G ⊆ P (Fqm ), which requires a suitable choice of δ since dim P −1 (G) = dim(G ∩ P (Fqm ))+1, replacing (G, ỹ) by (P −1 (G), ỹ◦P ) would raise both the dimension of the agreement space and the q-degree by one, whereas merely adding coordinates cannot help. The difficulty would be to control the solutions that such a lifting may create without coming from the original instance; if they could be characterized and avoided by a suitable choice of δ, the present core could serve as the base case of an induction on k.

9

Conclusion

Decoding a Gabidulin code of dimension one at radius n − 2, the first radius at which the question is not trivial, is NP-complete. Maximum-likelihood decoding of Gabidulin codes is therefore NP-hard already in dimension one, where its Hamming-metric counterpart is easy, and rank syndrome decoding and rank minimum distance for Fqm -linear codes are NP-complete under deterministic reductions, where only a randomized reduction was known. The proof rests on a single idea: once the received word is read as an Fq -linear map, decoding becomes the search for an eigenplane, and two Frobenius twists on the support U ⊕ τ W turn that eigenplane equation into the pivot problem TSM, which encodes 3-SAT. Our result is a first step towards understanding the complexity of decoding Gabidulin codes beyond the unique decoding radius. It raises natural questions on how far hardness extends, in the dimension of the code, in the decoding radius, and towards the square parameters m ≈ n of cryptography, which will require further investigation. Acknowledgment. AI tools (Claude, Anthropic, and ChatGPT, OpenAI) were used during the preparation of this manuscript for language editing, LATEX assistance, and exploratory discussions. All mathematical statements, proofs, and conclusions were independently verified by the author, who takes full responsibility for the content.

References 1. Aragon, N., Gaborit, P., Hauteville, A., Ruatta, O., Zémor, G.: Low rank parity check codes: new decoding algorithms and applications to cryptography. IEEE Trans. Inf. Theory 65(12), 7697–7717 (2019) 2. Aragon, N., Blazy, O., Gaborit, P., Hauteville, A., Zémor, G.: Durandal: a rank metric based signature scheme. In: EUROCRYPT 2019, LNCS 11478, pp. 728–758 (2019) 3. Aragon, N., Blazy, O., Deneuville, J.-C., Gaborit, P., Hauteville, A., Ruatta, O., Tillich, J.-P., Zémor, G., et al.: ROLLO – Rank-Ouroboros, LAKE and LOCKER. Submission to the NIST post-quantum cryptography standardization process (2019)

ML decoding of Gabidulin codes is NP-hard

21

4. Aguilar Melchor, C., Aragon, N., Bettaieb, S., Bidoux, L., Blazy, O., Deneuville, J.-C., Gaborit, P., Zémor, G., et al.: Rank Quasi-Cyclic (RQC). Submission to the NIST post-quantum cryptography standardization process (2019) 5. Berlekamp, E.R., McEliece, R.J., van Tilborg, H.C.A.: On the inherent intractability of certain coding problems. IEEE Trans. Inf. Theory 24(3), 384–386 (1978) 6. Buss, J.F., Frandsen, G.S., Shallit, J.O.: The computational complexity of some problems of linear algebra. J. Comput. Syst. Sci. 58(3), 572–596 (1999) 7. Cheng, Q.: Hard problems of algebraic geometry codes. IEEE Trans. Inf. Theory 54(1), 402–406 (2008) 8. Cheng, Q., Wan, D.: On the list and bounded distance decodability of Reed–Solomon codes. SIAM J. Comput. 37(1), 195–209 (2007) 9. Coggia, D., Couvreur, A.: On the security of a Loidreau rank metric code based encryption scheme. Des. Codes Cryptogr. 88, 1941–1957 (2020) 10. Cox, D.A., Little, J., O’Shea, D.: Ideals, Varieties, and Algorithms, 4th edn. Undergraduate Texts in Mathematics, Springer (2015) 11. Delsarte, P.: Bilinear forms over a finite field, with applications to coding theory. J. Combin. Theory Ser. A 25, 226–241 (1978) 12. Dumer, I., Micciancio, D., Sudan, M.: Hardness of approximating the minimum distance of a linear code. IEEE Trans. Inf. Theory 49(1), 22–37 (2003) 13. Faure, C., Loidreau, P.: A new public-key cryptosystem based on the problem of reconstructing p-polynomials. In: Coding and Cryptography, WCC 2005, LNCS 3969, pp. 304–315 (2006) 14. Forbes, M.A., Shpilka, A.: On identity testing of tensors, low-rank recovery and compressed sensing. In: STOC 2012, pp. 163–172 (2012) 15. Fraenkel, A.S., Yesha, Y.: Complexity of problems in games, graphs and algebraic equations. Discrete Appl. Math. 1, 15–30 (1979) 16. Gabidulin, E.M.: Theory of codes with maximum rank distance. Probl. Inf. Transm. 21(1), 1–12 (1985) 17. Gaborit, P., Murat, G., Ruatta, O., Zémor, G.: Low rank parity check codes and their application to cryptography. In: WCC 2013 (2013) 18. Gabidulin, E.M., Paramonov, A.V., Tretjakov, O.V.: Ideals over a non-commutative ring and their application in cryptology. In: EUROCRYPT 1991, LNCS 547, pp. 482–489 (1991) 19. Gaborit, P., Zémor, G.: On the hardness of the decoding and the minimum distance problems for rank codes. IEEE Trans. Inf. Theory 62(12), 7245–7252 (2016) 20. Gandikota, V., Ghazi, B., Grigorescu, E.: NP-hardness of Reed–Solomon decoding and the Prouhet–Tarry–Escott problem. In: FOCS 2015, pp. 760–773 (2015) 21. Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman (1979) 22. Guruswami, V., Kopparty, S.: Explicit subspace designs. In: FOCS 2013, pp. 608–617 (2013) 23. Guruswami, V., Sudan, M.: Improved decoding of Reed–Solomon and algebraicgeometry codes. IEEE Trans. Inf. Theory 45(6), 1757–1767 (1999) 24. Guruswami, V., Xing, C.: List decoding Reed–Solomon, algebraic-geometric, and Gabidulin subcodes up to the Singleton bound. In: STOC 2013, pp. 843–852 (2013) 25. Guo, Z., Xing, C., Yuan, C., Zhang, Z.: Random Gabidulin codes achieve list decoding capacity in the rank metric. In: FOCS 2024, pp. 1846–1873 (2024) 26. Guruswami, V., Vardy, A.: Maximum-likelihood decoding of Reed–Solomon codes is NP-hard. IEEE Trans. Inf. Theory 51(7), 2249–2256 (2005) 27. Koetter, R., Kschischang, F.R.: Coding for errors and erasures in random network coding. IEEE Trans. Inf. Theory 54(8), 3579–3591 (2008)

22

P. Gaborit

28. Lenstra, H.W., Jr.: Finding isomorphisms between finite fields. Math. Comp. 56(193), 329–347 (1991) 29. Loidreau, P.: A new rank metric codes based encryption scheme. In: PQCrypto 2017, LNCS 10346, pp. 3–17 (2017) 30. Overbeck, R.: Structural attacks for public key cryptosystems based on Gabidulin codes. J. Cryptology 21(2), 280–301 (2008) 31. Renner, J., Puchinger, S., Wachter-Zeh, A.: LIGA: a cryptosystem based on the hardness of rank-metric list and interleaved decoding. Des. Codes Cryptogr. 89, 1279–1319 (2021) 32. Raviv, N., Wachter-Zeh, A.: Some Gabidulin codes cannot be list decoded efficiently at any radius. IEEE Trans. Inf. Theory 62(4), 1605–1615 (2016) 33. Shoup, V.: New algorithms for finding irreducible polynomials over finite fields. Math. Comp. 54(189), 435–447 (1990) 34. Silva, D., Kschischang, F.R., Koetter, R.: A rank-metric approach to error control in random network coding. IEEE Trans. Inf. Theory 54(9), 3951–3967 (2008) 35. Vardy, A.: The intractability of computing the minimum distance of a code. IEEE Trans. Inf. Theory 43(6), 1757–1766 (1997) 36. Wachter-Zeh, A.: Bounds on list decoding of rank-metric codes. IEEE Trans. Inf. Theory 59(11), 7268–7277 (2013)

Related documents

• Maximum-Likelihood Decoding of Gabidulin Codes Is NP-Hard Even in Dimension One#1457558
• Sparse multi-decoder recursive projection aggregation for Reed-Muller codes#476216
• Decoding rank metric Reed-Muller codes#153696
• One-weight codes in the sum-rank metric#1402954
• A Matroidal Framework for Random Access in Linear Codes#1413061