Random Gabidulin Codes Achieve List Decoding Capacity in the Rank Metric

技術要約：ランダム・ガブイドリン符号はランク計量においてリスト復号容量を達成する

問題提起
ガブイドリン符号は、リード・ソロモン符号のランク計量における類似物であり、最大ランク距離（MRD）符号の主要なクラスを構成している。リード・ソロモン符号は、ジョンソン境界（Johnson bound）まで、そして最近ではランダム符号に対して一般化されたシングルトン境界（generalized Singleton bound）までリスト復号可能であることがよく知られているが、ガブイドリン符号のリスト復号可能性については、主に否定的な結果が示されてきた長年の未解決問題であった。RavivとWachter-Zehによる先行研究は、特定のガブイドリン符号が、一意復号半径を超えると組合せ論的なリスト復号すらできないことを示した。本論文が扱う中心的な問いは、ガブイドリン符号がランク計量において一意復号半径を超えてリスト復号可能か、具体的には、最適な一般化シングルトン境界を達成できるかという点である。

手法およびフレームワーク
著者らは、ランダムなリード・ソロモン符号のリスト復号可能性に関する最近の画期的な成果（Brakensiek, Gopi, and MakamによるBGM）と並行する理論的フレームワークを確立することで、この問題を解決する。その手法は、以下の3つの柱に基づいている：

1. 高次MRD符号： 本論文では、一般的な体拡大 $F/F_q$ 上の3つの異なる「高次MRD符号」の概念を導入し、定義する：

   • GKP($\ell$): 最大で次数 $\ell$ までのすべての「ジェネリック・カーネル・パターン（Generic Kernel Patterns）」を満たす符号。カーネル・パターンとは、それらの交差に関する次元制約を満たす部分空間のタプルである。
   • MRD($\ell$): 任意の $\ell$ 個の部分空間の像の交差の次元が、対応する部分空間のシンボリック（ジェネリック）な行列による像の交差の次元と等しくなるような符号。
   • LD-MRD($\le\ell$): ランク計量において $(\rho, \ell)$-平均半径リスト復号可能である符号。ここで $\rho$ は一般化されたシングルトン境界の半径である。

2. 同値性定理： 著者らは、これら3つの概念が同値であることを証明する。具体的には、ある線形符号がGKP($\ell$)であることと、それがMRD($\ell$)であることは同値であり、また、ある符号がMRD($\ell+1$)であることと、その双対符号がLD-MRD($\le\ell$)であることは同値である。この同値性により、リスト復号可能性の証明問題は、ランダムなガブイドリン符号がGKP特性を満たすことを証明する問題へと還元される。

3. GM-MRD定理： 中核となる技術的貢献は、「MRDのための一般化MDS（Generalized MDS for MRD: GM-MRD）」定理の証明である。この定理は、シンボリック・ガブイドリン符号（関数体上で定義される）がすべてのジェネリック・カーネル・パターンを満たすことを述べている。証明は、GM-MDS定理で使用された帰納的手法を適応させたものであるが、ガブイドリン符号を定義する $q$-線形多項式の非可換な合成に起因する、重大な新たな課題に直面する。著者らは、これらの合成から生じる構造的複雑さを管理するために、「$s$-許容タプル（$s$-admissible tuples）」という概念を導入している。

主な結果
本論文は、以下の主要な結果を確立している：

• 最適なリスト復号可能性： 十分に大きなアルファベット（$F_{q^m}$）の上では、ランダムなガブイドリン符号は、高い確率でランク計量における一般化されたシングルトン境界を達成する。具体的には、符号のレートが $R = k/n$ であるとき、体拡大次数 $m$ が十分に大きい場合（具体的には $m = \Omega_\ell(n^2)$）、その符号は任意のリストサイズ $L$ に対して $(\frac{L}{L+1}(1-R), L)$-平均半径リスト復号可能である。
• GM-MRD定理： 著者らは、シンボリック・ガブイドリン符号がすべての $\ell$ に対してGKP($\ell$)であることを証明した。これは、ランダムなガブイドリン符号が、特定の行列式多項式が消滅することを避けるために（シュワルツ・ジップの補題を介して）十分な体サイズを持つ限り、高い確率でGKP($\ell$)であることを意味する。
• 体サイズの低次境界： 本論文は、ガブイドリン符号が平均半径リスト復号可能性において一般化されたシングルトン境界を達成するために、$m = \Omega_\ell(n^2)$ が必要であることを示す、一致する下界を確立している。
• 訂正ノート： 著者らは、元の証明における特定の定理（定理4.7）において、線形射影下での部分空間の交差の次元に関する微妙な誤りにより、追加の仮定（$q \ge m-1$）が必要であったことを記した訂正を含めている。この仮定は主定理にも波及し、主要な正の結果を得るためには $q \ge n-k-1$ が必要となるが、ジェネリックな交差公式および同値性の結果自体は、この制限なしでも有効である。

意義および主張
本論文は、ランク計量において最適な組合せ論的リスト復号可能性を持つガブイドリン符号の存在を示すことで、長年の未解決問題を解決したと主張している。本研究の意義は、以下の文脈で構成されている：

• 理論的統一： 高次MDS符号の理論を反映した、高次MRD符号の統一的な理論を提供し、ガブイドリン符号に対するGM-MDS定理（ゼロ・パターンの代わりにカーネル・パターンを扱うため、より強力である）よりも厳密に強いGM-MRD定理を証明している。
• 暗号学的含意： これらの結果は、ランク計量符号ベースの暗号システム（例：LIGA）の安全性分析に影響を与える。ガブイドリン符号に対するランダム・シンドローム復号（RSD）問題のリスト探索版の困難性は、出力リストが指数関数的になると信じられていたため、以前は高いと想定されていた。本研究は、ランダムなガブイドリン符号に対しては、リストサイズが一般化されたシングルトン境界によって抑えられることを示しており、ガブイドリン符号のリスト復号の困難性に依存するスキームのセキュリティパラメータの再評価を迫る可能性がある。
• 擬似ランダム性： 本研究はランク計量符号を擬似ランダム性と結びつけ、ガブイドリン符号が、ハミング計量の対応物と同様に、次元エキスパンダーや抽出器などのタスクにおいて最適な対象となり得ることを示唆している。

著者らは、ランダムな符号がこれらのパラメータを達成する一方で、同様のパラメータを持つ明示的な構成法を見つけることは依然として未解決の課題であるとし、明示的な構成に関しては控えめな姿勢を保っている。また、体サイズの要件（$m = \Omega(n^2)$）は、リストサイズに依存する定数を除いて最適であることを強調している。