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,⟨a_i,s⟩+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$，解决这个线性系统将会变得容易得多，因为我们可以使用高斯消元法来解决线性系统。

在解释LWE（Learning With Errors）问题之前，让我们先明确一些基本概念。

符号说明：

• $a_i$：一个在有限域${\mathbb{Z}}_q^n$中随机选取的向量。
• $s$：一个固定的、未知的秘密向量，同样在${\mathbb{Z}}_q^n$中。
• $⟨a_i,s⟩$：向量$a_i$和向量$s$的内积。
• $e_i$：一个小的噪声项或误差，通常是从某个较小的范围（例如高斯分布）中选取。
• $b_i$：计算为$⟨a_i,s⟩+e_i$，即向量内积加上噪声。

LWE问题的描述

在LWE问题中，我们得到的是一系列的样本对$(a_i,b_i)$，其中每个对由以下构成：

• $a_i$是随机向量。
• $b_i$是$a_i$和一个秘密向量$s$的内积，再加上一个小的误差$e_i$。

任务是区分这些样本对是否是从以下两种情况之一生成的：

1. 结构化生成：即对是按照$(a_i,⟨a_i,s⟩+e_i)$的规则生成，这里包含了一个固定的秘密向量$s$和一个噪声项$e_i$。
2. 随机生成：即对$(a_i,b_i)$是完全随机从${\mathbb{Z}}_q^n\times {\mathbb{Z}}_q$中选取的，没有任何固定模式或内在结构。

目标和挑战

LWE问题的核心挑战是，尽管$b_i$中包含了噪声$e_i$，这些噪声可能足够小，不足以完全掩盖秘密向量$s$的效应，使得有足够技巧或计算资源的攻击者可能能从一系列的样本中恢复出秘密向量$s$。然而，如果$b_i$是随机生成的，那么就没有任何可利用的结构来进行这种恢复。

因此，LWE问题的目标是检验给定的样本对是否含有足够的信息来区分这两种情况,==即分形式为$(a_i,b_i)=(a_i,⟨a_i,s⟩+e_i)$的带噪声对和${\mathbb{Z}}_q^n\times {\mathbb{Z}}_q$中真正随机的对。==在密码学中，这种区分的困难性是用来构建安全的密码系统的基石，理论上如果LWE问题足够难，则相关的密码系统就被认为是安全的。

假设我们已生成了一个保密的秘钥$s\in {\mathbb{Z}}_q^n$，并发布了$n$对形式为$(a_i,⟨a_i,s⟩+e_i)$的对，可以写成矩阵形式为$(A,A\cdot s+e)$，其中$A\in {\mathbb{Z}}_q^{n\times n}$，$e\in {\mathbb{Z}}_q^n$。正如LWE问题所述，从这个对中恢复秘密钥是困难的，因此我们可以利用它来创建一个公钥。

实际上，我们将使用$p=(-A\cdot s+e,A)$作为我们的公钥，可以公开使用，因为很难从中提取出秘密钥。我们选择存储$-A\cdot s$而不是$A\cdot s$是为了方便，但这并不改变问题。

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

• 使用公钥$p$对$\mu$进行加密：输出$c=(\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$进行掩码。因此，消息被隐藏在密文的第一个坐标中，使用了掩码$-A\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有两个主要优势：

1. 公钥大小不再是二次的，而是线性的，因为我们现在输出公钥$p=(-a\cdot s+e,a)$，其中$a\cdot s$表示$a$与$s$的多项式乘积。由于所有操作都是在多项式之间进行的，私钥和公钥的大小都是$\mathcal{O}(n)$。
2. 乘法是在多项式上进行的，因此可以使用离散傅立叶变换进行多项式乘法，复杂度为$\mathcal{O}(n\log (n))$，而不是$\mathcal{O}(n^2)$，因为我们需要进行矩阵-向量乘法。

因此，通过使用RLWE而不是LWE，我们可以获得更小的密钥，并且操作速度更快，因此前面的方案变得更加实用。此外，RLWE仍然是一个困难问题，并提供强大的安全性保证，因此使用RLWE仍然提供了一个安全的方案。

现在我们明白了为什么使用多项式是重要的，因为它们为高效和安全的方案提供了基础。因此，现在你可以理解为什么我们要费力地将向量转换为${\mathbb{Z}}_q[X]/(X^N+1)$中的多项式，反之亦然，因为我们现在可以利用多项式环的代数结构。

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 }^{\prime }$，并将它们加密为$c=(c_0,c_1)$和$c^{\prime }=(c_0^{\prime },c_1^{\prime })$。那么$c_{\text{add}}=c+c^{\prime }=(c_0+c_0^{\prime },c_1+c_1^{\prime })$就是$\mu +{\mu }^{\prime }$的正确加密结果。也就是说，当我们使用秘密$s$进行解密时，我们会得到（近似地）$\mu +{\mu }^{\prime }$。

确切地说，对$c_{\text{add}}$的解密过程为:

$$\begin{array}{rl}{c}_{\text{add},0}+c_{\text{add},1}\cdot s& =c_0+c_0^{\prime }+(c_1+c_1^{\prime })\cdot s\\ & =c_0+c_1\cdot s+c_0^{\prime }+c_1^{\prime }\cdot s\\ & =\mu +{\mu }^{\prime }+2e\\ & \approx \mu +{\mu }^{\prime }.\end{array}$$

这里我们假设$e$是可以忽略的。

这意味着，如果你对密文进行加法操作，并将其解密，你将得到明文的加法结果！这意味着通过这个简单的方案，你可以允许某人在加密的数据上进行加法操作，而用户仍然可以解密它并得到正确的结果。这是我们朝着同态加密方案迈出的第一步。

Multiplication

然而，我们仍然需要定义密文上的乘法，这更加复杂。事实上，我们的目标是找到一个密文$c_{\text{mult}}$，当我们用秘密密钥$s$进行解密时，我们得到明文的乘积。

由于两个密文的乘法更加复杂，我们现在将重点放在将密文与明文相乘上，并在以后的文章中看看如何在密文之间进行乘法运算。

假设我们有一个明文$\mu$，加密为密文$c=(c_0,c_1)$，以及另一个明文${\mu }^{\prime }$。那么要获得乘法的密文，我们只需要输出$c_{\text{mult}}=({\mu }^{\prime }\cdot c_0,{\mu }^{\prime }\cdot c_1)$。

确实，当解密$c_{\text{mult}}$时，我们得到：

$$\begin{array}{rl}{\mu }^{\prime }\cdot c_0+{\mu }^{\prime }\cdot c_1\cdot s& ={\mu }^{\prime }\cdot (c_0+c_1\cdot s)\\ & ={\mu }^{\prime }\cdot (\mu +e)\\ & ={\mu }^{\prime }\cdot \mu +{\mu }^{\prime }\cdot e\\ & \approx {\mu }^{\prime }\cdot \mu .\end{array}$$

因此，通过这种加法和乘法的实现，我们已经看到可以加密一些数据，对其进行操作，然后解密后得到与对明文数据进行计算相同的结果。

由于我们还有一些其他概念要解决，例如密文-密文乘法、重线性化和重新缩放，我们暂时不会涵盖代码实现。一旦我们掌握了所有的基本组件，我们将把一切都组合在一起，构建一个端到端的近似同态加密方案，类似于CKKS！

所以我希望你理解了如何使用RLWE构建同态加密方案，并且下一步是密文-密文乘法！