We prove tight probabilistic bounds for the shortest vectors in module lattices over number fields using the results of arXiv:2308.15275. Moreover, establishing asymptotic formulae for counts of fixed rank matrices with algebraic integer entries and bounded Euclidean length, we prove an approximate Rogers integral formula for discrete sets of module lattices obtained from lifts of algebraic codes. This in turn implies that the moment estimates of arXiv:2308.15275 as well as the aforementioned bounds on the shortest vector also carry through for large enough discrete sets of module lattices.
論文ID : 2402.10305タイトル : Effective module lattices and their shortest vectors著者 : Nihar Gargava, Vlad Serban, Maryna Viazovska, Ilaria Viglino分類 : math.NT (数論)、cs.IT (情報理論)、math.IT (数学情報理論)発表時期 : arXivプレプリント、2024年2月提出、2025年10月更新論文リンク : https://arxiv.org/abs/2402.10305v2 本論文は先行研究 1 の結果を活用し、数体上のモジュール格子における最短ベクトルの厳密な確率界を証明している。さらに、代数的整数要素を持ち、ユークリッド長が有界な固定階数行列の計数に関する漸近公式を確立することで、代数符号の持ち上げから得られるモジュール格子の離散集合に対する近似Rogers積分公式を証明している。これにより、1 の積率推定および上述の最短ベクトル界が、十分に大きなモジュール格子の離散集合にも適用されることが示される。
格暗号学における中心的問題 ：最短ベクトル問題(SVP)は格暗号学の中核であり、格内の最短非零ベクトルの長さを求める問題である。高速アルゴリズムの存在性は未解決問題であり、公開チャレンジが研究者にアルゴリズム提出を促している。ランダム格に関する既知結果 ：Haar ランダム格に対して、定理1は最短ベクトル長の精密な予測を与える：
1 − log log d d ≤ λ 1 ( Λ ) γ ( d ) ≤ 1 + log log d d 1-\frac{\log\log d}{d} \leq \frac{\lambda_1(\Lambda)}{\gamma(d)} \leq 1+\frac{\log\log d}{d} 1 − d l o g l o g d ≤ γ ( d ) λ 1 ( Λ ) ≤ 1 + d l o g l o g d γ ( d ) ≈ d 2 π e \gamma(d) \approx \sqrt{\frac{d}{2\pi e}} γ ( d ) ≈ 2 π e d d d d モジュール格子の特殊性 ：モジュール格子は追加の代数構造を持つ格子であり、環上の学習誤差問題(Ring-LWE)や短整数解問題(SIS)など、効率的な暗号実装に広く応用されている。研究上の課題 ：モジュール格子に対して定理1と同様の漸近推定を確立することはより困難であり、数体の次数増加時の挙動を理解する必要がある。モジュール格子最短ベクトルの確率界 ：秩 t t t t ≥ 27 t \geq 27 t ≥ 27 有効Rogers積分公式 ：代数符号の持ち上げから構成されるモジュール格子の離散集合に対する近似Rogers積分公式を確立した(定理15)。行列計数の漸近公式 ：Katznelsonの結果を一般数体に拡張し、固定階数行列計数の漸近公式を与えた(定理4)。理論と実践の架橋 ：理論的結果が代数符号から得られる有効な構成にも適用されることを証明し、計算論および符号理論的意義を示した。数体 K K K t t t Λ ⊆ K t ⊗ R \Lambda \subseteq K^t \otimes \mathbb{R} Λ ⊆ K t ⊗ R λ 1 ( Λ ) \lambda_1(\Lambda) λ 1 ( Λ )
モジュール格子は ( g , M ) (g,M) ( g , M ) g ∈ G L t ( K ⊗ R ) g \in GL_t(K \otimes \mathbb{R}) g ∈ G L t ( K ⊗ R ) M ⊆ K t M \subseteq K^t M ⊆ K t O K O_K O K vol ( K t ⊗ R / ( g − 1 ⋅ M ) ) = 1 \text{vol}(K^t \otimes \mathbb{R}/(g^{-1} \cdot M)) = 1 vol ( K t ⊗ R / ( g − 1 ⋅ M )) = 1
内積は以下で与えられる：
⟨ x , y ⟩ = ∣ Δ K ∣ − 2 deg K tr ( x y ˉ ) \langle x,y \rangle = |\Delta_K|^{-\frac{2}{\deg K}} \text{tr}(x\bar{y}) ⟨ x , y ⟩ = ∣ Δ K ∣ − d e g K 2 tr ( x y ˉ )
各モジュール格子は Steinitz 類 [ Λ ] ∈ cl ( K ) [\Lambda] \in \text{cl}(K) [ Λ ] ∈ cl ( K ) [ Λ ] = [ I ] ∈ cl ( K ) [\Lambda] = [I] \in \text{cl}(K) [ Λ ] = [ I ] ∈ cl ( K ) I I I M M M t t t
非分岐素イデアル P ⊆ O K P \subseteq O_K P ⊆ O K s s s L ( P , s ) = { β π P − 1 ( S ) ∣ S ⊆ k P t は s -次元 k P -部分空間 } L(P,s) = \{\beta\pi_P^{-1}(S) | S \subseteq k_P^t \text{は} s\text{-次元} k_P\text{-部分空間}\} L ( P , s ) = { β π P − 1 ( S ) ∣ S ⊆ k P t は s - 次元 k P - 部分空間 } β = N ( P ) − ( 1 − s t ) 1 [ K : Q ] \beta = N(P)^{-(1-\frac{s}{t})\frac{1}{[K:\mathbb{Q}]}} β = N ( P ) − ( 1 − t s ) [ K : Q ] 1
重要な技術は、十分に大きな N ( P ) N(P) N ( P ) 1 # L ( P , s ) ∑ Λ ∈ L ( P , s ) ( ∑ v ∈ Λ n g ( v ) ) → ∑ m = 0 n ∑ D ∈ M m × n ( K ) rk ( D ) = m D 行簡約階段形 D ( D ) − t ∫ x ∈ K R t × m g ( x D ) d x \frac{1}{\#L(P,s)} \sum_{\Lambda \in L(P,s)} \left(\sum_{v \in \Lambda^n} g(v)\right) \to \sum_{m=0}^n \sum_{\substack{D \in M_{m \times n}(K) \\ \text{rk}(D)=m \\ D \text{行簡約階段形}}} \mathcal{D}(D)^{-t} \int_{x \in K_R^{t \times m}} g(xD)dx # L ( P , s ) 1 ∑ Λ ∈ L ( P , s ) ( ∑ v ∈ Λ n g ( v ) ) → ∑ m = 0 n ∑ D ∈ M m × n ( K ) rk ( D ) = m D 行簡約階段形 D ( D ) − t ∫ x ∈ K R t × m g ( x D ) d x
補題13 は重要な階数低下問題を処理する：x ∈ M t × n ( O K ) x \in M_{t \times n}(O_K) x ∈ M t × n ( O K ) rk ( π P ( x ) ) < rk ( x ) \text{rk}(\pi_P(x)) < \text{rk}(x) rk ( π P ( x )) < rk ( x ) ∥ x ∥ ≥ C N ( P ) 1 m [ K : Q ] \|x\| \geq C N(P)^{\frac{1}{m[K:\mathbb{Q}]}} ∥ x ∥ ≥ CN ( P ) m [ K : Q ] 1
これにより、十分に大きな N ( P ) N(P) N ( P ) g g g
命題19 は重要な漸近推定を確立する：
∣ ∑ A ∈ M t × n ( O K ) rk ( A ) = m g ( β A ) β m t d − ∑ D ∈ R m , n ( K ) 1 D ( D ) t ∫ M t × m ( K R ) g ( x D ) d x ∣ ≪ β δ \left|\sum_{\substack{A \in M_{t \times n}(O_K) \\ \text{rk}(A)=m}} g(\beta A)\beta^{mtd} - \sum_{D \in R_{m,n}(K)} \frac{1}{\mathcal{D}(D)^t} \int_{M_{t \times m}(K_R)} g(xD)dx\right| \ll \beta^\delta ∑ A ∈ M t × n ( O K ) rk ( A ) = m g ( β A ) β m t d − ∑ D ∈ R m , n ( K ) D ( D ) t 1 ∫ M t × m ( K R ) g ( x D ) d x ≪ β δ
本論文は主に理論的研究であるが、以下の検証を提供している：
数体の選択 ：主に円分体 K = Q ( μ k ) K = \mathbb{Q}(\mu_k) K = Q ( μ k ) パラメータ範囲 ：秩 t ≥ 27 t \geq 27 t ≥ 27 次元 s s s 1 − s t < 1 n 1-\frac{s}{t} < \frac{1}{n} 1 − t s < n 1 漸近体制 ：k → ∞ k \to \infty k → ∞ d = ϕ ( k ) → ∞ d = \phi(k) \to \infty d = ϕ ( k ) → ∞ 固定 t ≥ 27 t \geq 27 t ≥ 27 K = Q ( μ k ) K = \mathbb{Q}(\mu_k) K = Q ( μ k ) d = t ⋅ deg K = t ϕ ( k ) d = t \cdot \deg K = t\phi(k) d = t ⋅ deg K = tϕ ( k ) Λ ⊆ K t ⊗ R \Lambda \subseteq K^t \otimes \mathbb{R} Λ ⊆ K t ⊗ R
k → ∞ k \to \infty k → ∞ 1 − o ( 1 ) 1-o(1) 1 − o ( 1 ) 1 − log log k d ≤ k − 1 d λ 1 ( Λ ) γ ( d ) ≤ 1 + log log k d 1-\frac{\log\log k}{d} \leq \frac{k^{-\frac{1}{d}}\lambda_1(\Lambda)}{\gamma(d)} \leq 1+\frac{\log\log k}{d} 1 − d l o g l o g k ≤ γ ( d ) k − d 1 λ 1 ( Λ ) ≤ 1 + d l o g l o g k
m ≤ n < t m \leq n < t m ≤ n < t N ( T ; m , n , t , K ) N(T;m,n,t,K) N ( T ; m , n , t , K ) O K O_K O K m m m T T T n × t n \times t n × t N ( T ; m , n , t , K ) = C ⋅ T m t deg K + O ( T m t deg K − 1 + ε ) N(T;m,n,t,K) = C \cdot T^{mt \deg K} + O(T^{mt \deg K - 1 + \varepsilon}) N ( T ; m , n , t , K ) = C ⋅ T m t d e g K + O ( T m t d e g K − 1 + ε )
Bogomolov性質を満たす数体のクラス S S S n n n ω K n ⋅ m n ( V ω K ) ≤ E [ ( # B ∩ Λ ∖ { 0 } ) n ] ≤ ω K n ⋅ m n ( V ω K ) + E n , t , K ⋅ ( V + 1 ) n − 1 \omega_K^n \cdot m_n\left(\frac{V}{\omega_K}\right) \leq \mathbb{E}[(\#B \cap \Lambda \setminus \{0\})^n] \leq \omega_K^n \cdot m_n\left(\frac{V}{\omega_K}\right) + E_{n,t,K} \cdot (V+1)^{n-1} ω K n ⋅ m n ( ω K V ) ≤ E [( # B ∩ Λ ∖ { 0 } ) n ] ≤ ω K n ⋅ m n ( ω K V ) + E n , t , K ⋅ ( V + 1 ) n − 1
ここで誤差項は E n , t , K ≤ C ⋅ ( t d ) ( n − 2 ) / 2 ⋅ ω K n 2 / 4 ⋅ Z ( K , t , n ) ⋅ e − ε ⋅ d ( t − t 0 ) E_{n,t,K} \leq C \cdot (td)^{(n-2)/2} \cdot \omega_K^{n^2/4} \cdot Z(K,t,n) \cdot e^{-\varepsilon \cdot d(t-t_0)} E n , t , K ≤ C ⋅ ( t d ) ( n − 2 ) /2 ⋅ ω K n 2 /4 ⋅ Z ( K , t , n ) ⋅ e − ε ⋅ d ( t − t 0 )
円分体 K i = Q ( ζ k i ) K_i = \mathbb{Q}(\zeta_{k_i}) K i = Q ( ζ k i ) t ≥ 27 t \geq 27 t ≥ 27 V V V B B B V 2 + V ⋅ k i ≤ E [ ( # B ∩ Λ ∖ { 0 } ) 2 ] ≤ V 2 + V ⋅ k i ⋅ ( 1 + C ⋅ e − ε ⋅ d i ( t − t 0 ) ) V^2 + V \cdot k_i \leq \mathbb{E}[(\#B \cap \Lambda \setminus \{0\})^2] \leq V^2 + V \cdot k_i \cdot (1 + C \cdot e^{-\varepsilon \cdot d_i(t-t_0)}) V 2 + V ⋅ k i ≤ E [( # B ∩ Λ ∖ { 0 } ) 2 ] ≤ V 2 + V ⋅ k i ⋅ ( 1 + C ⋅ e − ε ⋅ d i ( t − t 0 ) )
Rogers (1947) ：Siegel平均値定理の有効版を初めて考察Katznelson (1994) ：Q \mathbb{Q} Q Schmidt (1967) ：代数部分空間の高さ推定格約化アルゴリズム ：BKZアルゴリズムの完全分析モジュール格子暗号学 ：Ring-LWEおよびモジュールLWE問題等分布理論 ：Hecke点の等分布本論文は古典的Rogers積分公式をモジュール格子の有効構成に拡張し、理論と計算の間に橋を架けている。
理論的突破 ：モジュール格子に対してランダム格と同様の最短ベクトル確率界を初めて確立した方法論的革新 ：代数符号の持ち上げを処理する新しい技術を開発した応用的価値 ：格暗号学に理論的基礎を提供した技術的制限 ：t ≥ 27 t \geq 27 t ≥ 27 数体の制限 ：主要な結果はBogomolov性質を満たす数体に限定される計算複雑性 ：実際の計算における定数は大きい可能性がある界の改善 ：t t t 数体クラスの拡張 ：より一般的な数体を考察するアルゴリズム応用 ：理論的結果を実際の格約化アルゴリズムに変換する技術的深さ ：階数低下などの技術的困難を巧妙に処理している理論的完全性 ：理論から応用への完全な枠組みを確立している革新性 ：Rogers積分公式の有効化をモジュール格子に初めて適用した実用性 ：格暗号学に重要な理論的ツールを提供しているパラメータ制限 ：t ≥ 27 t \geq 27 t ≥ 27 証明の複雑性 ：技術的証明は複雑であり、可読性の向上の余地がある数値検証 ：理論結果を検証する具体的な数値実験が不足している理論的貢献 ：モジュール格子理論に重要な進展をもたらした応用前景 ：格暗号学および符号理論に重要な意義を持つ方法的価値 ：開発された技術は他の関連問題に適用可能である格暗号学 ：モジュール格子ベースの暗号システムのセキュリティ分析符号理論 ：効率的な誤り訂正符号の構成数論応用 ：数体上のディオファントス近似問題の研究本論文は主に著者の先行研究 1 Gargava, Serban, Viazovska. "Moments of the number of points in a bounded set for number field lattices" (arXiv:2308.15275v2, 2023)に基づいており、Rogers (1947)、Katznelson (1994)、Schmidt (1967)などの古典的研究を引用している。
総合評価 ：これはモジュール格子理論において重要な進展を遂行した高品質な理論数学論文である。技術的要件が高く、いくつかのパラメータ制限が存在するが、格暗号学および関連分野に重要な理論的基礎を提供している。本論文の主要な価値は、理論と実際の構成の間に橋を架けたことにあり、この分野の発展にとって重要な意義を持つ。
