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

What it is

Philippe Gaborit's ePrint 2026/2637 (received 25 October 2026, approved 26 October 2026, listed as "in submission") proves a hardness result for rank-metric decoding. For a fixed prime power q, deciding whether a received word y in F_{q^m}^n lies at rank distance at most n − 2 from the one-dimensional Gabidulin code {λg : λ in F_{q^m}} is NP-complete. The paper presents this as the rank-metric analogue of the Guruswami-Vardy theorem for Reed-Solomon codes.

How it works

The paper introduces a pivot problem, Twisted Square Membership (TSM). Given F_q-subspaces U and W of F_q^N, decide whether some non-zero a in U satisfies a^(q+1) in W.

The chain has two encodings:

1. Quadratic systems in d unknowns are encoded into TSM.
2. TSM is encoded into Gabidulin decoding.

In the last step, the received word is viewed as an F_q-linear map. Decoding at radius n − 2 then becomes a search for an F_q-plane on which the map acts as a scalar. The support is U + τW in a cubic extension, and the map is a + τb → a^(q²) + τb^q. The two Frobenius twists force any solution plane to encode the relation a^(q+1) ∈ W.

All constructions are explicit and polynomial, with N = O(qd²), n ≤ N + d, and m = 3N.

Preconditions / Affected

• The result is for a fixed q, at the specific radius n − 2, and for dimension k = 1.
• The reduction is deterministic. Rank Syndrome Decoding and Rank Minimum Distance for F_{q^m}-linear codes are therefore NP-complete under deterministic polynomial reductions. The previously known reduction was randomized.
• In the Hamming metric, hardness at this radius requires the dimension to grow with the length. The paper states this as a contrast with the rank metric.

Caveats

The page is an abstract only, and the paper is not yet peer reviewed. It makes no claim about the security of any rank-based cryptosystem or parameter set, and it gives no attack. It is a worst-case complexity result, so it says nothing directly about average-case difficulty for cryptographic instances. The abstract also does not say how the radius n − 2 compares to the decoding radii used in practice.