Random Gabidulin Codes Achieve List Decoding Capacity in the Rank Metric

技术摘要：随机 Gabidulin 码在秩度量下达到列表译码容量

问题陈述
Gabidulin 码是 Reed–Solomon 码在秩度量（rank-metric）下的类比，也是最大秩距离（Maximum Rank Distance, MRD）码的一类主要形式。虽然已知 Reed–Solomon 码在 Johnson 界（Johnson bound）范围内是可列表译码的（且最近证明了随机代码可以达到广义 Singleton 界），但 Gabidulin 码是否具有列表可译性一直是长期悬而未决的问题，且此前多为负面结果。Raviv 和 Wachter-Zeh 的研究表明，特定的 Gabidulin 码甚至在超过唯一译码半径后就不具备组合列表可译性。本文探讨的核心问题是：Gabidulin 码能否在秩度量下超越唯一译码半径进行列表译码，即是否能达到最优的广义 Singleton 界。

方法论与框架
作者通过建立一个与近期 Brakensiek, Gopi, 和 Makam (BGM) 关于随机 Reed–Solomon 码列表可译性突破相平行的理论框架来解决这一问题。该方法依赖于三大支柱：

1. 高阶 MRD 码： 本文引入并定义了三种不同的“高阶 MRD 码”概念，它们定义在一般域扩张 $F/F_q$ 上：

   • GKP($\ell$)： 满足所有阶数至多为 $\ell$ 的“泛型核模式”（Generic Kernel Patterns）的码。核模式是一个满足其交集维度约束的子空间元组。
   • MRD($\ell$)： 满足此类性质的码，即任何 $\ell$ 个子空间在生成矩阵下的图像交集维度，与这些子空间在符号（泛型）矩阵下的图像交集维度相同。
   • LD-MRD($\le\ell$)： 在秩度量下对于半径 $\rho$ 是 $(\rho, \ell)$-平均半径可列表译码的码，其中 $\rho$ 为广义 Singleton 界半径。

2. 等价定理： 作者证明了这三种概念是等价的。具体而言，一个线性码是 GKP($\ell$) 当且仅当它是 MRD($\ell$)，且一个码是 MRD($\ell+1$) 当且仅当其对偶码是 LD-MRD($\le\ell$)。这一等价性将证明列表可译性的问题简化为证明随机 Gabidulin 码满足 GKP 性质。

3. GM-MRD 定理： 核心技术贡献是证明了“广义 MDS 用于 MRD”（Generalized MDS for MRD, GM-MRD）定理。该定理指出，符号 Gabidulin 码（定义在函数域上）能实现所有的泛型核模式。该证明借鉴了用于 GM-MDS 定理的归纳技术，但在处理由 $q$-线性多项式（定义 Gabidulin 码的多项式）的非交换复合性质所带来的复杂性时，面临着显著的新挑战。作者引入了“$s$-容许子空间元组”（$s$-admissible tuples）的概念，以管理由这些复合运算产生的结构复杂性。

关键结果
本文取得了以下主要成果：

• 最优列表可译性： 在足够大的字母表（$F_{q^m}$）条件下，随机 Gab 码以高概率达到秩度量下的广义 Singleton 界进行列表译码。具体而言，对于码率 $R = k/n$，只要域扩张次数 $m$ 足够大（具体为 $m = \Omega_\ell(n^2)$），对于任何列表大小 $L$，该码都是 $(\frac{L}{L+1}(1-R), L)$-平均半径可列表译码的。
• GM-MRD 定理： 作者证明了符号 Gabidulin 码对于所有 $\ell$ 都是 GKP($\ell$)。这意味着，只要域大小足够大，以避免特定行列式多项式的消失（通过 Schwartz–Zippel 引理），随机 Gab 码在有限域上以高概率满足 GKP($\ell$)。
• 域大小下界： 本文建立了一个匹配的下界，表明若要使 Gabidulin 码实现平均半径列表可译性的广义 Singleton 界，则 $m = \Omega_\ell(n^2)$ 是必要的。
• 勘误说明： 作者包含了一处勘误，指出原证明中的一个特定定理（定理 4.7）需要一个额外的假设（$q \ge m-1$），这是由于关于线性投影下子空间交集维度的细微错误导致的。该假设传播到了主要定理中，使得主要正向结果需要满足 $q \ge n-k-1$，尽管泛型交集公式和等价性结果在没有此限制的情况下依然有效。

意义与主张
本文声称解决了长期存在的开放问题，证明了存在具有最优组合列表可译性的秩度量 Gabadulin 码。其意义在以下几个背景下展开：

• 理论统一： 它为高阶 MRD 码提供了统一理论，镜像了高阶 MDS 码的理论，并证明了 GM-MRD 定理；该定理比已知的 GM-MDS 定理更强，因为它处理的是核模式而非仅仅是零模式。
• 密码学影响： 其结果影响了秩度量码基密码系统（如 LIGA）的安全分析。此前，人们认为基于 Gabadulin 码的随机综合征译码（Random Syndrome Decoding, RSD）问题的列表搜索版本具有很高的难度，因为其输出列表被认为呈指数级增长。这项工作表明，对于随机 Gabadulin 码，列表大小受限于广义 Singleton 界，这可能需要重新评估依赖于 Gabadulin 码列表译码难度的方案的安全参数。
• 伪随机性： 该工作将秩度量码与伪随机性联系起来，表明 Gabadulin 码可以作为维度扩展器（dimension expanders）和提取器（extractors）的最优对象，类似于其在汉明度量下的对应物。

作者对显式构造保持了审慎态度，指出虽然随机码可以达到这些参数，但寻找具有类似参数的显式 Gabadulin 码仍是一个开放性问题。他们同时强调，域大小要求（$m = \Omega(n^2)$）在取决于列表大小的常数因子意义下是优化的。