The Star Product of Uniformly Random Codes

技術要約：一様ランダム符号のスター積

問題提起
本論文は、有限体 $\mathbb{F}_q$ 上の2つの独立な一様ランダム線形符号 $C_1$ および $C_2$ のスター積（シュア積またはアダマール積とも呼ばれる）の期待次元を調査するものである。これらの符号は、それぞれ既定の次元 $k_1, k_2$ および長さ $n$ を持つ。スター積は、量子誤り訂正、プライベート情報検索（PIR）、および安全な分散型行列乗算（SDMM）における応用など、符号理論において基礎的な演算であるが、2つのランダム符号のスター積の次元を決定することは容易ではない。先行研究 [19] などでは、ランク1行列の線形独立性を分析することでこの次元を推定しており、制限されたパラメータ領域の下で、期待次元が確率的に $\min\{n, k_1k_2\}$ に等しくなることを示している。本論文の目的は、これらの制限された領域を超えて、期待次元およびその分散に関する、より一般的かつ明示的な解析を提供することである。

手法
著者らは、2つの符号のスター積と双線形形式の評価との間の対応関係を確立している。具体的には、$C_1$ と $C_2$ が生成行列 $G_1$ と $G_2$ を持つ場合、スター積 $C_1 \star C_2$ は、双線形形式の空間 $B = \text{Bil}(\mathbb{F}_q^{k_1}, \mathbb{F}_q^{k_2})$ に作用する線形写像 $\psi_{G_1, G_2}$ の像として特定される。スター積の次元は $k_1k_2 - \dim(\ker \psi_{G_1, G_2})$ で与えられる。

期待次元を分析するために、著者らはカーネルの期待サイズ $\mathbb{E}[|\ker \psi_{C_1, C_2}|]$ の計算に焦点を当てる。彼らは、生成行列の最後の $n-k$ 個の列を一様にランダムに選択することによって符号を生成するという確率モデルを利用している。分析には以下が含まれる：

1. 計数組合せ論： 生成行列の列上で消滅する特定のランク $r$ の双線形形式（行列として表現される）の数を数える。これには、ゼロ対角成分および特定のゼロパターンを持つ行列の計数が必要となる。
2. 明示的な公式： $q$-二項係数と包含排除原理を用いて、期待カーネルサイズの明示的な公式を導出する（補題 3.5 および定理 3.9）。
3. 漸近解析： 体のサイズ $q \to \infty$ および、特定の成長条件の下での $k_1, k_2 \to \infty$ におけるこれらの公式の挙動を調査する。
4. 分散解析： 期待カーネルサイズに対する導出された境界を用いて、スター積の次元の分散の上界を求める。

主な貢献と結果

1. 明示的な下界： 本論文は、評価写像のカーネルの期待サイズに関する明示的な公式を提供し、これにより、すべてのパラメータ選択に対してスター積の期待次元の明示的な下界が得られる（系 3.11）。このアプローチは、ランク1行列による解析とは異なり、カーネルの直接的な組合せ論的カウントを提供している点で異なる。

2. 体サイズにおける漸近性 ($q \to \infty$)：

   • 著者らは、体サイズ $q$ が無限大に発散するにつれて、期待されるスター積の次元が、$k_1$ と $k_2$ の関係に関わらず、最大可能値 $\min\{n, k_1k_2\}$ に漸近的に到達することを証明している（系 4.2）。
   • 具体的には、$k_1k_2 < n$ の場合、期待カーネルサイズは1に近づき、$k_1k_2 = n$ の場合は2に近づき、$k_1k_2 > n$ の場合は発散する。
   • 次元の分散は、漸近的に0へと減衰することが示されており、その速度は $k_1k_2 < n$ か $k_1k_2 \ge n$ かによって異なる（命題 4.3）。

3. 符号次元における漸近性 ($k_1, k_2 \to \infty$)：

   • 「適応的な」成長条件（$k_1$ と $k_2$ が厳密に単調に増加し、$k_1k_2$ が $q^{k_1}$ に対して急速に成長しない場合）の下で、本論文は期待カーネルサイズが安定することを証明している（定理 5.7）。
   • その結果、次元が増加するにつれて、スター積の期待次元は高確率で $\min\{n, k_1k_2\}$ に達する（系 5.12）。
   • 分散はこれらの条件下で漸近的に消失することが示されており、$n < k_1k_2$ であるか、あるいはギャップ $n - k_1k_2$ が線形に成長する場合、少なくとも指数関数的に減衰する（命題 5.14）。

4. 先行研究との比較： 結果は [19] のランク1行列アプローチと比較されている。著者らは、自身の研究が、特に $q \ge 3$ のような大きな体サイズにおいて、より広い範囲のパラメータ領域をカバーしており、次元の成長に関する境界が [19] よりも厳密に強いことを指摘している（注釈 5.13）。

意義と影響
本論文は、これらの結果が以下の領域に直接的な影響を与えることを主張している：

• プライベート情報検索 (PIR): スター積に基づくPIRスキームにおいて、リトリーバルレートはスター積の次元によって制限される。本結果は、ランダム符号は漸近的に最大次元のスター積をもたらすが（GRSのような構造化された符号と比較して低いリトリーバルレートとなる）、小さな体（例：$\mathbb{F}_2$）においては、好ましいランダム符号ペアをサンプリングできる非無視できない確率が存在することを示唆している。これは、エラーフリーな設定において、有利なランダム符号ペアの実験的な探索が実行可能であることを意味する。
• 安全な分散型行列乗算 (SDMM): PIRと同様に、SDMMにおけるリカバリ閾値とストラグラー耐性は、スター積の次元に依存する。本知見は、ランダムな構成は通常、漸近的に低いリカバリ閾値を達成しないものの、有利なパラメータを持つ実用的なインスタンスは小規模な体の上で見つけられる可能性があることを示している。
• 量子誤り訂正: 本論文は、バイナリCSS-T符号について論じている。これには $C_2 \subseteq C_1 \cap (C_1 \star C_1)^\perp$ が必要である。結果は、十分に大きな次元を持つ一様ランダム符号の場合、スター積 $C_1 \star C_1$ が大きくなる可能性が高く、その結果、直交補空間が小さくなることを示唆している。これは、ランダムな $C_1$ を用いて高距離のCSS-T符号を構築することは困難であることを示唆している。なぜなら、得られる量子符号は最小距離の弱い下限を持つことになるからである。
• 暗号解読: スター積の次元は、符号ベース暗号（例：Goppa符号に対するもの）における識別子として使用される。本論文は、ランダム符号は一般に最大のスター積次元を持ち（Goppa符号のような、より小さな平方を持つ構造化された符号と区別可能になる）、彼らの結果は標準的なMcElieceシステムのセキュリティを現在脅かすものではないが、解析された特定のパラメータ範囲については、そのように述べている。しかし、本手法は、新しいパラメータ範囲を探索するために異なる符号ペアのスター積を分析する道を開いている。

結論
本論文は、一様ランダムな2つの符号のスター積の期待次元は、体サイズが増加するにつれて、また特定の成長条件の下で符号の次元が増加するにつれて、理論上の最大値に漸近的に到達すると結論付けている。これらの領域では分散は消失し、測度の集中を示している。著者らは、分散のタイトな下界の導出および非漸近的なケースの解析を、将来の研究に向けた未解決の問題として挙げている。