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.
Effective module lattices and their shortest vectors 论文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随机格，Theorem 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)。研究挑战 ：为模格子建立类似Theorem 1的渐近估计更加困难，因为需要理解数域度数增长时的行为。模格子最短向量的概率界 ：证明了对于秩t t t t ≥ 27 t \geq 27 t ≥ 27 有效Rogers积分公式 ：建立了从代数码提升构造的模格子离散集合的近似Rogers积分公式（Theorem 15）。矩阵计数的渐近公式 ：推广了Katznelson的结果到一般数域，给出了固定秩矩阵计数的渐近公式（Theorem 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
Lemma 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
Proposition 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 渐近regime ：考虑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)等经典工作。
总体评价 ：这是一篇高质量的理论数学论文，在模格子理论方面取得了重要进展。虽然技术要求较高且存在一些参数限制，但为格密码学和相关领域提供了重要的理论基础。论文的主要价值在于建立了理论与实际构造之间的桥梁，这对于该领域的发展具有重要意义。
