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) 등의 고전 연구를 인용한다.
종합 평가 : 이는 모듈 격자 이론에서 중요한 진전을 이룬 고품질의 이론 수학 논문이다. 기술 요구사항이 높고 일부 매개변수 제약이 있지만, 격 암호학 및 관련 분야에 중요한 이론적 기초를 제공한다. 본 논문의 주요 가치는 이론과 실제 구성 사이의 다리를 구축한 것으로, 이는 해당 분야의 발전에 중요한 의미를 갖는다.
