Predicting Module-Lattice Reduction

기술 요약: 모듈 격자 축소(Module-Lattice Reduction) 예측

문제 정의
본 논문은 모듈 격자 기반 암호 체계(ML-KEM, ML-DSA, FN-DSA와 같은 NIST 표준)의 암호 해독에 있어 매우 중요한 질문을 다룬다: 동일한 최단 벡터 문제(SVP) 오라클이 주어졌을 때, 모듈형 격자 축소(특히 module-BKZ)가 비구조적 격자 축소(BKZ)보다 더 효율적인가, 아니면 덜 효율적인가?

기초적인 이론적 연구들은 LLL 및 블록 축소 알고리즘의 모듈 변형체의 존재를 확립했지만, 이는 최악의 경우(worst-case)의 점근적 동작에 초점을 맞추었다. Kyber NIST 제출물에서 "Q8"으로 강조된 구체적인 우려 사항은, 원분체(cyclotomic fields) 위의 모듈 격자의 대수적 구조가 속도 향상(예: $d$에서 $d^2$ 배의 인자)을 허용하거나, 반대로 비구조적 BKZ에 비해 축소된 기저의 품질을 저하시킬 수 있다는 점이다. 본 논문은 특정 기저 품질(slope)을 달성하기 위해 요구되는 블록 크기 $\beta$의 관점에서, module-BKZ가 이득(gain)을 주는지 혹은 손실(loss)을 주는지에 대한 답을 제공하기 위해 구체적인 평균 사례(average-case) 분석을 목표로 한다.

방법론
저자들은 module-BKZ를 실행한 후의 기저 프로파일(basis profile)의 '기울기(slope)'를 예측하기 위해, 광범위한 실험에 의해 뒷받침되는 휴리스틱 기반 분석을 채택한다. 여기서 기울기는 그람-슈미트 직교화(Gram-Schmidt orthogonalization)된 벡터들의 로그 노름(logarithmic norms)의 감소율로 정의된다.

1. 실험적 구현: 저자들은 기존 라이브러리인 fplll과 G6K를 활용하여, 원분체(conductor 16까지)에 대한 module-BKZ의 첫 번째 오픈 소스 구현체를 개발하였다. 저자들은 크기 축소(size reduction) 과정 중 모듈 구조를 보존하는 문제와, 트레이스 내적(trace inner product)이 표준 정수 격자 축소 라이브러리와 호환되도록 하는 "순환 임베딩(cyclic embedding)" 사용 문제를 해결하였다.
2. 이론적 모델링 (Module-Lattice GSA): 저자들은 비구조적 BKZ에서 흔히 사용되는 기하급수 가정(Geometric Series Assumption, GSA)을 모듈 격자로 확장한다. 이는 축소된 기저의 기대 $K$-프로파일(수체 $K$의 차수 $d$에 대해 평균화됨)을 모델링하는 과정을 포함한다.
3. 기울기의 분해: module-BKZ의 예측된 기울기는 비구조적 BKZ와의 편차를 유발하는 네 가지 별개의 항($t_1$ ~ $t_4$)으로 분해된다:
   • $t_1$ (가우시안 휴리스틱): 단위근의 개수($\mu_K$)에 의해 조정된, 무작위 모듈 격자 내 최단 벡터의 기대 길이.
   • $t_2$ (판별식 갭): 수체 $K$의 판별식 $\Delta_K$에 의존하는 항.
   • $t_3$ (왜도 갭): 벡터의 대수적 노름과 유클리드 노름 사이의 편차(임베딩에 따른 벡터의 왜도/skewness)를 측정함.
   • $t_4$ (인덱스 갭): 모듈 내 최단 벡터에 의해 생성된 아이디얼(ideal)의 인덱스를 고려함.
4. 점근적 분석: 저자들은 블록 크기 $\beta$를 가진 비구조적 BKZ의 기울기와 일치시키기 위해 module-BKZ가 요구하는 "등가 블록 크기(equivalent blocksize)" $\beta_{eq}$에 대한 점근적 공식을 도출한다.

주요 기여 및 결과

• 기울기의 정량적 예측: 본 논문은 블록 크기 $\beta$, 필드 차수 $d$, 그리고 필드 판별식 $\Delta_K$의 함수로서 module-BKZ의 기울기를 예측하는 구체적인 공식을 제공한다.
• 동력으로서의 판별식: 분석 결과, 판별식 $\Delta_K$가 성능 차이를 결정하는 주요량임을 확인하였다. 구체적으로, 로그 항 $\ln(|\Delta_K|/d^d)$가 module-BKZ가 이득을 얻을지 혹은 손실을 입을지를 결정한다.
• 점근적 블록 크기 이득/손실: 저자들은 다음과 같은 $\beta_{eq}$에 대한 점근적 관계식을 도출하였다:
  $$\beta_{eq} \approx \beta + \ln\left(\frac{|\Delta_K|}{d^d}\right) \frac{\beta}{d \ln \beta} + (d - 1)$$
  • 2의 거듭제곱 꼴 원분체: 컨덕터(conductor)가 2의 거듭제곱인 필드(현재 NIST 표준과 관련됨)의 경우, $|\Delta_K| = d^d$이다. 따라서 로그 항이 사라지며, 비용은 선형 항 $d-1$에 의해 지배된다. 이는 module-BKZ가 동일한 기울기를 달取得하기 위해 약 $d-1$만큼 더 큰 블록 크기를 요구함을 의미한다. 이는 Kyber의 Q8에서 제기된 우려를 확인 및 정량화하며, 속도 향상이 아닌 약간의 성능 저하(penalty)가 발생함을 시사한다.
  • 기타 원분체: 컨덕터에 홀수 소인수가 있는 필드(예: $2^i \cdot 3^j$ 형태의 컨덕터)의 경우, $|\Delta_K| < d^d$이다. 이 경우 로그 항이 음수가 되어, 요구되는 블록 크기에서 아하선형적(sublinear) 이득($\Theta(\beta / \ln \beta)$)을 얻는다. 이는 공격 복잡도 측면에서 아지수(subexponential) 속도 향상으로 이어진다.
• 실험적 검증: 다양한 원분체($\mathbb{Q}(\omega_3), \mathbb{Q}(\omega_4), \mathbb{Q}(\omega_{15}), \mathbb{Q}(\omega_{16})$)에 대한 저자들의 실험 데이터는 예측치와 잘 일치한다. 데이터는 $\mathbb{Q}(\omega_3)$와 $\mathbb{Q}(\omega_{15})$가 비구조적 기준선보다 더 평탄한 프로파일(더 나은 축소)을 보이는 반면, $\mathbb{Q}(\omega_{16})$(2의 거듭제곱)은 더 나쁜 프로파일을 보임을 확인시켜 준다.

의의 및 주장
본 논문은 최악의 경우의 이론적 경계를 넘어, module-BKZ에 대한 구체적인 평균 사례 분석을 제공한 첫 번째 연구라고 주장한다. 그 의의는 다음과 같다:

1. Q8 해결: 2의 거듭제곱 꼴 원분체에 대한 module-BKZ의 효율성에 관한 열린 질문을 직접적으로 해결하였으며, 이러한 특정 필드들에 대해서는 모듈 구조가 비구조적 BKZ보다 속도 향상을 제공하지 않으며, 오히려 작은 오버헤드를 발생시킨다는 결론을 내렸다.
2. 대안적 구성 식별: 작은 홀수 소인수(예: 3, 5)를 가진 컨덕터를 사용하는 모듈 격자 기반 방식이 예상보다 훨씬 취약할 수 있음을 강조한다. 이는 대수적 구조가 격자 축소 공격에 대해 아지수적 속도 향상을 제공하기 때문이다.
3. 실용적 도구 제공: 최초의 module-BKZ 오픈 소스 구현체를 제공함으로써, 저자들은 모듈 격자 기반 방식에 대한 추가적인 실험과 보안 추정을 가능하게 하였다.

저자들은 자신의 분석이 (모듈에 적응된 기하급수 가정을 포함한) 휴리스틱에 의존하고 있으며, "머리와 꼬리(head and tail)" 현상 및 알고리즘의 수렴 속도 모델링에 여전히 간극이 남아 있음을 언급하며 자신의 주장에 대해 신중한 태도를 유지하고 있다. 그들은 자신들의 결과가 아직 특정 공격에 대한 정확한 비용을 제공하는 것이 아니라, 축소된 기저의 기울기에 대한 예측 프레임워크를 제공하는 것임을 명시적으로 밝히고 있다.