기술 요약: 중심 산술(Centered Arithmetic)은 누설 중립적이지 않다

문제 정의

ML-KEM, ML-DSA와 같은 격자 기반 암호의 소프트웨어 구현에서, 민감한 값들은 비밀값이 $q$에 대한 모듈로 합이 되도록 무작위 공유값(shares)으로 분할되는 산술 마스킹을 통해 보호된다. 비록 이러한 연산은 수학적으로는 모듈러 연산이지만, 이 공유값들을 물리적으로 저장하기 위해서는 머신 워드 내에서의 표현 방식 선택이 필요하다. 일반적으로 공유값은 $[0, q)$ 범위의 부호 없는 잔여값(unsigned residues) 또는 2의 보수 형태인 $[-\lfloor q/2 \rfloor, \lceil q/2 \rceil - 1]$ 범위의 **중심 정수(centered signed integers)**로 저장된다.

두 인코딩 모두 동일한 모듈러 산술을 구현하지만, 이진 표현 방식에서는 상당한 차이를 보인다. 구체적으로, 2의 보수 형태의 음수는 부호 확장(sign extension, leading ones)을 나타내는 반면, 부호 없는 대응값은 그렇지 않다. 기존 연구들은 이러한 "부호 확장" 효과를 측면 채널 공격(예: 절대값 예측기)에 활용해 왔다. 그러나 유한한 노이즈 하에서, 모든 차수의 마스킹과 임의의 모듈리스에 대해 이 표현 방식의 선택이 누설에 어떻게 영향을 미치는지 규명하는 포괄적인 이론적 프레임워크는 부족했다. 본 논문은 근본적인 질문을 다룬다: 중심 산술은 부호 없는 저장 방식과 비교하여 누설 중립적인가?

방법론

본 논문은 측면 채널 누설 채널을 모델링하기 위해 확률론, 푸리에 분석, 조합론적 수론을 결합한 엄격한 수학적 접근 방식을 채택한다.

1. 유한 노이즈 채널 모델링: 저자는 마스킹된 공유값의 누설을 독립적인 가법 노이즈 채널로 모델링한다. 저자는 개별 공유값의 누설 분포를 **순환 합성곱(cyclic convolution)**으로 취급하여 마스킹된 합의 정확한 가능도(likelihood)를 도출한다.
2. 푸리에 분석: 분석에는 합성곱을 주파수 영역에서의 곱으로 변환하는 이산 푸리에 변환(DFT)이 사용된다. 이를 통해 최적의 공격법과 누설의 스펙트럼 분해를 도출할 수 있다.
3. 표현 최소 극대화(Representation Minimax): 본 연구는 누설 스펙트럼의 에너지를 최소화함으로써 $\mathbb{Z}_q$의 다양한 "섹션(representations)"을 평가한다. 이는 연속적인 섹션(부호 없는 방식 vs 중심 방식)과 임의의 단사 이진 코드북을 비교하는 과정을 포함한다.
4. 스펙트럼 분해: 본 논문의 주요 방법론적 혁신은 중심 2의 보수 누설 스펙트럼을 **부호 확장 항(sign-extension terms)**과 **캐리 항(carry terms)**으로 분해하여 정밀한 점근적 분석을 가능하게 하는 것이다.
5. 알고리즘 검증: 이론적 경계는 정확한 계산, 전체 크기의 ML-KEM 및 ML-DSA 파라미터를 사용한 합성 실험, 그리고 공개된 물리적 트레이스 분석을 통해 검증된다.

핵심 기여

1. 최적의 유한 노이즈 추론

본 논문은 FFT를 통해 계산되는 순환 합성곱을 사용하여 마스킹된 합의 완전한 가능도를 준선형 시간 $O(dq \log q)$ 내에 계산할 수 있음을 입증한다.

• 결과: 이는 모든 $q$개의 가설을 동시에 평가하는 최적의 공격 전략을 제공한다.
• 충분 조건: 저자는 흔히 사용되는 곱 통계량(product statistic)(중심 공유값을 곱하는 방식)이 모든 가능도 정보를 유지하는 정확한 조건을 도출한다. 저자는 노이즈가 유한할 때, $q \ge 2$ 및 차수 $d \ge 2$인 모든 모듈리스에 대해 곱 통계량이 엄격하게 불충분함을 증명한다. 전체 관측값은 곱 통계량보다 더 많은 정보(더 높은 KL 발산, Rényi 발산 등)를 포함한다.

2. 전역 표현 최소 극대화 법칙

본 논문은 누설을 최소화하기 위해 표현 방식을 최적화한다:

• 1차 누설: 모든 연속적인 섹션 중에서, 부호 없는 저장 방식($[0, q)$)은 모듈리스가 머신 워드 전체를 차지하는 경우($q=2^m$)를 제외하면 1차 누설의 유일한 최소화 모델이다.
• 고차 누설: 부호 없는 저장 방식의 최적성은 영구적이지 않다. 본 논문은 특정 파라미터(예: $q=14, \beta=4$)에서 중심 저장 방식이 차수 $d \ge 4$에 대해 유일한 최소화 모델이 되는 정확한 "상전이(phase change)"를 식별한다. 즉, 낮은 차수에서는 부호 없는 방식이 최적이지만 높은 차수에서는 중심 방식이 최적이다.
• 사전식 법칙(Lexicographic Law): 임의의 유한한 표현 방식 군에 대해, $d \to \infty$로 갈수록 결정되는 최종 최소화 모델은 누설 계수의 사전식으로 정렬된 가장 작은 스펙트럼에 의해 결정된다.
• 일정 가중치 코드북: 임의의 이진 인코딩에 대해, 누설은 코드북이 **일정 해밍 가중치(constant Hamming weight)**를 가질 때만 정확히 사라진다. 본 논문은 이러한 코드북이 존재하기 위한 날카로운 용량 경계($q \le \binom{\beta}{\lfloor \beta/2 \rfloor}$)를 제공하며, 표준 NIST 모듈리스(예: $q=3329$에 대해 $\beta=14$)에 필요한 최소 워드 폭을 계산한다.

3. 중심 감소 누설 법칙 (The Centered-Reduction Leakage Law)

본 논문의 핵심 이론적 결과는 중심 2의 보수 누설의 정확한 스펙트럼 분해이다:

• 분해: 누설 스펙트럼은 거시적인 부호 확장 항과 이진 **캐리 결함(carry defect)**으로 나뉜다.
• 지배 임계값: 본 논문은 날카로운 균일 임계값을 증명한다: 중심 저장 방식이 제1 푸리에 모드에서 부호 없는 저장 방식보다 엄격하게 큰 누설 크기를 나타내려면 세 개의 여분의 비트($s = \beta - \lceil \log_2 q \rceil \ge 3$)가 필요하다. 구체적으로, 조건 $D(q, \beta) > 2U(q)$는 $s \ge 3$인 경우에만 성립한다.
• 점근적 특성: 고정된 여분 폭에 대해, 중심 대 부호 없는 누설 계수의 비율은 $s+1$로 수렴한다. $q=2^m-1$인 특수 사례의 경우, 누설 비율은 탄젠트 합과 관련된 상수($\kappa \approx 1.81$)로 수렴한다.
• 중립성: 중심 산술은 누설 중립적이지 않다. 이는 오직 $q=2^m$이고 $\beta=m$인 정확한 경우에만 중립적(부호 없는 방식과 누설이 동등)이다. 그 외의 모든 경우, 중심 저장 방식은 제1 푸리에 모드에서 (그리고 일반적으로 낮은 마스킹 차수에서) 더 높은 누설을 초래하지만, 특정 파라터 세트에서는 높은 차수에서 최적의 표현 방식이 될 수도 있다.

4. 강건성 및 샘플 복잡도

• 강건성 반경: 가중 해밍 가중치 모델에 대한 정확한 강건성 반경을 정의하여, 여분 비트가 3 이상인 경우 부호 없는 저장 방식과 중심 저장 방식 사이의 엄격한 구분이 비트 민감도 변화에도 유지됨을 보여준다.
• 샘플 복잡도: 지수적 신뢰도를 가진 조화 테스트(harmonic test)를 제안한다. 본 논문은 중심 방식과 부호 없는 방식 공격 간의 샘플 복잡도 비율이 두 방식의 스펙트럼 계수 비율의 $2d$ 제곱에 따라 스케일링됨을 증명한다. 이는 높은 마스킹 차수에서, 중심 저장 방식이 갖는 페널티(제1 모드에서의 높은 누설로 인한)가 지수적으로 증가함을 의미한다. 단, 특정 파라미터 세트가 중심 저장 방식이 글로벌 최소화 모델이 되는 영역에 있는 경우는 예외이다.

결과 및 검증

• 합성 실험: 전체 크기의 ML-KEM($q=3329$) 및 ML-DSA($q=8,380,417$) 구현을 위한 실험은 이론적 샘플 복잡도 요인을 확인시켜 준다. $d=3, 4, 6$에 대해, 중심 표현 방식은 부호 없는 저장 방식과 동일한 성공률을 달리는 데 훨씬 더 많은 트레이스가 필요하며, 이는 도출된 점근적 한계와 일치한다.
• 물리적 트레이스: 분석은 마스킹된 ML-DSA 구현의 공개 물리적 트레이스를 통해 검증되었다. 부호 판별(sign predicate)은 Welch $|t|$ 값 155.73과 90.80%의 균형 정확도를 달성하였으며, 이는 이론이 예측한 부호 확장 누설 채널의 존재를 확인시켜 준다.
• 알고리즘 효율성: FFT 기반 합성법을 사용하는 제안된 최적 공격은 $q=8,380,417$에 대해 35초 이내에 모든 가설의 점수를 매기는 데 성공하여 실질적인 실행 가능성을 입증했다.

의의

본 논문은 소프트웨어에서의 산술 마스킹에 대한 이해를 근본적으로 변화시킨다. 이는 머신 표현 방식(중심 방식 vs 부호 없는 방식)의 선택이 단순한 구현 세부 사항이 아니라, 측면 채널 누설의 핵심 구성 요소임을 보여준다.

• 중립성 반박: 저자는 "중심 산술은 누설 중립적이지 않다"는 것을 결론적으로 보여준다. 2의 보수 표현에 내재된 부호 확장은 마스킹만으로는 완화되지 않는 독특한 누설 스펙트럼을 도입한다.
• 설계 가이드라인: 본 연구는 구현자들에게 정확하고 실행 가능한 가이드라인을 제공한다:
  • 1차 보안과 여분 비트가 적은 경우($s < 3$)에는 부호 없는 저장 방식을 사용하라. 이는 1차 누설을 유일하게 최소화한다.
  • 중심 저장 방식은 일반적으로 제1 모드에서의 높은 누설로 인해 샘플 복잡도 측면에서 심각한 페널티를 부여한다는 점을 인지하라. 이는 특정 파라미터 세트에서 최적의 표현 방식이 되는 상전이를 보일 때만 해당된다.
  • 일정 가중치 코드북은 이론적으로 제로 누설로 가는 경로를 제공하지만, 표준 하드웨어 제약과 일치하지 않을 수 있는 특정 워드 폭을 요구한다.
• 이론적 토대: 정확한 스펙트럼 법칙과 유한 노이즈 최적 조건을 제공함으로써, 본 논문은 이론적 마스킹 보안과 실제 구현 현실 사이의 간극을 메우며, 측면 채널 저항성이 있는 격자 암호 시스템을 평가하고 설계하기 위한 엄격한 기초를 제공한다.