Two Families of Linear Codes Containing Non-GRS MDS Codes

この論文「Two Families of Linear Codes Containing Non-GRS MDS Codes（GRS 符号を含む 2 つの線形符号族：非 GRS MDS 符号）」は、有限体上の線形符号、特に最大距離可分（MDS）符号の新しい構成法とその性質に関する研究です。著者らは、一般化されたリード・ソロモン（GRS）符号の生成行列を修正することで、既存の GRS 符号と単項同値（monomial equivalent）ではない新しい非 GRS MDS 符号の 2 つの族を構築しました。

以下に、論文の技術的な要約を問題定義、手法、主要な貢献、結果、そして意義に分けて詳述します。

1. 問題定義と背景

• MDS 符号の重要性: MDS 符号は、分散ストレージ、秘密共有、暗号システムなど、多岐にわたる応用分野で重要な役割を果たしています。
• GRS 符号の限界: 既知の MDS 符号の多くは一般化されたリード・ソロモン（GRS）符号ですが、暗号学的な観点からは、GRS 符号は Sidelnikov-Shestakov 攻撃や Wieschebrink 攻撃に対して脆弱であることが知られています。
• 非 GRS MDS 符号の必要性: これらの攻撃への耐性を高めるため、GRS 符号と単項同値ではない「非 GRS MDS 符号」の構築と分類が理論的・実用的に重要です。
• 既存研究: これまでに、ツイステッド・リード・ソロモン（TRS）符号や、GRS 生成行列から特定の行を削除・拡張した符号などが研究されてきましたが、より広範なパラメータを持つ新しい非 GRS MDS 符号の族の構築と、その自己直交性・自己双対性の完全な特徴付けは依然として課題でした。

2. 手法とアプローチ

著者らは、GRS 符号の生成行列を以下のように修正して 2 つの新しい符号族を定義しました。

1. 第一の符号族 ($C_{i,j}$):
   • GRS 符号 $RS(n, k+2, \Lambda)$ の生成行列から、特定の 2 つの行（$(i+1)$ 行目と $(j+1)$ 行目）を削除して得られる $k \times n$ 行列を生成行列とする符号。
   • ここで $1 \le i < j \le k$ です。
2. 第二の符号族 ($C_{h,k}$):
   • 通常の GRS 符号の生成行列（$0$次から$k-2$次までの項）に、$h$次（$h \ge k-1$）の項を追加した行列を生成行列とする符号。
   • ここで $3 \le k \le h \le n-1$ です。

解析手法:

• パリティチェック行列の導出: 対称関数（初等対称関数 $\sigma_t$ と完全対称関数 $S_t$）および Vandermonde 行列の性質を用いて、両符号族の明示的なパリティチェック行列を導出しました。
• MDS 性の判定: 生成行列のすべての $k \times k$ 部分行列が非特異であること（Lemma 2.2）に基づき、MDS 符号となるための必要十分条件を対称関数の式で導きました。
• 非 GRS 性の判定: Schur 積（Hadamard 積）と Schur 平方（$C \star C$）の次元を用いた判定法（Lemma 2.1）を採用しました。GRS 符号の場合、$\dim(C \star C) = 2\dim(C) - 1$ となりますが、構築した符号ではこの次元が $2k$ 以上になることを示すことで、非 GRS 性を証明しました。
• 自己直交性・自己双対性: 生成行列 $G$ に対して $GG^T = 0$ となる条件を解析し、特定の多項式 $f(x)$ の存在と係数に関する条件を導出しました。

3. 主要な貢献と結果

A. 新しい符号族の構築とパラメータ

• $C_{i,j}$ 族:

  • パラメータ $[n, k]$ を持つ符号を構成。
  • MDS 条件: 任意の $k$ 個の異なる評価点 $\{\beta_1, \dots, \beta_k\} \subseteq \Lambda$ に対して、特定の対称関数の式（$\sigma_{k-i}\sigma_{k-j+1} - \sigma_{k-i+1}\sigma_{k-j} \neq 0$）が成り立つこと。
  • 非 GRS 性: $k \ge 5$ の場合、Schur 平方の次元が $2k+1$ 以上となり、非 GRS であることが証明されました。また、$k=3, 4$ の特定の条件下でも非 GRS となることが示されました。
  • 構成例: 有限体 $\mathbb{F}_{p^m}$ 上で、長さ $n \le p^{\lfloor (m-1)/4 \rfloor}$ の非 GRS MDS 符号を明示的に構成する定理（Theorem 3.8）を提供しました。

• $C_{h,k}$ 族:

  • パラメータ $[n, k]$ を持つ符号を構成。
  • MDS 条件: 任意の $k$ 個の異なる評価点に対して、完全対称関数 $S_{h-k+1}(\beta_1, \dots, \beta_k) \neq 0$ となること。
  • 非 GRS 性: $h$ の値（$r = h-(k-1)$）に応じて、Schur 平方の次元が $2k$ 以上になることを示し、非 GRS 性を証明しました。
  • 構成例: 長さ $n \le p^{\lfloor (m-1)/2 \rfloor}$ の非 GRS MDS 符号を構成する定理（Theorem 4.6）を提供しました。また、$q=2^m$ の場合、長さ $q+2$ の MDS 符号（超楕円弧に対応）の構成も示唆しています。

B. 自己直交性と自己双対性の特徴付け

• 自己直交性の条件:
  • 両符号族について、符号が自己直交となるための必要十分条件を導出しました。これは、非ゼロベクトル $v$ に対して $v_i^2 = u_i f(\alpha_i)$ を満たす多項式 $f(x)$ の存在と、その係数が満たすべき線形方程式系（$S_t$ を用いた条件）として記述されます。
• 自己双対性の条件:
  • $n=2k$ の場合、自己双対符号が存在するための条件を特定しました。
  • 特に $C_{h,k}$ 族において、$r=1$ かつ $S_1=0$（および $u_i$ がすべて平方または非平方であること）が自己双対性の条件となることが示されました。
  • 偶数特性の体 $\mathbb{F}_q$ における自己双対符号の具体的な構成例（Corollary 4.11）も提示されました。

C. 具体的な構成と数値例

• 論文では、$q=17, 19, 23, 25, 37$ などの具体的な有限体上で、非 GRS MDS 符号や自己直交・自己双対符号の生成行列を明示的に計算し、その有効性を検証する多数の例（Example 1〜9）を提供しています。
• 表 1 には、Theorem 4.5 を用いて構成された、長さ $(q-1)/2$ の非 GRS MDS 符号のパラメータ一覧が記載されています。

4. 意義と将来の展望

• 理論的貢献: 有限射影空間における弧（arc）の分類において、既知の GRS 符号（正規有理曲線）以外の新しい MDS 符号の族を特定し、その存在を証明しました。これにより、MDS 符号の分類がさらに進みました。
• 暗号学的意義: 構築された非 GRS MDS 符号は、GRS 符号特有の攻撃に対して耐性を持つ可能性があり、暗号システム（特にコードベース暗号）におけるセキュリティ強化に寄与します。
• 量子符号理論: 自己直交および自己双対 MDS 符号の構成は、量子誤り訂正符号（特に CSS 符号）の構築に直接応用可能です。
• 将来の課題: 著者は、Vandermonde 行列から任意の数の行を削除して得られるより一般的な符号族 $C_I$ の研究を将来の課題として挙げています。しかし、一般化された場合の MDS 性の必要十分条件は極めて複雑になるため、その解析は技術的に困難であると指摘しています。

まとめ

本論文は、GRS 符号の生成行列を工夫して変形することで、非 GRS である MDS 符号の 2 つの新しい無限族を構築し、それらのパリティチェック行列、MDS 性、非 GRS 性、自己直交性・自己双対性を完全に特徴付けた画期的な研究です。特に、Schur 平方を用いた非 GRS 性の証明と、対称関数を用いた明示的な構成条件の導出は、符号理論の分野において重要な進展をもたらしています。