Module Lattice Security (Part I): Unconditional Verification of Weber's Conjecture for $k \le 12$

논문 요약: Weber 의 추측에 대한 무조건적 증명 (k ≤12)

1. 연구 배경 및 문제 제기

• Weber 의 추측 (1886): 모든 정수 $k \ge 1$에 대해, $2^k$-차 원분체의 최대 실수 부분체 $K_k^+ = \mathbb{Q}(\zeta_{2^k} + \zeta_{2^k}^{-1})$의 클래스 수 (class number) $h_k^+$가 1 이라는 추측입니다.
• 양자 컴퓨팅과 암호학의 위기: 쇼어 (Shor) 알고리즘은 RSA 및 타원곡선 암호를 무력화시켰으며, 이에 대한 대응으로 격자 기반 암호 (Lattice-based Cryptography) 가 양자 내성 암호 (PQC) 의 주류로 부상했습니다.
• NIST 표준과의 연관성: 2024 년 NIST 가 최종 확정 (또는 확정 예정) 한 ML-KEM, ML-DSA, FN-DSA 등의 표준은 $2^k$-차 원분 다항식 링 $Z[x]/(x^{2^k}+1)$에 기반합니다.
• 현재의 한계:
  • $h_k^+ = 1$은 주 아이디얼 문제 (PIP) 의 난이도, 모듈의 자유성 (freeness), 그리고 Ring-LWE/Module-LWE 의 최악 - 평균 경우 축소 (reduction) 의 엄밀성과 직접적으로 연관됩니다.
  • 기존 연구 ($k \ge 9$) 는 **일반화된 리만 가설 (GRH)**에 의존하여 검증되었습니다. GRH 는 증명되지 않은 가설이므로, 암호학적 안전성에 대한 무조건적 (unconditional) 인 보장이 부족했습니다.
  • GRH 없이 $h_k^+$를 계산하는 것은 민코프스키 경계 (Minkowski bound) 가 차수에 따라 기하급수적으로 증가하기 때문에 계산적으로 불가능했습니다.

2. 주요 기여 및 방법론

저자 Ming-Xing Luo 는 $k \le 12$에 대해 GRH 없이 무조건적으로 $h_k^+ = 1$임을 증명하는 최초의 방법을 제시했습니다. 이 방법은 세 가지 단계를 순차적으로 결합합니다.

단계 1: 소수 제거 (Fukuda-Komatsu Sieve)

• Wieferich 기준 활용: $h_k^+$의 소수 약수 $\ell$이 될 수 있는 후보를 좁힙니다.
• 조건: $k \le 12$인 경우, $10^9$ 미만의 모든 소수는 $h_k^+$를 나눌 수 없음을 계산적으로 확인했습니다.
• 합동 조건: 만약 $h_k^+$를 나누는 소수 $\ell$이 존재한다면, $\ell \equiv \pm 1 \pmod{2^{k-1}}$을 만족해야 함을 증명했습니다. 이는 후보 소수의 범위를 극적으로 축소시킵니다.

단계 2: 고유공간 가지치기 (Norm-coherence Argument)

• Z2-타워 구조 활용: $K_8^+ \subset K_9^+ \subset \dots \subset K_{12}^+$로 이어지는 원분체의 계층 구조 (Z2-확장) 를 이용합니다.
• 귀납적 증명: 이미 알려진 $h_8^+ = 1$ (Miller, 2023) 을 기저 (base case) 로 사용합니다.
• 고유공간 분석: Galois 군 $G_k$의 작용 하에 클래스 군의 $\ell$-비틀림 (torsion) 이 '완전 차수 (full-order)'인 Galois 특징 (character) 에 해당하는 고유공간에만 집중됨을 증명합니다. 즉, 낮은 차수의 특징에 해당하는 고유공간은 모두 소거됩니다. 이는 Herbrand 정리를 적용해야 할 경우의 수를 크게 줄여줍니다.

단계 3: 유한한 경계 설정 (Herbrand's Theorem)

• Herbrand 정리 적용: 남은 '완전 차수' 특징 $\chi$에 대해, 클래스 군의 비자명성 (non-triviality) 이 일반화된 베르누이 수 (Generalized Bernoulli number) $B_{1, \psi}$의 노름 (norm) 을 나누는 것과 동치임을 이용합니다.
• 계산 가능성: 베르누이 수의 노름은 유한한 크기의 정수로 경계가 잡힙니다.
  • $k=10$의 경우, 노름 크기는 약 143 자리 수로 추정됩니다.
  • $k=12$의 경우, 2 차 모멘트 (second-moment) 경계를 적용하면 약 325 자리 수로, ECM(타원곡선 방법) 과 NFS(수체 체) 를 결합하여 소인수분해가 가능한 범위입니다.
• 최종 검증: 생성된 유한한 후보 소수 집합 $S_k$에 대해 단계 1 의 Wieferich 테스트를 수행하여 모든 소수가 $h_k^+$를 나누지 않음을 확인하면, $h_k^+ = 1$이 무조건적으로 증명됩니다.

3. 주요 결과

• 무조건적 증명: $k \in \{9, 10, 11, 12\}$에 대해 $h_k^+ = 1$임을 GRH 없이 증명했습니다.
• 계산 복잡도:
  • 갈루아 궤도 대칭성 (Galois-orbit symmetry) 을 활용하여, $n/4$개의 켤레 쌍 중 하나의 정수만 소인수분해하면 됩니다.
  • $k=10$ (ML-KEM/ML-DSA 에 해당) 의 경우, 최대 143 자리 정수의 소인수분해만 수행하면 되며, 이는 현대 컴퓨팅으로 충분히 가능합니다.
  • $k=12$의 경우에도 타원곡선 방법 (ECM) 과 수체 체 (NFS) 를 조합하여 검증 가능한 수준입니다.

4. 암호학적 의의 및 시사점

이 결과는 양자 내성 암호 표준의 안전성 증명에 다음과 같은 결정적인 영향을 미칩니다.

1. 모듈의 자유성 (Module Freeness):
   • ML-KEM 및 ML-DSA 의 보안 증명은 $OK_k^+$ 위의 유한 생성 비틀림 없는 모듈이 자유 모듈 (free module) 임을 전제로 합니다.
   • $h_k^+ = 1$은 Steinitz 정리에 의해 모든 such 모듈이 자유임을 보장하므로, 보안 증명의 전제가 무조건적으로 성립합니다.
2. Ring-LWE 의 엄밀한 축소 (Tight Reduction):
   • 클래스 수가 1 인 경우, Ring-LWE 문제를 격자 문제 (Ideal-SVP) 로 축소할 때 노이즈 분석이 단순화되고, Ring-LWE 와 Polynomial-LWE (PLWE) 의 동치가 무조건적으로 성립합니다.
   • 이는 현재 사용 중인 모든 파라미터 ($k \le 12$) 에 대해 보안이 엄밀하게 보장됨을 의미합니다.
3. 양자 공격에 대한 견고성:
   • Biasse-Song 등의 양자 알고리즘은 $h_k^+ = 1$인 경우 PIP 를 효율적으로 풀 수 있지만, 이는 Ideal-LWE 기반 시스템에만 해당합니다.
   • NIST 표준인 ML-KEM/ML-DSA 는 Module-LWE를 사용하며, Module-LWE 는 PIP 기반 공격에 대해 저항성이 있는 것으로 알려져 있습니다. 따라서 $h_k^+ = 1$의 증명은 오히려 시스템의 구조적 단순성을 보장하여 보안 증명의 신뢰도를 높입니다.

5. 결론

이 논문은 1886 년 Weber 의 추측을 $k \le 12$까지 무조건적으로 해결함으로써, 현재 및 근미래의 격자 기반 암호 표준 (ML-KEM, ML-DSA 등) 이 수학적 가설 (GRH) 에 의존하지 않고도 안전함을 입증했습니다. Fukuda-Komatsu 체, Z2-타워의 귀납적 구조, 그리고 Herbrand 정리를 결합한 이 방법론은 다른 원분체 장 (cyclotomic fields) 에 대한 클래스 수 추측을 해결하는 데에도 확장 가능한 중요한 방법론을 제시합니다.