前言

借鉴致远的文章学习同态加密，本文主要记录无需自举的层次同态加密流程，参考文献为Zvika Brakerski、Craig Gentry和Vinod Vaikuntanathan的《(Leveled) Fully Homomorphic Encryption without Bootstrapping》，这篇文章是HElib库所使用的基础算法。下面介绍全同态加密的历史发展流程以及本文的针对性问题：

😄	方法演变	特点
1	部分同态加密方案均基于理想格难题。	两个原始噪声量为$B$的密文在加法运算后，噪声量轻微增长至$2B$，而在乘法运算时指数级增长至$B^2$，无法用于高阶多项式的计算。
2	为了解决上述问题，Gentry设计了Bootstrapping操作，通过在密文上同态运行解密函数来 “更新” 密文， 从而降低噪声。	解密函数往往比较复杂，超出了多数部分同态加密方案的深度限制，因此无法直接同态评估解密电路。
3	为了解决上述问题，Gentry在稀疏子集和假设下，引入压缩（Squashing step）技术。	① 参数的爆炸性增长。为了支持自举，部分同态加密必须满足一系列参数要求。例如，为了安全地评估深度为$D$的电路，格问题的维度必须为$\Omega (D\cdot \lambda )$；为了实现自举，解密函数的深度为$\Omega (\lambda )$密文系数的比特长度为$\Omega (D)$。因此，“新鲜”密文的大小为$\tilde{\Omega }({\lambda }^3)$。 ② 自举操作的内在成本高。自举需要同态地执行解密函数，解密函数本身的复杂度是$\Omega (\lambda )$，而密文的大小为$\tilde{\Omega }({\lambda }^3)$，因此自举的成本至少是$\tilde{\Omega }({\lambda }^4)$。
本文	为了解决上述问题，文章基于RLWE问题提出了一个无需自举的层次全同态加密，通过构建模数阶梯，在每层电路运算后，将密文切换到下一个更小的模数，从而缩小噪声。	在不使用自举作为优化的情况下，$L$层电路的每门计算开销为$\tilde{O}(\lambda \cdot L^3)$，随层数增加而增加；在使用的情况下，每门计算开销为$\tilde{O}({\lambda }^3)$，与层数无关。

---

---

一、预备知识

1. 模切换

令 $[\cdot {]}_p$ 表示模 $p$，下面介绍模切换的理论基础：

这个引理告诉我们以下信息：

• 一个不知道密钥 $s$ ，而只知道其密钥长度的评估器，可以将模 $q$ 下的密文 $c$ 转换为模 $p$ 下不同的密文 $c^{\prime }$ ，同时保证两个密文的解密结果一致，即$$⟨c^{\prime },s⟩\mathrm{mod}p=⟨c,s⟩\mathrm{mod}q\mathrm{mod}2$$
• 密文 $c$ 到密文 $c^{\prime }$ 只涉及简单的缩放操作和取整操作，即 $$c^{\prime }\approx (p/q)\cdot c$$
• 如果密文足够短，模数 $p$ 足够小于模数 $q$ ，密文中的噪声量会减小，即$$|[⟨c^{\prime },s⟩{]}_p|<|[⟨c,s⟩{]}_q|$$

根据上面的解释，我们知道：模数切换可以让评估者在不知道密钥和不自举的情况下降低噪声的幅度，可以用来管理FHE方案中的噪声！

2. 容错学习

本文的工作既可以基于LWE，也可以基于RLWE，但是在RLWE下效率更高。为了后续表述的方便，下面合并LWE和RLWE表示，形式化为 General Learning with Errors（GLWE），如下：

• GLWE：对于安全参数 $\lambda$ ，所有计算在环 $R_q=R/qR$ 上进行，其中商环 $R=\mathbb{Z}[x]/f(x)$ ，多项式 $f(x)=x^d+1$ ，环的维度 $d=d(\lambda )$ 为2的幂次。设置样本维度 $n=n(\lambda )$，素数模 $q=q(\lambda )\ge 2$，噪声分布 $\chi =\chi (\lambda )\in R$ ，则 ${\text{GLWE}}_{n,f,q,\chi }$ 问题是指区分样本 $(a_i,b_i)\in R_q^{n+1}$ 来自均匀分布还是GLWE分布。在GLWE分布下，$a_i$ 通过随机采样得到，$b_i$ 由消息 $s$ 和小噪声 $e_i\in \chi$ 构造得到 $b_i=⟨a_i,s⟩+e_i$ 。
• LWE：当 $d=1$ 时，GLWE问题转为LWE问题。
• RLWE：当 $n=1$ 时，GLWE问题转为RLWE问题。

值得注意的是，模数 $q$ 远大于噪声 $B$ 时，GLWE问题很容易破解。因此文章中，在无自举情况下，设置 $q/B=\exp (L)$，在自举情况下，设置 $q/B$ 为准多项式级别。

计算安全参数 $\kappa$：决定了加密算法的输入空间大小，单位为 bit 。
统计安全参数 $\lambda$ ：衡量了样本分布与均匀分布之间的统计距离（一般为 $2^{\lambda }$ ）。
准多项式：$2^{O(poly(\log L))}$
$d=d(\lambda )$：$d$ 是关于 $\lambda$ 的多项式

---

二、核心算法

下面将从基础方案开始，一步步描述算法设计。

1. 基础方案

1.1. 算法描述

• 参数设置

参数	描述
o ∈ { 0 , 1 } o\in\{0,1\} o∈{0,1}	决定是LWE的参数设置（$d=1$），还是RLWE的参数设置（$n=1$）
$\mu$	参数的比特位数
$q$	模数，$\mu$ 比特
$\chi =\chi (\lambda ,\mu ,b)$	噪声分布，其方差关于 $d/n$ 次线性，噪声的范数最大为$B\propto \text{sublinear}(q)$
$d=d(\lambda ,\mu ,b)$	环的维度
$n=n(\lambda ,\mu ,b)$	维度。为了实现 $2^{\lambda }$ 安全， $n\cdot d=\Omega (q/B)$，且$n,d\propto \log q$
$N=n\cdot polylog(q)$	样本个数。在LWE情况下，要求 $N>2n\log q$ ；在RLWE情况下，要求 $N=\log (q\cdot {\lambda }^{\omega (1)})$

次线性：函数 $f(x)$ 满足 $$\underset{n\to \infty }{\lim }\frac{f(n)}{n}=0$$ 即 $f(x)$ 的增长速度小于线性函数，常见的次线性函数有 $\log x$ 和 $\sqrt{x}$。

• 密钥生成

密钥	描述
$s$	私钥：随机采样 $n$ 维向量 $s^{\prime }\in {\chi }^n$，则私钥 $s=(1,s)=(1,s^{\prime }[1],\cdots ,s^{\prime }[n])$
$A$	公钥：随机采样矩阵 $A^{\prime }\in R_q^{N\times n}$ ，向量 $e\in {\chi }^N$，令 $$b=A^{\prime }{s}^{\prime }+2e$$ 则设置 $A=[b|-A^{\prime }]$ ，即矩阵第一列为 $b$ ，后 $n$ 列为 $-A^{\prime }$，共 $N$ 行 $n+1$ 列。 特别的，我们可以观察到 $A\cdot s=2e$，即$$A\cdot s=[b|-A^{\prime }]\cdot s=[A^{\prime }{s}^{\prime }+2e|-A^{\prime }]\cdot [1,s^{\prime }]=A^{\prime }{s}^{\prime }+2e-A^{\prime }{s}^{\prime }=2e$$

• 加密算法
  对于明文 $\mathrm{m}\in R_q$，设置向量 $m=(\mathrm{m},0,\cdots ,0)\in R_q^{n+1}$。随机采样$r\in R_q^N$，则密文为 $$c=m+A^{T}r\in R_q^{n+1}$$
• 解密算法
  $$\mathrm{m}=[[⟨c,s⟩{]}_q{]}_2$$
  这里需要注意的是，同态计算时只模 $q$，若在解密前噪声量就超过了 $q$，密文将发生改变，无法消除噪声的影响。

1.2. 正确性

首先计算内积：
$$\begin{array}{rl}⟨c,s⟩& =⟨m+A^{T}r,s⟩\\ & =⟨m,s⟩+⟨A^{T}r,s⟩\\ & =⟨m,s⟩+⟨r,As⟩\\ & =⟨m,s⟩+⟨r,2e⟩\\ & =⟨\left[\begin{array}{c}\mathrm{m}\\ 0\\ ⋮\\ 0\end{array}\right],\left[\begin{array}{c}1\\ s^{\prime }[1]\\ ⋮\\ s^{\prime }[n]\end{array}\right]⟩+2\cdot ⟨r,e⟩\\ & =\mathrm{m}+2\cdot ⟨r,e⟩\end{array}$$再进行模运算可以得到$$[[⟨c,s⟩{]}_q{]}_2=\mathrm{m}$$

1.3. 安全性

在选择明文攻击下，由于明文和密文独立采样，并且算法基于GLWE难题构造，因此攻击者无法破解明文。

2. 密钥切换

2.1. 算法描述

BV11 方案中，利用公钥中提供的“提示信息”，将同态乘法产生的长密文和长密钥转换为一个由不同密钥解密的短密文，从而解决密文维度爆炸问题。这个方法不仅可以用于约减密文维度，还可以用于切换密钥和对应密文。假设我们要将私钥 $s_1\in R_q^{n_1+1}$ 切换为 $s_2\in R_q^{n_2+1}$ ，其流程如下：

• 生成切换密钥

步骤	描述
Step1	设置维度 $N=(n_1+1)\cdot \lceil \log q\rceil$，以 $s_2$ 为私钥，生成对应的公钥 $A_2$ 。
Step2	将密钥 $s_1$ 转为二进制编码 $u=(u_0,u_1,\cdots ,u_{\lfloor \log q\rfloor })\in R_q^{(n_1+1)\times \lceil \log q\rceil }$ ，满足 $$s_1=\sum _{j=0}^{\lfloor \log q\rfloor }{2}^j\cdot u_j$$
Step3	将 $u$ 加到 $A_2$ 的第一列，得到切换密钥 ${\tau }_{s_1\to s_2}\in R_q^{N\times (n_2+1)}$，即 $${\tau }_{s_1\to s_2}=[b_2+u|-A_2^{\prime }]$$

• 密钥切换
  利用切换密钥 ${\tau }_{s_1\to s_2}$ 和密文 $c_1$进行如下操作，从而将以 $s_1$ 为私钥的密文 $c_1$，转为以 $s_2$ 为私钥的密文 $c_2$：$$c_2=(c_1,2\cdot c_1,\cdots ,2^{\lfloor \log q\rfloor }\cdot c_1)\cdot {\tau }_{s_1\to s_2}$$

2.2. 正确性

首先计算内积：
$$\begin{array}{rl}⟨c_2,s_2⟩& =(c_1,2\cdot c_1,\cdots ,2^{\lfloor \log q\rfloor }\cdot c_1)\cdot {\tau }_{s_1\to s_2}\cdot s_2\\ & =(c_1,2\cdot c_1,\cdots ,2^{\lfloor \log q\rfloor }\cdot c_1)\cdot ([b_2+u|-A_2^{\prime }]\cdot [1|s_2^{\prime }])\\ & =(c_1,2\cdot c_1,\cdots ,2^{\lfloor \log q\rfloor }\cdot c_1)\cdot (b_2+u-A_2^{\prime }\cdot s_2^{\prime })\\ & =(c_1,2\cdot c_1,\cdots ,2^{\lfloor \log q\rfloor }\cdot c_1)\cdot (2e_2+u)\end{array}$$再进行模运算可以得到$$\begin{array}{rl}[[⟨c,s⟩{]}_q{]}_2& =(c_1,2\cdot c_1,\cdots ,2^{\lfloor \log q\rfloor }\cdot c_1)\cdot (2e_2+u)(\mathrm{mod}q)(\mathrm{mod}2)\\ & =(c_1,2\cdot c_1,\cdots ,2^{\lfloor \log q\rfloor }\cdot c_1)\cdot u\\ & =(c_1,2\cdot c_1,\cdots ,2^{\lfloor \log q\rfloor }\cdot c_1)\cdot (u_0,u_1,\cdots ,u_{\lfloor \log q\rfloor })\\ & =c_1\cdot \sum _{j=0}^{\lfloor \log q\rfloor }{2}^j\cdot u_j\\ & =c_1\cdot s_1\\ & =\mathrm{m}\end{array}$$

3. 模切换

3.1. 核心思想

• 现有方法：BV11 通过一次性的模数切换，减小自举过程中的计算开销。
• 观察：当模数从 $q$ 切换为 $p<q$ 时，噪声 $B$ 也会降至 $(p/1)\cdot B$。
• 方法：设置阶梯递减的模数，对于每一层模数有 $q_i=q/x^i$ ，在模数切换后有 $$x^2(\mathrm{mod}{q}_{i-1})=\frac{q_i}{q_{i-1}}\cdot x^2(\mathrm{mod}{q}_i)=x(\mathrm{mod}{q}_i)$$这意味着噪声始终是 $B$-bound 的。

3.2. 算法描述

• 模切换：令环 $R$ 的度数为 $d$ ，模数 $q>p>r$ 满足 $p=q=1\mathrm{mod}r$，$n$ 维向量 $c\in R^n$。现在要在环 $R^n$ 中找一个最靠近 $(p/q)\cdot c$ 的元素 $c^{\prime }$ ，且该元素满足 $c^{\prime }=c\mathrm{mod}r$ 。那么，对于任意满足 $\Vert [⟨c,s⟩{]}_q\Vert <q/2-(q/p)\cdot {\gamma }_R\cdot (r/2)\cdot \sqrt{d}\cdot {\ell }_1^{(R)}(s)$ 的私钥 $s\in R^n$ 有：
  $$\begin{gathered} [[⟨c^{\prime },s⟩{]}_p{]}_r=[[⟨c,s⟩{]}_q{]}_r \\ \Vert [⟨c^{\prime },s⟩{]}_p\Vert <(p/q)\cdot \Vert [⟨c,s⟩{]}_q\Vert +{\gamma }_R\cdot (r/2)\cdot \sqrt{d}\cdot {\ell }_1^{(R)}(s) \end{gathered}$$其中$${\ell }_1^{(R)}(s)=\sum _i\Vert s[i]\Vert$$
  ⭐️ 这段形式化的定义和预备知识中介绍的差不多，都是要在一堆约束下寻找合适的 $c^{\prime }$ ，只不过以前是基于LWE问题，因此环的度数为1，现在可以扩展到RLWE问题上。

• 噪声管理：设置奇数模和短私钥后，使用模切换技术，原本上限为 $q/2-(q/p)\cdot {\gamma }_R\cdot (r/2)\cdot \sqrt{d}\cdot {\ell }_1^{(R)}(s)$ 的噪声将降到 $(q/p)\cdot \Vert [⟨c,s⟩{]}_q\Vert \cdot {\gamma }_R\cdot (r/2)\cdot \sqrt{d}\cdot {\ell }_1^{(R)}(s)$ 以下。

3.3. 正确性

根据模的定义，我们有
$$[⟨c,s⟩{]}_q=⟨c,s⟩-kq$$对于相同的 $k$ 计算
$$e_p=⟨c^{\prime },s⟩-kp$$在模 $p$ 运算下有
$$e_p\mathrm{mod}p=[⟨c^{\prime },s⟩{]}_p$$计算其范数
$$\begin{array}{rl}\Vert e_p\Vert & =\Vert ⟨c^{\prime },s⟩-kp\Vert \\ & =\Vert ⟨c^{\prime },s⟩-kp+⟨(p/q)\cdot c,s⟩-⟨(p/q)\cdot c,s⟩\Vert \\ & =\Vert ⟨c^{\prime }-(p/q)\cdot c,s⟩-kp+⟨(p/q)\cdot c,s⟩\Vert \\ & \le \Vert ⟨c^{\prime }-(p/q)\cdot c,s⟩\Vert +(p/q)\cdot \Vert ⟨c,s⟩-kq\Vert \\ & \le {\gamma }_R\cdot \sum _{j=[n]}\Vert c^{\prime }[j]-(p/q)\cdot c[j]\Vert \cdot \Vert s[j]\Vert +(p/q)\cdot \Vert [⟨c,s⟩{]}_q\Vert \\ & \le {\gamma }_R\cdot (r/2)\cdot \sqrt{d}\cdot {\ell }_1^{(R)}(s)+(p/q)\cdot \Vert [⟨c,s⟩{]}_q\Vert \\ & <p/2\end{array}$$这说明$$[⟨c^{\prime },s⟩{]}_p=⟨c^{\prime },s⟩-kp$$又因为$c^{\prime }=c\mathrm{mod}r,p=q\mathrm{mod}r$，所以
$$\begin{array}{rl}[⟨c^{\prime },s⟩{]}_p& =e_p(\mathrm{mod}r)\\ & =⟨c^{\prime },s⟩-kp\\ & =⟨c,s⟩-kq\\ & =[⟨c,s⟩{]}_q\end{array}$$

4. 总方案

4.1. 算法描述

• 参数设置

参数	描述
o ∈ { 0 , 1 } o\in\{0,1\} o∈{0,1}	决定是LWE的参数设置（$d=1$），还是RLWE的参数设置（$n=1$）
$L$	乘法深度，即允许计算的乘法次数
$\mu =\mu (\lambda ,L,b)$	参数的比特位数，取$\mu =\theta (\log \lambda +\log L)$
$para{m}_j=(q_j,d_j,n_j,N_j,{\chi }_j)$	对于第 $j\in [L]$ 层，设置模数 $q_j$ 、环的维度 $d_j$ 、维度 $n_j$ 、样本个数 $N_j$ 、噪声分布 ${\chi }_j$ 。其中，模数从 $(L+1)\cdot \mu$ 比特的 $q_L$ 阶梯下降至 $\mu$ 比特的 $q_0$ 。在使用时，从 $para{m}_L$ 开始使用。
$\chi =\chi (\lambda ,\mu ,b)$	，其方差关于 $d/n$ 次线性，噪声的范数最大为$B\propto \text{sublinear}(q)$

• 密钥生成

密钥	描述
$s_{j\in [L]}$	私钥：对于第 $j\in [L]$ 层，利用参数 $para{m}_j$ 生成私钥 $s_j$
$A_{j\in [L]}$	公钥：对于第 $j\in [L]$ 层，利用参数 $para{m}_j$ 生成共钥 $A_j$
$s_{j+1}^{\prime }$	乘法密钥： $s_{j+1}^{\prime }=s_j\otimes s_j$。例如，当 $s_j=(x_1,x_2,x_3)$ 时，$s_{j+1}^{\prime }=(x_1{x}_1,x_1{x}_2,x_1{x}_3,x_2{x}_1,x_2{x}_2,x_2{x}_3,x_3{x}_1,x_3{x}_2,x_3{x}_3)$
${\tau }_{s_{j+1}^{\prime }\to s_j}$	切换密钥：将乘法计算后的私钥 $s_{j+1}^{\prime }$ 切换为下一级私钥 $s_j$

• 加密算法
  对于明文 $\mathrm{m}\in R_{q_L}$，设置向量 $m=(\mathrm{m},0,\cdots ,0)\in R_{q_L}^{n_L+1}$。随机采样$r\in R_{q_L}^{N_L}$，则密文为$$c=m+(A_L{)}^T\cdot r\in R_{q_L}^{n_L+1}$$
• 解密算法
  $$\mathrm{m}=[[⟨c,s_j⟩{]}_{q_j}{]}_2$$
• 同态计算

流程	描述
Step1	利用密钥切换和模切换技术，将密文 $c_1$ 和 $c_2$ 的参数切换到同一层级 $j$。
Step2	同态加法的结果如下 $$c_3=c_1+c_2\mathrm{mod}{q}_j$$ 同态乘法的结果为线性方程 $L_{c_1,c_2}(y)=⟨c_1\otimes c_2,y⟩$ 的系数 。
Step3	利用切换密钥 ${\tau }_{s_j^{\prime }\to s_{j-1}}$ 将 $c_3$ 的密钥 $s_j^{\prime }$ 切换至 $s_{j-1}$，同时将模 $q_j$ 切换至 $q_{j-1}$，从而将密文 $c_3$ 的参数切换到下一层级。加法运算之后，可以不进行这一步，但是乘法运算之后必须进行。

4.2. 正确性

解密成功的前提是噪声上界小于 $q/2$ ，文章中推理了算法每个流程的噪声上界，并最终得到方案的整体噪声始终满足 $B$-bound 的充分条件是：

• 对于每一层 $j$ ，令 ${\eta }_{\text{SwitchKey},j}=2\cdot {\gamma }_R\cdot B_{\chi }\cdot C_{n_j+1}^2\cdot \lceil \log q_j\rceil \cdot \sqrt{d_j}$，${\eta }_{\text{Scale},j}={\gamma }_R\cdot B_{\chi }\cdot \sqrt{d_j}\cdot (n_{j-1}+1)$ ，噪声上界满足以下条件：
  $$B\ge 2\cdot ({\eta }_{\text{Scale},j}+{\eta }_{\text{SwitchKey},j})$$
• 对于每一层 $j$ ，模数满足以下条件：
  $$\frac{q_j}{q_{j-1}}\ge 2\cdot B\cdot {\gamma }_R$$

---

三、算法优化

1. 维度 - 次数转换

1.1. 核心思想

• 针对性问题：层次全同态加密方案的定义要求，解密电路的复杂度独立于乘法深度 $L$。
  上述方案在LWE场景下，底层（$j=0$）参数 $n_0,q_0,{\chi }_0$ 都与 $L$ 无关，满足条件；但在RLWE场景下，为了安全，环的维度 $d$ 与顶层（$j=L$）模数 $q_L$ 的比特长度成正比，而 $q_L$ 的比特长度与 $L$ 成正比，因此底层环维度也与 $L$ 成正比，并不满足定义要求。
• 方法：多项式系数的奇偶分解。
  环 $R_q=\mathbb{Z}[x]/(x^d+1)$ 上元素 $a$ 是一个多项式，可以根据项数的奇偶将其分解为环 $R_q=\mathbb{Z}[x]/(x^{d/2}+1)$ 上的两个元素。通过在每层同态计算后进行环分解，可以让环维度不断下降，最终维度下降至一个固定值，不再与 $L$ 相关。

1.2. 算法描述

利用多项式系数的奇偶分解，可以将 ${\text{GLWE}}_{n,d,q,\chi }$ 问题（$d=2^k$）转为 $2^k$ 个 ${\text{GLWE}}_{2^{k}n,d/2^k,q,\chi }$ 问题。

• 多项式系数的奇偶分解
  对于 $a(x)\in \mathbb{Z}[x]/(x^d+1)$ ，$d$ 为2的幂次（是偶数），可以进行如下分解：
  $$\begin{array}{rl}a(x)& =a_0{x}^0+a_1{x}^1+\cdots +a_{d-1}{x}^{d-1}\\ & =(a_0{x}^0+a_2{x}^2+\cdots +a_{d-2}{x}^{d-2})+(a_1{x}^1+a_3{x}^3+\cdots +a_{d-1}{x}^{d-1})\\ & =(a_0{x}^0+a_2{x}^2+\cdots +a_{d-2}{x}^{d-2})+x\cdot (a_1{x}^0+a_3{x}^2+\cdots +a_{d-2}{x}^{d-2})\\ & =(a_0\cdot (x^2{)}^0+a_2\cdot (x^2{)}^1+\cdots +a_{d-2}\cdot (x^2{)}^{d/2-1})+x\cdot (a_1\cdot (x^2{)}^0+a_3\cdot (x^2{)}^1+\cdots +a_{d-2}\cdot (x^2{)}^{d/2-1})\end{array}$$ 令$a^{(even)}=(a_0,a_2,\cdots ,a_{d-2})$，$a^{(odd)}=(a_1,a_3,\cdots ,a_{d-1})$，则上式可以转化为
  $$\begin{array}{rl}a(x)& =a^{(even)}(x^2)+x\cdot a^{(odd)}(x^2)\end{array}$$

• 奇偶分解下的密文加法
  对于密文加法 $c(x)=a(x)+b(x)$ 有：
  $$\begin{array}{rl}c(x)& =a(x)+b(x)\\ & =(a^{(even)}(x^2)+x\cdot a^{(odd)}(x^2))+(b^{(even)}(x^2)+x\cdot b^{(odd)}(x^2))\\ & =(a^{(even)}(x^2)+b^{(even)}(x^2))+x\cdot (a^{(odd)}(x^2)+b^{(odd)}(x^2))\end{array}$$则
  $$\begin{gathered} c^{(even)}=(a_0+b_0,a_2+b_2,\cdots ,a_{d-2}+b_{d-2}) \\ {c}^{(odd)}=(a_1+b_1,a_3+b_3,\cdots ,a_{d-1}+b_{d-1}) \end{gathered}$$

• 奇偶分解下的密文乘法
  对于密文乘法 $c(x)=a(x)\cdot b(x)$ 有：
  $$\begin{array}{rl}c(x)& =c^{(even)}(x^2)+x\cdot c^{(odd)}(x^2)=a(x)\cdot b(x)\\ & =(a^{(even)}(x^2)+x\cdot a^{(odd)}(x^2))\cdot (b^{(even)}(x^2)+x\cdot b^{(odd)}(x^2))\\ & =(a^{(even)}(x^2)\cdot b^{(even)}(x^2))+x^2\cdot (a^{(odd)}(x^2)\cdot b^{(odd)}(x^2))\\ & +x\cdot (a^{(even)}(x^2)\cdot b^{(odd)}+a^{(odd)}(x^2)\cdot b^{(even)}(x^2))\end{array}$$则
  $$\begin{array}{rl}{c}^{(even)}(x^2)& =(a^{(even)}(x^2)\cdot b^{(even)}(x^2))+x^2\cdot (a^{(odd)}(x^2)\cdot b^{(odd)}(x^2))\\ c^{(odd)}(x^2)& =a^{(even)}(x^2)\cdot b^{(odd)}+a^{(odd)}(x^2)\cdot b^{(even)}(x^2)\end{array}$$用 $x$ 代替 $x^2$ 有
  $$\begin{array}{rl}{c}^{(even)}(x)& =(a^{(even)}(x)\cdot b^{(even)}(x))+x\cdot (a^{(odd)}(x)\cdot b^{(odd)}(x))\\ c^{(odd)}(x)& =a^{(even)}(x)\cdot b^{(odd)}+a^{(odd)}(x)\cdot b^{(even)}(x)\end{array}$$

• 奇偶分解下的解密算法
  假设密文 $c(x)$ 对应私钥为 $s(x)$ ，则解密时有 $m(x)=[[⟨c(x),s(x)⟩{]}_q{]}_2$，此时
  $$\begin{array}{rl}{m}^{(even)}(x)& =\left[\right[⟨c^{(even)}(x),s^{(even)}(x)⟩+x\cdot ⟨c^{(odd)}(x),s^{(odd)}(x)⟩{]}_q{]}_2\\ m^{(odd)}(x)& =\left[\right[⟨c^{(even)}(x),s^{(odd)}(x)⟩+x\cdot ⟨c^{(odd)}(x),s^{(even)}(x)⟩{]}_q{]}_2\end{array}$$即 $m^{(even)}(x)$ 的私钥为 $(s^{(even)}(x),s^{(odd)}(x))$ ，而 $m^{(odd)}(x)$ 的私钥为 $(s^{(odd)}(x),s^{(even)}(x))$ ，通过对元素重新排序，就可以使二者的私钥相同。

1.3. 算法优化

• 针对性问题：奇偶分解下，需要解密两次，原来只需要一次。
• 方法：如果一开始就将明文编码为偶数次多项式，而奇数项为 0 ，即 $m^{(odd)}(x)=0$ ，则 $m(x)=m^{(even)}(x)$ 。此时，与奇数项相关的计算均为 0 ，只用对偶数项进行同态计算并解密，即只解密一次即可。

2. 批处理（Batching）

2.1. 核心思想

相关知识补充见：三.4 分圆整数环的分解

• 观察：基于理想格或 RLWE 的算法会降明文空间分解为代数理想，从而使一个明文多项式 $m(x)\in R_p$ 唯一地对应一个 $d$ 维元组 $(m_1,m_2,\cdots ,m_d)$。因此，加密一个环 $R_p$ 上的明文，相当于同时加密了 $d$ 个独立的消息，每个消息位于一个槽（Slot）中，使得一个密文有 $d$ 个明文槽 。根据中国剩余定理，$\bar{\varphi }:R_p\simeq R_p/{\mathfrak{p}}_1\times R_p/{\mathfrak{p}}_2\times \cdots \times R_p/{\mathfrak{p}}_d$ 。因此，对环 $R_p$ 下的一个元素进行同态计算，相当于对 $d$ 个槽独立地、并行地执行相同的操作。
• 方法：批处理技术将多个明文打包（Pack）至同一个密文，同步计算相同的函数，从而将每门关于安全参数的准线性计算开销降至 polylog 级别。

2.2. 算法描述

• Step1：选择模数 $p=1\mathrm{mod}2d$ 且满足 $p=poly(\lambda )$。
• Step2：在生成公钥时，将 $A\cdot s=2\cdot e$ 改为 $$A\cdot s=p\cdot e$$ 此时同态计算不再是环 $R_2$ 下的布尔电路，而是环 $R_p$ 下的算数电路，则对应的解密步骤变为 $$m=[[⟨c,s⟩{]}_{q_j}{]}_p$$需要注意的是，所有涉及生成公钥的步骤都要进行相应改动，比如说生成切换密钥时。此外，如果想在环 $R_p$ 下计算布尔电路，可以利用算术门模拟布尔门，比如 $\text{XOR}(a,b)=a+b-2ab\mathrm{mod}p$ 。
• Step3：在模切换时，在环 $R^n$ 中找一个最靠近 $(q_{j-1}/q_j)\cdot c$ 的元素 $c^{\prime }$ ，且该元素满足 $c^{\prime }=c\mathrm{mod}p$，而非 $c^{\prime }=c\mathrm{mod}2$ 。这一步虽然可能会引入较大的舍入误差，但是噪声仍可控。

3. 自举（Boostrapping）

3.1. 核心思想

• 针对性问题：在本文无自举方案中，计算开销与电路的乘法深度相关。
• 自举：在性能方面，自举可以使每门的计算开销与电路深度无关；在灵活性方面，自举可以进行无限次同态计算，而不用提前设置电路深度；在内存方面，允许将短密文解压为长密文。
• 方法：结合自举技术，并在模数链耗尽之前，预留进行自举的层数。此时，计算开销降为安全参数的准线性级别且与深度无关，从而可以进行任意次同态运算。

3.2. 优化解密电路

由于自举过程中，即解密算法主要涉及加法、乘法、模运算，为减小自举的计算开销，进行如下优化：

• 加法：使用“三进二”加法器，从而将 $N$ 个数的求和问题再 $O(\log N)$ 层内减少至2个数。
• 乘法：乘法 $c[i]\cdot s[i]$ 可以看作以 $c[i]$ 为参数对 $s[i]$ 进行旋转，最多旋转 $\log q$ 次。因此 $⟨c,s⟩$ 最多需要进行 $n\log q$ 次旋转。
• 模运算：模运算类似除法，对 $O(\log \lambda )$ 比特的数字进行模运算，可以由深度为 $O(\log \log \lambda )$ 的电路实现。特别的，模 2 运算相当于取数字的最低有效位，深度为 $O(1)$ 。

综上，电路中门的数量为 $\tilde{O}(\lambda )$ ，乘法深度为 $O(\log \lambda )$ 。

3.3. 优化自举频率

为了寻找最优的自举频率，文章进行数学建模。

• 建立成本模型：假设每计算 $L$ 层电路后进行一次自举； $f(\lambda ,L)$ 为 $L$ 层无自举全同态加密方案中每门的计算开销，与 $L$ 正相关，即 $f(\lambda ,L)=\tilde{O}(\lambda \cdot L^3)$ ；$g(\lambda ,L)$ 表示在一个自举一个密文所需计算开销， 由于 $L$ 层电路后进行一次自举，而自举需要 $c$ 层电路，因此 $g(\lambda ,L)=\tilde{O}(\lambda \cdot (c+L{)}^3)$ 。总的每门开销可以近似为：
  $$h(\lambda ,L)=f(\lambda ,L)+\frac{g(\lambda ,L+c)}{L}$$
• 定性分析：如果 $L$ 太小，会导致摊销成本 $g(\lambda ,L+c)/L$ 很高；如果 $L$ 太大，会导致 $f(\lambda ,L)$ 急剧增长，同时 $g(\lambda ,L)$ 也会变大，间接导致 $g(\lambda ,L+c)/L$ 增长。因此，存在一个中间值以最小化总开销。
• 定量分析：求导找极值点后可以得出，最优 $L_{opt}=\Theta (\log \lambda )$ 。

4. 批量自举（Batching the Boostrapping）

4.1. 核心思想

• 现有方法：批量自举可以让每门的计算开销降至 $\tilde{O}(\lambda )$ 级别，并且与乘法深度无关。
• 针对性问题：在使用批量自举后，如果想直接进行同态计算，会存在以下问题：在批处理后，加密数据被划分到相互独立的互素数明文槽中，而同态计算需要对多个槽的数据进行交互，因此批处理后的结果就无法直接用于计算。
• 方法：每个密文 $d$ 个槽，只有第一个槽存数，其他位置存 0。在进行同态计算时，将密文从第一个槽移到第 $i$ 个槽中，同时也要将对应密钥移到第 $i$ 个槽。

4.2. 算法描述

• Pack：准备切换密钥，把同一个密钥置换到 $d$ 个位置上，得到 $d$ 个新密钥；同时，将 $d$ 个不同密文置换到不同位置上，分别对应一个新密钥；由于同态计算需要在同一密钥下进行，现在每个位置的密文有不同的密钥，所以还需要用密钥切换技术统一密钥。
• Unpack：准备切换密钥，将不同位置上的密钥和密文分别置换到第一个槽中；对每个密文设置相应掩码，使得除了第一个位置上的掩码为1，其余位置为0，通过将该掩码与密文相乘，可以消除其他槽的数据；最终使用密钥和相应掩码密文可以还原指定槽上的明文数据。

5. 扩大明文空间

😵这一节没怎么好好看
大概意思是，如果扩大明文空间，即选择指数级别的模数，将导致模切换过程中的噪声也变为指数级别，从而导致解密失败。为此，文章改进了明文空间，不再使用整数作为模数，而是使用环中的理想作为模。

总结

文章中还有以下几个问题不理解：

• 奇偶分解的优化部分应该如何实现？是否会带来额外的安全风险？
• 为什么自举可以将短密文解压为长密文？