PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Philippe Gaborit

arXiv:2610.34404v1cs.CRcs.ITmath.IT

TL;DR

The complexity of maximum-likelihood decoding for Gabidulin codes had remained open, despite polynomial-time decoding up to half the minimum distance. The reduction encodes quadratic systems as Twisted Square Membership instances, then uses an eigenplane formulation and Frobenius twists to map them to Gabidulin decoding. For every fixed prime power q, GabDec1 is NP-complete via deterministic polynomial-time mapping of 3-SAT instances to parameters m = 3N and n ≤ N + d.

  • Problem

    The complexity of maximum-likelihood decoding for Gabidulin codes had remained open, despite polynomial-time decoding up to half the minimum distance.

    Source: §1.1 · p. 1

  • Method

    The reduction encodes quadratic systems as Twisted Square Membership instances, then uses an eigenplane formulation and Frobenius twists to map them to Gabidulin decoding.

    Source: §3 · p. 8, §6.1 · p. 14

  • Results

    For every fixed prime power q, GabDec1 is NP-complete via deterministic polynomial-time mapping of 3-SAT instances to parameters m = 3N and n ≤ N + d.

    Source: §3 · p. 7

  • Takeaways & Limitations

    The deterministic reduction establishes NP-completeness under deterministic polynomial reductions for rank syndrome decoding and rank minimum distance of Fqm-linear codes.

    Source: §9 · p. 20

    The reduction uses extension degree m ≈ 3n; decoding in the square or nearly square regime remains open.

    Source: §8 · p. 19

Abstract

from arXiv · show

Fix a prime power q. We prove that deciding whether a received word y in Fnqm lies at rank distance at most n-2 from the one-dimensional Gabidulin code {{\lambda.g : {\lambda} in 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 in FqN , decide whether some non-zero a in U satisfies a^(q+1) in 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 + {\tau} W in a cubic extension and map a + {\tau} b to a^(q^2) + {\tau} bq^q , two Frobenius twists force solution planes to encode the relation a^(q+1) in W . All constructions are explicit and polynomial, with N = O(qd^2 ), n less than N + d, and m = 3N .

1 Introduction

The paper closes an open question by proving NP-completeness for maximum-likelihood decoding of dimension-one Gabidulin codes at radius n −2. Its reduction uses eigenplanes and Twisted Square Membership, and yields deterministic hardness consequences for rank-metric problems.

1.1 Context and motivation

  • For every fixed prime power q, decoding dimension-one Gabidulin codes at radius n −2 is NP-complete, the first nontrivial radius.Source: §1.1 · p. 2, §1.3 · p. 3

1.2 The idea of the method

  • At radius n −2, decoding is equivalent to finding a plane on which the received-word map acts as a scalar, and Frobenius twists turn the eigenplane equation into TSM.TSM asks whether a nonzero a in U has a^(q+1) in W; twisted squares also encode homogeneous quadratic systems.Source: §1.2 · p. 3

1.3 Contributions and organization

  • The deterministic reduction makes rank syndrome decoding and rank minimum distance for Fqm-linear codes NP-complete, improving on the previously known randomized reduction.Source: §1.3 · p. 3
  • The paper introduces TSM as a compact NP-complete finite-field problem and gives explicit polynomial-size constructions with N = O(qd2), n ≤ N + d, and m = 3N.Source: §1.3 · p. 3

2 Background and preliminaries

The preliminaries define the rank-metric setting and explain why hardness for general MinRank does not automatically resolve the structured Fqm-linear decoding problems. They formulate dimension-one decoding as an eigenplane search and introduce TSM as the intermediate problem.

2.1 Background: known problems

  • The rank metric measures the Fq-dimension spanned by a vector’s coordinates, while dimension-one Gabidulin decoding is trivial at radius n −1 and first becomes nontrivial at n −2.Source: §2.1 · p. 4
  • Rank syndrome decoding for Fqm-linear codes is a structured MinRank instance, so NP-completeness of MinRank alone does not establish its hardness.The matrix spaces arising from these codes are stable under multiplication by Fqm.Source: §2.1 · p. 5

2.2 Preliminaries: the eigenplane formulation and the TSM pivot problem

  • A dimension-one decoding instance is equivalent to finding an Fq-plane on which the received-word map acts as a scalar.The received word corresponds to an Fq-linear map on the code support, and an eigenplane gives the required rank-distance bound.Source: §2.2 · p. 6
  • TSM asks whether a nonzero a in U has twisted square a^(q+1) in W; the operation is quadratic in a’s Fq-coordinates and feeds both reduction stages.The stated dimension condition ensures N is odd and coprime to 3, supporting the construction’s field extensions.Source: §2.2 · p. 7

3 Main result and overview of the reduction

The paper proves deterministic NP-completeness for decoding dimension-one Gabidulin codes at radius n −2, the first nontrivial radius. Its reduction proceeds from 3-SAT through homogeneous quadratic systems and Twisted Square Membership (TSM) to a Gabidulin decoding instance.

3 Main result and overview of the reduction

  • For every fixed prime power q, GabDec1 is NP-complete via a deterministic polynomial-time reduction from 3-SAT.The output has m = 3N and n ≤ N + d, where d = 1 + v + c and N = O(qd^2).Source: §3 · p. 7
  • The reduction maps a satisfying assignment to a non-zero quadratic-system solution, then a field element, and finally a plane on which the received map acts as a scalar.The chain consists of equivalences between yes-instances of consecutive problems.Source: §3 · p. 7
  • Homogenization encodes 3-SAT as homogeneous quadratic forms whose common non-zero solutions correspond exactly to satisfying assignments.The system uses h, one variable per Boolean variable, and one auxiliary variable per clause.Source: §3 · p. 7
  • The TSM instance encodes quadratic coordinates in one field element so that membership of its twisted square expresses all quadratic equations.The final reduction constructs a code and received word whose eigenplanes are exactly the planes associated with TSM solutions.Source: §3 · p. 8

4 From 3-SAT to HomMQ

The first reduction translates 3-SAT into homogeneous quadratic forms over Fq, with a common non-zero solution exactly when the formula is satisfiable. Homogenization uses a distinguished unknown h, and auxiliary variables let each clause be expressed using quadratic equations.

4 From 3-SAT to HomMQ

  • Homogenization replaces the constant 1 by h and linear terms by h-scaled terms, allowing the equations to be encoded as homogeneous quadratics.The twisted-square step handles homogeneous quadratic equations; requiring a non-zero solution prevents h = 0 from yielding a spurious solution.Source: §4 · p. 9
  • The construction uses h, one unknown per Boolean variable, and one auxiliary unknown per clause, giving d = 1 + v + c.The system has s = v + 3c equations.Source: §4 · p. 9
  • For each clause, auxiliary equations define wC from two literal forms and require its product with the third form to vanish, encoding that at least one literal is true.The first family constrains each zi to be a truth value; the clause equations use u1u2 and wCu3.Source: §4 · p. 9
  • The formula is satisfiable if and only if the quadratic system has a non-zero solution.Any non-zero solution must have h ≠ 0, after which scaling to h = 1 recovers a satisfying assignment.Source: §4 · p. 10

5 From HomMQ to TSM

The reduction encodes a homogeneous quadratic system as a TSM instance by representing its unknown vector with one field element and its equations as linear conditions on that element’s twisted square. Trace duality and carefully chosen exponents make the encoding explicit, yielding deterministic NP-completeness for TSM.

5.1 Trace duality

  • Trace duality represents every Fq-linear form on E as z ↦ Tr(tz), allowing prescribed values on independent elements to be computed by linear algebra.This lets each quadratic form be recovered by applying a suitable trace functional to the twisted square.Source: §5.1 · p. 10, §5 · p. 10

5.2 Choice of exponents

  • Interleaving base-q digits in the exponents makes each ordered pair (i, j) recoverable from ei + qej, so the twisted square keeps its monomials distinct.The chosen exponents satisfy the distinctness condition and are bounded by ed ≤ (d −1)^2.Source: §5.2 · p. 11

5.3 The encoding and the reduction

  • The encoding sends x to a = Σ xiα^ei in U, making the coordinates of x the coefficients of a in U’s basis.The independent monomial coefficients in a^(q+1) let trace functionals impose each equation, and W is defined by those trace constraints.Source: §5.3 · pp. 12–13
  • The quadratic system has a non-zero solution exactly when some non-zero a in U satisfies a^(q+1) in W.The encoding maps the system’s unknown vector linearly and bijectively to a field element in U, while W imposes the equations.Source: §5.3 · p. 13
  • For every fixed prime power q, TSM is NP-complete under deterministic polynomial-time reductions.Membership in NP uses a certificate a, and NP-hardness follows by composing the reductions from 3-SAT.Source: §5.3 · p. 13

6 From TSM to GabDec1

The construction makes decoding at radius n −2 equivalent to Twisted Square Membership by encoding its linear constraints in the code support and its nonlinear condition in an eigenplane equation. A deterministic polynomial reduction from 3-SAT then establishes NP-completeness with the stated field and length parameters.

6.1 What has to be shown

  • The decoding instance is a yes-instance exactly when a support plane satisfies the eigenplane equation, and the construction proves such planes encode solutions of TSM.The converse shows every solution plane has the form ⟨a, τaq+1⟩ for a ∈ U \ {0} with aq+1 ∈ W.Source: §6.1 · p. 14, §6.5 · p. 16

6.2 The field K

  • The cubic extension K = E(τ) gives basis 1, τ, τ^2, so an equality in K splits into three equalities in E.This coefficientwise comparison lets one eigenplane equation impose multiple conditions.Source: §6.2 · p. 14

6.3 The code

  • The code support is G = U ⊕ τW, placing the two linear membership conditions of TSM directly into the support.Its dimension is n = dim U + dim W ≤ d + N.Source: §6.3 · pp. 14–15

6.4 The received word

  • Different Frobenius twists, q² on a and q on b, make the eigenplane equation impose b ∈ Fq* aq+1 rather than merely b ∈ Fq* a.The map is chosen as part of the reduction and is checked to be Fq-linear.Source: §6.4 · p. 15

6.5 The shape of solution planes

  • Every solution plane projects to one-dimensional components in U and W, forcing its form to be ⟨a, τb⟩; the τ-coefficient then yields the TSM condition.Conversely, for a ∈ U \ {0} with aq+1 ∈ W, choosing b = aq+1 and λ = aq2−1 constructs a plane in the scalar eigenspace.Source: §6.5 · p. 16

6.6 Proof of Theorem 1

  • For fixed q, GabDec1 is NP-complete under a deterministic reduction from 3-SAT, with m = 3N, n ≤ N + d, and N = O(qd^2).Here d = 1 + v + c and N ≡ ±1 (mod 6).Source: §6.6 · p. 16

7 Consequences

The deterministic reduction yields hardness consequences for dimension-one Gabidulin decoding and NP-completeness for RSD and RMD. The paper contrasts this with fixed-dimension decoding in the Hamming metric, where the rank-metric result has no direct counterpart in the available freedom to choose positions.

7.1 Complexity consequences

  • Maximum-likelihood decoding of Gabidulin codes is NP-hard under deterministic polynomial reductions already for dimension k = 1.The paper also establishes deterministic NP-completeness of RSD and of RMD, with RMD already hard for dimension two.Source: §7.1 · p. 18

7.2 Comparison with the Hamming metric

  • For fixed-dimension Hamming-metric codes, decoding at radius n − k − 1 is polynomial-time, whereas the paper proves rank-metric hardness already for k = 1.The authors explain that Hamming reductions can encode subset-sum through choices of positions to keep, while the rank-metric construction places constraints in the field structure of the received map.Source: §7.2 · p. 19

8 Discussion and open questions

The discussion identifies the reduction’s established regime and outlines open questions about lowering the radius, using square codes, and increasing dimension.

Discussion scope

  • The established hardness regime is dimension one, radius n −2, and extension degree m ≈ 3n.The discussion asks whether the radius can be lowered, the extension degree reduced, or the dimension increased.Source: §8 · p. 19

Below radius n−2

  • For radii below n −2, a proposed approach uses additional support summands, but whether it works and its radius–extension-degree trade-off remain open.The proposal relies on pairwise linearly independent products of powers of τ.Source: §8 · p. 19

Square codes

  • Decoding complexity for square or nearly square codes is open; the paper’s instances instead have m ≈ 3n.A heuristic count suggests many nearby scalars at radius n −2 when m < 2(n −2), but the expectation alone does not establish that yes-instances are typical.Source: §8 · p. 19

Higher dimensions

  • For higher dimensions, a proposed lift composes a dimension-one instance with a degree-one linearized polynomial, but controlling new solutions is the difficulty.The authors suggest that characterizing and avoiding those solutions could make the construction a base case for induction on k.Source: §8 · p. 20

9 Conclusion

Dimension-one Gabidulin decoding at radius n −2 is NP-complete, and the result yields deterministic NP-completeness for rank syndrome decoding and rank minimum distance of Fqm-linear codes. The proof turns decoding into an eigenplane search, while the extension of hardness across dimensions, radii, and cryptographic parameters remains open.

9 Conclusion

  • Dimension-one Gabidulin decoding at radius n −2 is NP-complete, yielding deterministic NP-completeness for rank syndrome decoding and rank minimum distance of Fqm-linear codes.Source: §9 · p. 20
  • Reading the received word as an Fq-linear map turns decoding into an eigenplane search, and two Frobenius twists encode the TSM relation that encodes 3-SAT.Source: §9 · p. 20
  • The result is a first step; hardness across code dimensions, decoding radii, and cryptographic parameters m ≈ n remains for further investigation.Source: §9 · p. 20

Related papers

Loading 2610.34404v1…