IHHI's profile image

IHHI

January 31, 2025 07:00

Introduction

동형암호, 영어로는 HE(Homormorphic Encryption), 또는 FHE(Fully Homomorphic Encryption)은 일반적인 암호와 다르게, 암호화된 상태에서도 연산이 가능하게 하는 scheme입니다.

예를 들어, 어떤 기업에서 MRI 결과를 입력으로 받아 그 MRI를 찍은 사람이 암에 걸렸을 확률을 계산하는 알고리즘을 개발했다고 합니다. 원래는 그 기업에게 자신의 MRI를 공개해야만 그 결과를 받아볼 수 있었을텐데, 동형암호와 함께라면 자신의 MRI를 암호화해서 보낸 뒤, 암호화된 MRI 결과를 기업이 연산하고, 받은 결과를 복호화하면 기업은 아무런 내용도 알 수 없는 것입니다!

더 자세한 개념이 궁금하시다면 이 블로그에 cs71107님이 동형 암호의 개념에 대해서만 집중적으로 설명해주신 글을 참고하시기 바랍니다.

이러한 동형암호는 현재 두 가지 흐름으로 크게 나누어져 있다고 볼 수 있는데, BFV, BGV, CKKS 등의 leveled scheme과, TFHE, FHEW 등의 bootstrapped scheme입니다.

BFV, BGV, CKKS등의 leveled scheme은 여러 개의 원소를 묶어서 처리하는 연산에 강하고, 그 연산이 bootstrapped scheme과 비교하면 조금 비싼, 즉 high throughput의 특성을 가지는 반면 TFHE와 FHEW는 연산이 싼 반면에 여러 개의 원소를 묶어서 처리하기는 어려운 low latency의 특성을 가집니다.

이 글에서는 이런 특성을 가지게 하는 TFHE의 대략적인 동작 방식에 대해서 설명합니다. 주 자료로는 [1]을 참고하고 있습니다.

Backgrounds

Notation

이 글과 다음 글들에서 사용할 notation을 정리하고 시작하겠습니다.

• vector는 $\textbf{u}$ 처럼 굵은 글씨로 씁니다.
• matrix는 $A$ 처럼 대문자로 씁니다.
• $\textbf{u}$와 $\textbf{v}$ 의 inner product는 $\langle \textbf{u} , \textbf{v} \rangle$로 씁니다.
• vector $\textbf{v}$ 의 $i$ 번째 좌표는 $\textbf{v}_i$로 씁니다.
• 다항식 $p(X)$의 $i$번째 계수 ($X^i$의 계수)는 $p^{(i)}$로 씁니다.
• 다항식 벡터 $\textbf{w}$에 대해서, $w^{(j)}_i$ 는 $i$번째 좌표인 다항식의 $j$번째 계수를 나타냅니다.
• $\lfloor \cdot \rceil$은 $\mathbb{R} \rightarrow \mathbb{Z}$ 인 rounding(반올림) 을 나타냅니다.
• $R_q = R / (q \cdot R)$ 입니다.
• $a \xleftarrow{$} M$는 집합 $M$ 에서 $a$ 를 uniform random하게 뽑는다는 표기입니다.
• $a \leftarrow D$는 분포 $D$에서 $a$를 뽑는다는 이야기입니다.

Torus

TFHE의 T는 torus의 약자입니다. 과연 여기서 torus는 무엇일까요? torus라는 단어를 들었을 때 생각나는 기하학적 물체보다는, Additive group인 torus $\mathbb{T} := \mathbb{R}/\mathbb{Z}$ 를 나타냅니다.

즉, torus 상의 모든 원소는 $[0,1)$ 위에 위치하는 실수로 표현될 수 있고, torus 상에서의 덧셈은 일반적인 실수 덧셈 뒤에 $\mod 1$이 덧붙여진 것으로 생각할 수 있습니다. $0.5 + 0.7 = 0.2$ 인 것이죠.

또한, $\mathbb{T}$ 를 정수 환 $\mathbb{Z}$ 의 module로도 생각할 수 있는데, 다르게 말하자면 $\mathbb{Z} \times \mathbb{T} \rightarrow \mathbb{T}$ 인 곱셈 연산을 정의할 수 있다는 것입니다. 이는 반복된 덧셈으로 쉽게 정의가 가능합니다. 예를 들어, $3 \cdot 0.4 = 0.2$ 인 것이죠.

Discretized Torus

컴퓨터는 torus $\mathbb{T}$를 온전히 표현하지 못하는데, 이는 당연하게도 torus는 finite group이 아니기 때문입니다. 그래서 실제 구현 상에서는 torus를 그대로 사용하는 것이 아니라 unsigned 32-bit, 64-bit 정수를 이용해서 사용합니다. 예를 들어서, $t \in \texttt{uint32}$ 는 $t / 2^{32}$ 를 나타내는 것으로 생각하고 사용하는 것입니다.

LWE, RLWE problem

TFHE의 기반 문제는 LWE, RLWE 문제로, 여기서는 LWE를 먼저 설명한 뒤에 RLWE 문제에 대해서 설명합니다.

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

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

이는 양자컴퓨터로도 현재 쉽게 풀어내지 못하는 문제임이 알려져 있습니다. 그러나, 이를 그대로 이용하기엔 너무 비효율적이므로 [2] 에서 이를 다항식 환(Ring) 에서의 연산으로 바꾼 문제인 RLWE(Ring Learning With Errors)를 제시했으며, 이를 현재 대부분의 양자 내성 암호, 동형 암호 등이 사용합니다.

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

여기서 다항식 환 $R_q := \mathbb{Z}_q[X]/(X^n + 1)$ 으로 정의됩니다.

• $(a, as + e) \quad \text{where} \quad a \xleftarrow{$} R_q, \textbf{s} \leftarrow \chi_s^n, e \leftarrow \chi_e^n$
• $(a, u) \quad \text{where} \quad a \xleftarrow{$} R_q, u \xleftarrow{$} R_q$

이 문제 또한 LWE 문제와 동일하게 양자컴퓨터로도 쉽게 풀지 못하는 문제임이 알려져 있습니다.

이를 통해서 간단한 암호화를 할 수 있는데, $s$를 비밀로 한 채 위의 $as + e$에 메시지 $\mu$를 더해서 $\mu + as + e$가 된다고 해도, 여전히 uniform 분포와 구분하기 어렵기 때문입니다. 실제로 BFV, CKKS, TFHE 등의 모든 동형암호는 암호화 방식이 이러한 형태에서 크게 벗어나지 않습니다.

TFHE Encryption & Decryption

TFHE에서는 GLWE sampling 이라는 방식으로 암호화를 합니다. 이는 torus 상에서의 LWE와 RLWE를 통합해서 생각하는 것으로 이해할 수 있습니다. GLWE sample의 정의는 다음과 같습니다.

GLWE sample

• Dimension $k \in \mathbb{N}$
• Degree $N \in \mathbb{N}$

로 주어지면, 다음과 같이 평문, 암호문, 키 공간을 다음과 같이 정의합니다.

• Plaintext Space $\mathcal{P} = \mathbb{T}^{(N)}[X]$
• Ciphertext Space $\mathcal{C} = \mathbb{T}^{(N)}[X]^{1 + k}$
• Key Space $\mathcal{K} = \mathbb{Z}^{(N)}[X]^k$

여기서 $\mathbb{Z}^{(N)}[X] := \mathbb{Z}(X) / (X^N + 1)$ 이고, 이에 대해 모듈이 되는 torus를 $\mathbb{T}^{(X)}[X]$로 정의합니다. 이는 torus 다항식을 $(X^N + 1)$로 나눈 나머지로 생각할 수 있습니다.

이 때, $\mathcal{K}$ 상의 키 분포 $\chi$ (보통 계수가 binary, 혹은 ternary가 되는 분포를 사용합니다.)에 의해 뽑힌 키 $\textbf{z} \leftarrow \chi$ 가 있다면, 이 키에 의한 평문 $\mu \in \mathcal{P}$의 GLWE sample 을 다음과 같이 정의합니다.

\[\text{GLWE}_\textbf{z}(\mu) := \bar{\textbf{c}} = (b, \textbf{a})\]

if

\[b = \mu - \langle \textbf{z}, \textbf{a} \rangle + e\]

where $\textbf{a} \leftarrow \mathbf{T}^{(N)}[X]^k$, $\textbf{e} \leftarrow \chi_e$

여기서 $\chi_e$는 미리 정해진 noise 분포(주로 정규 분포를 사용합니다) 입니다.

이는 위에서 이야기한 RLWE 문제의 형태를 $k$번 사용한 것으로 볼 수 있습니다.

조금 풀어서 써 보자면, $k = 2$ 정도를 가정해보면, $b = \mu - z_1a_1 - z_2a_2 + e$ 이게 되는데, 이는 아까 RLWE에서 간단한 암호화를 설명한 형태인 $\mu + as + e$ 에서 $as$ 항의 부호를 바꾼 뒤 두 번 더해준 형태인 $\mu - as - as + e$와 비슷함을 느낄 수 있습니다.

따라서 이를 암호화 방식으로 사용할 수 있습니다.

여기서 $\textbf{a} = \textbf{0}$ 이게 되면 sample을 trivial 하다고 부릅니다. 물론 이 형태는 암호화를 위해 사용하지는 않습니다.

$\mu = \textbf{0}$ 이라면, sample을 homogeneous 하다고 부릅니다.

특이한 점은, $N$을 1로 두게 되면, 벡터의 원소들이 다항식이 아니게 되며 이는 그냥 LWE sample이 됩니다.

TFHE에서는, 평문은 그냥 LWE sample로 암호화합니다. 그러나 내부 연산 과정 중에 GLWE가 사용됩니다.

GLWE phase

우선, 편의의 표기성을 위해서 확장 키 $\bar{\textbf{z}} := (1, \textbf{z}) \in \mathbb{Z}^{(N)}[X]^{1 + k}$를 정의합니다.

그런 뒤, phase function $\varphi_z: \mathbb{T}^{(N)}[X] \times \mathbb{T}^{(N)}[X]^k \rightarrow \mathbb{T}^{(N)}[X]$ 를 다음과 같이 정의합니다.

\[\varphi_z(b, \textbf{a}) = b + \langle \textbf{z}, \textbf{a} \rangle = \langle \bar{\textbf{z}}, \bar{\textbf{c}} \rangle\]

이는 위에서의 정의에 따라 $\mu + e$ 가 됨을 알 수 있습니다.

물론 이를 그대로 복호화 과정으로 사용하면 우리가 원하는 평문인 $\mu$를 얻어내지 못하지만, $e$가 작은 경우에는 적절한 rounding을 통해서 $\mu$를 얻어낼 수 있을 것입니다.

물론, 평문인 $\mu \in \mathbb{T}$ 인 경우에는 rounding이 의미하는 것이 명확하지 않으나, cleartext space $\mathcal{M} := \frac{1}{2^{\pi}}\mathbb{Z} / \mathbb{Z} \subset \mathbb{T}$를 정의하고 이 안에서만 메시지를 골라준다면, $|e| < \frac{1}{2^{\pi + 1}}$ 인 경우에는 cleartext space로 정상적인 rounding이 될 것입니다. 그리고 여기서 $\pi$를 cleartext precision이라고 합니다.

당연하게도, 처음 암호화할 때에는 $e$가 충분히 작으나, 연산 과정 중에 $e$가 커질 수 있어 이를 어떻게 해결해야 하는지가 동형암호의 공통적인 과제입니다.

TFHE는 이를 매 연산 이후에 bootstrapping 하는 방법으로 해결하며, 이는 이후 게시글에서 다룰 예정입니다!

Homomorphic Addition

같은 키 $\textbf{z}$에 의해 암호화된 여러 GLWE sample이 있는 경우, 이를 그대로, 혹은 상수배하여 더하면, 그 sample들이 담고 있는 메시지에 똑같은 연산을 한 효과가 생깁니다. 즉 이 GLWE sample들의 linear combination은 homomorphic합니다.

간단한 증명의 outline을 설명하겠습니다.

$\bar{\textbf{c}}_1, \bar{\textbf{c}}_2, \ldots, \bar{\textbf{c}}_n$ 가 $\textbf{z}$에 대한 GLWE sample이고, 각각이 담고 있는 plaintext를 $\mu_1, \mu_2, \ldots, \mu_n$이라고 하자. 이를 weight $w_1, w_2, \ldots, w_n \in \mathbb{Z}^{(N)}[X]$ 에 대해 linear combination한 결과

\[\bar{\textbf{c}} := \sum_{i = 1}^nw_i \cdot \bar{\textbf{c}}_i\]

의 phase를 계산해보면,

\[\varphi_\mathbf{z}(\bar{\textbf{c}}) = \langle \bar{\textbf{z}}, \bar{\textbf{c}} \rangle = \sum_{i = 1}^n w_i \langle \bar{\textbf{z}}, \bar{\textbf{c}}_i \rangle = \sum_{i = 1}^n w_i (\mu_i + e_i) \approx \sum_{i = 1}^n w_i \mu_i\]

여기서 쉽게 관찰할 수 있는 사실은, error도 같이 linear combination 되며 그 크기가 커졌다는 것입니다. 전 section에서 언급한 $e$가 커지는 경우에 해당하는 것입니다!

Conclusion

이 글에서는 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

[2] Vadim Lyubashevsky, Chris Peikert, and Oded Regev. 2013. On Ideal Lattices and Learning with Errors over Rings. J. ACM 60, 6, Article 43 (November 2013), 35 pages. https://doi.org/10.1145/2535925