2025-11-10T02:37:02.890602

Module lattices and their shortest vectors

Gargava, Serban, Viazovska et al.

We study the shortest vector lengths in module lattices over arbitrary number fields, with an emphasis on cyclotomic fields. In particular, we sharpen the techniques of arXiv:2308.15275v2 to establish improved results for the variance of the number of lattice vectors of bounded Euclidean norm in a random module lattice. We then derive tight probabilistic bounds for the shortest vector lengths for several notions of random module lattice.

academic

モジュール格とその最短ベクトル

基本情報

論文ID: 2510.12893
タイトル: Module lattices and their shortest vectors
著者: Nihar Gargava, Vlad Serban, Maryna Viazovska, Ilaria Viglino
分類: math.NT（数論）、cs.IT（情報理論）、math.IT（数学情報理論）
発表日: 2025年10月14日（arXiv プレプリント）
論文リンク: https://arxiv.org/abs/2510.12893

要約

本論文は、任意の数体上のモジュール格（module lattices）における最短ベクトルの長さを研究し、特に円分体（cyclotomic fields）に焦点を当てている。著者らは先行研究arXiv:2308.15275v2の技術を改善し、ランダムモジュール格における有界ユークリッドノルムを持つ格ベクトルの個数の分散に関する、より良い結果を確立した。その後、ランダムモジュール格の複数の概念における最短ベクトル長の厳密な確率界を導出した。

研究背景と動機

問題背景

格ベース暗号学の中心的問題：最短ベクトル問題（SVP）は格ベース暗号学の基礎であり、その困難性は多くの耐量子暗号システムの安全性の根拠となっている。
モジュール格の重要性：NTRU暗号システムの導入以来、代数構造を持つモジュール格は、無構造格と比較した効率上の利点から注目を集めており、現在複数のNIST耐量子標準の基礎となっている。
理論的空白：一般的なランダム格に対しては定理1により最短ベクトル長の正確な漸近挙動が与えられているが、追加の代数構造を持つモジュール格に対しては同様の結果が不足している。

研究動機

安全性評価の必要性：量子計算の脅威下において、モジュール格上の計算問題の困難性をより深く理解する必要がある。
理論の完成：モジュール格理論における最短ベクトルの確率的挙動に関する空白を埋める。
実用的価値：モジュール格ベースの暗号システムに理論的支援と安全性分析ツールを提供する。

核心的貢献

改善されたモーメント推定：先行研究における最小秩条件をt ≥ 27からt ≥ 11に低下させ、低Weil高さを持つ代数数の寄与をより精密に処理することで実現した。
円分体の統一的結果：円分体上のモジュール格の最短ベクトルの漸近挙動を確立し（定理3）、無構造格の古典的結果と同様の形式を得た。
実用的な確率界：現在の実装方案における具体的な数体と秩に適用可能な、計算可能な厳密な確率界を提供した。
技術的方法の改善：モジュール格における追加的な対称性（単位群の作用）を処理する精密な技術を開発し、特に円分体の場合に最適化した。

方法の詳細

タスク定義

ランダムモジュール格Λ ∈ Mod_t(K)における最短非零ベクトルλ₁(Λ)の確率分布を研究する。ここでKは数体、tはO_K-秩である。核心的なランダム変数は以下の通り： $\rho_V(\Lambda) := \#(B \cap (\Lambda \setminus \{0\}))$ ここでBは体積Vの原点中心球である。

モデルアーキテクチャ

1. Rogers積分公式の拡張

モジュール格に対して、二次モーメントの積分表現は以下の通り： $E[\rho_V(\Lambda)^2] = \text{vol}(B)^2 + \sum_{\alpha \in K^{\times}} D(\alpha)^{-t} \cdot \text{vol}(B \cap \alpha^{-1}B)$

ここでD(α) = O_K : α^{-1}O_K ∩ O_Kは格指数である。

2. 単位群の処理

重要な観察：単位群O_K^×の対角作用により、ρ_V(Λ)は常にω_K = #μ(K)の倍数であるため、自然な研究対象はω_K-組の個数である。

3. 高さ界の応用

Weil高さ理論を利用して、幾何学的推定を確立する： $\frac{\text{vol}(B \cap \alpha^{-1}B)}{\text{vol}(B)} \leq \left(\frac{e^{2h_{\infty}(\alpha)} + e^{-2h_{\infty}(\alpha)} \cdot N(\alpha)^{2/d}}{2}\right)^{-dt/2}$

技術的革新点

1. 階層化された高さ処理

代数数をWeil高さに基づいて階層化し、異なる高さ範囲に対して異なる推定戦略を採用することで、最小秩条件を最適化した。

2. 円分体の特殊性

円分体のCM性質とSchinzel-Smythの全正代数整数に関する高さ下界を利用して、均一な定数を得た：

c(K) = 0.155（一般的な場合）
c_o(K) = 0.2406（無限位の場合）
c_S(K) = 0.271763（単位群外の場合）

3. 単位計数の精密推定

補題10は有界高さを持つ単位の個数に関する上界を提供する： $\#\{\beta \in O_K^{\times} | h(\eta + L(\beta)) \leq X\} \leq \#S_K \cdot \left(\frac{X + c_S(K)/2}{c_S(K)/2}\right)^{r_1+r_2-1}$