IHHI's profile image

IHHI

February 21, 2025 00:00

Introduction

안녕하세요. 이전 글에서는 TFHE라는 동형암호를 다루기 위한 기본적인 암호화, 복호화와 덧셈 연산이 어떻게 이루어지는지를 알아보았습니다. 이번 글에서 다루는 주제는 동형암호는 맞으나 TFHE는 아닌데요. 이는 TFHE scheme 중간에 등장하게 되는 개념인 GGSW sample이라는 개념이 바로 지금 제가 다루고자 하는 동형암호인 GSW scheme[1] 에서 가져온 것이기 때문에, 중간에 한 번 쉬어가더라도 GSW scheme과 gadget이라는 개념을 다루고 가는 것이 도움이 될 것이라 생각해서 GSW scheme에 대한 글을 먼저 쓰게 되었습니다.

동형암호의 개념 자체에 대해 생소하신 분이라면 먼저 저의 저번 글 이나 cs71107님이 동형 암호의 개념에 대해서만 집중적으로 설명해 주신 글을 참고하시기 바랍니다.

GSW scheme은 이 scheme을 처음 제안한 저자 3명의 이름인 Gentry, Sahai, 그리고 Waters의 이름을 따서 붙인 이름입니다. 사실 TFHE가 특수한 경우라고 볼 수 있는 것이, 다른 동형암호 scheme들(BFV, BGV, CKKS) 등도 전부 저자들의 이름 나열로 붙여진 이름이기 때문입니다. 이 scheme은 2013년에 처음 제안되었는데, Gentry(위에 나온 GSW의 저자 중 1명이 맞습니다!)가 bootstrapping의 개념을 제안하면서 동형암호가 실질적으로 가능함을 보인 논문이 2009년도에 나왔으니 상당히 초기 scheme에 해당하고 그런 만큼 상당히 단순해 TFHE와는 다르게 글 하나로 설명해 보고자 합니다.

Backgrounds

LWE Problem

GSW도 다른 모든 동형암호와 동일하게 격자 암호 기반으로, LWE 문제에 기반을 두고 있습니다. 저번 글에서는 LWE와 RLWE에 대해 모두 설명했는데, GSW가 나온 시점과 RLWE가 제안된 시점이 publish 된 시점 기준 전부 2013년으로, 크게 차이가 나지 않습니다. 이러한 이유로 GSW는 RLWE 기반이 아닌 LWE 기반 암호입니다.

LWE(Learning With Errors) 문제는 $n$, $m$, $q$, $\chi_s$, $\chi_e$ 가 주어졌을 때, 다음의 두 분포를 구분할 수 있는지 묻는 문제입니다.

• $(A, A\vec{s} + \vec{e}) \quad \text{where} \quad A \xleftarrow{$} \mathbb{Z}_q^{n\times m}, \vec{s} \leftarrow \chi_s^m, \vec{e} \leftarrow \chi_e^n$
• $(A, \vec{u}) \quad \text{where} \quad A \xleftarrow{$} \mathbb{Z}_q^{n\times m}, \vec{u} \xleftarrow{$} \mathbb{Z}_q^n$

이는 양자컴퓨터로도 효율적으로 푸는 방법이 현재 알려지지 않았습니다.

Gadget

GSW의 핵심 아이디어는 바로 gadget을 이용하는 것이라고 할 수 있습니다! 우선 gadget의 정의부터 보여드린 뒤, 이에 대한 설명을 하겠습니다.

$\vec{g} = (g_i) \in \mathbb{Z}^d$ 가 있을 때,

어떤 계산하기 쉬운 decomposition $g^{-1} : \mathbb{Z}_q \rightarrow \mathbb{Z}^d_q$가 있어서,

어떤 정수 bound $B$에 대해서

\[\forall a, \|g^{-1}(a)\|_{\infty} < B, \langle \vec{g},g^{-1}(a) \rangle = a\]

를 만족한다면, $\vec{g}$ 를 gadget vector라고 하고, $g^{-1}$을 gadget decomposition이라고 합니다.

표기를 조금 설명해 드리자면 여기서 $||\cdot||_{\infty}$는 infinity norm, $\langle \cdot, \cdot \rangle$은 내적입니다.

위의 정의만 보고는 정확히 어떠한 것들을 gadget vector, gadget decomposition이라고 부르고 싶은지가 좀 명시적으로 다가오지 않을 수 있습니다. 주목해야 할 부분은, 바로 $||g^{-1}(a)||_{\infty} < B$ 인데요, 어떤 수가 들어오든 간에 정해진 bound $B$ 이하의 수들로만 이루어진 벡터로 이 수를 나타낼 수 있다는 점이 gadget의 강력함입니다.

이러한 gadget이 굉장히 찾기 어려울 것이라고 생각할 수 있으나, 사실은 그렇지 않습니다! 바로 2진법으로 나타내는 것만으로도 간단하게 gadget이 되기 때문이죠. 그것도 $B=1$이라는 굉장히 강력한 조건으로 말이죠! 이를 binary gadget이라고 부릅니다.

$\vec{g} = (1, 2^1, 2^2, \ldots, 2^{d - 1})$으로 정의하고, $g^{-1}$을 2진법으로 주어진 수를 나타내는 것으로 정의하면, gadget의 모든 조건을 만족함을 확인할 수 있습니다.

예를 들어서, $d=3$인 단순한 예시를 보여드리겠습니다. $a = 5$ 를 gadget decompose 한 벡터는 $g^{-1}(a) = (1, 0, 1)$이 되고, $\vec{g} = (1, 2, 4)$ 이므로 내적하게 되면 $\langle \vec{g},g^{-1}(a) \rangle = 1 \cdot 1 + 2 \cdot 0 + 4 \cdot 1 = 5$로 올바른 복원이 됩니다.

비슷하게 N진법으로도 gadget을 만들 수도 있고, 중국인의 나머지 정리를 이용한 gadget도 있으나, 이는 GSW scheme에서는 참고 사항 정도로만 생각하면 됩니다!

사실, 2013년에 써진 GSW 논문에서는 gadget이라는 단어가 단 한 번도 등장하지 않습니다! 대신 binary gadget에 대해서만 다른 이름(Powersof2, BitDecomp) 으로 부르며, binary gadget만을 사용합니다. 이후 다른 scheme에서도 자연스럽게 사용하는 개념이 되면서, 나중에 이름이 붙여진 것이라고 볼 수 있겠습니다. 따라서 만약 gadget에 대한 종합적인 이해가 어려우셨다면, 예시로 말씀드린 binary gadget만 생각하고 이 글을 읽어도, 원본 논문의 내용 정도는 이해할 수 있는 것입니다.

아직은 이 gadget이 어떤 면에서 유용한 것인지 감이 잘 잡히지 않을 수 있는데, 우선 gadget이 없이 GSW와 비슷한 scheme을 만드는 시도를 해본 뒤에, 왜 이 접근이 문제가 되는지 파악해 보고 gadget을 도입해서 해결하는 방식으로 gadget의 유용성을 보여드리고자 합니다.

Gadget Matrix

추가적인 notation으로, gadget matrix를 설명하고자 합니다.

\[G_n = \vec{g} \otimes I_n = \begin{bmatrix} 1\\ 2\\ \vdots\\ 2^{d-1} \\ &1\\ &2 \\&\vdots \\& 2^{d-1} \\ &&\ddots \\ &&& 1 \\&&& 2 \\&&& \vdots \\&&&2^{d-1} \end{bmatrix} \in \mathbb{Z}_q^{(nd) \times n}\]

으로 정의됩니다. 여기서 $\otimes$는 텐서곱이고, binary gadget에 대해서 그 결과를 오른쪽에 풀어서 행렬로 나타내었습니다. 비워진 부분은 0으로 채워진 부분이고, 일반적인 gadget에 대한 이해가 필요하지 않으신 분은 오른쪽처럼 생긴 matrix라고 생각하시면 됩니다. gadget vector가 하나의 수를 gadget decomposition 한 뒤에 복원하기 위해 곱해주는 vector라면, gadget matrix는 matrix를 gadget decomposition 한 뒤에 복원하기 위해 곱해주는 matrix입니다.

여기서 matrix의 gadget decomposition은 단순히, 각 원소의 gadget decomposition한 값을 이어 붙여 만든 matrix가 되고, $G^{-1}$로 나타냅니다.

예를 들어서, $d = 3$인 binary gadget에 대해서

\[C = \begin{bmatrix}1&2\\3&4\end{bmatrix}\]

라면

\[G^{-1}(C) =\begin{bmatrix}1&0&0&0&1&0\\1&1&0&0&0&1\end{bmatrix}\]

이 됩니다.

\[G^{-1}(C) \cdot G_2 =\begin{bmatrix}1&0&0&0&1&0\\1&1&0&0&0&1\end{bmatrix} \cdot \begin{bmatrix}1&0\\2&0\\ 4& 0\\ 0& 1\\ 0& 2\\ 0& 4\end{bmatrix} = \begin{bmatrix}1&2\\3&4\end{bmatrix} = C\]

임을 확인할 수 있습니다.

Naive GSW

위에서 이야기한 대로, gadget을 이용하지 않고 GSW와 동일한 기능을 하는 scheme을 한번 만들어봄으로써, GSW에서 gadget의 중요성을 이야기해 보고자 합니다.

1-bit message $\mu \in {0, 1}$를 암호화해 봅시다. 이는 LWE를 통해서 단순하게 할 수 있습니다. secret key $\vec{s} \leftarrow \chi_s^n$ 로 설정해 준 뒤,

$B \xleftarrow{$}\mathbb{Z}_q^{m \times n}$ $, \vec{e} \leftarrow \chi_e^m$ 를 분포에서 뽑고, $\vec{b} := B\vec{s} + \vec{e}$, $A := [B|\vec{b}] \in \mathbb{Z}_q^{m \times (n + 1)}$ 으로 정해줍니다. 여기서 LWE Problem의 어려움에 의해서, $\vec{b}$는 $\mathbb{Z}_q^m$에서의 uniform random한 벡터와 구분하기 어렵습니다. 따라서 $A$ 또한 $\mathbb{Z}_q^{m \times (n + 1)}$에서의 uniform 분포와 구분하기 어렵습니다.

$\vec{t} = (-s_1, -s_2, \ldots, -s_n, 1) \in \mathbb{Z}_q^{n + 1}$ 으로 정의해주면, $A \cdot \vec{t} = -B\vec{s} + \vec{e} + \vec{b} = \vec{e} \approx 0$ 이게 됩니다.

$m = n + 1$로 설정해 주면, $A$에 $\mu$를 더하기 위해서 identity matrix와 곱해준 뒤, 즉 $\mu \cdot I_{n + 1}$를 계산해 준 뒤에 $C = A + \mu \cdot I_{n + 1}$으로 암호화가 가능합니다. $A$가 uniform 분포와 구분하기 어렵기 때문에, 더해진 Ciphertext 또한 uniform 분포와 구분하기 어려워 보안성을 달성합니다.

\[C \cdot \vec{t} = (A + \mu \cdot I_{n + 1}) \cdot \vec{t} = A \cdot \vec{t} + \mu \cdot \vec{t} =\mu \cdot \vec{t} + \vec{e}\]

이므로, $\mu_1$ 을 암호화해서 얻은 암호문 $C_1$, $\mu_2$를 암호화해서 얻은 암호문 $C_2$가 있다고 하면, 다시 말해서

\[C_i \cdot \vec{t} = \mu_i \cdot \vec{t} + \vec{e}_i\]

일 때,

\[C_{+} = C_1 + C_2\] \[C_{\times} = C_1 \cdot C_2\]

로 덧셈과 곱셈에 대한 연산을 암호화된 상태에서도 할 수 있게 됩니다! 이는 쉽게 확인할 수 있습니다.

\[\begin{aligned} C_{+} \cdot \vec{t} &= C_1 \cdot \vec{t} + C_2 \cdot \vec{t} \\&= \mu_1 \cdot \vec{t} + \vec{e}_1 + \mu_2 \cdot \vec{t} + \vec{e}_2 \\&= (\mu_ 1 + \mu_2) \cdot \vec{t} + \vec{e}_1 + \vec{e}_2 \end{aligned}\]

와 같이 덧셈에서는 각각의 암호문이 가지고 있는 에러만 더해진 채로 메시지가 더해진 암호문의 형태를 그대로 가지고 있음을 확인할 수 있습니다.

\[\begin{aligned} C_{\times} \cdot \vec{t} &= C_1 \cdot C_2 \cdot \vec{t} \\ &= C_1 \cdot (\mu_2 \cdot \vec{t} + \vec{e}_2) \\ &= C_1 \cdot \vec{t} \cdot \mu_2 + C_1 \cdot \vec{e}_2 \\ &= (\mu_1 \cdot \vec{t} + \vec{e}_1) \cdot \mu_2 + C_1 \cdot \vec{e}_2 \\ &= \mu_1 \cdot \mu_2 \cdot \vec{t} + \vec{e}_1 \cdot \mu_2 + C_1 \cdot \vec{e}_2 \\ \end{aligned}\]

가 되는데, $\mu_1 \cdot \mu_2$ 인 암호문의 형태는 그대로 가지고 있으나, 여기서는 $\vec{e}_2 \cdot C_1$ term이 문제가 됩니다! $C_2 \in \mathbb{Z}_q^{(n + 1) \times (n + 1)}$ 이기 때문에, 에러가 너무 커졌다는 문제가 생기게 됩니다. 이대로는 복호화가 쉽지 않겠죠. 이 부분을 위에서 설명한 gadget으로 해결하게 됩니다!

GSW

이번에는 gadget을 이용해서, 1-bit message $\mu$를 암호화해 봅시다. 초반 과정까지는 동일합니다. secret key $\vec{s} \leftarrow \chi_s^n$ 로 설정해 준 뒤,

$B \xleftarrow{$}\mathbb{Z}_q^{m \times n}$ $, \vec{e} \leftarrow \chi_e^m$ 를 분포에서 뽑고, $\vec{b} := B\vec{s} + \vec{e}$, $A := [B|\vec{b}] \in \mathbb{Z}_q^{m \times (n + 1)}$ 으로 정해줍니다. 여기서 LWE Problem의 어려움에 의해서, $\vec{b}$는 $\mathbb{Z}_q^m$에서의 uniform random한 벡터와 구분하기 어렵습니다. 따라서 $A$ 또한 $\mathbb{Z}_q^{m \times (n + 1)}$에서의 uniform 분포와 구분하기 어렵습니다.

이번에는 $m = d \cdot (n + 1)$로 설정해 줍니다. 여기서 $d$ 는 gadget dimension이고, binary gadget의 경우 $log(q)$ 정도 되는 값이라고 생각하시면 됩니다. Gadget을 이용하기 위해서, 아까보다 dimension이 커지긴 했습니다.

이번에는 message $\mu$를 identity matrix가 아닌, gadget matrix에 곱해서 더해줍니다.

\[C = A + \mu \cdot G_{n + 1}\]

위에서와 동일하게, $A$가 uniform과 구분하기 어렵기 때문에 안전한 암호화라고 할 수 있습니다. $\vec{t} = (-s_1, -s_2, \ldots, -s_n, 1) \in \mathbb{Z}_q^{n + 1}$ 으로 정의해주면,

\[C \cdot \vec{t} = A \cdot \vec{t} + \mu \cdot G_{n + 1} \cdot \vec{t} = \mu \cdot G_{n + 1} \cdot \vec{t} + \vec{e}\]

가 되고, 아까의 naive한 예시와 비교해 보면 메시지에 gadget matrix가 곱해진 것이 큰 차이라고 볼 수 있습니다.

이제 덧셈과 곱셈을 살펴보겠습니다.

$\mu_1$ 을 암호화해서 얻은 암호문 $C_1$, $\mu_2$를 암호화해서 얻은 암호문 $C_2$가 있다고 하면, 다시 말해서

\[C_i \cdot \vec{t} = \mu_i \cdot G_{n + 1} \cdot \vec{t} + \vec{e}_i\]

일 때,

\[C_{+} = C_1 + C_2\] \[C_{\times} = G^{-1}(C_1) \cdot C_2\]

로 덧셈과 곱셈을 암호화된 상태에서도 할 수 있습니다. 아까와는 다르게 gadget decomposition이 들어가게 되었다는 차이가 있습니다. 결과를 확인해 보면,

\[\begin{aligned} C_{+} \cdot \vec{t} &= C_1 \cdot \vec{t} + C_2 \cdot \vec{t} \\&= \mu_1 \cdot G_{n + 1} \cdot \vec{t} + \vec{e}_1 + \mu_2 \cdot G_{n + 1} \cdot \vec{t} + \vec{e}_2 \\&= (\mu_ 1 + \mu_2) \cdot G_{n + 1}\cdot \vec{t} + \vec{e}_1 + \vec{e}_2 \end{aligned}\] \[\begin{aligned} C_{\times} \cdot \vec{t} &= G^{-1}(C_1) \cdot C_2 \cdot \vec{t} \\ &= G^{-1}(C_1) \cdot (\mu_2 \cdot G_{n + 1} \cdot \vec{t} + \vec{e}_2)\\ &= G^{-1}(C_1) \cdot G_{n+1} \cdot \mu_2 \cdot \vec{t} + G^{-1}(C_1) \cdot \vec{e}_2\\ &= C_1 \cdot \vec{t} \cdot \mu_2 + G^{-1}(C_1) \cdot \vec{e}_2\\ &= (\mu_1 \cdot G_{n + 1} \cdot \vec{t} + \vec{e}_1) \cdot \mu_2 + G^{-1}(C_1) \cdot \vec{e}_2\\ &= \mu_1 \cdot \mu_2 \cdot G_{n + 1} \cdot \vec{t} + \vec{e}_1 \cdot \mu_2 + G^{-1}(C_1) \cdot \vec{e}_2\\ \end{aligned}\]

가 되고, 위에서의 예시와 다르게 곱셈에서도 암호문이 가지고 있는 에러가 크게 증가하지 않음을 확인할 수 있는데 이는 $G^{-1}(C_1)$의 각 항이 $B$ 이하라는 성질을 가지고 있기 때문에, $G^{-1}(C_1)\cdot \vec{e}_1$가 여전히 작은 값이기 때문입니다!

마지막으로 decryption의 경우에도 gadget을 이용하여 진행됩니다.

\[\vec{u} = \begin{bmatrix}0\\0\\\vdots\\\frac{q}{2}\end{bmatrix} \in \mathbb{Z}_q^{n + 1}\]

을 정의해주면,

\[\begin{aligned} G^{-1}(\vec{u}^{t}) \cdot C \cdot \vec{t} &= G^{-1}(\vec{u}^{t}) \cdot (\mu \cdot G_{n + 1} \cdot \vec{t} + \vec{e}) \\ &= G^{-1}(\vec{u}^{t}) \cdot (\mu \cdot G_{n + 1} \cdot \vec{t} + \vec{e}) \\ &= G^{-1}(\vec{u}^{t}) \cdot G_{n + 1} \cdot \vec{t} \cdot \mu + G^{-1}(\vec{u}^t) \cdot \vec{e} \\ &= \vec{u}^{t} \cdot \vec{t} \cdot \mu + G^{-1}(\vec{u}^t) \cdot \vec{e} \\ &= \langle\vec{u}, \vec{t} \rangle \cdot \mu + G^{-1}(\vec{u}^t) \cdot \vec{e} \\ &= \frac{q}{2}\mu + G^{-1}(\vec{u}^t) \cdot \vec{e} \\ \end{aligned}\]

이 값이 $\frac{q}{2}$에 가까운지 0에 가까운지에 따라, $\vec{e}$가 너무 크지만 않으면 $\mu$의 값을 복원할 수 있게 됩니다.

Conclusion

이번 글에서는 상당히 초기 동형암호 scheme에 해당하는 GSW scheme에 대해서 살펴봤습니다. TFHE를 설명하기 위해서 곁다리로 설명한 것이긴 하지만, 오히려 하나의 글로 전체 동형암호 scheme을 살펴볼 수 있다는 점에서 더 의미 있는 설명이었을지도 모르겠습니다. 또한, 이번 글에서 중점적으로 설명한 gadget은 TFHE가 아니라 다른 대부분의 동형암호에서 이용한다는 점에서, 동형암호에 관심이 있으시다면 알아두면 좋을 개념이라고 생각합니다.

이어지는 글에서는 이러한 GSW scheme을 이용하는 TFHE의 곱셈에 해당하는 external product에 대해서 살펴보도록 하겠습니다.

읽어주셔서 감사합니다.

Reference

[1] Craig Gentry, Amit Sahai, and Brent Waters. 2013. Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based https://eprint.iacr.org/2013/340