FV Scheme
서론
본 포스팅에서는 SHE(Somewhat Practical Fully Homomorphic Encryption) 을 만족하는 FV Scheme 에 대해 설명 하고, 이러한 FV Scheme 을 FHE(Fully Homomorphic Encryption) 으로 전환 하는 방법에 대해 간단하게 소개하며 마치도록 하겠습니다.
Basic Notation
\[\begin{equation} R= \mathbb{Z}[x]/(f(x)),\;f(x)∈\mathbb{Z}[x]\nonumber \end{equation}\]\[\begin{equation} f(x) = x^d + 1 \quad with \quad d= 2^n \nonumber \end{equation}\]기본적으로 FV 는 RLWE 기반으로 동작합니다. 즉, 다항식 Ring 위에서 동작합니다.
\[\begin{equation} \mathbf{a} ∈R ,\quad \mathbf{a}=\sum_{i=0}^{d-1}a_i \cdot x^i\nonumber \end{equation}\]일반적으로 $f(x)$ 는 cyclotomic polynomial 으로 설정하고, $d=2^n$ 로 설정합니다. 이렇게 설정하는 이유는 다항식 연산 시 계산 복잡도를 줄일 수 있기 때문입니다.
\[\begin{gather} ||\mathbf{a}||\;\; is\;defined\;as\;\; max_i|a_i|\nonumber\\ δ_R = max\{||\mathbf{a}·\mathbf{b}||/(||\mathbf{a}||·||\mathbf{b}||):\mathbf{a},\mathbf{b} ∈R\}\nonumber \end{gather}\]$R$ 의 원소는 굵은 소문자로 표시합니다.
$||\mathbf{a}||$ 은 다항식 a 가 가질 수 있는 가장 큰 계수의 크기를 나타냅니다. 그리고 $\delta_R$ 은 곱셈 연산으로 인해 다항식의 크기가 얼마나 증가하는지 나타내는 확장 계수를 의미 합니다.
예를 들어 보겠습니다.
\[\begin{gather} \mathbf{a} = 1+2x+x^2,\;\mathbf{b} = 1+3x+x^2,\;\mathbf{ab}=1+5x+8x^2+5x^3+x^4 \nonumber\\ δ_R = max\{||\mathbf{a}·\mathbf{b}||/(||\mathbf{a}||·||\mathbf{b}||)\} = \frac{8}6\nonumber \end{gather}\]이러한 확장 계수는 추후 노이즈의 범위를 정의하는 데 사용됩니다.
\[\begin{gather} \mathbb{Z}_q : the\;set\;of\;integers\;(-q/2,q/2],\;q>1\;be\;an\;integer\; (not\;be\;confused\;with\;the\;ring\;\mathbb{Z}/q\mathbb{Z})\nonumber\\ \mathbf{R}_q : the\;set\;of\;polynomials\;in\;\mathbf{R}\;with\;coefficients\;in\;\mathbb{Z_q}\nonumber \end{gather}\]\[\begin{gather} χ\text{ is Gaussian distribution on }\mathbf{R}\nonumber\\ \text{A distribution }χ \text{ is called B-bounded if it is supported on [−B,B]}\nonumber \end{gather}\]$\mathbb{Z}_q$ 은 다항식 계수가 가질 수 있는 값의 범위 입니다.
$f(x) = x^d+1,\;d=2^k$ 인 $f(x)$ 를 사용할 때, $χ$ 는 가우시안 분포를 따른다고 합니다. 그리고 $B$ 는 $χ$ 의 범위를 나타낼 때 쓰입니다.
다음 두 가지만 알고 계시면 됩니다.
- $χ$ 는 비밀 키 $\mathbf{s}$ , 에러 $\mathbf{e}$ 등 특정 파라미터 설정에 사용할 무작위 다항식을 추출할 때 사용된다.
- $B$ 는 $\chi$ 에서 추출한 다항식이 최대로 가질 수 있는 계수 값의 범위를 설정할 때 사용된다.
$χ$ 와 $B$는 자주 등장하니 그 때 다시 한 번 설명 하겠습니다.
\[\begin{gather} [\mathbf{a}]_q:\text{다항식 a 의 계수에 mod q 를 한 결과}\nonumber\\ r_q(a):\text{a 를 q 로 나눈 나머지}\nonumber\\ ⌊x⌉:\text{반올림},\;x ∈\mathbb{R}\nonumber\\ ⌊x⌋:\text{버림},\;x ∈\mathbb{R}\nonumber\\ ⌈x⌉:\text{올림},\;x ∈\mathbb{R}\nonumber\\ size(n)=⌈log_2(n+ 0.5)⌉(bit\;size)\nonumber \end{gather}\]마지막으로 자주 사용되는 정의들을 정리 해두었습니다.
RLWE Problem
Definition 1. (Decision-RLWE)
보안 매개 변수 λ 에 대해, $deg(f) = φ(m),\;f(x)\text{ : cyclotomic polynomial}$ , $R= Z[x]/(f(x))$ 라 하자. 또한 $Q= q(λ) ≥2$ , $s ∈R_q$ , $R$ 위의 분포 $χ= χ(λ)$ 에 대해 균일 무작위 요소 $a ←R_q$ 와 노이즈 항 $e ←χ$ 및 출력 $(a,[a\cdot s+e]_q)$ 을 선택하여 얻은 분포를 $A(q) _{s,χ}^q$ 라 하자.
$Decision-RLWE _{d,q,χ}$ 은 분포 $A(q) _{s,χ}^{(q)}$ 와 균일 분포 $U(R^2_q)$ 를 구별하는 문제이다.
결론적으로 $(a,[a \cdot s + e] _q)$ 를 생성하는 $A(q) _{s,χ}^{(q)}$ 와 랜덤한 균일 출력 $U(R^2_q)$ 을 구분할 수 없어야 합니다. 이를 전제로 앞으로의 설명을 진행 하겠습니다. 그리고 $s←R_q$ 대신 $s←χ$ 을 사용해도 보안 상에 문제가 없기에 $s$ 는 $χ$ 에서 추출 합니다. 마지막으로 $q$ 는 꼭 소수일 필요 없이 2의 거듭제곱 형태로 나타낼 수 있으면 됩니다.
Encryption Scheme ($LPR.ES$)
$∆ = ⌊q/t⌋$ , $r _t(q)=\text{q mod t}$ , $t>1$ 일 때 $q=∆\cdot t + r _t(q)$ 이고 $LPR.ES$ 는 다음과 같다.
여기서 $q$ 는 암호문 모듈러스, $t$ 는 평문 모듈러스 입니다.
$LPR.ES.SecretKeyGen(1^\lambda)$
- $s ←χ$ 을 샘플링 후 $sk= s$ 출력
$LPR.ES.PublicKeyGen(sk)$
- $s = sk$ 라 하고, $a ←R _q$, $e ←χ$ 를 샘플링 후 $pk = ([−(a·s + e)] _q,\;a)$ 출력
$LPR.ES.Encrypt(pk,m)$
- $\mathbf{m} \in R_t \;,\;p_0 = pk[0]$, $p_1 = pk[1]$ 라 할 때 $u,e1,e2 ←χ$ 을 샘플링 하여 $ct = ([p_0·u + e1 + ∆·m]_q,\;[p_1·u + e2]_q)$ 을 출력
$LPR.ES.Decrypt(sk,ct)$
\[\left[\left\lfloor \frac{t \cdot [c_0+c_1 \cdot s]_q}{q} \right\rceil\right]_t\]- $s = sk, \;c_0 = ct[0], \;c_1 = ct[1]$ 일 때 $LPR.ES.Encrypt$ 에서 출력하는 $ct$ 와 비밀 키 $\mathbf{s}$ 을 통해 $\mathbf{c}_0 + \mathbf{c}_1 \cdot \mathbf{s}$ 형태의 다항식을 만들고, 각 계수에 $t/q$ 을 곱한 후 반올림 한 다음 $mod \;t$ 하여 평문을 복구
아래 Lemma 1 을 통해 $LPR.ES$ 스킴을 통해 $LPR.ES.Decrpyt$ 과정을 자세히 살펴보겠습니다.
Lemma 1.
\[\begin{equation} [\mathbf{c}_0+\mathbf{c}_1 \cdot s] _q = \Delta \cdot \mathbf{m} + \mathbf{v}\label{eq:num1} \end{equation}\]$LPR.ES$ 의 암호문에 대해 ${||\chi|| < B}$ , ${||\mathbf{v}|| \leq 2 \cdot \delta _R \cdot B^2 + B}$ 일 때
$2\cdot\delta _R\cdot B^2 + B < \Delta/2$ 이면 올바른 복호화가 이루어진다.
Lemma 1 에 따르면 $2\cdot\delta _R\cdot B^2 + B < \Delta/2$ 를 만족할 때 decryption 이 제대로 동작하게 됩니다.
Optimisation & Assumption 1
$\mathbf{s},\mathbf{u}\leftarrow\chi$ 의 추출 방식 대신 $\mathbf{s},\mathbf{u} \leftarrow \mathbf{R}_2, ||\mathbf{s}||=||\mathbf{u}||=1$ 인 다항식 $\mathbf{s}, \mathbf{u}$ 를 사용합니다. 또한 $\mathbf{s}$ 의 계수는 ${0,1}$ 로 설정합니다. 그렇게 되면 $||\mathbf{e} \cdot \mathbf{u}|| \text{ and } ||\mathbf{e}_2 \cdot \mathbf{s}|| \le \delta_R \; , \; ||\mathbf{e}_1|| \le B$ 이 되므로 $\eqref{eq:num1}$ 의 노이즈 범위를 ${||\mathbf{v}|| \leq 2 \cdot \delta _R \cdot B + B}$ 로 줄일 수 있습니다.
또한 앞으로 $\mathbf{s}$ 의 Hamming Weight 를 $h$ 라고 정의합니다. Hamming Weight 는 다항식 $\mathbf{s}$ 의 계수 중 값이 1인 항의 개수를 의미 합니다. 계수가 1인 항은 곱셈 연산 시 노이즈 증가율에 영향을 미치므로, $h$ 를 작게 설정할 수 있다면 노이즈의 증가 크기를 제한할 수 있습니다. 일반적으로 $d$ 차 다항식에서 특정 $h$ 를 가진 비밀 키를 충분히 많이 생성할 수 있다면, 작은 $h$ 로도 보안성을 유지할 수 있다고 알려져 있습니다.
Somewhat Homomorphic Encryption
이제 SHE Scheme 인 $FV.SH$ 을 유도 해보겠습니다. 크게 보았을 때 덧셈, 곱셈, 재선형화 총 3 가지의 과정이 추가됩니다. 이 과정을 통해 보이려고 하는 것은 암호화 된 상태에서 연산을 진행하고 난 후 원래 평문의 복구 여부 입니다. FV.SH 은 RLWE 을 기반으로 한 $LPR.ES$ 을 이용하여 유도 합니다.
먼저 필요한 용어를 정의 하겠습니다. $\eqref{eq:num1}$ 에서 $c_0+c_1 \cdot s = ct(s)$ 라 하면 아래 식이 성립합니다.
\[[ct(s)]_q=\Delta \cdot \mathbf{m} + \mathbf{v}\nonumber\]- $ct = ([p_0·u + e1 + ∆·m]_q,\;[p_1·u + e2]_q)$ 과 헷갈리지 않도록 주의. $ct(s)$ 는 $c_0=ct[0],c_1=ct[1]$ 을 계수로 가지는 $\mathbf{s}$ 에 대한 다항식을 의미함.
$ct(s)$ 을 정의한 이유는 $c_0+c_1 \cdot s$ 형태의 식을 사용하면 $\Delta \cdot \mathbf{m} + noise$ 형태가 되고, 결과로 평문이 포함된 다항식을 얻을 수 있기 때문입니다. $ct$ 자체로는 유의미한 정보를 얻을 수 없기 때문에 앞으로 나올 내용에서 $ct(s)$ 를 주로 사용할 예정입니다.
이제 두 개의 다른 암호문에 대한 $ct_1(s),ct_2(s)$ 을 선언하고, 덧셈 스킴인 $FV.SH.Add$ 와 곱셈 스킴인 $FV.SH.Mul$ 이 암호화 된 상태에서 연산 후에도 원래의 평문을 복구 할 수 있다는 것을 보이겠습니다.
Addition
\[\begin{align} [ct_1(s)+ct_2(s)]_q &=\Delta \cdot \mathbf{m_1} + \mathbf{v_1} + \Delta \cdot \mathbf{m_2} + \mathbf{v_2} \label{eq:num4} \\ &=\Delta \cdot [\mathbf{m}_1 + \mathbf{m}_2]_t + \mathbf{v}_1 + \mathbf{v}_2 + \Delta \cdot t \cdot \mathbf{r} \; mod\;q\nonumber \\ &=\Delta \cdot [\mathbf{m}_1 + \mathbf{m}_2]_t + \mathbf{v}_1 + \mathbf{v}_2 + \cancel{q \cdot \mathbf{r}} - (q/t - \Delta) \cdot t \cdot \mathbf{r} \nonumber \\ note : \mathbf{m}_1 &+ \mathbf{m}_2=[\mathbf{m}_1 + \mathbf{m}_2]_t+t \cdot \mathbf{r}\;,\;||\mathbf{r}||\le1\;,\;q/t-\Delta<1 \nonumber \end{align}\]$\eqref{eq:num4}$ 는 두 개의 암호문에 대한 $ct_1(s),ct_2(s)$ 을 더한 결과입니다. 여기서 덧셈 연산의 결과로 따라 평문 모듈러스인 $t$ 가 등장합니다. 이 때 $\mathbf{v}_1 + \mathbf{v}_2 + \Delta \cdot t \cdot \mathbf{r}$ 은 새로운 노이즈가 되고, 노이즈의 범위가 $\Delta/2$ 보다 작다면 원래의 평문을 복구할 수 있습니다. 여기서 주목할 점은 최악의 경우 덧셈을 진행할 때마다 노이즈는 대략 평문 모듈러스인 $t$ 만큼 증가한다는 점 입니다. 보통 $||\mathbf{v}_1||=||\mathbf{v}_2||« ||t||$ 이고 $||t|| « ||q||$ 이기 때문에 덧셈의 경우는 노이즈가 급격하게 증가하지 않습니다. 하지만 곱셈의 경우는 다릅니다. 아래에서 자세히 살펴 보겠습니다.
Multiplication
곱셈 연산은 생각보다 복잡합니다. 덧셈 연산과 달리, 연산이 진행됨에 따라 최악의 경우 노이즈의 크기가 $t^2$ 배 정도로 커지기 때문입니다. 뿐만 아니라 $ct(s)=c_0+c_1 \cdot s$ 형태의 암호문을 계속해서 곱하면 암호문의 크기도 제곱 형태로 커지게 됩니다. 따라서 $ct_1(s),ct_2(s)$ 에 대한 단순 곱셈 후, 노이즈의 증가율을 $t$ 배 정도로 줄이는 과정인 Basic Multiplication 과 계속해서 커지는 암호문의 크기를 $s $ 에 대한 일차식으로 줄이는 Relinearisation 과정을 차례로 소개 하겠습니다.
Basic Multiplication
\[ct(s)=\Delta \cdot \mathbf{m_i} + \mathbf{v_i} + q \cdot \mathbf{r}_i\nonumber\]모듈러 q 를 취하기 전 상태의 $ct(s)$ 를 위와 같이 표기할 수 있습니다. 이 때 $\mathbf{r}$ 은 $\eqref{eq:num4}$ 에서와 마찬가지로 계수가 {-1, 0, 1} 인 다항식 입니다. 이제 실제로 암호문 곱셈을 해보겠습니다.
\[\begin{align} (ct_1 \cdot ct_2)(s) = &\Delta^2 \cdot \mathbf{m_1} \cdot \mathbf{m_2} + \Delta \cdot (\mathbf{m_1} \cdot \mathbf{v_2} + \mathbf{m_2} \cdot \mathbf{v_1}) + \mathbf{v_1} \cdot \mathbf{v_2} \label{eq:num5} \\ &+ q \cdot \Delta \cdot (\mathbf{m_1} \cdot \mathbf{r_2} + \mathbf{m_2} \cdot \mathbf{r_1}) + q \cdot (\mathbf{v_1} \cdot \mathbf{r_2} + \mathbf{v_2} \cdot \mathbf{r_1}) + q^2 \cdot \mathbf{r_1} \cdot \mathbf{r_2}\nonumber \end{align}\]이 상태에서 바로 decryption 을 진행할 수는 없습니다. decryption 을 진행하기 위해서는 $\eqref{eq:num5}$ 의 식을 $\Delta$ 로 나누어야 합니다. 그런데 $\Delta$ 가 포함되지 않은 항 들을 $\Delta$ 로 나누게 되면 $mod\;q$ 가 의도한 대로 동작하지 않아 decryption 에 문제가 생깁니다. 따라서 $\Delta$ 로 나누는 대신, 모든 항을 $t/q$ 로 나누겠습니다.
\[\begin{align} \frac{t \cdot (ct_1 \cdot ct_2)(s)}{q} &= \Delta \cdot [\mathbf{m_1} \cdot \mathbf{m_2}]_t + (\mathbf{m_1} \cdot \mathbf{v_2} + \mathbf{m_2} \cdot \mathbf{v_1}) + t \cdot (\mathbf{v_1} \cdot \mathbf{r_2} + \mathbf{v_2} \cdot \mathbf{r_1})\label{eq:num6} \\ &+ \mathbf{r_v} + (q - r_t(q)) \cdot (\mathbf{r_m} + \mathbf{m_1} \cdot \mathbf{r_2} + \mathbf{m_2} \cdot \mathbf{r_1}) + q \cdot t \cdot \mathbf{r_1} \cdot \mathbf{r_2} \nonumber \\ &+ \frac{t}{q} \cdot [\mathbf{v_1} \cdot \mathbf{v_2}]_\Delta - \frac{r_t(q)}{q} \cdot (\Delta \cdot \mathbf{m_1} \cdot \mathbf{m_2} + (\mathbf{m_1} \cdot \mathbf{v_2} + \mathbf{m_2} \cdot \mathbf{v_1}) + \mathbf{r_v})\nonumber \\ \nonumber\\ ¬e : \mathbf{m}_1 \cdot \mathbf{m}_2 = [\mathbf{m}_1 \cdot \mathbf{m}_2]_t + t \cdot \mathbf{r}_m \nonumber \\ &\;\;\;\qquad \mathbf{v}_1 \cdot \mathbf{v}_2 = [\mathbf{v}_1 \cdot \mathbf{v}_2]_\Delta + t \cdot \mathbf{r}_v \nonumber\\ &\;\;\;\qquad t \cdot\Delta=q-r_t(q)\nonumber\\ \end{align}\]식이 조금 복잡해 보이는데요. $\eqref{eq:num5}$ 의 식에 $t/q$ 를 곱하고, $t \cdot\Delta$ 대신 $q-r_t(q)$ 를 대입하여 전개하면 됩니다. 이 식은 $q/t - \Delta = r_t(q)/t$ 에서 유도할 수 있습니다.
$\eqref{eq:num6}$ 에서 노이즈 증가에 가장 큰 영향을 미치는 항은 어느 부분일까요? 곱셈 연산이 가장 많이 일어나는 항을 살펴보면 됩니다.
\[t \cdot (\mathbf{v_1} \cdot \mathbf{r_2} + \mathbf{v_2} \cdot \mathbf{r_1})\nonumber\]$\eqref{eq:num1}$ 에서 $\mathbf{v}$ 는 $\mathbf{s}$ 에 대한 일차 다항식이라고 했습니다. 따라서 $||\mathbf{v}_1 \cdot \mathbf{r}_2||=||\mathbf{v}_2 \cdot \mathbf{r}_1||\le\delta_R \cdot ||\mathbf{s}||$ 이고, $t \cdot ||\mathbf{v}_1 \cdot \mathbf{r}_2||=t \cdot||\mathbf{v}_2 \cdot \mathbf{r}_1||\le t \cdot \delta_R$ 이 됩니다. 따라서 Basic Multiplication 을 진행한 후의 노이즈 최대 크기는 $2 \cdot t \cdot \delta_R^2 \cdot ||\mathbf{s}||$ 정도로 볼 수 있습니다. 이제 전체 내용을 아래 Lemma 2 에서 정리 하겠습니다.
Lemma 2.
$[ct_i(s)]_q=\Delta \cdot \mathbf{m}_i+\mathbf{v}_i$ , $ct_1(s) \cdot ct_2(s)=\mathbf{c}_0+\mathbf{c}_1 \cdot \mathbf{s} + \mathbf{c}_2 \cdot \mathbf{s}^2$ 라 할 때
$\left[\left\lfloor \frac{t \cdot c_0}{q} \right\rceil + \left\lfloor \frac{t \cdot c_1}{q} \right\rceil \cdot s + \left\lfloor \frac{t \cdot c_2}{q} \right\rceil \cdot s^2 \right]_q = \Delta \cdot [\mathbf{m_1} \cdot \mathbf{m_2}]_t + \mathbf{v}_3$ 라 하고 $||\mathbf{v}_3|| \le 2 \cdot t \cdot \delta_R^2 \cdot ||\mathbf{s}|| < \Delta/2$ 이면 올바른 복호화가 이루어진다.
Lemma 2 를 보면 덧셈 연산과는 다르게 $||\mathbf{s}||$ 가 노이즈의 크기에 영향을 미칩니다. 이 때 우리는 Optimisation & Assumption 1 과 같이 $||\mathbf{s}||=1$ 로 설정할 수 있고 곱셈 연산 시 노이즈의 증가율을 $t^2$ 이 아닌 $t$ 정도로 낮출 수 있습니다. 즉, $t^2, t^4 …$ 가 아닌 $t,t^2,t^3…$ 형태로 노이즈의 증가율을 억제할 수 있습니다.
Relinearisation
\[[\mathbf{c}_0+\mathbf{c}_1 \cdot \mathbf{s} + \mathbf{c}_2 \cdot \mathbf{s}^2]_q = [\mathbf{c'}_0+\mathbf{c'}_1\cdot \mathbf{s} + \mathbf{error}]_q \; , \; \text{error is small}\nonumber\]Lemma 2 를 이용하면 곱셈 연산 후에도 올바른 평문을 복구할 수 있습니다. 하지만 아직 암호문의 크기가 제곱 크기로 커진다는 문제가 남아 있습니다. 이 문제를 해결하기 위해서는 적절한 $\mathbf{c’}_0, \mathbf{c’}_1$ 을 설정하여 곱셈 연산을 진행한 결과가 항상 $\mathbf{s}$ 에 대한 일차 다항식 꼴로 나오게 하면 됩니다. 이러한 기법을 Relinearisation 이라 합니다. Relinearisation 을 수행하기 위해 재선형화 키 $rlk$ 을 공개하여 공개 키로 사용합니다
\[\begin{equation} rlk=([-(\mathbf{a}_0 \cdot \mathbf{s} + \mathbf{e}_0) + \mathbf{s}^2]_q\;,\;\mathbf{a}_0)\;,\; \mathbf{a}_0 \leftarrow R_q \;,\; \mathbf{e}_0 \leftarrow \chi \label{eq:num7} \end{equation}\]$rlk$ 는 $\eqref{eq:num7}$ 과 같이 사용합니다. 만약 $[\mathbf{c}_0+\mathbf{c}_1 \cdot \mathbf{s} + \mathbf{c}_2 \cdot \mathbf{s}^2]_q$ 을 계산해야 하는 상황이라면, $\mathbf{c}_2 \cdot \mathbf{s}^2$ 을 계산하는 대신 $rlk$ 을 이용하여 $rlk[0]+rlk[1] \cdot \mathbf{s} = \mathbf{s}^2+\mathbf{e}_0$ 을 계산합니다. 그 다음 이 결과에 $\mathbf{c}_2$ 를 곱하여 $\mathbf{c}_2 \cdot \mathbf{s}^2 + \mathbf{c}_2 \cdot \mathbf{e}_0$ 라는 결과를 얻습니다. 이렇게 하면 이차 항에 대한 계산을 하지 않으면서 이차 다항식을 연산한 결과를 얻을 수 있습니다.
다만 이 과정에는 문제점이 존재하는데, $\mathbf{error} = \mathbf{c}_2 \cdot \mathbf{e}_0$ 의 값이 너무 커지면 이 부분에 mod q 가 진행되어 복호화가 제대로 되지 않을 수 있습니다. 따라서 $\mathbf{c}_2 \cdot \mathbf{s}^2$ 항을 얻을 수 있으면서 $\mathbf{c}_2 \cdot \mathbf{e}_0$ 가 mod q 되지 않는 재선형화 키를 사용해야 합니다. 이러한 공개 재선형화 키는 두 가지 버전이 있으며, 차례로 설명 하겠습니다.
Version 1
Version 1 에서는 $\mathbf{c}_2$ 의 값을 작은 단위로 쪼개어 계산하는 기법을 이용합니다. 예를 들어보겠습니다. \(\begin{align} 3 \cdot s &= (0011)_2 \cdot s = (2^0 \cdot 1 + 2 ^1 \cdot 1) \cdot s \nonumber \\ 23 \cdot s &= (23)_{10} \cdot s = (10^0 \cdot 3 + 10^1 \cdot 2) \cdot s \nonumber \end{align}\)
위 계산을 진법에 따라 쪼개어서 계산해도 결과는 같습니다. 이를 조금 더 일반화 해보겠습니다.
\[\begin{equation} \mathbf{c_2} \cdot \mathbf{s}^2=\mathbf{s}^2 \cdot \sum_{i=0}^l T^i \cdot \mathbf{c}_2^{(i)}\;mod\;q\;,\;l=\lfloor log_T(q)\rfloor \label{eq:num8} \end{equation}\]$T$ 는 베이스를 의미하고, $\mathbf{c}_2$ 는 베이스에 맞게 적절히 쪼개어 나타낸 값입니다. 이해하기 쉽게 $T=2$ 를 대입해보면 Bit Decomposition 의 동작과 같게 됩니다. 이제 이 기법을 이용하여 $rlk$ 을 생성 하겠습니다.
\[rlk=[\;([-(\mathbf{a}_i \cdot \mathbf{s} + \mathbf{e}_i) + T^i \cdot \mathbf{s}^2]_q\;,\;\mathbf{a}_i):i \in[0...l] \;]\nonumber\]$\eqref{eq:num8}$ 의 우변에서 $T^i, \mathbf{s}^2$ 을 분리하여 $l + 1$ 개의 공개 재선형화 키에 포함합니다.
이제 $\mathbf{c’}_0, \mathbf{c’}_1$ 을 설정합니다.
\[\begin{align} \mathbf{c'}_0 &=\left[ \mathbf{c}_0 + \sum_{i=0}^lrlk[i][0] \cdot \mathbf{c}_2^{(i)}\right]_q\;,\; \nonumber \\ \mathbf{c'}_1 &=\left[ \mathbf{c}_1 + \sum_{i=0}^lrlk[i][1] \cdot \mathbf{c}_2^{(i)}\right]_q \nonumber \end{align}\]이를 이용하여 $\mathbf{c’}_0+\mathbf{c’}_1\cdot \mathbf{s}$ 을 나타내보면 다음과 같습니다.
\[\mathbf{c'}_0+\mathbf{c'}_1\cdot \mathbf{s} = \mathbf{c}_0+\mathbf{c}_1 \cdot \mathbf{s} + \mathbf{c}_2 \cdot \mathbf{s}^2 - \sum_{i=0}^l\mathbf{c}_2^{(i)} \cdot \mathbf{e}_i\;mod\;q \nonumber\]이제 $\mathbf{error}=\sum_{i=0}^l\mathbf{c}_2^{(i)} \cdot \mathbf{e}_i\;mod\;q$ 가 되고, $T$ 값을 조절함으로써 $\mathbf{error} = \mathbf{c}_2 \cdot \mathbf{e}_0$ 에 비해 에러의 크기를 낮출 수 있습니다.
Version 2
Version 1 은 $\mathbf{error}$ 의 크기를 줄일 수 있었지만 다수의 재선형화 키를 생성하여 여러 번의 연산을 하므로 복잡도가 증가한다는 문제가 있습니다. 따라서 Version 2 에서는 하나의 재선형화 키를 이용하여 적은 계산으로 $\mathbf{c}_2 \cdot \mathbf{e}_0$ 가 mod q 되는 상황을 방지합니다. Version 1 과의 차이점은 $modulo\;q$ 가 아닌 $modulo\;p \cdot q$ 에서 연산 후, 다시 $modulo\;q$ 로 낮추어 계산한다는 점 입니다. 이는 일종의 Modulus Switching 으로 볼 수 있습니다.
\[\begin{equation} rlk=([-(\mathbf{a} \cdot \mathbf{s} + \mathbf{e}) + p \cdot \mathbf{s}^2]_{p \cdot q}\;,\;\mathbf{a}) \;,\; \mathbf{a} \leftarrow R_{p \cdot q} \; , \; \mathbf{e} \leftarrow \chi' \label{eq:num9} \end{equation}\]$\eqref{eq:num9}$ 에서 $\mathbf{e}$ 의 값을 $\chi$ 가 아닌 $\chi’$ 에서 추출 하는 이유는 $\chi=\chi’$ 일 때는 보안성을 잃을 수 있기 때문입니다. 따라서 $\chi’$ 은 기존 $\chi$ 와는 다른 가우시안 분포를 따릅니다. 이제 $\eqref{eq:num9}$ 을 이용하여 $\mathbf{c}_2 \cdot \mathbf{s}^2$ 의 값을 나타내어 보겠습니다.
\[\begin{gather} \mathbf{c'}_0 = \mathbf{c}_0 + \left[\left\lfloor \frac{\mathbf{c}_2 \cdot rlk[0]}p \right\rceil\right]_q \; , \; \mathbf{c'}_1 = \mathbf{c}_1 + \left[\left\lfloor \frac{\mathbf{c}_2 \cdot rlk[1]}p \right\rceil\right]_q \nonumber \\ \mathbf{c'}_0+\mathbf{c'}_1\cdot \mathbf{s} = \mathbf{c}_0+\mathbf{c}_1 \cdot \mathbf{s} + \mathbf{c}_2 \cdot \mathbf{s}^2 + \mathbf{error} \;,\; \mathbf{error}= \left[\left\lfloor\frac{\mathbf{c}_2 \cdot (-\mathbf{e})} p \right\rceil\right]_q \;,\; p >> q \nonumber \end{gather}\]Version 1 에 비해서는 훨씬 간단한 연산으로 암호문의 크기를 줄일 수 있습니다.
요약하자면
- Version 1 : 비교적 작은 모듈러스 $q$ 에서 비교적 많은 연산
- Version 2 : 비교적 큰 모듈러스 $p \cdot q$ 에서 비교적 적은 연산
이라는 특징이 있습니다. 실제 동형암호 에서는 두 가지 버전을 함께 사용하여 최적화를 합니다.
Fully Homomorphic Encryption
앞서 설명한 $FV.SH$ 스킴은 제한된 조건 안에서 동형성을 보장합니다. 제한된 조건이라 함은 노이즈의 크기가 일정 크기 이하가 되어야만 복호화가 성공적으로 수행된다는 것입니다. 그런데 만약 덧셈, 혹은 곱셈 연산을 계속해서 수행하게 되면, 기존 노이즈의 크기가 아무리 작더라도 연산 후 전체 노이즈의 합은 계속해서 증가하게 될 것입니다. 따라서 완전 동형암호 스킴 FHE 를 만족하도록 하려면 매 번 연산이 진행될 때 마다 노이즈의 크기를 일정 크기 이하로 유지해야 합니다.
암호문 속 노이즈의 크기를 줄이기 위해서는 암호문 $ct$ 를 복호화 한 후, 노이즈를 제거한 다음 새로운 에러 $e$ 와 함께 암호화를 하여 에러의 크기를 줄이는 방식을 사용할 수 있습니다. 다만 이 방법을 사용하게 되면 동형암호화를 하는 이유가 없어지게 됩니다. 따라서 암호문 $ct$ 의 암호화를 유지한 상태에서 노이즈를 제거 하는 방법이 필요합니다. 이 때 사용되는 기법을 $boostrapping$ 이라고 합니다.
$bootstrapping$ 에 대해서는 추후 자세히 다루도록 하겠습니다.