《Somewhat Practical Fully Homomorphic Encryption》笔记 （BFV 源于这篇文章）

---

一、摘要

1. 本文将基于LWE问题的 Brakerski 完全同态方案移植到 R-LWE 中。
2. 介绍了两个优化版本的 重线性化(relinearisation)，它不仅拥有一个较小的重线性化密钥，而且具有更快的计算。
3. 对于各种同态操作，如乘法、重线性化、bootstrapping 提供了一个详细但简单的分析，并给出了这些操作引起的 噪声的最坏情况界限。
4. 介绍了通过 模数切换技巧 (modulus switching trick)，大大简化了 bootstrapping 步骤的分析。

---

二、引言

1、FHE 一般分为三个逻辑部分

1. 首先，构造一个 SWHE，它可以支持有限次的同态操作
2. 然后，尽可能简化该方案的解密代价，通过 squashing
3. 最后，通过 bootstrapping，获得具有固定固有噪声大小的密文

2、噪声的管理

 所有现有的方案的共同特点，在加密过程中添加一个 小的“噪声”组件。 在密文上进行 同态计算将导致这些噪声增长，特别是 同态乘法，待到噪声增长到一定程度时，解密算法将失败。

 Gentry的 bootstrapping 方法可以用来将密文中的噪声降低到 由解密电路的复杂性决定的固定级别。

1. 在 Clear 的密文 (带有噪声 E) 上评估深度为 n 的电路会产生噪声为 $E^{2^n}$。
2. 在之后的某篇文献中，将深度为 n 的电路的噪声降低到了 $E^n$。
3. 再之后，通过改进，深度为 n 的电路的噪声水平降低到了 $E\cdot c(\lambda {)}^n$

 但是，这该是不足以支撑工业级使用。

3. 贡献点

1. 它的简单性，由于我们采用了“接地气”的方法，因此任何多余的数学机制 (可能是非常优雅美丽的) 都被省略了。
2. 将 Brakersk 的方案从 LWE 移植到 RLWE 中。
3. 对各种同态运算进行了详细而简单的分析，并推导出了这些运算所引起噪声最坏情况的严格界限。
4. 使用一个简单的模数转换技巧，我们简化了 bootstrapping 步骤的分析。
5. 在此基础上，结合方案 [14]，对方案进行了实际的安全分析，最终得到了给定安全级别的全同态方案的具体参数。
6. 提供了两个新版本的重线化。

4. 文章思路

本文的其余部分组织如下：

• 第2节简要回顾了概率的符号表示和一些背景
• 第3节回顾了一个非常优雅的基于RLWE的加密方案，它将作为第4节描述的 somewhat 同态方案的基础
• 第5节分析了 bootstrapping 步骤，并确定了最小深度，在这个最小深度上，somewhat 同态方案可以被全同态化
• 第6节使用 Lindner 和 Peikert [14] 的分析来推导给定安全级别的全同态方案的参数
• 最后，第7节是本文的结论，并强调了正在进行的工作

---

三、基础数学知识

 详细内容看专栏一些散乱的数学基础。

---

四、基于 RLWE 的加密

1. LWE 问题

 先来简单概括一下 LWE 问题的基本思路：给定一个线性方程 $A\cdot s+e$，其中：

• A 是一个已知矩阵
• s 是未知的秘密向量
• e 是一个小的错误向量，通常是随机的

 目标是通过已知的 $A\cdot s+e$ 来恢复 s，即从带有噪声的线性方程中恢复秘密 s。
 LWE 问题的难度在于：即使知道 A 和 $A\cdot s+e$，也无法有效地从中恢复出秘密 s（尤其当错误 e 是一个随机小数时）。这种难度是基于数学中的格问题。

2. RLWE 问题

 RLWE 是 LWE 的一种改进形式，主要通过引入 环结构 来提高 计算效率。RLWE 问题可以表示为一下形式：

1. 首先给定一些参数：
   • 一个环 $R=Z[x]/(f(x))$，其中 f(x) 是不可约多项式，通常选用的是环多项式 ${\varphi }_m(x)$ ，他是某个整数 m 的 循环多项式 (即 分圆多项式)。
   • 一个大整数 q，称为 模数，它用来定义环的商域 $R_q$。
   • 一个 秘密向量 $s\in R_q$，它通常从某种分布 $\chi$（通常是离散高斯分布）中随机选择。
   • $\chi$ 是一个分布，用来生成噪声项 e，该噪声项是由环 $R_q$ 中的元素通过 $\chi$ 随机生成的。
2. 加密过程：
    对于一个秘密向量 s 和一个随机选择的元素 $a\in R_q$，选择一个噪声项 $e\in \chi$，加密的输出是一个二元组 $(a,[a\cdot s+e{]}_q)$，其中：
   • a 是环 $R_q$ 中的一个随机元素。
   • $s\cdot a$ 是 s 和 a 的乘积，并且这个乘积是加上一个噪声项 e 后，再对模数 q 取模。
3. RLWE 问题的任务 (Decision-RLWE Problem)：
    判断该二元组是来自加密过程（即 $(a,[a\cdot s+e{]}_q)$），还是来自均匀分布 $U(R_q^2)$，即判断 a 和 $(a,[a\cdot s+e{]}_q)$ 是不是随机选取的。
4. 为什么 RLWE 很重要：
   • 加密安全性：抗量子攻击
   • 高效的同态加密：RLWE 被广泛用于构造同态加密方案。RLWE 的结构使得这种加密技术变得更为高效。
   • 环结构优化：与传统的 LWE 问题相比，RLWE 通过环结构优化了计算，减少了加密算法的计算开销，使其在实际应用中更具可操作性。

3. RLWE 问题的难度和安全性

 RLWE 问题的安全性来自于 理想格（ideal lattices） 的 最短向量问题（SVP），这意味着 RLWE 问题是 计算上困难 的，且目前没有已知的高效算法能解决它。
 RLWE 通过巧妙的数学结构，在保证加密安全性的同时，提供了处理噪声增长的可能性。

---

五、加密方案

1. LPR.ES 加密方案

 上述的决策问题直接导致了以下的加密方案，作为 [15]¹ 扩展版中描述的加密系统。

• 明文空间 被设定为 $R_t$，其中 $t>1$ 是一个整数
• $\Delta =\lfloor q/t\rfloor$ 并定义 $r_t(q)=qmodt$，
• 显然我们有 $q=\Delta \cdot t+r_t(q)$。需要注意的是，q 和 t 不必是质数，也不要求 t 和 q 互质。

 加密方案 LPR.ES 定义如下：

• LPR.ES.SecretKeyGen(1λ)：
  $$\begin{gathered} Samples\leftarrow \chi \\ Outputsk=s \end{gathered}$$
• LPR.ES.PublicKeyGen(sk)：
  $$\begin{gathered} Sets=sk \\ Samplea\leftarrow R_q,e\leftarrow \chi \\ Outputpk=([-(a\cdot s+e){]}_q,a) \end{gathered}$$
• LPR.ES.Encrypt(pk, m)：
  $$\begin{gathered} Messagem\in R_t \\ Let{p}_0=pk[0],p_1=pk[1] \\ Sampleu,e_1,e_2\leftarrow \chi \\ Returnct=([p_0\cdot u+e_1+\Delta \cdot m{]}_q,[p_1\cdot u+e_2{]}_q) \end{gathered}$$
• LPR.ES.Decrypt(sk, ct)：
  $$\begin{gathered} Sets=sk,c_0=ct[0],c_1=ct[1] \\ Compute[\lfloor \frac{t\cdot [c_0+c_1\cdot s{]}_q}{q}\rceil {]}_t \end{gathered}$$

2. Lemma 1 (引理 1)

 为了证明当密文正确加密时解密是正确的，证明以下 引理 (Lemma)。
 使用上述加密方案 LPR.ES 的符号，并假设 $||\chi ||<B$，我们有：
$$[c_0+c_1\cdot s{]}_q=\Delta \cdot m+v(1)$$$$\begin{gathered} 通过上面给出的ct和pk可以计算出 \\ [c_0+c_1\cdot s{]}_q=\Delta \cdot m+(e_1+e_2\cdot s-e\cdot u) \\ 然后用v表示(e_1+e_2\cdot s-e\cdot u) \end{gathered}$$其中，$||v||\le 2\cdot {\delta }_R\cdot B^2+B$。这意味着当 $2\cdot {\delta }_R\cdot B^2+B<\Delta /2$ 时，解密正确，即当 噪声项 v 较小 时，解密过程就能正确进行。

B 代表了噪声的 最大幅度，即在选择噪声分布 (这里是 $\chi$) 时，通常会设定一个上界 B 来表示噪声项的可能范围。

 可以看出来，如果可以使得 u 和 s 越小，则噪声 v 就会越小。这句话导致了下面的优化和相应的假设。

3. Optimisation/Assumption 1 (优化/假设 1)

 我们将不从 $\chi$ 中采样 $s,u$，而是从 $R_2$ 中采样，即 $||s||=||u||=1$。但是 $e_1,e_2$ 仍从 $\chi$ 中采样。这种情况下 Lemma 1 中的界限 $||v||$ 变成了 $B\cdot (2\cdot {\delta }_R+1)$。

sk 只从 R₂ 中采样，会不会有什么问题。

---

六、Somewhat Homomorphic Encryption

 这一部分是 FHE 的前一个版本，是这篇文章的重点部分。在本节中，我们将基于 RLWE 的 LPR.ES 给出一个 SHE 方案 FV.SH。
 事实上，FV.SH 和 LPR.ES 的密钥生成、加密、解密过程完全相同，只不过使用了上一章中的 优化/假设1 $u,s\leftarrow R_2$ 进行优化。FV.SH 对 LPR.ES 的主要优化是，补充了一个名为 rlk 的 重线性化密钥，这是用来计算 同态乘法 的。

 LPR.ES 方案的主要不变量由 公式 (1) 给出，即 Lemma 1 中的公式 (1)，即 当我们将密文 ct 的元素视为多项式 ct(x) 的系数，并在 s 中对该多项式进行评估时，我们得到：
$$[ct(s){]}_q=[c_0+c_1\cdot s{]}_q=\Delta \cdot m+v$$通过这种方式，我们可以轻松恢复消息 m。利用这种解释，推导同态加法 FV.SH.Add 和同态乘法 FV.SH.Mul 就变得相对容易。

$ct(s)$ 就是 $c_0+c_1\cdot s$，其中 s 是私钥 sk 这里从 $R_2$ 中获取。
为什么可以轻松恢复消息 m？为什么加法和乘法会变简单？

理解这个内容非常重要！！！！！！！！这涉及到下面的加法和乘法的理论推导。

由于对于这里的同态加密来说，对于每个密文，密钥 sk 是不变的，而 $m,u,e_1,e_2$ 的改变会导致 $ct=[c{t}_0,c{t}_1]$ 的改变。
这个将密文元素视为多项式系数的方法，也就是 用多项式来表示密文，这个多项式的自变量是私钥 sk。同时，它也是解密算法中的核心内容。通过 在秘密值 s 上评估密文多项式，能够 恢复 出加密前的消息 m（或者其近似值），并且还会有噪声项 v。

• 在加法中，对于左边的多项式部分，直接相加并不会影响其结构。由于左边可以直接相加，所以右边的评估部分也直接相加即可。
• 在乘法中，对于左边的多项式部分，直接相乘会导致产生一个新的项，通过适当的缩放、四舍五入和重线性化技术来处理结果。最终，乘法后的结果仍然是一个可以在秘密值 s 上进行评估的多项式。

整体思路就是，在 LPR.ES 方案的基础上，首先将加密的输出弄成 $[c_0+c_1\cdot s{]}_q=\Delta \cdot m+v$ 的形式，然后解密的过程就是对这个式子进行简单的解方程。关键就在于中间的同态操作如何进行。

1. Addition

 假设有两个密文 $c{t}_1$ 和 $c{t}_2$，其中：
$$[c{t}_i(s){]}_q=[c_{i,0}+c_{i,1}\cdot s{]}_q=\Delta \cdot m_i+v_i(i=1,2)$$那么可以很容易地看出：
$$\begin{gathered} [c{t}_1(s)+c{t}_2(s){]}_q=[(c_{1,0}+c_{2,0})+(c_{1,1}+c_{2,1})\cdot s{]}_q \\ =\Delta \cdot [m_1+m_2{]}_t+v_1+v_2-ϵ\cdot t\cdot r \end{gathered}$$其中，$ϵ=\frac{q}{t}-\Delta =\frac{r_t(q)}{t}<1$，并且 $m_1+m_2=[m_1+m_2{]}_t+t\cdot r$。注意 $||r||\le 1$，这意味着 加法操作中噪声最多增加 t。因此，可以定义 同态加法 操作为：
$$FV.SH.Add(c{t}_1,c{t}_2):=([c{t}_1[0]+c{t}_2[0]{]}_q,[c{t}_1[1]+c{t}_2[1]{]}_q)$$

关于上面公式中 $-ϵ\cdot t\cdot r$ 是怎么来的：

• $ϵ$ 表示一个小于1的量，它是由于加法操作中出现的四舍五入误差。
• $t\cdot r$ 是由于取模 $t$ 时的误差项引入的 调整项。这个误差项来源于 $m_1+m_2$ 和 $t$ 之间的关系。

2. Multiplication

 同态乘法包括两个步骤：
 第一步相对简单，基本上是将多项式 $c{t}_1(x)$ 和 $c{t}_2(x)$ 相乘并按 $t/q$ 缩放 (scaling)。然而，问题在于我们得到的密文包含了 3 个环元素，而不是 2 个。
 第二步解决了这个问题，这一过程称为 “重线性化” (relinearisation)。

2.1 基本的乘法 (第一步)

 首先，我们将密文 $c{t}_i(x)$ 在 s 上的评估写为：
$$c{t}_i(s)=c_{i,0}+c_{i,1}\cdot s=\Delta \cdot m_i+v_i+q\cdot r_i$$

关于这里的表示，为什么比之前的表示多了一个 $q\cdot r_i$：
实际上和取模相关，上面式子中的 $c{t}_i(s)$ 是对 q 取模的，如果将取模符号去掉，则需要加上一个 $r_i$ 倍的 $q$，才能使等式成立。

 简单计算表明 $||r_i||<\delta \cdot ||s||$。然后我们将这些表达式相乘，得到：
$$\begin{gathered} (c{t}_1\cdot c{t}_2)(s)=c_0+c_1\cdot s+c_2\cdot s^2(2) \\ ={\Delta }^2\cdot m_1\cdot m_2+\Delta \cdot (m_1\cdot v_2+m_2\cdot v_1)+q\cdot (v_1\cdot r_2+v_2\cdot r_1)+v_1\cdot v_2+q\cdot \Delta \cdot (m_1\cdot r_2+m_2\cdot r_1)+q^2\cdot r_1\cdot r_2 \end{gathered}$$上述表达式显示，为了恢复一个密文表示 $[m_1\cdot m_2{]}_t$，我们需要按 $1/\Delta$ 进行缩放，由于 $\Delta$ 不一定能整除 q，我们会得到由 最后一项 的四舍五入误差 (rounding error) 引起的 大噪声。为了解决这个问题，我们将 按 $t/q$ 进行缩放 (scaling)。

q 应该是要大于 t 的。

 假设 $c{t}_1(x)\cdot c{t}_2(x)=c_0+c_1\cdot x+c_2\cdot x^2$，那么我们使用以下 近似：
$$\frac{t}{q}\cdot (c{t}_1\cdot c{t}_2)(s)=\lfloor \frac{t\cdot c_0}{q}\rfloor +\lfloor \frac{t\cdot c_1}{q}\rfloor \cdot s+\lfloor \frac{t\cdot c_2}{q}\rfloor \cdot s^2+r_a(3)$$这里引入了一个 近似误差 $r_a$，其大小小于 $(\delta \cdot ||s||+1{)}^2/2$。
 通过这些步骤，我们得到了一个密文，该密文表示乘法结果，但它的噪声已经增长，因此需要通过重线性化来恢复。

 $r_a$ 表示在缩放和四舍五入过程中引入的 附加误差。这通常是因为在进行密文乘积和缩放时，可能无法完全精确地恢复原始的乘积结果，导致误差的引入。
 $r_a$ 通常是一个很小的量，表示在计算过程中引入的不可避免的噪声。
 关于公式 $c{t}_1(x)\cdot c{t}_2(x)=c_0+c_1\cdot x+c_2\cdot x^2$ 是怎么来的，实际上就是把 多项式表示的密文 相乘了。

 如果我们写 $m_1\cdot m_2=[m_1\cdot m_2{]}_t+t\cdot r_m$，则 $||r_m||<(t\cdot {\delta }_R)/4$。
 同样地，如果我们写 $v_1\cdot v_2=[v_1\cdot v_2{]}_{\Delta }+\Delta \cdot r_v$，则 $||r_v||<(E^2\cdot {\delta }_R)/\Delta$。其中，E 是原始噪声项的界限，$||v_i||<E$。
 通过将 等式 (2) 两边乘以 t/q，并对方程进行分组，我们得到一个稍显复杂的等式，其中我们主要用了 $t\cdot \Delta =q-r_t(q)$:
$$\begin{gathered} \frac{t\cdot (c{t}_1\cdot c{t}_2)(s)}{q}=\Delta \cdot [m_1\cdot m_2{]}_t+(m_1\cdot v_2+m_2\cdot v_1)+t\cdot (v_1\cdot r_2+v_2\cdot r_1) \\ +r_v+(q-r_t(q))\cdot (r_m+m_1\cdot r_2+m_2\cdot r_1)+q\cdot t\cdot r_1\cdot r_2 \\ +\frac{t}{q}\cdot [v_1\cdot v_2{]}_{\Delta }-\frac{r_t(q)}{q}\cdot (\Delta \cdot m_1\cdot m_2+(m_1\cdot v_2+m_2\cdot v_1)+r_v) \end{gathered}$$

这个式子是使用了上面提到的 $m_1\cdot m_2$ 和 $v_1\cdot v_2$ 代入到式子 (2) 中获得的。
下面会将最后一行表示为 $r_r$，它是由于 $q\gg t,q\gg [q{]}_t$ 而产生的 舍入误差。

写出这种表达式的基本思路是明确哪些项在对模 q 取余后会消失，以及哪些项会因四舍五入而受到影响。请注意，在上面的表达式中，除了 最后一行 (记为 $r_r$) 外，所有项都是 整数。rounding 仅影响最后一行，并且 $||r_r||<{\delta }_R\cdot (t+1/2{)}^2+1/2$。对模 q 取余并代入方程 (3) 后得到：
$$\begin{gathered} [|\frac{t\cdot c_0}{q}|+|\frac{t\cdot c_1}{q}|\cdot s+|\frac{t\cdot c_2}{q}|\cdot s^2{]}_q \\ =\Delta \cdot [m_1\cdot m_2{]}_t+(m_1\cdot v_2+m_2\cdot v_1) \\ +t\cdot (v_1\cdot r_2+v_2\cdot r_1)+r_v-r_t(q)\cdot (r_m+m_1\cdot r_2+m_2\cdot r_1)+\lfloor r_r-r_a\rceil \end{gathered}$$很容易对右侧的 新噪声项 的大小进行 界定，从而最终得出以下引理。

• Lemma 2
   设 $c{t}_i$ 为 $i=1,2$ 时的两个密文，其中 $[c{t}_i(s){]}_q=\Delta \cdot m_i+v_i$ 且 $||v_i||<E<\Delta /2$，并且设 $c{t}_1(x)\cdot c{t}_2(x)=c_0+c_1\cdot x+c_2\cdot x^2$，则：
  $$[|\frac{t\cdot c_0}{q}|+|\frac{t\cdot c_1}{q}|\cdot s+|\frac{t\cdot c_2}{q}|\cdot s^2{]}_q=\Delta \cdot [m_1\cdot m_2{]}_t+v_3$$其中 $||v_3||<2\cdot {\delta }_R\cdot t\cdot E\cdot ({\delta }_R\cdot ||s||+1)+2\cdot t^2\cdot {\delta }_R^2\cdot (||s||+1{)}^2$。
  • 噪声增长：
     引理表明，在进行密文乘法时，噪声不会呈二次增长，而是大致由因子 $2\cdot t\cdot {\delta }_R^2\cdot ||s||$ 进行放大。
  • 密钥范数的影响：
     密钥 s 的范数对噪声增长有显著影响，尤其是当 $||s||$ 较大时，噪声增长会更快。通过使用优化假设 $||s||=1$，可以显著限制乘法过程中噪声的增长。

按照之前的思路可以看到，这里对于等式右边的部分，已经通过一些方法变成了解密算法中的形式，接下来要做的是把灯饰左边多出来的那一项通过重线性化去掉。

2.2 重线性化 (第二步)

 利用引理 2，我们已经有了一个加密了两个明文乘积的密文。现在需要将密文多项式，从二次变成一次，正是这个步骤需要引入一个 重线性化密钥 rlk。
 设 $ct=[c_0,c_1,c_2]$ 表示一个二次密文，我们需要找到 $c{t}^{\prime }=[c_0^{\prime },c_1^{\prime }]$，使得：
$$[c_0+c_1\cdot s+c_2\cdot s^2{]}_q=[c_0^{\prime }+c_1^{\prime }\cdot s+r{]}_q$$其中，$||s||$ 是小的。
 由于 $s^2$ 是未知的，一个初步的想法是提供一个 $s^2$ 的 masked version 如下（与 LPR.ES.PublicKeyGen 比较）：
$$\begin{gathered} Sample{a}_0\leftarrow R_q,e_0\leftarrow \chi \\ Outputrlk:=([-(a_0\cdot s+e_0)+s^2{]}_q,a_0) \end{gathered}$$请注意，$rlk[0]+rlk[1]\cdot s=s^2+e_0$。
 然而，问题在于，由于 $c_2$ 是 $R_q$ 中的随即元素，噪声 $e_0$ 会被放大，导致产生一个对 $c_2\cdot s^2$ 的不太好的近似 (bad approximation)，从而引入巨大的误差 r。

---

1. On Ideal Lattices and Learning with Errors over Rings ↩︎