Module Lattice Security (Part II): Module Lattice Reduction via Optimal Sign Selection

이 논문은 Part I에서 확립된 조건을 바탕으로 CDPR 격자 축소 알고리즘을 아이디얼 격자에서 모듈 격자로 확장하여, MLWE 분포 기반의 모듈 격자에 대해 효율적인 정밀도 제어와 최적의 부호 선택(sign selection)을 통해 최적의 Hermite 인자를 달성하는 방법을 제시합니다.

핵심

1. 배경: 암호라는 이름의 "복잡한 미로"

오늘날 우리가 사용하는 암호(ML-KEM 등)는 아주 복잡한 '격자 미로' 속에 보물을 숨겨두는 것과 같습니다. 이 미로는 규칙적인 점들이 찍혀 있는 거대한 그물망 같은 구조인데, 그 점들 사이에서 **"가장 짧은 거리의 점(보물)"**을 찾는 것은 슈퍼컴퓨터나 양자 컴퓨터로도 엄청나게 어려운 일입니다. 암호의 보안은 바로 이 "찾기 너무 어렵다"는 점에 기반하고 있습니다.

2. 이 논문의 핵심 아이디어: "미로를 조각내어 공략하기"

기존에는 이 미로 전체를 한꺼번에 해결하려고 했습니다. 하지만 이 논문의 저자(Ming-Xing Luo)는 미로가 가진 특수한 수학적 성질(모듈 격자)을 이용해 **"거대한 미로를 여러 개의 작은 미로 조각으로 쪼개서 공략하는 방법"**을 제안했습니다.

① 미로 조각내기 (Module Reduction)

거대한 미로를 통째로 뒤지는 대신, 미로를 $d$개의 작은 통로(Rank-1 submodules)로 나눕니다. 각 통로는 원래 미로보다 훨씬 단순합니다. 저자는 이 작은 통로들에서 각각 보물을 찾은 뒤, 그중 가장 짧은 것을 고르면 전체 미로에서도 아주 짧은 길을 찾을 수 있다는 것을 수학적으로 증명했습니다.

• 비유: 거대한 성 전체를 뒤지는 대신, 성을 여러 개의 복도로 나누어 각 복도에서 가장 짧은 경로를 찾은 뒤 그중 최고를 고르는 전략입니다.

② 정밀한 나침반 만들기 (CRT-scaled Rounding)

미로를 탐색할 때는 위치를 계산해야 하는데, 계산이 너무 복잡하면 오차가 생겨 길을 잃을 수 있습니다. 저자는 **'CRT(중국인의 나머지 정리)'**라는 수학적 도구를 사용하여, 계산 오차를 아주 작게 유지하면서도 컴퓨터가 아주 빠르게 계산할 수 있는 "정밀한 디지털 나침반"을 만들었습니다.

• 비유: 안개 낀 미로에서 눈대중으로 걷는 대신, 아주 정밀하고 빠른 GPS를 사용하여 오차 없이 길을 찾는 것과 같습니다.

③ 최적의 방향 결정하기 (MILP Sign Selection)

미로를 탐색하다 보면 "왼쪽으로 갈까, 오른쪽으로 갈까?" 하는 선택의 순간이 옵니다. 기존 방식은 "대충 이 정도면 되겠지" 하고 결정했다면, 이 논문은 **'MILP(혼합 정수 선형 계획법)'**라는 고도의 최적화 기법을 도입했습니다. 이를 통해 수많은 선택지 중 가장 오차가 적은 완벽한 방향을 찾아냅니다.

• 비유: 갈림길에서 대충 감으로 가는 게 아니라, 수학적으로 계산된 '가장 완벽한 각도'로 발을 내디뎌 오차를 최소화하는 것입니다.

---

3. 그래서 결론이 무엇인가요? (보안에 미치는 영향)

이 논문은 기존의 공격 방식보다 훨씬 더 정교하고 효율적인 공격 방법을 제시했습니다.

• 공격자 입장: "이제 미로를 훨씬 더 빠르고 정확하게 탐색할 수 있는 도구(조각내기 + 정밀 나침반 + 최적의 방향)를 갖게 되었다!"
• 방어자(암호 설계자) 입장: "공격 기술이 발전했으니, 미로를 더 복잡하게 설계해야겠구나. 하지만 이 논문의 공격 방식도 여전히 '지수적인 시간'이 걸리기 때문에, 현재의 암호 체계가 당장 무너지는 것은 아니다. 다만, 더 강력한 방패를 준비해야 한다."

요약하자면:

이 논문은 **"복잡한 수학적 미로(모듈 격자)를 효율적으로 깨뜨리기 위해, 미로를 조각내고, 정밀한 계산 도구를 사용하며, 최적의 경로 선택 알고리즘을 적용하는 법"**을 다룬 연구입니다. 이는 미래의 양자 컴퓨터 시대에 우리가 사용할 암호가 얼마나 안전한지 검증하는 아주 중요한 잣대가 됩니다.

기술 요약

[기술 요약] 최적 부호 선택을 통한 모듈 격자 축소 (Module Lattice Reduction via Optimal Sign Selection)

1. 연구 배경 및 문제 정의 (Problem Statement)

본 논문은 양자 내성 암호(PQC)의 핵심 표준인 ML-KEM(FIPS 203) 등의 기반이 되는 MLWE(Module Learning With Errors) 문제의 안전성을 분석합니다.

• 핵심 문제: 기존의 CDPR 알고리즘은 '이상 격자(Ideal Lattice, rank $d=1$)'에서는 지수적 개선($\exp(\tilde{O}(\sqrt{n}))$)을 이루었으나, 이를 '모듈 격자(Module Lattice, $d \ge 2$)'로 확장하는 것은 구조적 복잡성 때문에 미해결 과제로 남아 있었습니다.
• 부호 선택 문제(Sign-selection Problem): CDPR 파이프라인의 핵심 단계로, 로그 임베딩 기하학에서 오차 벡터의 $L_\infty$ 불일치(discrepancy)를 최소화하기 위해 궤도(orbit) 요소들에 최적의 부호($\pm 1$)를 할당하는 문제입니다. 기존의 'Tower Greedy' 방식은 불일치가 $\Theta(\sqrt{nk})$로 증가하는 한계가 있었습니다.

2. 연구 방법론 (Methodology)

저자는 모듈 격자를 효율적으로 축소하기 위해 다음과 같은 세 가지 주요 접근법을 제안합니다.

① 대각 CDPR을 이용한 모듈 축소 (Diagonal CDPR)

모듈 격자를 $d$개의 rank-1 부분 모듈(submodules)로 분해합니다.

• Trace Orthogonality(자취 직교성): $2^k$차 사이클로토믹 환(cyclotomic ring)의 거듭제곱 기저(power basis)가 갖는 직교성을 활용하여, 모듈을 $d$개의 독립적인 rank-1 부분 모듈로 분해합니다.
• Gram-Schmidt 직교화: $K$-선형 Gram-Schmidt 과정을 통해 기저를 직교화하고, 각 부분 모듈에 CDPR을 독립적으로 적용한 후 가장 짧은 벡터를 선택합니다.

② CRT 스케일링 반올림 (CRT-scaled Rounding)

계산 정밀도 문제를 해결하기 위해 도입되었습니다.

• Totally Split Primes 활용: NTT(Number Theoretic Transform) 기반 연산이 가능한 '완전 분할 소수(totally split primes)'에서 CRT(중국인의 나머지 정리)를 사용하여 반올림을 수행합니다.
• 이를 통해 반올림 오차 $\rho$를 $n/2$에서 $1$ 이하로 줄여, 유한 정밀도 환경에서도 안정적인 구현이 가능하게 합니다.

③ MILP를 이용한 부호 최적화 (MILP Sign Optimization)

부호 선택 문제를 **혼합 정수 선형 계획법(Mixed-Integer Linear Program, MILP)**으로 재정의했습니다.

• 부호 할당 문제를 이진 변수($x \in \{0, 1\}$)를 사용하는 최적화 문제로 변환하여, 기존의 휴리스틱 방식보다 훨씬 정밀한 부호를 결정합니다.

3. 주요 기여 및 결과 (Key Contributions & Results)

① 모듈 축소 성능 증명 (Theorem 5.1)

• 결과: 입력 기저가 'Balance Hypothesis(균형 가설)'를 만족할 경우(MLWE 분포에서는 자동으로 만족됨), 모듈 축소 인자(reduction factor) $\alpha_d = O(1)$를 달성합니다.
• 의미: 이는 랭크 $d$에 독립적이며, 이상 격자에서의 CDPR과 동일한 $\exp(\tilde{O}(\sqrt{n}))$의 Hermite factor를 유지함을 의미합니다.

② 최적 불일치 상수 발견 (Theorem 7.1)

• 결과: MILP를 통해 계산한 결과, 최적의 균형 불일치(balanced discrepancy) $\delta^*$는 궤도 크기와 무관하게 $\approx 0.4407$이라는 보편적 상수임을 밝혀냈습니다.
• 의미: 기존 Tower Greedy 방식의 $\Theta(\sqrt{nk})$ 오차를 상수 수준으로 낮추어, CDPR의 근사 인자를 $\sqrt{nk}$ 배만큼 정밀하게 개선했습니다.

③ 구현 효율성 및 복잡도

• 결과: CRT 스케일링을 통해 Phase-1의 계산 복잡도를 $O(d^2 rn \log n)$ 비트 연산으로 제어했습니다.
• 의미: 실질적인 ML-KEM 파라미터에서 매우 효율적인 구현이 가능함을 입증했습니다.

4. 보안적 함의 (Significance & Security Implications)

본 논문은 ML-KEM의 보안성을 직접적으로 파괴하는 것이 아니라, 공격의 정밀도를 높임으로써 보안 마진을 재측정하는 데 의의가 있습니다.

• ML-KEM 안전성 확인: 공격을 통해 얻은 근사 인자가 $\exp(\tilde{O}(\sqrt{n}))$ 수준임에도 불구하고, ML-KEM-768을 깨기 위해 필요한 근사 인자($\gamma \approx 2^{11.7}$)와 비교했을 때 여전히 거대한 보안 격차(Security Gap $\approx 2^{11}$)가 존재함을 수학적으로 증명했습니다.
• 결론: 제안된 공격은 기존의 일반적인 격자 축소 알고리즘(BKZ 등)보다 강력하지만, 현재의 ML-KEM 표준을 위협하기에는 여전히 지수적인 장벽이 존재함을 확인시켜 줍니다.

---

요약 키워드: Module Lattices, CDPR Attack, MLWE, MILP, Cyclotomic Rings, CRT-scaled Rounding, Discrepancy Theory.