TFHE : Fully Homomorphic Encryption over the Torus - 2
Introduction
안녕하세요. 지난 게시글에서는 동형암호 scheme중 하나인 TFHE의 암호화 / 복호화 / 덧셈 연산에 대해서 다루었습니다.
그리고 다음 게시글에서는 TFHE의 곱셈에 대해 다루기 위해서 GSW scheme과 gadget decomposition을 다루었는데요, 이 글의 이해를 위해서는 두 게시글을 읽고 오시길 추천드립니다!
이번 글에서는 TFHE에서의 곱셈(external product)가 어떻게 진행되는지와, 그리고 이러한 연산을 통해서 최종적으로 TFHE의 bootstrapping이 어떤 식으로 진행되는지에 대한 개괄적 설명을 하고자 합니다!
TFHE Multiplication(External Product)
Gadget Decomposition
Gadget decomposition을 처음 접하시는 분은 이 글 의 설명을 읽으신다면 더욱 도움이 될 것입니다!
Base $B = 2^\gamma$로 정하고, gadget vector를 다음과 같이 정의합니다.
\[\textbf{g} :=(1/B, 1/B^2, \ldots, 1/B^d)\]여기서 $d$는 gadget dimension이고, decomposition depth라고도 부릅니다.
Torus 위의 $\mu$에 대해서 $\textbf{g}^{-1}(\mu)$을 $\tilde{\mu} = \left \lceil B^d \cdot \mu \right \rfloor$ 를 $B$진법으로 나타낸 것으로 정의하면 ($\mu$를 소수점 아래로 $B$진법으로 나타낸 것으로 생각할 수도 있습니다.) $|\mu - \langle \textbf{g}, \textbf{g}^{-1}(\mu) \rangle| \leq \frac{1}{2B^d}$ 이게 됩니다.
예를 들어서, $\mu = \frac{9}{16}$이고 $B = 2$, $d = 2$라고 하면, $\textbf{g} = (0.5, 0.25)$, $\textbf{g}^{-1}(\mu) = (1, 0)$ 이 되고, $\langle \textbf{g}, \textbf{g}^{-1}(\mu) \rangle = 0.5$이며 오차는 $\frac{1}{16}$이 됩니다.
이 글에서는 자세한 에러 분석을 하진 않을 예정이므로, 오차가 매우 적게 나며, $B$와 $d$를 어떻게 잡느냐에 따라서 이를 조정할 수 있다는 정도로만 생각하시면 됩니다.
벡터 $\textbf{t} \in \mathbb{T}^n$에 대해서는, $\textbf{g}^{-1}$을 vector의 각 component에 대한 decomposition $\textbf{g}^{-1}(t_i)$을 이어붙인 것으로 정의하고, 즉 $\textbf{g}^{-1}(\textbf{t}) \in \mathbb{T}^{nd}$ 이고, 다항식 $t \in \mathbb{T}^{(N)}[X]$에 대해서는 계수별로 decompose한 것이 결과물이 됩니다. 즉, $\textbf{g}^{-1}(t) \in \mathbb{T}^{(N)}[X]^d$입니다. 마지막으로, 다항식 벡터에 대해서는 각 component인 다항식의 decomposition을 이어붙인 것이 결과물이 됩니다.
벡터를 decomposition하면, 길이가 $nd$가 되기 때문에, 기존의 gadget vector와 내적해주는 것으로 원래 형태로 돌릴 수 없게 됩니다. 따라서, gadget matrix를 다음과 같이 정의합니다.
\[\textbf{G}_k:=I_k\otimes\textbf{g} \in \mathbb{T}^{kd \times k}\]여기서 $I_k$은 $k \times k$ identity matrix이고, $\otimes$는 텐서곱입니다.
GGSW Sample
GSW 글에서의 GSW encryption과 비슷한 느낌으로, GGSW sample을 정의합니다.
\[\bar{\textbf{C}} = \bar{\textbf{Z}} + m \cdot \textbf{G}_{1 + k} \in \mathbb{T}^{(N)}[X]^{(1+k)d, 1+k}\]여기서 $\bar{\textbf{Z}}$의 모든 행이 상호 독립이고, key $\textbf{z}$에 의한 homogeneous한 GLWE sample이라면, 위의 $\bar{\textbf{C}}$를 $\textbf{z}$에 의한 GGSW sample이라고 부릅니다.
즉, $(1 + k)d$개의 homongenous(즉, 메시지를 담고 있지 않는)한 GLWE sample을 이용해서, gadget matrix와 원하는 메시지 $m$이 곱해진 형태를 숨기고 있는 형태라고 볼 수 있습니다!
External Product
GSW 글에서, GSW 암호문 두개를 곱해줄 때 단순하게 둘 중 하나의 암호문에 gadget decomposition을 적용해준 뒤, 행렬 곱셈을 하면 그것이 곱셈이 되는 것을 확인했습니다. 여기서의 external product도 같은 방식인데요, 조금 다른 점은 곱해지는 값 중 하나는 GGSW sample이지만, 나머지 하나가 GLWE sample이 된다는 점이 다릅니다. 정의는 간단합니다.
GLWE sample $\bar{\textbf{c}} = (b, \textbf{a}) \in \mathbb{T}^{(N)}[X]^{1 + k}$와, GGSW sample $\bar{\textbf{A}} \in \mathbb{T}^{(N)}[X]^{(1 + k)d, 1+k}$가 있다고 하면,
\[\bar{\textbf{A}} \boxdot \bar{\textbf{c}} := \textbf{g}^{-1}(\bar{\textbf{c}})^{T} \cdot \bar{\textbf{A}}\]로 정의합니다. $\bar{\textbf{c}}’= \bar{\textbf{A}} \boxdot \bar{\textbf{c}}$라고 하고, $\bar{\textbf{A}}$가 가지고 있는 메시지가 $m_A$라고 하면,
\[\langle \bar{\textbf{z}}, \bar{\textbf{c}}' \rangle \approx m_A \cdot \langle \bar{\textbf{z}}, \bar{\textbf{c}} \rangle\]이 성립합니다. 즉, 메시지를 곱해준 효과가 되고, 암호화된 상태에서도 곱셈을 하게 된 것입니다!
간단히 위의 식이 왜 성립하는지 생각해보면, $\textbf{G}_{1 + k}$ 와 $\mathbb{g}^{-1}(\bar{\textbf{c}})$ 가 곱해지면서 $\bar{\textbf{c}}$가 나오게 되는 부분을 생각해보고, 나머지는 작은 오류로만 남게 된다는 것을 생각해보면 대략적인 느낌은 알 수 있습니다! 실제적인 증명이 궁금하시다면 참고하고 있는 글[1]을 참고하시면 됩니다. 증명만으로도 한 페이지를 넘게 채워 제대로 소개하기에는 어려운 부분이 있었습니다.
Bootstrapping
동형암호의 가장 큰 문제는, 연산을 할 수록 암호문이 가지고 있는 에러가 커져 어느 횟수 이상으로 연산을 할 수 없다는 점입니다. 그러나, 바로 이 에러를 줄여주는 방식인 Bootstrapping이 존재합니다.
이는 Gentry가 2009년에 자신의 박사 졸업 논문에서 처음으로 제시한 방식으로, 암호화되어있는 상태에서 암호화된 키를 통해서 복호화를 하는 방식입니다.
복호화된 결과값은 당연하게도 평문이니 에러를 가지지 않습니다. 그러나 암호화된 상태에서 이 연산이 수행되기 때문에 결과값은 여전히 암호화되어 있습니다.
처음 들었을 때는 상당히 이상하고 오묘한 개념이라 와닿지 않을 수 있어서, 비유로 이를 설명해보겠습니다. 이는 Gentry가 직접 든 비유[2] 입니다.
Analogy to Bootstrapping
여러분이 보석상을 운영하는 상황이고, 여러 비싼 보석들을 가공해서 제품을 만들어서 이를 팔아 이윤을 남기고자 하는 상황이라고 합시다. 직원들에게 보석을 직접 맡겨서 제품을 만들게 할 수는 없습니다. 왜냐하면 보석 자체로도 비싸기 때문에 직원들이 이를 빼돌린다거나 할 수 있기 때문이죠. 대신, 글러브 박스(장갑이 달린 투명한 박스를 생각하시면 됩니다.) 에 보석을 넣은 뒤, 글러브 박스를 자신만 가진 열쇠로 잠그고 이 박스에서 직원들이 작업하도록 하면 직원들은 작업은 할 수 있으나 물건을 빼돌릴 수는 없고, 보석상인 여러분의 입장에서는 작업이 끝나면 열쇠를 이용해 열어서 제품만 꺼내면 되는 상황으로, 모든 문제가 해결되었습니다.
위의 비유는 동형암호에 대한 비유입니다. 그러나 동형암호의 큰 문제는, 연산을 할 수록 에러가 커져 연산을 더 하게 되면 복호화가 불가능하다는 점이고 이는 어느 정도의 시간이 지나면 글러브 박스의 장갑이 딱딱하게 굳어 사용하지 못한다는 제약사항으로 생각해볼 수 있습니다.
이러한 문제는 여러개의 글러브 박스를 사용하고, 글러브 박스에 단방향으로 다른 글러브 박스를 넣을 수 있는 구멍을 만듬으로서 해결할 수 있습니다.
예를 들어, 박스 1과 박스 2, 박스 3이 있다고 해 봅시다. 그리고 이 때, 박스 2 안에는 박스 1의 열쇠가, 박스 3 안에는 박스 2의 열쇠가 있고, 박스 3의 열쇠는 보석상인 여러분만 가지고 있다고 해 봅시다.
박스 1에서 작업을 하다가 장갑을 사용하지 못하게 되었다면, 이를 통째로 박스 2에 넣은 뒤, 안에 있는 박스 1의 열쇠를 이용해서 박스 1을 연 뒤, 박스 2의 장갑을 통해서 작업을 계속해나갑니다. 그러다 박스 2의 장갑도 사용하지 못하게 되었다면, 박스 3에 박스 2를 넣고, 박스 2의 열쇠를 이용해서 박스 3 안에서 작업을 이어나가면 되는 것입니다. 작업이 다 끝나면 보석상인 여러분만 가진 열쇠로 최종 결과물을 꺼내면 되겠죠.
여기서 박스 안에 있는 열쇠는 암호화된 키, 그리고 그 박스 안에 다른 박스를 넣어 열어버리는 상황은 암호화된 상태에서 암호화된 키를 이용해 복호화 하는 것으로 생각할 수 있습니다.
TFHE Bootstrapping Overview
TFHE의 Bootstrapping은 위에서 이야기한 에러를 줄여준다는 기능 이외에도, Lookup Table(LUT) 를 계산할 수 있다는 기능을 가집니다. 위에서 설명한 대로 암호화된 상태에서 복호화를 수행하게 되는데, 이것이 어떻게 가능한지는 마지막 글인 다음 글에서 다루게 될 예정입니다.
Conclusion
이번 글에서는 TFHE에서의 곱셈이 어떻게 수행되는지 알아보기 위해서 GGSW sample과 그리고 이를 통해 실질적으로 곱셈을 어떻게 할 지, 그리고 Bootstrapping의 개념에 대해서 살펴보았습니다. 다음 글에서는 TFHE에서의 Bootstrapping 과정을 살펴보며 마칠 예정입니다. 읽어주셔서 감사합니다.
Reference
[1] Jakub Klemsa. Hitchhiker’s Guide to the TFHE Scheme. Journal of Cryptographic Engineering, In press, ⟨10.21203/rs.3.rs-2841900/v1⟩. ⟨hal-04121360⟩ https://hal.science/hal-04121360v1