Predicting Module-Lattice Reduction

技術要約：モジュール格子簡約の予測

問題提起
本論文は、モジュール格子ベースの暗号スキーム（ML-KEM、ML-DSA、FN-DSAなどのNIST標準）の暗号解読における極めて重要な問いを扱っている。すなわち、「モジュール格子簡約（具体的にはmodule-BKZ）は、同じ最短ベクトル問題（SVP）オラクルが与えられた場合、非構造化格子簡約（BKZ）よりも効率的なのか、あるいは非効率なのか？」という問いである。

基礎的な理論的研究では、LLLおよびブロック簡約アルゴリズムのモジュール版の存在が示されてきたが、それらは最悪ケースのアスンプトティック（漸近的）な挙動に焦点を当てたものであった。KyberのNIST提出における「Q8」として強調された特定の懸念は、円分体上のモジュール格子の代数的構造が、スピードアップ（例：$d$ から $d^2$ の因子）を可能にするのか、あるいは逆に、非構造化BKZと比較して基底の質を低下させるのかという点であった。本論文は、具体的な平均ケースの解析を提供することで、特定の基底の質（スロープ）を達成するために必要なブロックサイズ $\beta$ に関して、module-BKZが利得を得るのか損失を生じるのかという問いに答えることを目的としている。

手法
著者らは、module-BKZを実行した後の基底プロファイルの「スロープ」を予測するために、広範な実験に裏打ちされたヒューリスティックに基づく解析を用いている。スロープは、グラム・シュミット直交化されたベクトルの対数ノルムの減衰率として定義される。

1. 実験的実装: 著者らは、既存のライブラリ fplll および G6K を利用し、円分体（導数16まで）に対するmodule-BKZの初のオープンソース実装を開発した。彼らは、サイズ簡約中のモジュール構造の保持、およびトレース内積が標準的な整数格子簡約ライブラリと互換性を持つようにするための「巡回埋め込み（cyclic embedding）」の使用に関する技術的課題に対処した。
2. 理論的モデリング（Module-Lattice GSA）: 彼らは、非構造化BKZで一般的に使用される幾何級数仮定（GSA）をモジュール格子へと拡張した。これには、簡約された基底の期待される $K$-プロファイル（数体の次数 $d$ にわたって平均化されたもの）のモデリングが含まれる。
3. スロープの分解: module-BKZの予測スロープは、非構造化BKZからの偏差を駆動する4つの明確な項（$t_1$ から $t_4$）に分解される。
   • $t_1$ (ガウス・ヒューリスティック): ランダムなモジュール格子における最短ベクトルの期待長を、単数（roots of unity）の数 $\mu_K$ で調整したもの。
   • $t_2$ (判別式ギャップ): 数体 $K$ の判別式 $\Delta_K$ に依存する項。
   • $t_3$ (歪みギャップ): ベクトルの代数的ノルムとユークリッドノルムの偏差（埋め込みにわたるベクトルの歪み）を測定するもの。
   • $t_4$ (指数ギャップ): モジュール内の最短ベクトルによって生成されるイデアルの指数を考慮したもの。
4. 漸近解析: 著者らは、module-BKZがブロックサイズ $\beta$ の非構造化BKZと同じスロープに一致するために必要な「等価ブロックサイズ」$\beta_{eq}$ に関する漸近公式を導出した。

主要な貢献と結果

• スロープの定量的予測: 本論文は、ブロックサイズ $\beta$、体次数 $d$、および体の判別式 $\Delta_K$ の関数として、module-BKZのスロープを予測する具体的な公式を提供している。
• 駆動要因としての判別式: 解析により、性能差を駆動する主要な量は判別式 $\Delta_K$ であることが特定された。具体的には、対数項 $\ln(|\Delta_K|/d^d)$ が、module-BKZが利得を得るか損失を生じるかを決定する。
• 漸近的なブロックサイズの利得/損失: 著者らは以下の等価ブロックサイズ $\beta_{eq}$ に関する漸近関係を導出した：
  $$\beta_{eq} \approx \beta + \ln\left(\frac{|\Delta_K|}{d^d}\right) \frac{\beta}{d \ln \beta} + (d - 1)$$
  • 2のべき乗円分体: 導数が2のべき乗である場（現在のNIST標準に関連）では、$|\Delta_K| = d^d$ である。したがって、対数項は消失し、コストは線形項 $d-1$ によって支配される。これは、module-BKZが同じスロープを実現するために、非構造化BKZよりも約 $d-1$ だけ大きなブロックサイズを必要とすることを意味する。これは、KyberのQ8で提起された懸念を裏付け、定量化しており、スピードアップではなく、わずかな性能低下を示唆している。
  • その他の円分体: 導数に奇素因数を持つ場（例：$2^i \cdot 3^j$ の形式の導数）では、$|\Delta_K| < d^d$ となる。これらの場合、対数項は負となり、必要なブロックサイズの劣線形な利得（$\Theta(\beta / \ln \beta)$）をもたらす。これは、攻撃複雑性における劣指数的なスピードアップに相当する。
• 実験による検証: 様々な円分体（$\mathbb{Q}(\omega_3), \mathbb{Q}(\omega_4), \mathbb{Q}(\omega_{15}), \mathbb{Q}(\omega_{16})$）を用いた著者らの実験データは、彼らの予測とよく一致している。データは、$\mathbb{Q}(\omega_3)$ および $\mathbb{Q}(\omega_{15})$ が非構造化のベースラインと比較して平坦なプロファイル（より優れた簡約）を示す一方で、$\mathbb{Q}(\omega_{16})$（2のべき乗）はより悪いプロファイルを示すことを裏付けている。

意義と主張
本論文は、最悪ケースの理論的境界を超えて、module-BKZの具体的な平均ケースの解析を提供した最初の研究であると主張している。その意義は以下の通りである：

1. Q8の解決: 2のべき乗円分体におけるmodule-BKZの効率に関する未解決の問いに直接答え、これらの特定の場においては、モジュール構造は非構造化BKZに対するスピードアップを提供せず、むしろ小さなオーバーヘッド（より大きなブロックサイズを必要とする）を課すことを結論づけた。
2. 代替構成の特定: 小さな奇素因数（例：3, 5）を持つ導数を使用するモジュール格子スキームは、以前の想定よりも大幅に脆弱である可能性があることを強調している。なぜなら、代数的構造が格子簡約攻撃に対して劣指数的なスピードアップを提供するからである。
3. 実践的なツール提供: 初のmodule-BKZのオープンソース実装を提供することで、著者らはモジュール格子スキームのさらなる実験とセキュリティ推定を可能にした。

著者らは、自身の解析がヒューリスティック（モジュール用に適応された幾何級数仮定など）に依存しており、「ヘッド・アンド・テール（頭部と尾部）」現象のモデリングやアルゴリズムの収束速度には依然としてギャップがあることを認め、自らの主張に対して謙虚な姿勢を保っている。彼らは、自らの結果がまだ特定の攻撃に対する正確なコストを提供するものではなく、あくまで簡約された基底のスロープに関する予測的な枠組みを提供するものであることを明示している。