Random Gabidulin Codes Achieve List Decoding Capacity in the Rank Metric

Technical Summary: Random Gabidulin Codes Achieve List Decoding Capacity in the Rank Metric

Problem Statement
Gabidulin codes are the rank-metric analogues of Reed–Solomon codes and constitute a primary class of Maximum Rank Distance (MRD) codes. While Reed–Solomon codes are well-understood to be list decodable up to the Johnson bound (and recently up to the generalized Singleton bound for random codes), the list decodability of Gabidulin codes has remained a long-standing open problem with predominantly negative results. Prior work by Raviv and Wachter-Zeh demonstrated that specific Gabidulin codes are not even combinatorially list decodable beyond the unique decoding radius. The central question addressed in this paper is whether Gabidulin codes can be list decoded beyond the unique decoding radius in the rank metric, specifically whether they can achieve the optimal generalized Singleton bound.

Methodology and Framework
The authors resolve this problem by establishing a theoretical framework parallel to the recent breakthroughs on the list decodability of random Reed–Solomon codes by Brakensiek, Gopi, and Makam (BGM). The methodology relies on three main pillars:

1. Higher Order MRD Codes: The paper introduces and defines three distinct notions of "higher order MRD codes" over a general field extension $F/F_q$:

   • GKP($\ell$): Codes that attain all Generic Kernel Patterns of order at most $\ell$. A kernel pattern is a tuple of subspaces satisfying a dimension constraint on their intersections.
   • MRD($\ell$): Codes where the intersection of the images of any $\ell$ subspaces under the generator matrix has the same dimension as the intersection of the images of the corresponding subspaces under a symbolic (generic) matrix.
   • LD-MRD($\le\ell$): Codes that are $(\rho, \ell)$-average-radius list decodable in the rank metric, where $\rho$ is the generalized Singleton bound radius.

2. Equivalence Theorems: The authors prove that these three notions are equivalent. Specifically, a linear code is GKP($\ell$) if and only if it is MRD($\ell$), and a code is MRD($\ell+1$) if and only if its dual is LD-MRD($\le\ell$). This equivalence reduces the problem of proving list decodability to proving that random Gabidulin codes satisfy the GKP property.

3. The GM-MRD Theorem: The core technical contribution is the proof of the "Generalized MDS for MRD" (GM-MRD) theorem. This theorem states that symbolic Gabidulin codes (defined over a function field) attain all generic kernel patterns. The proof adapts the inductive techniques used for the GM-MDS theorem but faces significant new challenges due to the non-commutative nature of the composition of $q$-linearized polynomials, which define Gabidulin codes. The authors introduce the concept of "$s$-admissible tuples" of subspaces to manage the structural complexity arising from these compositions.

Key Results
The paper establishes the following main results:

• Optimal List Decodability: With high probability, random Gabidulin codes over sufficiently large alphabets ($F_{q^m}$) achieve the generalized Singleton bound for list decoding in the rank metric. Specifically, for a code of rate $R = k/n$, the code is $(\frac{L}{L+1}(1-R), L)$-average-radius list decodable for any list size $L$, provided the field extension degree $m$ is sufficiently large (specifically $m = \Omega_\ell(n^2)$).
• The GM-MRD Theorem: The authors prove that symbolic Gabidulin codes are GKP($\ell$) for all $\ell$. This implies that random Gabidulin codes over finite fields are GKP($\ell$) with high probability, provided the field size is large enough to avoid the vanishing of specific determinant polynomials (via the Schwartz–Zippel lemma).
• Field Size Lower Bound: The paper establishes a matching lower bound, showing that $m = \Omega_\ell(n^2)$ is necessary for Gabidulin codes to achieve the generalized Singleton bound for average-radius list decodability.
• Correction Note: The authors include an erratum noting that a specific theorem (Theorem 4.7) in the original proof required an additional assumption ($q \ge m-1$) due to a subtle error regarding the dimension of subspace intersections under linear projection. This assumption propagates to the main theorems, requiring $q \ge n-k-1$ for the main positive results, though the generic intersection formula and equivalence results remain valid without this restriction.

Significance and Claims
The paper claims to resolve a long-standing open problem by demonstrating the existence of Gabidulin codes with optimal combinatorial list decodability in the rank metric. The significance of this work is framed in several contexts:

• Theoretical Unification: It provides a unified theory for higher-order MRD codes, mirroring the theory of higher-order MDS codes, and proves the GM-MRD theorem, which is strictly stronger than the previously known GM-MDS theorem for Gabidulin codes (as it addresses kernel patterns rather than just zero patterns).
• Cryptographic Implications: The results impact the security analysis of rank-metric code-based cryptosystems (e.g., LIGA). The hardness of the list search version of the Random Syndrome Decoding (RSD) problem for Gabidulin codes was previously assumed to be high because the output list was believed to be exponential. This work shows that for random Gabidulin codes, the list size is bounded by the generalized Singleton bound, potentially necessitating a re-evaluation of security parameters for schemes relying on the hardness of list decoding Gabidulin codes.
• Pseudorandomness: The work connects rank-metric codes to pseudorandomness, suggesting that Gabidulin codes may serve as optimal objects for tasks like dimension expanders and extractors, similar to their Hamming-metric counterparts.

The authors remain modest regarding explicit constructions, noting that while random codes achieve these parameters, finding explicit constructions of Gabidulin codes with similar parameters remains an open question. They also highlight that the field size requirement ($m = \Omega(n^2)$) is optimal up to a constant factor depending on the list size.