CKKS EXPLAINED, PART 3: ENCRYPTION AND DECRYPTION

Introduction

在之前的文章中，CKKS解釋了第二部分：完整的編碼和解碼，我們看到了如何實現CKKS的編碼器和解碼器，這使我們能夠將向量轉換為多項式，反之亦然。這一步驟是必要的，因為我們將看到，與直接使用向量相比，使用多項式來構建同態加密方案要高效得多。

在本文中，我們將看到如何利用困難問題，如LWE或RLWE來構建一個近似同態加密方案。CKKS使用近似算術而不是精確算術，這意味著一旦我們完成計算，我們可能會得到一個略有不同于直接進行計算的結果。這意味著如果您加密了2和3，將它們的密文相加，然后解密，您可能會得到類似于4.99或5.01但不是5的結果。而其他方案，如BFV是精確的，這意味著它們將產生確切的5。

那么為什么要使用CKKS呢？CKKS更適用于實數上的算術運算，其中我們可以得到近似但接近的結果，而BFV更適用于整數上的算術運算。

在本文中，我們將看到如何利用LWE和RLWE實現近似算術同態加密方案的加密和解密過程。

Learning with Error

CKKS是一種公鑰加密方案，其中生成了一個秘鑰對，包括一個私鑰和一個公鑰。公鑰用于加密并可以共享，而私鑰用于解密并必須保密。

LWE（Learning With Error）是CKKS的基礎，也是許多其他同態加密方案的基礎之一。LWE問題最初由Regev在論文《On lattices, learning with errors, random linear codes, and cryptography》中引入。LWE問題是要區分形式為 $(a_i, b_i) = (a_i, \langle a_i, s \rangle + e_i)$ 的帶噪聲對和 $\mathbb{Z}_q^n\times\mathbb{Z}_q$ 中真正隨機的對。這里 $a_i, s \in \mathbb{Z}_q^n$ ， $a_i$ 是均勻采樣的， $s$ 是我們的秘密， $e_i \in \mathbb{Z}_q$ 是小的噪聲，通常是高斯分布的，用于增加問題的難度。如果不引入 $e_i$ ，解決這個線性系統將會變得容易得多，因為我們可以使用高斯消元法來解決線性系統。

$\mathbb{Z}_q^n\times\mathbb{Z}_q$ 表示一個元素由兩部分組成的集合，其中第一部分是長度為 $n$ 的整數向量，每個分量都來自于模 $q$ 的整數集合 $\mathbb{Z}_q$ ，第二部分是一個整數，同樣來自于模 $q$ 的整數集合 $\mathbb{Z}_q$ 。

具體來說， $\mathbb{Z}_q^n\times\mathbb{Z}_q$ 可以表示為：

$\mathbb{Z}_q^n\times\mathbb{Z}_q = \{(x_1, x_2, \ldots, x_n, y) \mid x_i \in \mathbb{Z}_q, y \in \mathbb{Z}_q\}$

其中 $x_1, x_2, \ldots, x_n$ 是整數向量的分量，每個分量都來自于模 $q$ 的整數集合 $\mathbb{Z}_q$ ， $y$ 是一個整數，同樣來自于模 $q$ 的整數集合 $\mathbb{Z}_q$ 。

LWE問題的目標是區分形式為 $(a_i, b_i) = (a_i, \langle a_i, s \rangle + e_i)$ 的帶噪聲對和 $\mathbb{Z}_q^n\times\mathbb{Z}_q$ 中真正隨機的對。

在LWE問題中，我們有一組帶噪聲的對 $a_i, b_i)$ ，其中 $a_i$ 是長度為 $n$ 的向量， $b_i$ 是一個整數。這些帶噪聲的對是通過選擇秘密向量 $s$ ，生成矩陣 $A=(a_1,\ldots,a_m)$ ，并添加噪聲項 $e_i$ 來構造的。

對于每個帶噪聲的對 $a_i, b_i)$ ，其中 $a_i$ 是隨機選擇的向量， $b_i$ 是通過將 $a_i$ 與秘密向量 $s$ 的內積加上噪聲項 $e_i$ 計算得到的。噪聲項 $e_i$ 是從特定分布中生成的隨機數，通常是一個小的擾動項。

與此相對， $\mathbb{Z}_q^n\times\mathbb{Z}_q$ 表示一個集合，其中元素是由長度為 $n$ 的向量和一個整數組成的對。在這個集合中，向量和整數的取值是完全獨立的，沒有任何關聯性。

LWE問題的目標是通過觀察一組帶噪聲的對 $a_i, b_i)$ 來區分它們是否是由秘密向量 $s$ 生成的。換句話說，我們需要確定給定的帶噪聲對是來自于LWE構造還是來自于純隨機的對。這種區分能力是LWE問題的核心，而解決LWE問題的算法將能夠從帶噪聲的對中恢復出秘密向量 $s$ 的近似。

example

假設我們有一個模數 $q = 7$ ，向量維度 $n = 3$ ，并且我們希望生成一個帶噪聲的對 $a_i, b_i)$ ，其中 $a_i$ 是長度為 $n$ 的向量， $b_i$ 是一個整數。

首先，我們隨機選擇一個秘密向量 $s = (2, 4, 1)$ ，其中每個分量都來自于模 $q$ 的整數集合 $\mathbb{Z}_q$ 。然后，我們生成一個噪聲項 $e_i$ ，該項滿足特定的噪聲分布。在這個例子中，我們假設 $e_i$ 是從均值為0、方差為2的離散高斯分布中生成的。

現在，我們生成帶噪聲的對 $a_i, b_i)$ 。對于每個 $i$ ，我們隨機選擇向量 $a_i$ ，其中每個分量 $a_{i,j}$ 都是從模 $q$ 的整數集合 $\mathbb{Z}_q$ 中隨機選擇的。然后，我們計算 $b_i = \langle a_i, s \rangle + e_i$ ，其中 $\langle\cdot,\cdot\rangle$ 表示向量的內積。

讓我們通過一個具體的例子來說明：

假設我們生成的隨機向量 $a_i$ 如下：

$a_1 = (3, 6, 4)$
$a_2 = (2, 3, 5)$

對于這兩個向量，我們計算相應的 $b_i$ ：

$b_1 = \langle a_1, s \rangle + e_1 = (3 \cdot 2 + 6 \cdot 4 + 4 \cdot 1) + e_1 = 29 + e_1$
$b_2 = \langle a_2, s \rangle + e_2 = (2 \cdot 2 + 3 \cdot 4 + 5 \cdot 1) + e_2 = 23 + e_2$

在這個例子中， $e_1$ 和 $e_2$ 是從離散高斯分布中生成的隨機噪聲項。

這樣，我們就得到了兩個帶噪聲的對 $a_1, b_1)$ 和 $a_2, b_2)$ ，其中 $a_1, a_2$ 是長度為 3 的向量， $b_1, b_2$ 是整數。通過解決LWE問題，我們的目標是從這些帶噪聲的對中學習到秘密向量 $s$ 的近似。

LWE問題被認為與最壞情況的格問題一樣困難，目前對來自量子計算機的攻擊是安全的。因此，我們可以利用從 $(a_i,\langle a_i, s \rangle + e_i)$ 對中找到秘密 $s$ 的難度，并基于此構建一個加密系統。

假設我們已生成了一個保密的秘鑰 $\in \mathbb{Z}_q^n$ ，并發布了 $n$ 對形式為 $(a_i,\langle a_i, s \rangle + e_i)$ 的對，可以寫成矩陣形式為 $\cdot s + e)$ ，其中 $A\in\mathbb{Z}_q^{n\times n}$ ， $\in \mathbb{Z}_q^n$ 。正如LWE問題所述，從這個對中恢復秘密鑰是困難的，因此我們可以利用它來創建一個公鑰。

實際上，我們將使用 $\cdot s + e,A)$ 作為我們的公鑰，可以公開使用，因為很難從中提取出秘密鑰。我們選擇存儲 $\cdot s$ 而不是 $\cdot s$ 是為了方便，但這并不改變問題。

然后，為了使用公鑰和私鑰加密和解密一個消息 $\mu \in \mathbb{Z}_q^n$ ，我們可以使用以下方案：

使用公鑰 $p$ 對 $\mu$ 進行加密：輸出 $(\mu, 0) + p = (\mu - A \cdot s + e, A) = (c_0, c_1)$ 。
使用私鑰 $s$ 對 $c$ 進行解密：輸出 $\tilde{\mu}=c_0+c_1.s=\mu-A.s+e+A.s=\mu+e\approx\mu$ 。

因此，在加密階段，我們使用公鑰來對消息 $\mu$ 進行掩碼。因此，消息被隱藏在密文的第一個坐標中，使用了掩碼 $\cdot s$ 。請記住， $A$ 是均勻采樣的，因此它確實會有效地掩蓋 $\mu$ 。要移除掩碼，我們可以使用 $c$ 的第二個坐標，其中僅存儲了 $A$ ，并將其與私鑰 $s$ 結合以獲得解密結果 $\mu + e$ 。注意，這里我們并沒有得到原始消息 $\mu$ ，而是 $\mu$ 加上一些噪音 $e$ ，這就是為什么我們說我們有一個近似算術方案。如果 $e$ 足夠小，那么解密結果將接近于原始的 $\mu$ 。

因此，我們已經看到如何利用 LWE 問題構建一個安全防御量子攻擊的公共加密方案。上述實現的問題在于，雖然秘密密鑰的大小為 $\mathcal{O}(n)$ ，但由于矩陣 $A$ 的存在，公鑰的大小為 $\mathcal{O}(n^2)$ ，并且計算也需要 $\mathcal{O}(n^2)$ 次操作。因為 $n$ 將決定我們方案的安全性，如果我們使用 LWE 構建我們的方案，它在實踐中將會太低效，因為密鑰的 $\mathcal{O}(n^2)$ 大小和復雜度將使其太不實際。

Ring Learning with Error

因此，我們將考慮《On Ideal Lattices and Learning with Errors Over Rings》中介紹的Ring Learning With Error（RLWE）問題，它是LWE在環上的一種變體。我們不再使用 $\mathbb{Z}_q^n$ 中的向量，而是在 $\mathbb{Z}_q[X]/(X^N+1)$ 中使用多項式進行計算（這里假設 $N$ 是2的冪）。現在我們從 $\mathbb{Z}_q[X]/(X^N+1)$ 中隨機選擇多項式 $a$ 、 $s$ 和 $e$ ，其中 $a$ 仍然是均勻采樣的， $s$ 是一個小的秘密多項式， $e$ 是一個小的噪聲多項式。轉向RLWE有兩個主要優勢：

密鑰大小不再是二次的，而是線性的，因為我們現在輸出公鑰 $p=(-a\cdot s+e,a)$ ，其中 $a\cdot s$ 表示 $a$ 與 $s$ 的多項式乘積。由于所有操作都是在多項式之間進行的，私鑰和公鑰的大小都是 $\mathcal{O}(n)$ 。
乘法是在多項式上進行的，因此可以使用離散傅立葉變換進行多項式乘法，復雜度為 $\mathcal{O}(n\log(n))$ ，而不是 $\mathcal{O}(n^2)$ ，因為我們需要進行矩陣-向量乘法。

因此，通過使用RLWE而不是LWE，我們可以獲得更小的密鑰，并且操作速度更快，因此前面的方案變得更加實用。此外，RLWE仍然是一個困難問題，并提供強大的安全性保證，因此使用RLWE仍然提供了一個安全的方案。

現在我們明白了為什么使用多項式是重要的，因為它們為高效和安全的方案提供了基礎。因此，現在你可以理解為什么我們要費力地將向量轉換為 $\mathbb{Z}_q[X]/(X^N+1)$ 中的多項式，反之亦然，因為我們現在可以利用多項式環的代數結構。

假設我們有一個RLWE方案，其中我們在環 $\mathbb{Z}_q[X]/(X^4 + 1)$ 上進行計算， $q$ 是我們的模量。我們希望生成一個公鑰和一個私鑰來加密和解密消息。

密鑰生成：
- 我們首先隨機選擇一個小的秘密多項式 $s = 3X^2 + 2X + 1$ 和一個小的噪聲多項式 $e = X^3 + X^2 + 2X + 1$ 。
- 然后我們隨機選擇一個多項式 $a = X^3 + 2X^2 + X + 1$ ，這個多項式仍然是均勻采樣的。
- 我們計算公鑰 $\cdot s + e, a)$ 。首先，計算 $\cdot s = -(X^3 + 2X^2 + X + 1) \cdot (3X^2 + 2X + 1)$ ，得到 $\cdot s = -3X^5 - 5X^4 - 3X^3 - X^2 - 2X - 1$ ，然后加上噪聲多項式 $e$ ，得到 $\cdot s + e = -3X^5 - 5X^4 - 3X^3 - 2X^2 - X$ 。公鑰 $p$ 就是這個結果和 $a$ 的組合，即 $p = (-3X^5 - 5X^4 - 3X^3 - 2X^2 - X, X^3 + 2X^2 + X + 1)$ 。
加密：

假設我們有一個消息 $\mu = 2X^2 + X + 1$ ，我們希望將其加密。我們隨機選擇一個小的噪聲多項式 $e' = X^2 + 1$ 。

我們計算密文 $(\mu - a \cdot s + e', a)$ 。首先，計算 $\mu - a \cdot s = (2X^2 + X + 1) - (X^3 + 2X^2 + X + 1) \cdot (3X^2 + 2X + 1)$ ，得到 $\mu - a \cdot s = -3X^6 - 3X^5 - 2X^4 - 2X^3 - X^2$ ，然后加上噪聲多項式 $e^{'}$ ，得到 $\mu - a \cdot s + e' = -3X^6 - 3X^5 - 2X^4 - X^3 - X^2 + 1$ 。密文 $c$ 就是這個結果和 $a$ 的組合，即 $c = (-3X^6 - 3X^5 - 2X^4 - X^3 - X^2 + 1, X^3 + 2X^2 + X + 1)$ 。
解密：

使用私鑰 $s$ 對密文 $c$ 進行解密。解密過程為 $\mu' = c_0 + c_1 \cdot s$ 。將 $c_0$ 替換為 $3X^6 - 3X^5 - 2X^4 - X^3 - X^2 + 1$ ， $c_1$ 替換為 $X^3 + 2X^2 + X + 1$ ， $s$ 替換為 $3X^2 + 2X + 1$ 。進行多項式乘法和加法后，得到解密結果 $\mu' = 2X^2 + X + 1$ ，與原始消息 $\mu$ 相同。

這是一個簡化的RLWE示例，演示了如何生成密鑰、加密消息和解密密文。 RLWE的優勢在于密鑰的大小更小，并且可以使用更高效的乘法操作進行計算。

Homomorphic operations

現在我們已經了解了為什么要在 $\mathbb{Z}_q[X]/(X^N+1)$ 的多項式上工作，以及如何基于此構建加密方案，讓我們看看如何定義密文上的加法和乘法，以實現同態加密方案。

我們說過我們有一個秘密 $s$ 和一個公鑰 $p=(b,a)=(-a\cdot s+e,a)$ 。要加密一個消息 $\mu$ ，我們簡單地輸出 $c=(\mu+b,a)$ ，而要使用 $s$ 解密它，我們評估 $c_0+c_1\cdot s$ ，這將近似地給出原始消息。

Addition

假設我們有兩個消息 $\mu$ 和 $\mu'$ ，并將它們加密為 $c=(c_0,c_1)$ 和 $c'=(c'_0,c'_1)$ 。那么 $c_{\text{add}}=c+c'=(c_0+c'_0,c_1+c'_1)$ 就是 $\mu+\mu'$ 的正確加密結果。也就是說，當我們使用秘密 $s$ 進行解密時，我們會得到（近似地） $\mu+\mu'$ 。

確切地說，對 $c_{\text{add}}$ 的解密過程為 $c_{\text{add},0}+c_{\text{add},1}\cdot s=c_0+c'_0+(c_1+c'_1)\cdot s=c_0+c_1\cdot s+c'_0+c'_1\cdot s= \mu+\mu'+2e\approx\mu+\mu'$ 。這里我們假設 $e$ 是可以忽略的。

這意味著，如果你對密文進行加法操作，并將其解密，你將得到明文的加法結果！這意味著通過這個簡單的方案，你可以允許某人在加密的數據上進行加法操作，而用戶仍然可以解密它并得到正確的結果。這是我們朝著同態加密方案邁出的第一步。

Multiplication

然而，我們仍然需要定義密文上的乘法，這更加復雜。事實上，我們的目標是找到一個密文 $c_{\text{mult}}$ ，當我們用秘密密鑰 $s$ 進行解密時，我們得到明文的乘積。

由于兩個密文的乘法更加復雜，我們現在將重點放在將密文與明文相乘上，并在以后的文章中看看如何在密文之間進行乘法運算。

假設我們有一個明文 $\mu$ ，加密為密文 $c=(c_0,c_1)$ ，以及另一個明文 $\mu'$ 。那么要獲得乘法的密文，我們只需要輸出 $c_{\text{mult}}=(\mu'\cdot c_0,\mu'\cdot c_1)$ 。

確實，當解密 $c_{\text{mult}}$ 時，我們得到 $\mu'\cdot c_0+\mu'\cdot c_1\cdot s=\mu'\cdot (c_0+c_1\cdot s)=\mu'\cdot (\mu+e)=\mu'\cdot \mu+\mu'\cdot e\approx\mu'\cdot \mu$ 。