1.6.1 합성곱을 직접 계산하면 왜 느린가

차수 $\(N\)$ 미만인 두 다항식 $\(a,b\)$ 에는 각각 $\(N\)$ 개의 계수가 있다. 직접 곱셈에서는 각 $\(a_i\)$ 와 각 $\(b_j\)$ 를 곱한다. 총 $\(N^2\)$ 개의 계수 곱이 필요하므로 기본 연산 횟수는 $\(O(N^2)\)$ 다.

$\(N\)$ 이 수천 또는 수만이면 이러한 곱셈을 암호문 연산마다 반복하는 것은 큰 부담이다. 그러나 다항식을 적절한 점들에서 평가하면 곱셈을 좌표별 곱으로 바꿀 수 있다.

계산의 큰 흐름은 다음과 같다.

계수 배열을 평가값 배열로 변환한다.
같은 평가점에 대응하는 값끼리 곱한다.
평가값 배열을 다시 계수 배열로 변환한다.

변환을 직접 수행하면 역시 $\(O(N^2)\)$ 이므로 아직 이득이 없다. FFT나 NTT를 사용하여 변환 자체를 $O(N\log N)$ 에 수행할 때 전체 곱셈이 빨라진다.

여기서 큰 $\(O\)$ 표기는 입력 크기가 커질 때 연산량이 대략 어떤 함수로 증가하는지를 나타낸다. 계수 연산 하나를 일정 비용으로 세는 모델이다. 매우 큰 정수나 여러 RNS 소수를 사용하는 실제 비용은 계수 비트 수와 소수 개수까지 함께 고려해야 한다.

1.6.2 선형, cyclic, negacyclic convolution을 구별하기

길이 $\(N\)$ 의 두 계수 배열을 보통 다항식으로 곱하면 결과 길이는 최대 $\(2N-1\)$ 이다. 이를 선형 합성곱이라고 부른다.

결과를 $\(x^N-1\)$ 로 줄이면 높은 차수 항을 같은 부호로 접으므로 cyclic convolution이다.

c_k^{\mathrm{cyclic}} = \sum_{i+j\equiv k\ (\mathrm{mod}\ N)}a_ib_j.

$\(x^N+1\)$ 로 줄이면 한 번 넘어간 항의 부호가 바뀌므로 negacyclic convolution이다.

c_k^{\mathrm{nega}} = \sum_{i+j=k}a_ib_j - \sum_{i+j=k+N}a_ib_j.

길이 $\(N\)$ 의 보통 DFT를 하고 좌표별로 곱한 뒤 역변환하면 cyclic convolution이 나온다. 그 결과를 그대로 CKKS의 $\(x^N+1\)$ 곱으로 사용하면 틀린 계산이다. negacyclic 곱에는 적절한 twist를 사용하거나 $\(x^N+1\)$ 의 근에서 직접 평가하는 변환이 필요하다.

선형 합성곱을 DFT로 계산할 때는 길이를 $\(2N-1\)$ 이상으로 늘리고 나머지를 0으로 채우면 감김을 피할 수 있다. 이 방법과 $\(x^N+1\)$ 몫환의 negacyclic 계산은 목적이 다르다.

1.6.3 DFT: 복소 단위근에서 평가하기

길이 $\(N\)$ 의 배열 $a_0,\ldots,a_{N-1}$ 과 복소수 원시 $\(N\)$ 차 단위근 $\omega$ 를 생각하자.

\omega=e^{2\pi i/N}.

이 문서의 discrete Fourier transform(DFT)은 다음 양의 지수 관례를 사용한다.

A_k = \sum_{j=0}^{N-1}a_j\omega^{kj}, \qquad 0\le k<N.

이는 다항식 $\(a(x)\)$ 를 $1,\omega,\ldots,\omega^{N-1}$ 에서 평가한 결과다. 문헌이나 라이브러리에서는 정방향에 음의 지수를 쓰는 경우도 많다. 정방향과 역방향의 부호를 일관되게 정하면 수학적 내용은 같다.

역변환은 다음과 같다.

a_j = \frac1N \sum_{k=0}^{N-1}A_k\omega^{-kj}.

그 근거는 단위근의 직교성이다.

\sum_{k=0}^{N-1}\omega^{k\ell} = \begin{cases} N,&N\mid\ell,\\ 0,&N\nmid\ell. \end{cases}

$\omega^\ell\ne1$ 인 경우 이 합은 등비수열이고, $(1-\omega^{N\ell})/(1-\omega^\ell)=0$ 이다. 역변환 식에 정방향 정의를 대입하면 다른 계수들의 항은 모두 0이 되고 목표 계수만 $\(N\)$ 배 남는다.

$\(N=4\)$ 에서 $\omega=i$ 이고 계수가 $\((1,2,3,4)\)$ 이면 다음을 얻는다.

\begin{aligned} A_0&=1+2+3+4=10,\\ A_1&=1+2i-3-4i=-2-2i,\\ A_2&=1-2+3-4=-2,\\ A_3&=1-2i-3+4i=-2+2i. \end{aligned}

네 개의 평가값을 역변환하면 원래 네 계수를 복원한다.

1.6.4 FFT: 짝수와 홀수 항으로 나누는 알고리즘

DFT는 변환의 정의이고, fast Fourier transform(FFT)은 그 변환을 빠르게 계산하는 알고리즘들의 이름이다. 가장 익숙한 radix-2 방식은 $\(N\)$ 이 2의 거듭제곱일 때 짝수 번호와 홀수 번호 계수를 분리한다.

a(x)=a_{\mathrm{even}}(x^2)+x\,a_{\mathrm{odd}}(x^2).

그러면 크기 $\(N\)$ 의 평가를 크기 $\(N/2\)$ 의 두 평가로 바꿀 수 있다. $\(E_k,O_k\)$ 를 각각 짝수 계수와 홀수 계수의 길이 $\(N/2\)$ DFT라고 하면 다음이 성립한다.

A_k=E_k+\omega^kO_k,

A_{k+N/2}=E_k-\omega^kO_k, \qquad 0\le k<N/2.

두 결과가 하나의 곱셈 $\omega^kO_k$ 를 공유하고, 덧셈과 뺄셈으로 만들어진다. 이러한 두 출력 계산 단위를 butterfly라고 부른다.

각 단계에서 문제 크기를 절반으로 줄이고, 한 단계에 전체적으로 $\(O(N)\)$ 의 일을 하므로 단계 수는 $\log_2N$ 이고 총 비용은 $O(N\log N)$ 다.

T(N)=2T(N/2)+O(N)=O(N\log N).

실제 구현에는 입력이나 출력을 bit-reversed 순서로 다루는 방식, decimation-in-time 또는 decimation-in-frequency 방식, 반복문 기반 in-place 계산 등 여러 변형이 있다. 이 차이는 결과 좌표를 어떤 순서로 저장하고 중간 계산을 어떻게 배열하는가의 문제이며, 변환이 표현하는 수학은 같다.

복소 FFT는 실수·복소수 데이터 처리에 널리 사용되지만, 컴퓨터가 유한 정밀도의 부동소수점으로 계산하면 반올림 오차가 생긴다. 정수 합성곱을 복소 FFT로 계산한 뒤 가장 가까운 정수로 반올림할 수도 있으나, 크기와 정밀도 조건을 확인해야 한다.

1.6.5 NTT: 복소수 대신 유한체의 단위근을 사용하기

Number Theoretic Transform(NTT)은 Fourier 변환과 같은 구조를 유한체에서 수행한다. 복소수 $\omega$ 대신 법 $\(q\)$ 의 원시 $\(N\)$ 차 단위근 $\omega\in\mathbb F_q$ 를 사용한다.

A_k = \sum_{j=0}^{N-1}a_j\omega^{kj}\pmod q.

역변환은 다음과 같다.

a_j = N^{-1} \sum_{k=0}^{N-1}A_k\omega^{-kj}\pmod q.

여기서 $N^{-1}$ 은 실수 $\(1/N\)$ 가 아니라 법 $\(q\)$ 의 모듈러 역원이다. $\(q\)$ 가 소수이고 $N\mid(q-1)$ 이면 원시 $\(N\)$ 차 단위근이 존재하며 $\(q\)$ 는 $\(N\)$ 을 나누지 않으므로 $N^{-1}$ 도 존재한다.

직교성 증명도 유한체 안에서 동일하게 성립한다. 필요한 차수 조건과 역원이 존재하면 변환은 정확히 되돌릴 수 있다.

NTT 연산은 정수의 나머지 계산이다. 올바르게 구현하면 부동소수점 반올림 오차가 생기지 않는다. 그러나 모듈러 결과가 원래 무한정 큰 정수의 결과를 모두 보존한다는 뜻은 아니다. NTT는 어디까지나 정해진 법 $\(q\)$ 에서의 곱셈 결과를 정확히 계산한다. 그리고 구현에서 정수 overflow를 잘못 처리하면 수학이 정확해도 프로그램 결과는 틀릴 수 있다.

1.6.6 negacyclic NTT에 필요한 $\(2N\)$ 차 단위근

CKKS의 환에서는 $\(x^N+1\)$ 로 나눈 곱이 필요하다. 소수 $\(q\)$ 에 대한 기본 형태의 완전한 negacyclic NTT를 사용하려면 $\mathbb F_q$ 안에 원시 $\(2N\)$ 차 단위근 $\psi$ 가 필요하다.

\operatorname{ord}(\psi)=2N, \qquad \psi^N=-1, \qquad \omega=\psi^2.

그러면 $\omega$ 의 차수는 $\(N\)$ 이다. $\psi^N=-1$ 은 $\(q\)$ 가 홀수이고 $\psi$ 의 차수가 정확히 $\(2N\)$ 일 때 성립한다.

소수체의 곱셈군 크기는 $\(q-1\)$ 이므로 이 형태의 변환에는 다음 조건이 필요하며 충분하다.

2N\mid(q-1) \quad\Longleftrightarrow\quad q\equiv1\pmod{2N}.

이때 $\(x^N+1\)$ 의 모든 근은 다음과 같다.

\alpha_k=\psi\omega^k=\psi^{2k+1}, \qquad 0\le k<N.

서로 다른 $\(N\)$ 개 근이 모두 $\mathbb F_q$ 안에 있으며, 다항식은 일차식들의 곱으로 완전히 분해된다.

x^N+1 = \prod_{k=0}^{N-1}(x-\alpha_k) \quad\text{in }\mathbb F_q[x].

$q\equiv1\pmod N$ 은 길이 $\(N\)$ 의 cyclic NTT를 위한 조건이다. 이것만으로 원시 $\(2N\)$ 차 단위근이 보장되지는 않는다. 예를 들어 $\(N=4,q=13\)$ 에서는 $4\mid12$ 이지만 $8\nmid12$ 다. 길이 4 cyclic NTT와 여기서 설명하는 기본 negacyclic NTT의 조건을 혼동하면 안 된다.

이 조건은 “어떤 다른 방식으로도 $\(x^N+1\)$ 의 곱을 계산할 수 없다”는 주장까지 포함하지 않는다. 확장체, 다른 변환 길이, 불완전 NTT 등 별도 구성이 가능하다. 여기서는 CKKS 구현에서 흔히 사용하는, 소수체 안에서 모든 평가 좌표가 스칼라로 분해되는 형태를 설명한다.

원시 생성원 $\(g\)$ 를 알고 있다면 다음으로 $\psi$ 를 얻을 수 있다.

\psi=g^{(q-1)/(2N)}\pmod q.

$\(g\)$ 가 실제로 $\mathbb F_q^\times$ 의 생성원이어야 한다. 임의의 0이 아닌 값을 대입하면 차수가 더 작아질 수 있다.

1.6.7 twist로 negacyclic 곱을 cyclic 변환에 연결하기

다항식의 계수에 다음 가중치를 곱하자.

\widetilde a_j=a_j\psi^j.

이 twist를 한 배열에 길이 $\(N\)$ NTT를 적용하면 다음이 성립한다.

\begin{aligned} A_k &= \sum_{j=0}^{N-1}\widetilde a_j\omega^{kj}\\ &= \sum_{j=0}^{N-1}a_j(\psi\omega^k)^j\\ &= a(\alpha_k). \end{aligned}

즉 보통 cyclic NTT와 같은 계산을 사용하지만, 실제로는 $\(x^N+1\)$ 의 근에서 다항식을 평가한다.

곱셈 절차는 다음과 같다.

$\(a_j,b_j\)$ 에 각각 $\psi^j$ 를 곱한다.
두 배열에 $\omega$ 를 사용하는 길이 $\(N\)$ NTT를 적용한다.
변환 결과를 좌표별로 곱한다.
inverse NTT를 적용하여 twist된 결과 계수를 얻는다.
$\(j\)$ 번째 계수에 $\psi^{-j}$ 를 곱해 twist를 해제한다.

twist를 별도 단계로 하지 않고 butterfly의 twiddle factor에 통합하는 구현도 많다. 그러므로 라이브러리가 별도의 “twist 함수”를 노출하지 않더라도 negacyclic 곱이 아닌 것은 아니다. 어떤 변환점과 정규화를 사용하고 있는지 확인해야 한다.

1.6.8 완전한 작은 예제: $\(N=4,q=17\)$

다음 환에서 곱셈을 계산하자.

\mathbb F_{17}[x]/(x^4+1).

법 $\(17\)$ 에서는 $17\equiv1\pmod8$ 이므로 원시 8차 단위근이 존재한다. 다음 값을 선택한다.

\psi=2,\qquad \omega=\psi^2=4.

실제로 $\(2^4=16=-1\)$ 이고 $2^8=1\pmod{17}$ 이다. $\(2^1,2^2,2^4\)$ 는 1이 아니므로 2의 차수는 정확히 8이다. $\omega=4$ 의 차수는 4다.

입력 다항식은 다음과 같다.

\[ a(x)=1+2x+3x^2+4x^3, \]

\[ b(x)=2+x+x^3. \]

먼저 일반 정수 다항식으로 곱하면 다음을 얻는다.

\[ a(x)b(x) = 2+5x+8x^2+12x^3+6x^4+3x^5+4x^6. \]

$\(x^4=-1\)$ 로 접으면 결과는 다음과 같다.

\[ c(x)=-4+2x+4x^2+12x^3. \]

법 $\(17\)$ 의 0부터 시작하는 계수 대표값은 다음이다.

\mathbf c=(13,2,4,12).

이제 같은 결과를 NTT로 얻어보자. twist 가중치는 다음과 같다.

(\psi^0,\psi^1,\psi^2,\psi^3)=(1,2,4,8).

따라서 다음 배열을 얻는다.

\widetilde{\mathbf a}=(1,4,12,15), \qquad \widetilde{\mathbf b}=(2,2,0,8).

이후 표의 모든 연산은 법 $\(17\)$ 이다.

단계	첫째 입력 또는 결과	둘째 입력
원래 계수	$\((1,2,3,4)\)$	$\((2,1,0,1)\)$
twist	$\((1,4,12,15)\)$	$\((2,2,0,8)\)$
NTT	$\((15,13,11,16)\)$	$\((12,12,9,9)\)$
좌표별 곱	$\((10,3,14,8)\)$	—
inverse NTT	$\((13,4,16,11)\)$	—
twist 해제	$\((13,2,4,12)\)$	—

NTT의 두 번째 평가값을 직접 확인하면 다음과 같다.

\begin{aligned} A_1 &= 1+4\cdot4+12\cdot4^2+15\cdot4^3\\ &\equiv 1+16+12\cdot16+15\cdot13\\ &= 404\\ &\equiv13\pmod{17}. \end{aligned}

이 NTT는 원래 $\(a(x)\)$ 를 다음 점들에서 평가한 것과 같다.

(\alpha_0,\alpha_1,\alpha_2,\alpha_3) = (2,8,15,9).

예를 들어 $a(2)=1+4+12+32=49\equiv15$ 이므로 $\(A_0=15\)$ 다. 네 점 모두 네제곱이 $\(-1\)$ 이다.

좌표별 곱의 첫째 값은 $15\cdot12=180\equiv10$ 이다. 역변환에서는 다음 역원을 사용한다.

4^{-1}=13\pmod{17}, \qquad \omega^{-1}=13\pmod{17}.

$\(N=4\)$ 와 $\omega=4$ 가 이 예에서 우연히 같은 숫자이므로 두 역원도 같다. 일반적으로 $N^{-1}$ 과 $\omega^{-1}$ 은 서로 다른 대상이다.

역변환의 첫째 계수는 다음이다.

\widetilde c_0 = 13(10+3+14+8) \equiv13\pmod{17}.

둘째 계수는 다음이다.

\begin{aligned} \widetilde c_1 &= 13(10+3\cdot13+14\cdot16+8\cdot4)\\ &= 13\cdot305\\ &\equiv4\pmod{17}. \end{aligned}

전체 역변환 결과는 $\((13,4,16,11)\)$ 이다. $\psi^{-1}=9$ 이므로 twist 해제 가중치는 다음과 같다.

\[ (1,9,13,15). \]

좌표별로 곱하면 $(13,36,208,165)\equiv(13,2,4,12)$ 다. 직접 negacyclic 계산과 정확히 같은 결과를 얻었다.

1.6.9 정의를 그대로 실행하는 검산 코드

다음 코드는 빠른 NTT 구현이 아니라 정의의 합을 직접 계산하는 $\(O(N^2)\)$ 검산용 코드다. 작은 예제에서 표의 숫자를 확인하기 위한 목적이다. 큰 암호 매개변수에는 butterfly 기반 구현을 사용한다.

q, N = 17, 4
psi, omega = 2, 4
a = [1, 2, 3, 4]
b = [2, 1, 0, 1]

def transform(values, root):
    return [
        sum(values[j] * pow(root, k * j, q)
            for j in range(N)) % q
        for k in range(N)
    ]

def inverse_transform(values):
    inverse_root = pow(omega, -1, q)
    inverse_N = pow(N, -1, q)
    return [
        inverse_N * v % q
        for v in transform(values, inverse_root)
    ]

a_twisted = [a[j] * pow(psi, j, q) % q for j in range(N)]
b_twisted = [b[j] * pow(psi, j, q) % q for j in range(N)]
A = transform(a_twisted, omega)
B = transform(b_twisted, omega)
C = [A[k] * B[k] % q for k in range(N)]
c_twisted = inverse_transform(C)
inverse_psi = pow(psi, -1, q)
c = [c_twisted[j] * pow(inverse_psi, j, q) % q
     for j in range(N)]

print(A)          # [15, 13, 11, 16]
print(B)          # [12, 12, 9, 9]
print(C)          # [10, 3, 14, 8]
print(c_twisted)  # [13, 4, 16, 11]
print(c)          # [13, 2, 4, 12]

1.6.10 다항식 CRT: NTT가 정확한 표현 변환인 이유

정수 CRT에서는 서로소인 정수 법들을 사용했다. 다항식 CRT에서는 서로소인 다항식 법들을 사용한다. NTT용 소수 $\(q\)$ 에서는 $\(x^N+1\)$ 이 서로 다른 일차식들의 곱으로 분해되므로 다음 환 동형을 얻는다.

\mathbb F_q[x]/(x^N+1) \cong \prod_{k=0}^{N-1}\mathbb F_q[x]/(x-\alpha_k) \cong \mathbb F_q^N.

각 일차식으로 나눈 나머지는 $a(\alpha_k)$ 다. 따라서 오른쪽 좌표들은 바로 NTT 평가값이다. 환 동형이라는 것은 원소가 서로 일대일로 대응하고, 덧셈과 곱셈을 모두 보존한다는 뜻이다.

RNS와 NTT를 함께 사용하면 두 종류의 CRT가 겹쳐진다. 모든 $\(q_i\)$ 가 적절한 NTT 소수이고 $Q=\prod_iq_i$ 일 때 다음의 표현이 가능하다.

R_Q \cong \prod_i \left(\mathbb F_{q_i}[x]/(x^N+1)\right) \cong \prod_i\mathbb F_{q_i}^{N}.

첫 번째 분해는 계수의 정수 CRT, 두 번째 분해는 각 소수에서의 다항식 CRT다. 원소 하나를 $\(L\)$ 개의 소수 성분으로 나누고, 각 소수 성분을 $\(N\)$ 개의 평가 좌표로 나타낸다.

이 표현에서 같은 레벨과 같은 기저의 두 다항식 곱은 각 $\((i,k)\)$ 위치에서 법 $\(q_i\)$ 의 곱 하나로 처리할 수 있다. 변환, modulus 변경, basis conversion 등 다른 단계에는 별도의 작업이 필요하다.

1.6.11 복소 FFT, NTT, CKKS 슬롯은 서로 어떻게 다른가

구분	복소 FFT	NTT	CKKS의 복소 슬롯
계산 공간	$\mathbb C$	$\mathbb F_q$	$\mathbb C^{N/2}$ 에 대응하는 근사 메시지
단위근	복소 단위원의 점	유한체의 원소	원분다항식의 복소근과 켤레쌍
보통 용도	신호 처리, 복소 평가, 인코딩 변환	모듈러 다항식 곱셈 가속	여러 실수·복소수를 담아 동시 계산
값의 정확성	컴퓨터에서는 반올림 가능	올바른 정수 구현에서는 모듈러 결과가 정확	인코딩·복호·연산이 근삿값
좌표 개수	변환에 지정한 길이 $\(N\)$	보통 각 소수마다 $\(N\)$	최대 $\(N/2\)$ 복소 슬롯
곱셈 보존	평가점에서 좌표별 곱	평가점에서 좌표별 모듈러 곱	근사적인 슬롯별 곱에 대응

NTT의 $\(N\)$ 개 모듈러 평가값을 CKKS의 $\(N/2\)$ 개 복소 슬롯으로 읽으면 안 된다. NTT 좌표는 암호문 다항식의 계산 표현이고, 슬롯은 사용자 메시지의 의미 표현이다. 하나는 유한체의 평가, 다른 하나는 복소수의 평가에서 나온다.

또 NTT를 하는 행위 자체가 데이터를 암호화하는 것은 아니다. 정방향 변환을 누구나 역변환할 수 있다. NTT는 계산 가속 도구다. 비밀키, 무작위 오류, RLWE와 연결되는 암호문 구성은 별도의 보안 구조다.

CKKS가 근사 암호라는 말도 NTT가 근사 변환이라는 뜻은 아니다. 메시지를 정수화하고 scale을 바꾸는 과정에서 근사 오차가 생기는 반면, 정해진 법의 NTT 곱셈은 정확하게 수행될 수 있다.