09. Matrix-Vector Multiplication in CKKS: Diagonal and BSGS Methods

필기 원본

이 글에서 다룬 원본 PDF 39–42쪽이다. 두 단과 여백 필기를 포함한 페이지 전체를 실었다. 이미지를 누르면 확대해서 볼 수 있다.

인공지능보안 필기 원본 PDF 39쪽 전체
원본 PDF 39쪽. 이 글은 오른쪽 단의 Week 5부터 다룬다. 왼쪽 단도 함께 보존했다.
인공지능보안 필기 원본 PDF 40쪽 전체
원본 PDF 40쪽.
인공지능보안 필기 원본 PDF 41쪽 전체
원본 PDF 41쪽.
인공지능보안 필기 원본 PDF 42쪽 전체
원본 PDF 42쪽. 이 글은 왼쪽 단의 BSGS까지 다룬다. 오른쪽 단도 함께 보존했다.

들어가며

앞 글[1]에서는 슬롯 회전과 켤레 연산을 만들었다. 이번에는 회전과 평문 곱을 조합하여 공개 행렬과 암호화된 벡터의 곱을 계산한다. 이어서 비싼 회전을 재사용하는 baby-step giant-step, 즉 BSGS 최적화를 유도한다.

정리 범위는 원본 PDF의 39쪽 오른쪽부터 42쪽 왼쪽까지다. Week 5의 CKKS 연산 요약, 머신러닝의 행렬 연산, 대각선 분해, 원문의 숫자 예제, BSGS의 수식과 연산 횟수를 다룬다. 42쪽 오른쪽에서 시작하는 합성곱은 다음 글로 넘긴다.

원문의 키 생성·암호화식도 생략하지 않는다. 유리수·실수 계수의 구별, 실제 슬롯 수, 스케일 변화, BSGS의 회전 방향은 앞 글들과 일관되게 적는다. 추가 예제와 일반화한 증명은 보충으로 구별한다.

1. CKKS 매개변수와 인코딩을 다시 정리한다

1.1 다항식 차수, 슬롯 수, 레벨 수

다항식 환은

R=Z[X]/(XN+1),RQ=R/QRR=\mathbb Z[X]/(X^N+1),\qquad R_Q=R/QR

이다. N≥2N\ge2는 22의 거듭제곱이며, 독립 복소 슬롯 수를

n=N/2n=N/2

로 쓴다. 원문의 필기처럼

N=216=65536⟹n=32768N=2^{16}=65536 \quad\Longrightarrow\quad n=32768

이다. 이는 슬롯 수를 계산하는 예시다.

앞 글에서는 슬롯 수를 LL로 썼다. 이번에는 원문의 modulus chain 표기와 맞추기 위해 슬롯 수는 nn, 최대 레벨은 LL로 구별한다.

법 체인은

Qℓ=∏j=0ℓqj,0≤ℓ≤LQ_\ell=\prod_{j=0}^{\ell}q_j,\qquad0\le\ell\le L

로 둔다. 처음에는 QLQ_L을 사용하고, rescaling할 때

Qℓ⟼Qℓ−1=Qℓ/qℓQ_\ell\longmapsto Q_{\ell-1}=Q_\ell/q_\ell

로 내려간다. 원문은 q1,…,qLq_1,\ldots,q_L을 목표 스케일 Δ\Delta에 가까운 크기로 정하는 구성을 설명한다.

1.2 스케일과 보조 법은 역할이 다르다

Δ>0\Delta>0는 메시지를 정수 다항식으로 표현하는 스케일이고, PP는 키 전환에서 임시로 법을 확장하는 보조 인수다.

RQℓ⟶RPQℓ⟶RQℓR_{Q_\ell}\longrightarrow R_{PQ_\ell} \longrightarrow R_{Q_\ell}

이라는 키 전환의 보조 계산과

RQℓ⟶RQℓ−1R_{Q_\ell}\longrightarrow R_{Q_{\ell-1}}

이라는 rescaling의 레벨 감소를 구별한다.

같은 스케일의 두 값을 곱한 뒤 rescaling하면 정확한 새 스케일은

Δnew=Δ2qℓ.\Delta_{\mathrm{new}}=\frac{\Delta^2}{q_\ell}.

qℓ≈Δq_\ell\approx\Delta이면 이것이 다시 Δ\Delta에 가까워진다. 일반적으로 정확히 같은 수가 되는 것은 아니다. 예를 들어 Δ=64\Delta=64, qℓ=61q_\ell=61이면

Δnew=409661≈67.14754.\Delta_{\mathrm{new}}=\frac{4096}{61}\approx67.14754.

원문의 “곱셈에 맞춰 법과 스케일을 줄인다”는 필기는 이 레벨 체인의 의미다. 실제 소인수로 스케일을 나누는 구별은 CKKS 저자의 설명에서도 확인할 수 있다. Yongsoo Song, Theory to Practice, PDF 22쪽[2]

1.3 벡터에서 정수 메시지로

입력은

z=(z0,…,zn−1)∈Cn\boldsymbol z=(z_0,\ldots,z_{n-1})\in\mathbb C^n

이다. 앞 글의 근 순서

ξk=eπi5k/N,0≤k<n\xi_k=e^{\pi i5^k/N},\qquad0\le k<n

를 사용한다. 켤레 쌍의 나머지 값까지 완성한 뒤 역변환하여

m∈AR=R[X]/(XN+1),m(ξk)=zkm\in A_{\mathbb R}=\mathbb R[X]/(X^N+1),\qquad m(\xi_k)=z_k

인 이상적인 다항식을 얻는다. 실제 정수 인코딩은

M=⌊Δm⌉∈RM=\lfloor\Delta m\rceil\in R

이다. 반올림은 계수별로 한다.

원문의 화살표에 쓰인 유리수 계수 표기는 07번 글[3]에서 구별한 조건에 따라 읽는다. 임의 복소 벡터의 정확한 역변환은 실수 계수 공간에서 설명하고, 정수화에는 근사 오차를 포함한다.

2. 키 생성·암호화·복호화의 전체 관계

2.1 키 생성

원문의 χ\chi는 작은 계수를 뽑는 분포를 나타낸다. 비밀키·임시 다항식·오차의 역할을 구별하기 위해 여기서는 각각 χs,χr,χe\chi_s,\chi_r,\chi_e로 적는다. 원문처럼 같은 기호로 묶는 것은 단순화된 표기다.

최초 법을 q=QLq=Q_L로 줄여 쓰자. 비밀키와 공개키는

s←χsN,sk⁡=s,s\leftarrow\chi_s^N,\qquad\operatorname{sk}=s, apk←URq,epk←χeN,a_{\mathrm{pk}}\xleftarrow{\mathrm U}R_q,\qquad e_{\mathrm{pk}}\leftarrow\chi_e^N, bpk=[−apks+epk]q,pk⁡=(bpk,apk)b_{\mathrm{pk}}=[-a_{\mathrm{pk}}s+e_{\mathrm{pk}}]_q, \qquad\operatorname{pk}=(b_{\mathrm{pk}},a_{\mathrm{pk}})

로 만든다. 따라서

bpk+apks=[epk]q.b_{\mathrm{pk}}+a_{\mathrm{pk}}s=[e_{\mathrm{pk}}]_q.

키 생성의 출력은 (pk⁡,sk⁡)(\operatorname{pk},\operatorname{sk})다. 곱셈·회전에 필요한 평가키는 06번 글[4]과 앞 글의 구성을 추가로 사용한다.

2.2 공개키 암호화

정수 메시지 M=⌊Δm⌉M=\lfloor\Delta m\rceil를 준비하고

r←χrN,e0,e1←χeNr\leftarrow\chi_r^N,\qquad e_0,e_1\leftarrow\chi_e^N

를 뽑는다. 원문과 같은 암호화식은

c=(u,v)=[rpk⁡+(e0,e1)+(M,0)]q=([rbpk+e0+M]q,[rapk+e1]q).\begin{aligned} c=(u,v) &=[r\operatorname{pk}+(e_0,e_1)+(M,0)]_q\\ &=([rb_{\mathrm{pk}}+e_0+M]_q, [ra_{\mathrm{pk}}+e_1]_q). \end{aligned}

원문의 (b,a)(b,a)는 이 글의 공개키 두 성분, (u,v)(u,v)는 암호문 두 성분에 해당한다. 인코딩과 암호화는 별도의 단계다.

2.3 복호화 조합을 전개한다

Ds(c)=u+vs=[rbpk+e0+M+(rapk+e1)s]q=[M+r(bpk+apks)+e0+e1s]q=[M+repk+e0+e1s]q.\begin{aligned} D_s(c)=u+vs &=[rb_{\mathrm{pk}}+e_0+M+(ra_{\mathrm{pk}}+e_1)s]_q\\ &=[M+r(b_{\mathrm{pk}}+a_{\mathrm{pk}}s)+e_0+e_1s]_q\\ &=[M+re_{\mathrm{pk}}+e_0+e_1s]_q. \end{aligned}

인코딩 반올림을

ρ=M−Δm\rho=M-\Delta m

로 분리하면 총오차는

η=ρ+repk+e0+e1s\eta=\rho+re_{\mathrm{pk}}+e_0+e_1s

이며

Ds(c)=[Δm+η]q.D_s(c)=[\Delta m+\eta]_q.

메시지와 오차의 합이 중심 대표 범위 안에 있을 때

ctr⁡q(Ds(c))=Δm+η\operatorname{ctr}_q(D_s(c))=\Delta m+\eta

를 읽고, 스케일로 나누어 근에서 평가한다.

z^k=ctr⁡q(Ds(c))(ξk)Δ=zk+η(ξk)Δ.\widehat z_k =\frac{\operatorname{ctr}_q(D_s(c))(\xi_k)}\Delta =z_k+\frac{\eta(\xi_k)}\Delta.

이것이 원문 39쪽의 u+vs≈Δmu+vs\approx\Delta m 뒤에 있는 인코딩·잡음·디코딩 관계다.

3. 사용할 기본 연산과 비용

3.1 다섯 연산의 메시지·스케일 변화

원문은 덧셈, 평문 곱셈, 암호문 곱셈, 회전, 켤레를 요약한다. 아래는 같은 키·법 아래에서 필요한 스케일을 맞춘 입력을 가정한 표다.

연산이상적인 슬롯 결과출력 스케일과 처리
덧셈z1+z2\boldsymbol z_1+\boldsymbol z_2같은 입력 스케일 Δ\Delta 유지
평문 곱p⊙z\boldsymbol p\odot\boldsymbol z평문·암호문 스케일이 모두 Δ\Delta면 Δ2\Delta^2
암호문 곱z1⊙z2\boldsymbol z_1\odot\boldsymbol z_2Δ2\Delta^2; 세 성분의 곱을 relinearization으로 정리
왼쪽 rr칸 회전(z(k+r) mod n)k(z_{(k+r)\bmod n})_kΔ\Delta 유지; 치환한 키를 원래 키로 전환
켤레(zk‾)k(\overline{z_k})_kΔ\Delta 유지; 켤레 평가키로 키 전환

원문의 다항식 복호화 관계로도 적어 두자. 메시지와 오차가 현재 법의 중심 대표 범위에 있고 오차가 작다고 가정한다. 평문은 M1=⌊Δm1⌉M_1=\lfloor\Delta m_1\rceil이며, 아래 암호문 곱은 relinearization까지 포함한 결과다.

ctr⁡q(Ds(c1⊕c2))≈Δ(m1+m2),ctr⁡q(Ds(M1⊙c2))≈Δ2m1m2,ctr⁡q(Ds(c1⊗c2))≈Δ2m1m2,ctr⁡q(Ds(Rot⁡(c,r)))≈Δm(X5r),ctr⁡q(Ds(Conj⁡(c)))≈Δm(X−1).\begin{aligned} \operatorname{ctr}_q(D_s(c_1\oplus c_2)) &\approx\Delta(m_1+m_2),\\ \operatorname{ctr}_q(D_s(M_1\odot c_2)) &\approx\Delta^2m_1m_2,\\ \operatorname{ctr}_q(D_s(c_1\otimes c_2)) &\approx\Delta^2m_1m_2,\\ \operatorname{ctr}_q(D_s(\operatorname{Rot}(c,r))) &\approx\Delta m(X^{5^r}),\\ \operatorname{ctr}_q(D_s(\operatorname{Conj}(c))) &\approx\Delta m(X^{-1}). \end{aligned}

⊙\odot는 성분별 곱이다. 평문 곱에서 사용하는 것은 이상적인 벡터 자체가 아니라, 그 벡터를 인코딩한 다항식이다. 평문의 스케일이 Δp\Delta_p, 암호문의 스케일이 Δx\Delta_x이면 출력은 일반적으로

Δout=ΔpΔx\Delta_{\mathrm{out}}=\Delta_p\Delta_x

다. 같은 스케일을 가정한 원문의 Δ2\Delta^2는 그 특수한 경우다. 곱셈 뒤의 rescaling은 앞 절의 레벨 체인과 연결된다.

3.2 왜 회전 수를 줄이는가

원문의 비용 비교는

Add⁡≈PMult⁡≪CMult⁡≈Rot⁡≈Conj⁡\operatorname{Add}\approx\operatorname{PMult} \ll\operatorname{CMult}\approx\operatorname{Rot}\approx\operatorname{Conj}

이다. 이는 이 단원에서 사용하는 구현의 비용을 크게 나눈 직관이다. 정확한 시간 비율이나 모든 매개변수에서의 등식으로 해석하지 않는다. 필기처럼 CMult에는 relinearization까지 포함해 비교한다.

특히 relinearization·회전·켤레에서 사용하는 키 전환의 비용이 크므로, 같은 결과를 더 적은 회전으로 계산하는 방법이 중요하다. 이 글의 BSGS는 그 회전 횟수를 줄인다.

4. 머신러닝의 행렬 연산으로 연결한다

4.1 공개 가중치와 암호화된 입력

원문은 기본 연산을 조합하는 응용으로 행렬 연산, 합성곱, ReLU, Softmax를 든다. CNN의 fully connected layer와 convolution 모두 행렬 연산과 연결된다. 합성곱에는 그 구조를 이용하는 전용 방법도 있으며 다음 글에서 다룬다.

공개 가중치 ww를 가진 서버와 입력 x\boldsymbol x를 가진 클라이언트를 생각하자. 클라이언트가 입력을 인코딩·암호화하고, 서버가 그 암호문과 공개 가중치로 함수를 평가한 뒤 결과 암호문을 돌려준다. 클라이언트는 복호화·디코딩하여 결과를 읽는다.

정확성을 수식으로 적으면

Decode⁡Δout(Dec⁡s(Eval⁡w(cx)))≈F(x;w).\operatorname{Decode}_{\Delta_{\mathrm{out}}} \left(\operatorname{Dec}_s \left(\operatorname{Eval}_w(c_x)\right)\right) \approx F(\boldsymbol x;w).

여기서 cxc_x는 인코딩한 입력의 암호문이고, Dec⁡s\operatorname{Dec}_s는 중심 대표의 정수 다항식을 반환한다. 암호문 성분 자체를 평문 함수값과 같다고 쓰지 않는다.

ReLU·Softmax는 일반 실수 입력 전체에서 유한한 덧셈·곱셈만으로 정확히 표현되는 다항식이 아니다. 원문의 응용 목록은 계산 가능한 기본 연산으로 적절한 근사 등을 설계하는 문제로 읽어야 한다.

4.2 Attention 안에서는 두 입력이 모두 암호문일 수도 있다

완전연결층의 공개 가중치 행렬과 암호화된 벡터의 곱은 평문·암호문 연산이다. 원문은 이와 달리 Transformer attention 안에 암호문 행렬끼리의 연산이 필요할 수 있음을 강조한다.

Attention⁡(Q,K,V)=softmax⁡ ⁣(QKTdk)V.\operatorname{Attention}(Q,K,V) =\operatorname{softmax}\!\left(\frac{QK^{\mathsf T}}{\sqrt{d_k}}\right)V.

여기서 Q,K,VQ,K,V는 query, key, value 행렬이며 dkd_k는 key의 차원이다. 앞 절의 암호문 법 QℓQ_\ell과 다른 기호다. 이 식은 원 논문의 scaled dot-product attention이다. Vaswani et al., §3.2.1[5]

개인 입력에서 만든 Q,K,VQ,K,V를 모두 암호화한 설정이라면 QKTQK^{\mathsf T} 등의 계산에 암호문끼리의 곱이 필요하다. 이번 글은 우선 행렬은 공개 평문, 벡터는 암호문인 경우를 다룬다.

5. 행렬벡터곱을 순환 대각선으로 분해한다

5.1 목표와 회전 방향

공개 행렬과 입력 벡터를

A∈Rn×n,x=(x0,…,xn−1)TA\in\mathbb R^{n\times n},\qquad \boldsymbol x=(x_0,\ldots,x_{n-1})^{\mathsf T}

라 하자. 목표는

y=Ax,yj=∑k=0n−1Aj,kxk\boldsymbol y=A\boldsymbol x,\qquad y_j=\sum_{k=0}^{n-1}A_{j,k}x_k

다. 같은 위치의 성분끼리만 곱해서는 서로 다른 입력 위치를 읽는 모든 항을 만들 수 없다.

이하 벡터의 왼쪽 회전을

Ri(x)j=x(j+i) mod n\mathcal R_i(\boldsymbol x)_j=x_{(j+i)\bmod n}

로 쓴다. i=1i=1이면

R1(x)=(x1,x2,…,xn−1,x0)T.\mathcal R_1(\boldsymbol x) =(x_1,x_2,\ldots,x_{n-1},x_0)^{\mathsf T}.

이는 앞 글의 암호문 회전 방향과 같다. 벡터 사상 Ri\mathcal R_i와 암호문 연산 Rot⁡(c,i)\operatorname{Rot}(c,i)는 구별한다.

5.2 첫 대각선과 다음 대각선

주대각선의 값들을

d0=(A0,0,A1,1,…,An−1,n−1)T\boldsymbol d_0=(A_{0,0},A_{1,1},\ldots,A_{n-1,n-1})^{\mathsf T}

로 모으면

d0⊙x=(A0,0x0,A1,1x1,…,An−1,n−1xn−1)T.\boldsymbol d_0\odot\boldsymbol x =(A_{0,0}x_0,A_{1,1}x_1,\ldots,A_{n-1,n-1}x_{n-1})^{\mathsf T}.

이것이 원문 40쪽에서 먼저 표시한 항들이다.

다음 대각선은 마지막 행에서 처음 열로 돌아온다.

d1=(A0,1,A1,2,…,An−2,n−1,An−1,0)T.\boldsymbol d_1=(A_{0,1},A_{1,2},\ldots,A_{n-2,n-1},A_{n-1,0})^{\mathsf T}.

그러면

d1⊙R1(x)=(A0,1x1,A1,2x2,…,An−1,0x0)T.\boldsymbol d_1\odot\mathcal R_1(\boldsymbol x) =(A_{0,1}x_1,A_{1,2}x_2,\ldots,A_{n-1,0}x_0)^{\mathsf T}.

행렬의 오른쪽 끝을 넘으면 왼쪽 열로 돌아오는 순환 대각선을 사용한다. 원문의 ai\boldsymbol a_i가 이 글의 di\boldsymbol d_i다.

5.3 모든 대각선을 더하면 원래 행렬곱이다

일반적으로

(di)j=Aj,(j+i) mod n,0≤i,j<n.(\boldsymbol d_i)_j=A_{j,(j+i)\bmod n},\qquad0\le i,j<n.

원문의 x(i)\boldsymbol x^{(i)}는 이 글의 Ri(x)\mathcal R_i(\boldsymbol x)다. 따라서

Ax=∑i=0n−1di⊙Ri(x).\boxed{A\boldsymbol x =\sum_{i=0}^{n-1}\boldsymbol d_i\odot\mathcal R_i(\boldsymbol x)}.

원문 41쪽 왼쪽의 필기처럼 출력 위치 jj 하나를 보면

(∑idi⊙Ri(x))j=∑i=0n−1Aj,(j+i) mod nx(j+i) mod n=∑k=0n−1Aj,kxk=yj.\begin{aligned} \left(\sum_i\boldsymbol d_i\odot\mathcal R_i(\boldsymbol x)\right)_j &=\sum_{i=0}^{n-1}A_{j,(j+i)\bmod n}x_{(j+i)\bmod n}\\ &=\sum_{k=0}^{n-1}A_{j,k}x_k\\ &=y_j. \end{aligned}

고정한 jj에서 (j+i) mod n(j+i)\bmod n은 ii가 변할 때 모든 열을 한 번씩 방문한다. 따라서 각 출력 위치에 해당 행의 내적이 완성된다. 같은 대각선 분해는 HElib의 선형대수 설명에서도 확인할 수 있다. Halevi–Shoup, Algorithms in HElib, §4.3[6]

5.4 원문의 3×3 예제

원문은 벡터 계산을 보여 주기 위해

A=(123456789),x=(123)A=\begin{pmatrix}1&2&3\\4&5&6\\7&8&9\end{pmatrix},\qquad \boldsymbol x=\begin{pmatrix}1\\2\\3\end{pmatrix}

를 사용한다. 이 절에서는 길이 33의 벡터에 대한 순환 연산을 계산한다. 실제 CKKS 슬롯에 넣는 방법은 다음 절에서 구별한다.

회전량순환 대각선회전한 입력성분별 곱
00(1,5,9)(1,5,9)(1,2,3)(1,2,3)(1,10,27)(1,10,27)
11(2,6,7)(2,6,7)(2,3,1)(2,3,1)(4,18,7)(4,18,7)
22(3,4,8)(3,4,8)(3,1,2)(3,1,2)(9,4,16)(9,4,16)

세 결과를 더하면

(1,10,27)+(4,18,7)+(9,4,16)=(14,32,50).(1,10,27)+(4,18,7)+(9,4,16)=(14,32,50).

직접 계산한

Ax=(1+4+94+10+187+16+27)=(143250)A\boldsymbol x =\begin{pmatrix} 1+4+9\\4+10+18\\7+16+27 \end{pmatrix} =\begin{pmatrix}14\\32\\50\end{pmatrix}

와 일치한다.

3×3 원문 행렬을 세 순환 대각선으로 나누고 각각 회전한 입력과 곱해 합하는 예제

6. 세 값의 예제와 실제 네 슬롯을 구별한다

6.1 0 하나를 붙이면 회전의 주기도 달라진다

보충: 지금의 NN은 22의 거듭제곱이므로 전체 독립 슬롯 수 n=N/2n=N/2도 22의 거듭제곱이다. 앞 절의 길이 33 예제를 곧바로 “세 슬롯짜리 CKKS”로 해석하지 않는다.

N=8N=8의 네 슬롯에

x′=(1,2,3,0)T\boldsymbol x'=(1,2,3,0)^{\mathsf T}

를 넣으면 기본 왼쪽 회전은

R1(x′)=(2,3,0,1)T\mathcal R_1(\boldsymbol x')=(2,3,0,1)^{\mathsf T}

이다. 세 값만 주기적으로 도는 (2,3,1,0)T(2,3,1,0)^{\mathsf T}와 다르다.

6.2 행렬도 함께 확장하면 같은 결과를 얻는다

A′=(1230456078900000)A'=\begin{pmatrix} 1&2&3&0\\4&5&6&0\\7&8&9&0\\0&0&0&0 \end{pmatrix}

로 두고 길이 44의 순환 대각선을 다시 구한다.

회전량확장 행렬의 대각선해당 곱의 결과
00(1,5,9,0)(1,5,9,0)(1,10,27,0)(1,10,27,0)
11(2,6,0,0)(2,6,0,0)(4,18,0,0)(4,18,0,0)
22(3,0,7,0)(3,0,7,0)(9,0,7,0)(9,0,7,0)
33(0,4,8,0)(0,4,8,0)(0,4,16,0)(0,4,16,0)

합은

A′x′=(14,32,50,0)T.A'\boldsymbol x'=(14,32,50,0)^{\mathsf T}.

처음 세 출력이 원래 예제와 같다. 입력뿐 아니라 실제 슬롯 수에 맞춰 행렬과 대각선도 함께 구성해야 한다.

7. 대각선 분해를 암호문 연산으로 옮긴다

7.1 공개 대각선을 인코딩하고 입력을 회전한다

cxc_x는 x\boldsymbol x를 스케일 Δx\Delta_x로 인코딩·암호화한 두 성분 암호문이다. 각 공개 대각선을 같은 평문 스케일 Δp\Delta_p로 인코딩하여

Pi=Encode⁡Δp(di)P_i=\operatorname{Encode}_{\Delta_p}(\boldsymbol d_i)

를 준비한다. 이 글의 PiP_i는 인코딩한 평문 다항식이며, 키 전환의 보조 인수 PP와 다르다.

기본 알고리즘은

cyraw=∑i=0n−1Pi⊙Rot⁡(cx,i).\boxed{c_y^{\mathrm{raw}} =\sum_{i=0}^{n-1}P_i\odot\operatorname{Rot}(c_x,i)}.

이 식의 ⊙\odot는 평문 다항식과 암호문의 곱이다. 같은 기호로 표시한 벡터의 성분별 곱과는 층위가 다르지만, 인코딩의 대응에 의해 목표 슬롯 연산을 수행한다.

모든 대각선 항이 있는 기본 구성의 연산 횟수는

평문 곱:n,암호문 덧셈:n−1,회전:n−1.\begin{aligned} \text{평문 곱}&:n,\\ \text{암호문 덧셈}&:n-1,\\ \text{회전}&:n-1. \end{aligned}

00칸 회전은 원본을 재사용한다. 각 회전을 직접 실행하는 평가키가 있다는 가정으로 센다. 원문의 O(n)O(n)은 이러한 포장된 암호문 연산의 개수를 말한다. 한 연산의 내부 비용이나 행렬의 평문 전처리까지 상수 시간이라는 뜻은 아니다.

7.2 더할 때의 스케일과 마지막 rescaling

회전은 입력 스케일 Δx\Delta_x를 유지한다. 각 평문 곱의 스케일은

ΔxΔp\Delta_x\Delta_p

이므로 같은 법·레벨에서 이 항들을 더할 수 있다. 이상적인 결과와 실제 결과의 관계는

Decode⁡ΔxΔp(Dec⁡s(cyraw))≈Ax\operatorname{Decode}_{\Delta_x\Delta_p} \left(\operatorname{Dec}_s(c_y^{\mathrm{raw}})\right) \approx A\boldsymbol x

이다. 입력 오차, 평문 인코딩 반올림, 회전의 키 전환 오차가 포함된다.

중간 합이 법의 표현 범위 안에 들어가고 필요한 여유가 있으면, 같은 스케일의 항들을 먼저 더한 뒤 rescaling하는 계산 계획을 사용할 수 있다. 각 항을 먼저 rescaling하는 계획도 가능하지만 레벨·스케일을 맞춰 더해야 한다. 최종 rescaling의 새 스케일은

Δout=ΔxΔpqℓ\Delta_{\mathrm{out}}=\frac{\Delta_x\Delta_p}{q_\ell}

이다. 평문 곱은 암호문의 성분 수를 세 개로 늘리지 않으므로, 이 행렬곱 자체에 암호문끼리의 곱셈용 relinearization을 추가할 필요는 없다.

8. BSGS는 작은 회전을 재사용한다

8.1 회전량을 블록과 블록 안 위치로 나눈다

기본 알고리즘은 서로 다른 n−1n-1개의 회전을 사용한다. BSGS는 이 회전량을 작은 이동과 큰 이동의 합으로 분해한다.

n=bgn=bg인 양의 정수 b,gb,g를 고르고

i=kb+t,0≤k<g,0≤t<bi=kb+t,\qquad0\le k<g,\quad0\le t<b

로 쓴다. bb는 baby step의 블록 크기, kk는 giant step의 블록 번호다.

대각선 합을 블록으로 나누면

Ax=∑k=0g−1∑t=0b−1dkb+t⊙Rkb+t(x).A\boldsymbol x =\sum_{k=0}^{g-1}\sum_{t=0}^{b-1} \boldsymbol d_{kb+t}\odot\mathcal R_{kb+t}(\boldsymbol x).

8.2 가중치를 반대 방향으로 미리 돌린다

핵심 항등식은

dkb+t⊙Rkb+t(x)=Rkb ⁣(R−kb(dkb+t)⊙Rt(x)).\boxed{ \boldsymbol d_{kb+t}\odot\mathcal R_{kb+t}(\boldsymbol x) =\mathcal R_{kb}\!\left( \mathcal R_{-kb}(\boldsymbol d_{kb+t}) \odot\mathcal R_t(\boldsymbol x)\right)}.

왼쪽 회전은 성분별 곱을 보존하므로

Ra(u⊙v)=Ra(u)⊙Ra(v).\mathcal R_a(\boldsymbol u\odot\boldsymbol v) =\mathcal R_a(\boldsymbol u)\odot\mathcal R_a(\boldsymbol v).

오른쪽 식을 전개하면 가중치는 원래 위치로 돌아오고 입력의 회전량은 더해진다.

RkbR−kb(dkb+t)=dkb+t,\mathcal R_{kb}\mathcal R_{-kb}(\boldsymbol d_{kb+t}) =\boldsymbol d_{kb+t}, RkbRt(x)=Rkb+t(x).\mathcal R_{kb}\mathcal R_t(\boldsymbol x) =\mathcal R_{kb+t}(\boldsymbol x).

그래서 사전 가중치 회전의 부호는 마이너스다. 공개 대각선은 미리 재배열할 수 있으므로, 이 작업에 암호문 키 전환을 사용할 필요가 없다.

8.3 합을 먼저 만들고 큰 회전은 한 번만 한다

사전 회전한 대각선을

d~kb+t=R−kb(dkb+t)\widetilde{\boldsymbol d}_{kb+t} =\mathcal R_{-kb}(\boldsymbol d_{kb+t})

로 두자. 회전은 덧셈도 보존하므로

Ax=∑k=0g−1Rkb ⁣(∑t=0b−1d~kb+t⊙Rt(x)).\boxed{ A\boldsymbol x =\sum_{k=0}^{g-1}\mathcal R_{kb}\!\left( \sum_{t=0}^{b-1} \widetilde{\boldsymbol d}_{kb+t}\odot\mathcal R_t(\boldsymbol x) \right)}.

각 블록에서 필요한 입력은 R0(x),…,Rb−1(x)\mathcal R_0(\boldsymbol x),\ldots,\mathcal R_{b-1}(\boldsymbol x)로 같다. 블록마다 다른 것은 사전 회전한 가중치다. 이 작은 회전들을 한 번 만들어 모든 블록에 재사용한다.

8.4 암호문 알고리즘

먼저

Ct=Rot⁡(cx,t),0≤t<bC_t=\operatorname{Rot}(c_x,t),\qquad0\le t<b

를 저장한다. C0=cxC_0=c_x다. 공개 평문은

P~kb+t=Encode⁡Δp(d~kb+t)\widetilde P_{kb+t} =\operatorname{Encode}_{\Delta_p} \bigl(\widetilde{\boldsymbol d}_{kb+t}\bigr)

로 미리 준비한다. 각 블록의 합은

Tk=∑t=0b−1P~kb+t⊙CtT_k=\sum_{t=0}^{b-1}\widetilde P_{kb+t}\odot C_t

이고 최종 출력은

cyBSGS=∑k=0g−1Rot⁡(Tk,kb).\boxed{c_y^{\mathrm{BSGS}} =\sum_{k=0}^{g-1}\operatorname{Rot}(T_k,kb)}.

첫 블록은 kb=0kb=0이므로 사전 가중치 회전과 바깥 회전이 모두 항등이다. 이 때문에 원문의 첫 블록에는 원래 PiP_i가, 이후 블록에는 사전 회전한 P~i\widetilde P_i가 나타난다.

각 TkT_k의 스케일은 ΔxΔp\Delta_x\Delta_p이고 큰 회전도 그 스케일을 유지한다. 최종 합의 레벨·스케일 처리 조건은 앞 절과 같다. 정확한 벡터 항등식이 성립해도 두 암호문 알고리즘의 반올림·키 전환 오차나 성분들이 동일하다는 뜻은 아니다.

9. 원문의 16슬롯 예제를 항별로 확인한다

9.1 작은 회전 네 개로 시작한다

원문의 예제는 n=16n=16, b=4b=4, g=4g=4다. 기본 방법은

P0⊙cx+P1⊙Rot⁡(cx,1)+⋯+P15⊙Rot⁡(cx,15)P_0\odot c_x+P_1\odot\operatorname{Rot}(c_x,1) +\cdots+P_{15}\odot\operatorname{Rot}(c_x,15)

로 1515회의 회전을 사용한다.

BSGS에서는

C0=cx,C1=Rot⁡(cx,1),C2=Rot⁡(cx,2),C3=Rot⁡(cx,3)C_0=c_x,\quad C_1=\operatorname{Rot}(c_x,1),\quad C_2=\operatorname{Rot}(c_x,2),\quad C_3=\operatorname{Rot}(c_x,3)

를 만든다. 필요한 회전은 33회다.

9.2 다음 블록의 4, 5, 6, 7은 어떻게 만드는가

두 번째 블록은 회전량 4,5,6,74,5,6,7에 해당한다.

4=4+0,5=4+1,6=4+2,7=4+3.4=4+0,\quad5=4+1,\quad6=4+2,\quad7=4+3.

가중치를 각각 오른쪽으로 네 칸, 즉 왼쪽으로 −4-4칸 돌려 놓고

T1=P~4⊙C0+P~5⊙C1+P~6⊙C2+P~7⊙C3T_1=\widetilde P_4\odot C_0 +\widetilde P_5\odot C_1 +\widetilde P_6\odot C_2 +\widetilde P_7\odot C_3

를 먼저 계산한다. 그 후

Rot⁡(T1,4)\operatorname{Rot}(T_1,4)

를 한 번 적용하면 된다. 이 바깥 회전이 네 항 모두의 입력 위치를 네 칸 더 이동시킨다.

안쪽 마지막 회전은 33, 바깥 회전은 44다. 원문 41쪽 오른쪽과 42쪽 왼쪽에도 안쪽 값은 0,1,2,30,1,2,3으로 적혀 있다. 두 역할을 섞으면 목표 회전량 77을 다른 값으로 바꾸게 된다.

16슬롯 BSGS에서 baby step 0부터 3과 giant step 0,4,8,12를 합쳐 모든 회전량을 만드는 표

9.3 가중치를 미리 옮기는 이유를 한 항으로 본다

원문 42쪽 왼쪽의 필기는 출력 00번에 A0,4x4A_{0,4}x_4를 만들고 싶다는 예다.

C0C_0의 입력 x4x_4는 슬롯 44에 있다. 그래서 d4\boldsymbol d_4의 슬롯 00에 있던 가중치 A0,4A_{0,4}를 사전 오른쪽 회전으로 슬롯 44에 둔다.

(R−4(d4))4=(d4)0=A0,4.\bigl(\mathcal R_{-4}(\boldsymbol d_4)\bigr)_4 =(\boldsymbol d_4)_0=A_{0,4}.

성분별 곱을 하면 슬롯 44에서 A0,4x4A_{0,4}x_4가 만들어진다. 마지막 왼쪽 네 칸 회전이 이 값을 출력 슬롯 00으로 옮긴다.

원문의 항별 약식 등식에는 이 마지막 회전까지 포함해야 한다. 벡터 수준의 정확한 식은

R4 ⁣(R−4(d4)⊙x)=d4⊙R4(x),\mathcal R_4\!\left( \mathcal R_{-4}(\boldsymbol d_4)\odot\boldsymbol x\right) =\boldsymbol d_4\odot\mathcal R_4(\boldsymbol x), R4 ⁣(R−4(d5)⊙R1(x))=d5⊙R5(x)\mathcal R_4\!\left( \mathcal R_{-4}(\boldsymbol d_5)\odot\mathcal R_1(\boldsymbol x)\right) =\boldsymbol d_5\odot\mathcal R_5(\boldsymbol x)

이다. 바깥 회전을 제외한 왼쪽의 중간 곱이 오른쪽의 최종 항과 같은 벡터라고 쓰지는 않는다.

추가 숫자 검산: 16×1616\times16 행렬과 입력을

Aj,k=100j+k+1,xk=k+1A_{j,k}=100j+k+1,\qquad x_k=k+1

로 정하면 두 번째 블록이 출력 00에 주는 값은

∑k=47A0,kxk=52+62+72+82=174.\sum_{k=4}^{7}A_{0,k}x_k =5^2+6^2+7^2+8^2=174.

BSGS의 블록 합을 만든 뒤 네 칸 회전해도 정확히 174174를 얻었다. 마지막 baby step을 잘못 44로 바꾸면 이 예제에서는 182182가 되어 목표와 달라진다. 이는 인덱스 확인을 위한 추가 벡터 계산이다.

10. 회전 횟수는 얼마나 줄어드는가

10.1 원문의 15회에서 6회, 255회에서 30회

n=bgn=bg일 때 필요한 작은 회전은 b−1b-1회, 큰 회전은 g−1g-1회다. 따라서

BSGS 회전 수=b+g−2=b+nb−2.\boxed{\text{BSGS 회전 수}=b+g-2=b+\frac nb-2}.

평문 곱은 여전히 nn회다. 덧셈은 블록 내부와 블록 사이를 합쳐

g(b−1)+(g−1)=n−1g(b-1)+(g-1)=n-1

회다. 모든 대각선 항이 있는 구성에서, 필요한 직접 회전키를 갖췄다고 가정한 횟수다.

구성기본작은 회전큰 회전합계
n=16n=16
b=g=4b=g=4
1515333366
n=28n=2^8
b=g=16b=g=16
255255151515153030

이것이 원문 41쪽의 255→30255\to30, 42쪽 필기의 15→615\to6이다. 첫 구성의 바깥 회전량은 4,8,124,8,12이며, 원본인 00칸은 세지 않는다.

10.2 블록을 제곱근 크기로 잡는 이유

원문 마지막 필기는 산술·기하평균 부등식을 적용한다.

b+nb≥2n.b+\frac nb\ge2\sqrt n.

실수 변수로 보면 같아지는 지점은

b=nb,b=n.b=\frac nb,\qquad b=\sqrt n.

따라서 정수 인수 제약 아래에서 b,gb,g를 가능한 한 비슷하게 잡는다. nn이 완전제곱수이고 b=g=nb=g=\sqrt n이면 정확히

2n−22\sqrt n-2

회의 회전으로 계산한다. 완전제곱수가 아닌 경우에는 n=bgn=bg를 만족하는 가까운 인수 쌍을 사용한다. nn이 22의 거듭제곱이면 지수를 가능한 한 반씩 나누면 된다.

회전 수는 O(n)O(n)에서 O(n)O(\sqrt n)으로 줄지만, 평문 곱과 덧셈까지 모두 O(n)O(\sqrt n)개가 되는 것은 아니다. 공개 가중치의 사전 재배열과 작은 회전 결과를 보관하는 작업도 함께 필요하다.

다음 글은 42쪽 오른쪽의 Homomorphic Convolution부터 이어간다. 행렬곱에서 사용한 회전·성분별 곱·합을 이미지의 이웃 값과 커널 가중치에 연결하고, 경계에서 순환한 값이 섞이지 않도록 처리하는 과정을 살펴본다.

Discussion

Comments