Explicit cost analysis of Toom-4 multiplication for incomplete NTT in lattice-based cryptography

기술 요약: 격자 기반 암호학에서 불완전 NTT 를 위한 Toom-4 곱셈의 명시적 비용 분석

문제 제기
다항식 곱셈은 Kyber(ML-KEM) 및 Dilithium(ML-DSA) 과 같은 격자 기반 암호 체계에서 기본적인 연산이며, 일반적으로 잉여 환 $R_q = \mathbb{F}_q[x]/\langle x^n + 1 \rangle$ 위에서 수행됩니다. 수론적 변환 (NTT) 은 $O(n \log n)$의 곱셈 속도를 제공하지만, 엄격하게 $2n \mid (q-1)$ 조건을 요구합니다. 이 제약 조건은 매개변수 선택을 제한하고 보안 또는 효율성 목표를 훼손할 수 있습니다.

이를 해결하기 위해 Hafiz 등 (2025) 은 불완전 NTT 를 도입했는데, 이는 깊이가 $\ell$인 (여기서 $2^{\ell+1} \mid (q-1)$) 잘라낸 NTT 를 수행하고 나머지 부분 문제에 대해 전통적인 다항식 곱셈을 결합함으로써 모듈러스 제약을 완화합니다. Karatsuba 곱셈은 이 프레임워크 내에서 잘 이해되고 있지만, Toom-4 곱셈의 정확한 비용, 특히 덧셈과 곱셈에 관한 상수 인자는 불완전 NTT 비용 모델과 호환되는 형태로 표현된 바가 없습니다. Toom-Cook 에 대한 기존 분석 (예: Bodrato 와 Zanoni) 은 일반적인 최적화에 초점을 맞추고 있지만, 불완전 NTT 에 필요한 특정 하이브리드 프레임워크에 직접 통합되지는 않았습니다.

방법론
저자들은 불완전 NTT 프레임워크에 맞춘 Toom-4 곱셈의 구체적인 구현을 제시하고 명시적인 연산 횟수 모델을 유도합니다.

1. 구현 전략: 저자들은 분수 상수를 피하기 위해 정수 평가점 $\{0, \pm 1, \pm 2, 3, \infty\}$을 채택합니다. 모든 나눗셈은 최종 스케일링 단계로 미루어집니다.
2. 덧셈 체 최적화: 방법론의 핵심 구성 요소는 보간 단계에서 필요한 스칼라 배수를 계산하기 위해 덧셈 체를 사용하는 것입니다. 개별 스칼라 곱셈을 수행하는 대신, 저자들은 역 Vandermonde 행렬에서 요구되는 목표 계수에 대한 최소 덧셈 체를 구성합니다. 이를 통해 필요한 덧셈과 뺄셈의 정확한 횟수를 체계적으로 결정할 수 있습니다.
3. 비용 유도: 저자들은 계수 필드 $\mathbb{F}_q$ 위의 덧셈/뺄셈 ($A$) 과 곱셈 ($M$) 의 연산 횟수를 분리합니다. Toom-4 단계 (분할, 평가, 재귀적 곱셈, 보간, 재구성) 에 대한 재귀 공식을 유도하고, 이를 Hafiz 등이 확립한 불완전 NTT 의 가중 비용 모델에 통합합니다.
4. 하이브리드 분석: 이 연구는 Toom-4, Karatsuba, 불완전 NTT 를 결합한 하이브리드 전략을 분석합니다. 덧셈 대 곱셈의 상대 비용인 $w$를 사용하여 가중 비용 함수 $C_w(n; \ell, L)$을 최소화함으로써, 저자들은 다양한 부분 문제 크기에 대한 최적의 재귀 깊이 $L$을 결정합니다.

주요 기여

• 명시적 Toom-4 비용 모델: 이 논문은 불완전 NTT 프레임워크와 호환되는 최초의 명시적 Toom-4 비용 모델을 제공합니다. 최적화된 덧셈 체에서 유도된 상수 인자를 포함하여 덧셈과 곱셈의 정확한 횟수를 상세히 설명합니다.
• 덧셈 체 검증: 저자들은 보간 스칼라에 사용된 덧셈 체의 최적성을 확인하는 검증 스크립트 (저자의 저장소에서 제공됨) 를 제공하여, 선택된 평가점에 대해 유도된 횟수가 최소임을 보장합니다.
• 하이브리드 전략 최적화: 이 연구는 불완전 NTT 맥락에서 순수 Karatsuba 나 순수 Toom-4 보다 Toom-4/Karatsuba 하이브리드가 더 우수한 성능을 발휘하는 특정 매개변수 범위를 식별합니다.
• 실험적 검증: 저자들은 제안된 하이브리드 방법을 Python 으로 구현하고, 2-진 valuation 이 제한된 (Dilithium 의 모듈러스와 크기는 비슷하지만 2-진 valuation 이 제한된) NTT-비우호적 소수 모듈러스를 사용하여 실험적 실행 시간과 이론적 예측을 검증했습니다.

결과
분석에 따르면, 이 맥락에서 Toom-4 의 효과는 허용 가능한 NTT 깊이 ($\ell$) 와 결과적인 부분 문제 크기 ($d = n/2^\ell$) 에 크게 의존합니다.

• 제한된 깊이 영역: 허용 가능한 NTT 깊이가 작을 때 (예: $\ell=0$ 또는 $\ell=1$), 부분 문제가 충분히 커서 Toom-4 는 상당한 이점을 제공합니다. 예를 들어, $n=256$이고 $\ell=0$인 경우, 하이브리드 방법은 순수 Karatsuba 대비 가중 비용을 약 5% 감소시켰으며, 순수 Toom-4 보다 훨씬 우수한 성능을 보였습니다.
• 최적 재귀: 최적의 재귀 깊이 $L$은 $d$에 따라 변합니다. $d \le 128$인 경우 최적 전략은 $L=0$(순수 Karatsuba) 입니다. $d=256$인 경우 $L=1$이 최적이며, $d \ge 512$인 경우 $L=2$가 최적입니다.
• 실험적 확인: 2-진 valuation 이 제한된 소수에 대한 실험은 이론적 모델을 확인했습니다. 최대 허용 깊이가 최소일 때 ($\ell_{max}=0$), 하이브리드 방법은 Karatsuba 를 크게 능가했습니다 (예: $n=256$인 경우 14.182 ms 대 16.722 ms). 허용 가능한 깊이가 증가함에 따라 하이브리드 방법의 성능 우위는 감소하여, 부분 문제가 너무 작아지면 결국 Karatsuba 와 수렴했습니다.

의의 및 주장
저자들은 겸손하게도 그들의 주요 기여가 새로운 곱셈 알고리즘이 아니라 불완전 NTT 프레임워크에 맞춘 Toom-4 의 정밀한 상수 수준 분석이라고 주장합니다. 그들은 이 명시적 비용 모델이 문헌의 간극을 메워, 완전한 NTT 를 사용할 수 없는 상황에서 하이브리드 전략을 체계적으로 평가할 수 있게 한다고 주장합니다.

이 논문은 Toom-4 가 불완전 NTT 의 "제한된 깊이 영역", 특히 $q-1$의 2-진 valuation 이 변환 깊이를 제한하는 경우에 가장 유리하다고 결론지었습니다. 이러한 경우 제안된 하이브리드 전략은 표준 Karatsuba 기반 접근법보다 측정 가능한 성능 개선을 제공합니다. 저자들은 현재 구현이 Python 으로 되어 있으며, 향후 작업은 저수준 구현 (예: C/C++) 최적화와 구체적인 격자 기반 체계에서의 추가 평가를 포함한다고 언급했습니다.