1.   引言

传统的密码体制往往涉及加密信息的交换，需要在交换的节点中分享密钥，这种操作容易引发隐私泄露的问题，特别是需要将敏感数据交给第三方的场景，例如云计算中服务器、提供商和云运营商都可以接触到用户的敏感信息。同态加密，作为密码学里一种特殊的加密方式，可以解决这个问题^[1,2]：在不提供解密密钥的情况下，同态密文可以发给任意的第三方进行计算，第三方返回密文形式的计算结果，最后由用户自行下载解密。全同态加密的概念最早于上世纪70年代被提出，1978年，Rivest等人^[3]第一次提到了通过对密文进行计算，获得对应明文被执行相同运算操作的系统构想，后人把这一想法重新总结命名为全同态加密。

根据密文数据上允许进行运算的种类和次数，同态加密方案可以分为3大类：单同态加密、类同态加密和全同态加密。单同态加密(Partially Homomorphic Encryption, PHE)的特点是仅能支持一种同态运算，但是可以执行无限次该同态运算。例如用ElGamal函数^[4]：${g^{{m_0}}} \cdot {g^{{m_1}}} = {g^{{m_0} + {m_1}}}$可以构造支持加法同态的单同态加密方案，RSA算法^[5]：$m_0^e \cdot m_1^e = {\left( {{m_0} \cdot {m_1}} \right)^e}$则可以用来构造支持乘法同态的单同态加密方案。它们的局限性在于只能进行单一的加法或乘法运算，无法支持同时需要多种同态运算的计算场景。类同态加密(Somewhat Homomorphic Encryption, SWHE)的特点是可以支持多种同态运算，但是允许的运算次数有限。例如基于配对的循环群加密算法^[6]可以同时支持加法和乘法的同态运算，但是乘法只能进行至多1次。此外，还有一种层次型同态加密(Leveled Fully Homomorphic Encryption)，它可以在给定深度的电路上完成有限次的函数同态运算，执行同态运算的次数与电路深度成正相关，本质上仍属于类同态加密。相比于单同态仅支持单一运算，类同态已经初步实现支持混合电路同态运算，但对于一个任意逻辑和深度的函数仍无法实现完整的同态计算。全同态加密(Fully Homomorphic Encryption, FHE)，顾名思义，可以支持无限次、所有种类的电路同态运算。全同态加密方案支持对密文进行任意次数同态计算的特点，可以借此为任何想要的功能构建程序，这些程序可以直接在密文输入上运行，产生密文为相应明文运算结果的加密。全同态加密在私有计算外包方面具有很大的实际意义，例如，在云计算^[7,8]、机器学习^[9]、医疗^[10]等领域，由于不需要数据的解密就可直接运算，它可以由不受信任的一方运行且不会暴露其输入和内部状态，用户的数据安全得到了有效保障。

2009年，Gentry^[11]提出了第1个基于理想格(ideal lattice)构造的全同态方案，它可以支持任意电路的求值。Gentry在他的论文中不仅提出了第1个全同态方案，而且设计了一种由类同态方案构造全同态方案的方法——自举。自举是目前全同态加密方案构造最通用途径，它可以理解为加密方案同态的运行自己的解密算法，将一个噪音接近临界值的密文“刷新”成一个噪声很低的新密文，进而得以继续新一轮的运算。因为对称同态加密方案对云计算的适用性有限，且存在通用转换可以将按比特加密的对称全同态转换成公钥全同态加密，所以全同态加密方案的研究工作主要基于公钥加密体制。在Gentry思想的影响下，涌现了许多新结构的同态加密方案，除了基于格上困难学习假设(Learning With Errors, LWE)的方案之外，还有基于近似最大公约数假设(Approximate Greatest Common Divisor, AGCD)的方案例如Pereira^[12]，基于NTRU(Nth-degree Truncated polynomial Ring Unit)算法的有FINAL^[13], Kamil^[14]和国内向斌武等人^[15]的最新研究成果，其中基于AGCD和NTRU的方案目前均从基于LWE的全同态加密方案“移植”得到，因此本文不对基于这两个困难问题的全同态加密方案做重点讨论。

本文提供了全同态加密自2009年Gentry取得突破性进展以来的一个全面的视角，探究不同技术路线下全同态加密方案的发展脉络和相关应用。本文的第2节补充了格的数学定义，以及基于格的密码学中涉及的相关数学问题，帮助理解后续给出的全同态方案的概念和构造；第3节，根据全同态方案的关键技术特点，分成4个部分详细讲述了每类代表性全同态方案的优化进程和自举算法，并给出了具体实现的相关数据；第4节，根据前文提到的代表性全同态方案，介绍了一些基于这些加密方案设计的全同态算法库及其支持的优化算法；第5节讨论了全同态领域发展的现状和目前存在的一些问题和挑战，总结回顾了本文内容，并对未来全同态加密算法的改进优化方向做出了展望。

2.   背景知识

本节的第1部分介绍格的数学定义，并描述基于格的同态加密方案安全性所依赖的数学困难问题。第2部分则介绍全同态方案中的基本算法模型和同态加密相关的安全性定义。

2.1   格定义及格上困难问题

一个$k$维格是${R^n}$的离散加性子群。令$B = \left( {{{\boldsymbol{b}}_1},{{\boldsymbol{b}}_2}, \cdots ,{{\boldsymbol{b}}_k}} \right)$为${R^n}$中线性无关的向量集合，则$B$中元素的所有整数线性组合的集合可以定义为$B$生成的格$\mathcal{L}\left( B \right)$

其中$B$称为格$\mathcal{L}\left( B \right)$的基。

大多数已知格上的定义都是基于距离的概念。具体来说，对于${R^n}$中的任意向量${\boldsymbol{t}}$和格$\mathcal{L}$中的任意元素${\boldsymbol{v}}$，这两个向量之间的距离定义为${{\mathrm{dist}}}\left( {{\boldsymbol{t}},{\boldsymbol{v}}} \right) = |{\boldsymbol{t}} - {\boldsymbol{v}}{|_2}$。因此，${\boldsymbol{t}}$与$\mathcal{L}$中任意元素之间的最小距离为

定义格$\mathcal{L}$的最小距离为${\lambda _1}\left( \mathcal{L} \right)$，即$\mathcal{L}$中最短的非零向量的长度，即

许多基于格的全同态方案的安全性依赖于最短向量问题(Shortest Vector Problem, SVP)及其变体的困难性。SVP表示在给定格中寻找最短的非零向量。如果将给定的格限制为理想格，则可以得到IdealSVP^[16]。

定义1 SVP问题^[16]

(1) $\gamma -$近似最短向量问题(${{\mathrm{SVP}}_\gamma }$)：确定一个近似最短的向量。给定$\gamma > 1$，在格上找到一个非零向量${\boldsymbol{v}} \in \mathcal{L}$使得$\left| {\boldsymbol{v}} \right| \le \gamma \cdot {\lambda _1}\left( \mathcal{L} \right)$。

(2) 判定最短向量问题(${{\mathrm{GapSVP}}_{\gamma ,r}}$)：判定最短向量的边界是否正确。给定$\gamma > 1,r > 0$，判断是否满足${{\lambda}_1}\left( \mathcal{L} \right) \le r$或${\lambda _1}\left( \mathcal{L} \right) \ge \gamma \cdot r$。

注意，如果最短向量问题是可解的，那么判定最短向量问题也是可解的，即${{{\mathrm{GapSVP}}}_{\gamma ,r}} \le {{\mathrm{SVP}}}$。

最近向量问题(Closest Vector Problem, CVP)是最短向量问题的一个推广。给定非零向量${\boldsymbol{t}} \in {R^n}$，在格$\mathcal{L}$中寻找一个最接近${\boldsymbol{t}}$的向量${\boldsymbol{v}}$，即${{\mathrm{dist}}}\left( {{\boldsymbol{t}},{\boldsymbol{v}}} \right) = {{\mathrm{dist}}}\left( {{\boldsymbol{t}},\mathcal{L}} \right)$。

定义2 CVP问题^[17]

(1) ${\gamma} -$近似最短向量问题(${{\mathrm{CVP}}_{\gamma}}$)：在格中找到一个与目标向量最接近的向量。给定$\gamma \ge 1, {\boldsymbol{t}} \in {R^n}$，找到向量${\boldsymbol{v}} \in \mathcal{L}$使得${{\mathrm{dist}}}\left( {{\boldsymbol{t}},{\boldsymbol{v}}} \right) \le \gamma \cdot {{\mathrm{dist}}}\left( {{\boldsymbol{t}},\mathcal{L}} \right)$。

(2) 判定最近向量问题(${{{\mathrm{DCVP}}}_{\gamma ,r}}$)：给定$\gamma \ge 1,r > 0,{\boldsymbol{t }}\in {R^n}$，判断是否满足${{\mathrm{dist}}}\left( {{\boldsymbol{t}},\mathcal{L}} \right) \le r$或${{\mathrm{dist}}}\left( {{\boldsymbol{t}},\mathcal{L}} \right) \ge \gamma \cdot r$。

错误学习问题(LWE)是由Regev^[18]在2005年引入的，作为Blum等人^[19]的“奇偶校验学习”问题的扩展，在密码学的发展中起到了关键作用。

定义3 LWE问题^[18]

给定一个向量${\boldsymbol{b}} \in \mathbb{Z}_q^m$和矩阵${\boldsymbol{A}} \in \mathbb{Z}_q^{m \times n}$，LWE问题即为找到一个向量${\boldsymbol{s}} \in \mathbb{Z}_q^n$，使得${\boldsymbol{A}} \cdot {\boldsymbol{s}} + {\boldsymbol{e}} = {\boldsymbol{b}}$，其中${\boldsymbol{e}} \in \mathbb{Z}_q^m$为误差分布${{\chi }}$的抽样。

2005年，Regev^[18]通过量子归约将格中最坏情况下的判定最短向量GapSVP归约为LWE问题，即如果能找到一个算法在多项式时间内解决LWE问题，那么也能在多项式时间内解决GapSVP问题。因此，基于LWE的同态加密方案的安全性与SVP及其变体的格上困难问题密切相关。

定义4 RLWE问题^[20]

给定多个抽样$\left( {a,b = a \cdot s + e} \right) \in {R_q} \times {R_q}$，寻找$s \in {R_q}$，其中$a$为${R_q}$中均匀随机的抽样，$e \in {R_q}$为误差分布${{\chi }}$的抽样。

环上错误学习(Ring Learning with Errors problem, RLWE)问题是LWE问题的环版本。从实际应用角度来看，基于RLWE问题的同态加密方案比基于LWE的方案计算效率更高，密文大小更紧凑。

2.2   全同态加密算法模型及安全性质

全同态加密方案可以解释为这样一种加密方案:给定一些密文，对明文的加法乘法操作都可以通过直接在密文上进行且无需要解密。记全同态加密方案为$\varepsilon$，共有4个算法：密钥生成算法${\mathrm{KeyGen}}$、加密算法${\mathrm{Enc}}$、解密算法${\mathrm{Dec}}$、同态运算算法${\mathrm{Eval}}$，其主要工作流程为：

(1)给定安全参数${\lambda}$，运行密钥生成算法${\mathrm{KeyGen}}\left( {{1^{\lambda}}} \right)$，生成公钥${{\mathrm{pk}}}$，私钥${{\mathrm{sk}}}$，同态计算公钥${{\mathrm{evk}}}$。

(2)给定明文${m_1},{m_2}, \cdots ,{m_k}$和公钥${{\mathrm{pk}}}$，对$i \in \left[ {1,k} \right]$，运行加密算法${\mathrm{Enc}}\left( {{{\mathrm{pk}}},{m_i}} \right)$，生成密文${{\mathrm{c}}}{{{\mathrm{t}}}_i}$。

(3)给定函数$f$和一些密文${{\mathrm{c}}}{{\mathrm{{t}}}_1},{{\mathrm{c}}}{{{\mathrm{t}}}_2}, \cdots ,{{\mathrm{c}}}{{{\mathrm{t}}}_k}$，同态计算公钥${\text{evk}}$，运行同态运算算法${\mathrm{Eval}}\left( f,{{\mathrm{evk}}}, {{\mathrm{c}}}{{{\mathrm{t}}}_1},{c}{{t}_2}, \cdots ,{{\mathrm{c}}}{{{\mathrm{t}}}_k} \right)$，获得密文${{\mathrm{c}}}{{{\mathrm{t}}}_1},{{\mathrm{c}}}{{{\mathrm{t}}}_2}, \cdots ,{{\mathrm{c}}}{{{\mathrm{t}}}_k}$在经过函数$f$同态运算的密文结果${{\mathrm{c}}}{{{\mathrm{t}}}_f}$。

(4)用私钥${{\mathrm{sk}}}$对密文${{\mathrm{c}}}{{{\mathrm{t}}}_f}$运行解密算法${\mathrm{Dec}}\left( {{{\mathrm{sk}}},{{\mathrm{c}}}{{{\mathrm{t}}}_f}} \right)$，获得相应的明文${m_f} = f\left( {m_1},{m_2}, \cdots , {m_k} \right)$。

其中第(3)步的同态运算算法就是同态加密方案的核心，对${{\mathrm{Eval}}}$输入密文可以实现任意函数的计算，更进一步还可以计算解密函数，这也是构造全同态加密方案的重要途径。

一个安全且合理的全同态加密方案具有4个安全性质：正确性，语义安全性，同态性，紧凑性。

(1) 正确性：对于任意的消息$m \in \left\{ {0,1} \right\}$，经同态加密方案加密的消息都能正确解密，即$m = {{\mathrm{Dec}}}\left( {{{\mathrm{sk}}},{{\mathrm{Enc}}}\left( {{{\mathrm{pk}}},m} \right)} \right)$。

(2) 语义安全性：一个任意多项式时间敌手${\mathrm{A}}$成功区分两个加密不同消息的密文，它的优势是可忽略的，也可以称这个加密方案是不可区分选择明文安全的(IND-CPA安全)

(3) 同态性：给定一个电路$f$，任意一组消息${m_1},{m_2}, \cdots ,{m_k}$，有

在同态加密密文上所做运算解密后得到的明文，与直接对明文做对应运算得到的结果相同。

(4) 紧凑性：对于任意电路$f$，任意一组密文${{\mathrm{c}}}{{{\mathrm{t}}}_1},{{\mathrm{c}}}{{{\mathrm{t}}}_2}, \cdots ,{{\mathrm{c}}}{{{\mathrm{t}}}_k}$，经过同态运算后得到的密文长度与电路$f$无关，即

其中正确性和语义安全性跟公钥加密方案中的定义相同，这是一个健全的加密体系的必要条件；同态性和简短性则是同态加密方案特有的安全性定义，同态性是同态加密方案独特属性，紧凑性是同态算法有意义的前提^[21]，如果没有紧凑性的限制，假设将原始密文输入运算函数$f\left( {{{\mathrm{c}}}{{{\mathrm{t}}}_1},{{\mathrm{c}}}{{{\mathrm{t}}}_2}, \cdots ,{{\mathrm{c}}}{{{\mathrm{t}}}_k}} \right)$直接作为新密文输出，解密时就需要先对原始密文${{\mathrm{c}}}{{{\mathrm{t}}}_1},{{\mathrm{c}}}{{\mathrm{{t}}}_2}, \cdots ,{{\mathrm{c}}}{{{\mathrm{t}}}_k}$解密再将解密后的内容${m_1},{m_2}, \cdots ,{m_k}$放入函数$f$中运算才能得到经过同态运算后的消息$f\left( {{m_1},{m_2}, \cdots ,{m_k}} \right)$，导致的后果是密文会随着同态运算次数的增加越来越大，这样不仅毫无意义，而且对于一些需要非公开计算的函数$f$，最后输出与$f$强相关的密文结果也会泄露$f$的信息。

自举是由类同态构造全同态加密方案的核心步骤，运算过程中涉及公开加密密钥的密文，为了保证密钥安全性，密钥需要满足循环安全(Circular Security)，这也是Gentry在方案中提出的一个额外假设，下面给出在公钥密码体制(PKE)下的定义：

定义5 循环安全假设^[22]

令$n = n(\lambda )$为多项式，${\mathrm{PKE}} = ({\mathrm{KeyGen}}, {\mathrm{Enc}}, {\mathrm{Dec}})$为1个比特公钥加密方案，其私钥长度为${l_{{\text{sk}}}}$。对任意多项式时间的敌手$A$，若此公钥加密方案是n-key 循环安全的，则有

其中${{\mathrm{negl}}}(\lambda )$是可忽略函数，因此敌手获胜的概率是可忽略的。

该定义说明循环安全假设保证了敌手无法区分随机消息的密文与加密私钥的密文，满足了公钥加密方案中语义安全的经典安全性要求。

3.   技术路线

根据全同态方案核心技术，可以按照技术路线划分为如下几类：第1类的代表是Gentry^[11]在2009年提出的全同态加密方案，它找到了理想格这个既支持同态加法又支持同态乘法的工具，还开创性地提出了自举的思想，使得全同态加密方案可以通过类同态加密方案构造。第2类是Brakerski和Vaikuntanathan^[23]在2011年提出的类同态加密方案，它率先提出了密钥切换操作控制密文乘法的维数扩展、模切换操作控制噪声增长速度的想法。在此基础上，后续的同态方案对BV11的效率和噪声控制进行了优化，并设计了适配的自举算法。第3类是Gentry, Sahai和Waters^[24]提出的基于矩阵的近似特征向量技术的同态加密方案，它的技术特点是使用了矩阵的密文形式，矩阵密文做乘法避免了向量密文的维数扩张问题，同时将乘法噪声的增长速度由指数级降低到线性级。第4类是Cheon团队^[25]在2017年提出近似同态加密方案，它适用于一些不需要精确计算的场景，在自举操作中用多项式函数近似计算替代了精确的比特提取。本节将对每类代表性全同态加密方案的理论基础，加密方案的结构通式，核心的技术特点，算法的发展过程，目前方案存在的局限性以及实现效果等方面进行叙述分析。图1展示了4类全同态方案诞生的时间顺序，括号内列举了其分支下的重要论文，箭头表示两类方案存在一定的相关性但发表时间有先后：BGV方案继承了Gentry类方案的主要思想，但方案构造的基础假设不同，控制噪声的技术也不同。GSW方案与BGV的基础假设相同，但改变了密文结构；CKKS方案的密文结构、同态操作与BGV基本相同，但消息空间不同、适用运算场景不同。

图 1  全同态加密的不同技术路线分支及其代表性方案

下载: 全尺寸图片 幻灯片

3.1   理想格和自举理论

以2009年Gentry的工作为代表的同态加密方案，这类方案构造的安全性是基于理想格上的困难问题^[50]。格上的两个著名困难问题是最近向量问题 (CVP)^[16]和最短向量问题 (SVP)^[17]，分别是在格上找一个已知格点的最近向量和最短向量 ，后续又在此基础上引申出了格约简问题^[51]，为给定的格找一组尽可能接近正交的、既正交又短的“好”格基。若已知一组“好”格基，则求解CVP和SVP问题只需要多项式时间，反之则需要指数级的时间。在Gentry的方案中，密钥就相当于一组“好”格基，求解密文可以归约到求解CVP和SVP问题。

3.1.1   具体方案

因为理想本身支持加法和乘法，所以是用于构建全同态加密方案的自然数学对象。Gentry在方案中定义的理想具有两个性质：首先在理想中假设一个随机元素来加密消息，保证加密的安全性；其次生成一个消除理想的秘密陷门。依据这两个属性可以实现密文的同态加法和同态乘法。方案的主要思想是先构造一个支持有限次加法和乘法同态计算的类同态加密方案，然后借助稀疏子集和问题(sparse subset sum problem,SSSP)压缩解密电路^[26]，降低电路深度，使得这个解密电路可以被同态计算，接着又基于循环安全假设(Circular Security)进行同态解密操作，最终实现全同态加密。这里给出以Gentry09为代表的全同态加密方案的一般结构：

密钥生成：对于给定的环$R$和理想$I$的基${B_I}$，${{\mathrm{IdealGen}}}\left( {R,{B_I}} \right) = \left( {B_J^{{{\mathrm{sk}}}},B_J^{{{\mathrm{pk}}}}} \right)$，满足$I + J = R$，其中$B_J^{{{\mathrm{sk}}}},B_J^{{{\mathrm{pk}}}}$为理想$J$的基${B_J}$组成的私钥和公钥。

加密。选择随机向量${\boldsymbol{r}},{\boldsymbol{g}}$，消息$m \in \left\{ {0,1} \right\}$，生成密文${{\mathrm{ct}}} = {{\mathrm{Enc}}}\left( m \right) = m + {\boldsymbol{r}} \cdot {B_I} + {\boldsymbol{g}} \cdot B_J^{{{\mathrm{pk}}}}$

解密。${{\mathrm{Dec}}}({{\mathrm{ct}}},B_J^{{{\mathrm{sk}}}}) = ({\mathrm{ct}} - B_J^{{{\mathrm{sk}}}} \cdot {(B_J^{\rm{sk}})^{ - 1}} \cdot {{\mathrm{ct}}})\; \text{mod} \,{B_I}$

密文加法。${{\mathrm{c}}}{{{\mathrm{t}}}_1} + {c}{{t}_2} = {{\mathrm{Enc}}}\left( {{m_1}} \right) + {{\mathrm{Enc}}}\left( {{m_2}} \right) = {m_1} + {m_2} + \left( {{{\boldsymbol{r}}_1} + {{\boldsymbol{r}}_2}} \right){B_I} + \left( {{{\boldsymbol{g}}_1} + {{\boldsymbol{g}}_2}} \right) \cdot B_J^{{{\mathrm{pk}}}}$

密文乘法。

此类同态方案正确解密的要求是噪声量$\text{ct}; \text{mod}\; {B}_{J}^{\text{pk}}$要小于$B_J^{\rm{pk}}/2$，因此乘法操作后剧烈增长的噪声会导致密文解密失败，限制了同态操作的继续进行。

3.1.2   自举算法

Gentry在著作中提出了的一个关键技术——自举，这个术语表示刷新一个密文的操作过程：自举电路由同态方案的解密电路组成，旧密文输入这个自举电路产生一个新的密文，该密文加密相同的消息，但具有较低的噪声水平，可以对其进行更多的同态操作。自举是迄今为止大部分全同态加密方案的核心，更通俗的讲，自举过程就是把一个噪音马上达到临界点的同态密文二次加密，并且用加密的私钥同态计算解密算法，把里层的密文解密成明文，只留外层的加密，这样就获得了一个全新的低噪音同态密文且加密的内容不变。为了实现自举，Gentry设计了一种压缩类同态方案解密函数的方法。这种方法将原来的类同态方案${{\varepsilon }}$转换成另一个具有相同的同态容量和更简单的允许自举的解密函数全同态加密方案${{{\varepsilon }}^*}$。同时Gentry^[26]证明了在同态计算公钥中添加一些关于私钥的“额外信息”就足够了，降低了解密算法的复杂性。因为自举过程中用到了私钥的加密，所以需要针对私钥设置一个额外的安全假设，称为循环安全假设。这个假设意味着公开发布用公钥加密的私钥密文不会影响私钥的安全性，即它保证了敌手无法观察到该方案在公钥下加密的私钥信息。目前的全同态加密方案结构都需要在自举中用到私钥的加密，因此所有已知的全同态结构都要求循环安全性，但是目前循环安全性并没有严谨的数学证明，因此它通常被作为方案基础安全假设之上的附加假设。

接下来将给出自举的具体算法流程。考虑一个类同态加密方案${{\varepsilon }}$，两个公私钥对$\left( {{{\mathrm{p}}}{{{\mathrm{k}}}_1},{{\mathrm{s}}}{{{\mathrm{k}}}_1}} \right)$，$\left( {{{\mathrm{p}}}{{{\mathrm{k}}}_2},{\mathrm{{s}}}{{{\mathrm{k}}}_2}} \right)$，加密算法${{\mathrm{Enc}}}$，公钥${{\mathrm{p}}}{{{\mathrm{k}}}_1}$加密消息$m$得到的密文${{\mathrm{ct}}} = {{\mathrm{Enc}}}\left( {{{\mathrm{p}}}{{{\mathrm{k}}}_1},m} \right)$。对密文${\mathrm{ct}}$的自举分为以下3步：

(1)用公钥${\rm p}{{\rm k}_2}$加密私钥${\rm s}{{\rm k}_1}$，生成自举密钥$\boxed{{\text{s}}{{\text{k}}_1}}$：${{\mathrm{Enc}}}\left( {{\rm p}{{\rm k}_2},{\rm s}{{\rm k}_1}} \right) \to \boxed{{\rm s}{{\rm k}_1}}$

(2)用公钥${\rm p}{{\rm k}_2}$加密密文${{\mathrm{ct}}}$(非必需步骤 ¹)：${{\mathrm{Enc}}}\left( {{\rm p}{{\rm k}_2},{{\mathrm{ct}}}} \right) \to \boxed{{{\mathrm{ct}}}}$

(3)使用自举密钥同态解密新密文：${{\mathrm{Dec}}}\left( {\boxed{{\rm s}{{\rm k}_1}},\boxed{\rm{ct}}} \right)$。

通过这种方式，就可以在公钥${\mathrm{p}}{{\mathrm{k}}_2}$下获得同一消息$m$的加密${{\mathrm{c}}}{{{\mathrm{t}}}_{{\mathrm{new}}}} = {{\mathrm{Enc}}}\left( {{\rm p}{{\rm k}_2},m} \right)$。$\boxed \cdot$表示对方框里内容的加密。

自举是为了降低密文同态操作中引入的噪声。从概念上讲，自举调用解密函数并同时执行重加密，这些操作生成了“新”密文，这个“新”密文的噪声包含了重加密的噪声加上解密电路同态计算导致的噪声。因此，自举得到的“新”密文噪声大于用加密算法得到的初始密文噪声，但小于用比解密电路深度更高的同态求值函数得到的密文噪声。将自举应用于在多次同态运算后的密文，这使得构造任意大深度函数的同态电路成为可能，前提是解密电路必须可同态运算。2011年，Gentry 和Halevi^[28]尝试用类同态加密和乘法同态加密的混合体构造全同态加密方案，用Decision Diffie-Hellman替换SSSP假设，这个方案仍然依赖于自举。Gentry等人^[29]的研究结果证明，构造一个全同态方案的问题足以转移到构造一个只能对特定的小次函数集求值的方案，即类同态方案，且当该方案满足循环安全假设。满足上述情况的类同态加密方案，则可以应用自举(必要时还可以压缩)来获得全同态方案，因此，自举是由类同态加密方案构造全同态加密方案的唯一途径。不幸的是，自举在计算上很复杂，同时还需要很大的内存空间。

3.1.3   研究现状

Gentry的工作做出了许多理论贡献，但方案中包含的一些数学概念过于复杂难以实现，而且运算成本过高，单个比特的自举就需要30 min^[27]。虽然此时全同态方案巨大的开销制约了其实用性，但是自举思想的提出为后续全同态加密方案的诞生提供了实现途径。后来的全同态加密方案设计都据此思想：先构造一个高效的类同态加密方案，再根据方案设计相应的高效自举算法，最后令类同态加密方案调用自举算法实现全同态加密。此时Gentry方案的性能表明全同态加密距离投入实际应用还有一段路程，简化方案结构、降低成本、提升效率都是当时全同态加密方案设计需要解决的问题。

3.2   密钥切换和模切换

以BFV/BGV为代表的这类全同态加密方案是基于LWE问题和RLWE问题构造的。LWE问题在2005年由Regev提出，且解决LWE问题不比解决格上的CVP和SVP简单^[52]；RLWE问题则是LWE问题的代数变体，其安全性可以归约到理想格上最坏情况问题，在2011年被Brakerski和Vaikuntanathan^[20]提出。同一时期人们发现，基于RLWE构造全同态加密方案^[53]似乎比基于LWE更有优势。在BGV方案中，LWE型密文的明文空间为${\mathbb{Z}_t}$，RLWE型密文的明文空间为${R_t} = {\mathbb{Z}_t}\left[ X \right]/{X^n} + 1$，但一个LWE密文仅能存储一个明文，而一个RLWE密文最多能存储$n$个明文，空间利用率大幅度提高。进一步，引入了单指令多数据(Single Instruction Multiple Data, SIMD)操作^[54]之后， RLWE密文的$n$位对应明文全都有效使用，因此后续BGV类的全同态加密方案大多基于RLWE问题设计。

3.2.1   具体方案

接下来以BGV为例，给出这类全同态加密方案的一般结构：

密钥生成：给定安全参数${\lambda}$，${{\mathrm{KeyGen}}}\left( {{1^{\lambda}}} \right) \to {{\mathrm{pk}}},{{\mathrm{sk}}}$，生成公钥${{\bf{pk}}}$，私钥${{\bf{sk}}} = \left( {1,s} \right)$

加密：${{\mathrm{Enc}}}(m,{{\bf{pk}}}) = {{\bf{ct}}} = ({c_0},{c_1}) \in R_q^2$

解密：${{\mathrm{Dec}}}({{\bf{ct}},{\bf{sk}}}) = (({c_0} + {c_1} \cdot s\; \text{mod} \,q) \; \text{mod} \,t) =m \in {R_t}$

密文加法：${\bf c}{{\bf t}_1} + {\bf c}{{\bf t}_2} = \left( {{c_{10}},{c_{11}}} \right) + \left( {{c_{20}},{c_{21}}} \right) = \left( {{c_{10}} + {c_{20}},{c_{11}} + {c_{21}}} \right) = {{\bf{c}}}{\bf{t}_{{\text{add}}}}$

密文乘法：${{\bf{c}}}{{{\bf{t}}}_1} \cdot {{\bf{c}}}{{{\bf{t}}}_2} = \left( {{c_{10}},{c_{11}}} \right) \cdot \left( {{c_{20}},{c_{21}}} \right) = \left( {{c_{10}}{c_{20}},{c_{10}}{c_{21}} + {c_{11}}{c_{20}},{c_{11}}{c_{21}}} \right) = \left( {{c_0},{c_1},{c_2}} \right) = \overline {\bf{ct}}$，

2011年，Brakerski和Vaikuntanathan^[23]基于LWE问题设计了一个不使用自举技术就能增加计算轮次的类同态加密方案(BV)，它用重线性化技术来控制密文的维数膨胀，用模切换技术来控制噪声增长，将密文的尺寸缩小到了$O\left( {{\lambda}\log_2{\lambda}} \right)$。但由于LWE问题本身的数学结构限制，导致BV方案的空间利用率并不高，所以在BV方案的基础上，2012年就出现了基于RLWE的优化BV同态加密方案^[37,30]，分别从不同角度改进拓展了BV的核心技术，使得BV类同态加密方案的性能得到进一步提升。

2012年，Fan和Vercauteren^[37]将基于LWE问题的Brakerski全同态方案移植到RLWE中构造了BFV方案，提出了两个优化版本的重线性化算法，用来解决乘法后密文维数增加的问题。与BV方案相比，BFV的算法缩小了重线性化密钥，计算速度得到提升。第1种重线性化方法是选一组合适的基$T$，将重线性密钥${\mathrm{rlk}}$在这组基上进行分解，减小重线性化过程中由于密文乘法引入的噪声。

另一种重线性化方法则借助模切换的思想，先将密文切换到大模数，做完重线性化之后再切换回小模数，利用模约简缩小重线性化乘法中引入的密文噪声。

BGV方案是Brakerski等人^[30]在2012年提出的一种基于RLWE无自举的全同态方案，主要贡献是优化了密钥切换技术(keyswitch)和控制密文噪声增长速度的模切换技术(modswitch)。

密文同态乘法的实质是向量张量积，会造成密文维度的增加，此时就需要密钥切换技术来降低维数，确保密文能正确解密。同时乘法后的密文噪声也会增加，用模切换技术将密文切换到小模数可以同步的缩小密文和噪声，减小乘法噪声的增长速度，使密文支持更多次的同态乘法。

此时BGV方案1次只能对单个密文进行运算，运算效率低下，为了降低BGV方案的开销、提升计算效率，人们开始思考如何同时处理多个密文。在2014年，Smart和Vercauteren^[54]在BGV方案中引入了SIMD操作，通过在多项式环上使用中国剩余定理，令密文呈现多槽 (slots)结构 ，允许把明文数组插进槽中，这样对两个密文进行同态操作的时候，即对数组向量按分量进行同态操作，提高了空间利用率和计算效率，降低了密文转换率，使得基于RLWE的同态加密方案相较于LWE方案呈现了巨大的优势。2012年，Gentry团队^[38,39]针对SIMD算法的特点优化了计算电路，将输入消息打包到$l$个数组中，每层使用SIMD操作，再将输出作为到下一层的输入，对于浅层算数电路可以实现${{\mathrm{polylog}}}$的低开销：对于安全参数${\lambda}$，任意$t$个门，深度$L$，平均宽度$\varOmega \left( \lambda \right)$的电路，可以在时间$t \cdot {{\mathrm{polylog}}}_2\left( {\lambda} \right)$内同态计算。虽然BGV方案中模数会随着同态计算逐渐变小，但上述算法对深度的依赖可以通过使用自举操作来规避：一旦模数小到无法进行进一步的计算，则自举刷新密文，用模数较大的新密文来支持后续计算。

基于(R)LWE问题构造的这些全同态方案，在算法上有一些相似性，但同时也有它们各自的特点。当BGV, BFV的明文空间都是${R_t}$，明文模$t$，密文模$q$时，BGV会将消息放在低位加密：${{\mathrm{Dec}}}\left( {{\bf c}{{\bf t}_{{\text{BGV}}}}} \right) = m + t \cdot {\boldsymbol{e}}$，而BFV会把消息放在高位加密：${{\mathrm{Dec}}}\left( {{\rm c}{{\rm t}_{{\text{BFV}}}}} \right) = \dfrac{q}{{t \cdot m}} + {\boldsymbol{e}}$，因此在t较大时BGV噪声的增长速度会比BFV小。总而言之，对于较大的明文模数，BGV方案的噪声增加速度较小，计算效率较高，而较小明文模数的情况下，BFV的运算效率较高，表现更好。

3.2.2   自举算法

BFV/BGV类同态加密方案从类同态转变为全同态的方法使用了Gentry的思想，即在密文噪声达到最大噪声界前，用自举步骤刷新密文降低噪声，这样得到的新密文噪声只与同态解密电路相关，与初始噪声无关。自举的具体流程为：模切换→线性变换→比特提取→逆线性变换。模切换步骤的目的是将密文提升到大模数下，需要使用线性变换操作将多项式系数放到明文槽中，比特提取系数的主比特同时去噪，最后进行线性变换的逆过程将明文槽中的系数放回原位，其中复杂度最高的部分是比特提取。2016年，IBM基于BGV开发了一个开源的全同态运算库HElib^[40-42]，Halevi和Shoup详细描述了如何在Helib中实现BGV的自举算法。对消息进行稀疏打包的情况下，平均每比特自举仅需1.3 ms，具有实际应用价值。

3.2.3   研究现状

跟据BFV和BGV的这些特点，Andrey Kim团队^[43]在2021年对这两个经典全同态加密方案做出了进一步优化，如表1。有趣的是，这两个经典方案的改进方法几乎都源于对方的技术特点。经过上述优化之后，明文模较小时(如取t=2)改进BFV的速度占优，但随着明文模的增大，改进BGV的速度更快：对于所有明文模量，改进BFV方案运算速度均有提升，当明文模取t=2电路深度为20时仅需50 s运算时间，相比原始方案的150 s快了3倍，这归功于在BFV加密过程中将部分内容进行了预计算；当进行7层乘法深度的二叉树计算时，改进BGV仅需1.27 s，快于改进BFV的1.54 s，这两个结果都优于原始BFV的2.48 s。

表 1  Andrey Kim团队对BFV和BGV方案的算法优化

BFV	BGV	优化效果
$\left\lfloor {\dfrac{q}{t}} \right\rfloor m \to \left\lfloor {\dfrac{{qm}}{t}} \right\rfloor$预计算$qm$	\	降低初始噪声
将乘法中的模切换步骤置于重线性化之后	\	降低模切换维数
将BFV的模数分层，乘法之后切换到小模数	\	减缓噪声增长速度
\	静态噪声管理	增强方案的实用性

下载: 导出CSV 

| 显示表格

3.3   密文矩阵和非对称噪声

2013年Gentry等^[24]提出了基于矩阵特征值和特征向量构造的GSW方案，标志着全同态方案引入了新的密文结构——矩阵，因为矩阵的特征值与特征向量具有线性关系${\boldsymbol{Ax}} = \lambda {\boldsymbol{x}}$，在原始体系中引入随机噪音${\boldsymbol{e}}$，就可以得到一个LWE型的加密方案${\boldsymbol{C}} \cdot {\boldsymbol{s}} = \mu {\boldsymbol{s}} + {\boldsymbol{e}}$，其中$C$为密文，${\boldsymbol{s}}$为密钥，$\mu$为加密的消息，${\boldsymbol{e}}$为随机噪声。GSW方案的安全性可以归约到与BFV/BGV方案相同的LWE问题和RLWE问题，不同的是，以BGV, BFV为代表加密方案的密文和密钥都是以向量形式表示，需要额外的密钥切换技术来控制乘法运算后密文的维数扩展，而以GSW为代表加密方案的矩阵密文做乘法不会改变密文维数，避免了密钥交换技术需要用到的大量密钥交换的矩阵而导致公钥长度的增长。

3.3.1   具体方案

GSW方案继承了BGV方案的设计思路，并在此基础上加入了自己的核心技术——近似特征向量技术，构造了一个无需同态计算公钥就可以进行同态运算的“层次型”同态加密方案。GSW类方案的特点是同态密文运算为简单的矩阵运算，相比于向量结构的密文，矩阵结构虽然不支持消息打包，但避免了维数膨胀问题和密钥切换运算。GSW类同态加密方案的一般结构如下：

密钥生成。随机抽取一个向量$\bar {\boldsymbol{s}} \in \mathbb{Z}_q^{n - 1}$，生成私钥${\boldsymbol{s}} \to {\left( {\bar {\boldsymbol{s}}, - 1} \right)^{\text{T}}} \in \mathbb{Z}_q^n$

加密。给定消息$u$和n阶单位矩阵${{\boldsymbol{I}}_n}$，随机选取矩阵${\boldsymbol{A}} \in \mathbb{Z}_q^{n \times \left( {n - 1} \right)}$，噪声向量${\boldsymbol{e}} \to {{\chi }}_{\boldsymbol{e}}^n$，生成密文矩阵${\boldsymbol{C}} = \left( {{\boldsymbol{A}},{\boldsymbol{A}} \cdot \bar {\boldsymbol{s }}+ {\boldsymbol{e}}} \right) + u \cdot {{\boldsymbol{I}}_n} \in \mathbb{Z}_q^{n \times n}$

解密。${{\mathrm{Dec}}}\left( {{\boldsymbol{C}},{\boldsymbol{s}}} \right) = {\boldsymbol{C }}\cdot {\boldsymbol{s}} = u \cdot {\boldsymbol{s}} - {\boldsymbol{e}}$，这里噪音向量${\boldsymbol{e}}$表示引入的LWE噪声，后文统一取正号

密文加法。矩阵加法${{\boldsymbol{C}}_1} + {{\boldsymbol{C}}_2}$，${{\mathrm{Dec}}}\left( {{\boldsymbol{C}}_1} + {{\boldsymbol{C}}_2} \right) = \left( {{u_1} + {u_2}} \right) \cdot {\boldsymbol{s}} + \left( {{{\boldsymbol{e}}_1} + {{\boldsymbol{e}}_2}} \right)$

密文乘法。矩阵乘法${{\boldsymbol{C}}_1} \cdot {{\boldsymbol{C}}_2}$，${{\mathrm{Dec}}}\left( {{\boldsymbol{C}}_1} \cdot {{\boldsymbol{C}}_2} \right) = \left( {{u_1} \cdot {u_2}} \right) \cdot {\boldsymbol{s}} + {u_2} \cdot {{\boldsymbol{e}}_1} + {{\boldsymbol{C}}_1} \cdot {{\boldsymbol{e}}_2}$

可以观察到密文乘法中噪声并不是对称增长的，即${{\boldsymbol{C}}_1} \cdot {{\boldsymbol{C}}_2}$与${{\boldsymbol{C}}_2} \cdot {{\boldsymbol{C}}_1}$引起的噪声增长不同。因为密文矩阵${\boldsymbol{C}}$远大于消息$u$，所以${\boldsymbol{C}} \cdot {\boldsymbol{e}}$在乘法噪声中占主导地位。因为GSW密文正确解密的噪声上界为$q/4$，所以为了控制乘法中产生的噪声项${\boldsymbol{C}} \cdot {\boldsymbol{e}}$，就需要限制密文${\boldsymbol{C}}$的大小，GSW方案中使用二进制分解的思想定义了函数

为向量${\boldsymbol{a}} = \left( {{a_1},{a_2}, \cdots ,{a_n}} \right)$从最低位到最高位每项系数的比特分解

为${{\mathrm{BitDecomp}}}\left( \cdot \right)$的逆函数

生成一个系数为$\left\{ {0,1} \right\}$的向量

对于任意${\boldsymbol{a}},{\boldsymbol{s}} \in \mathbb{Z}_q^n$，满足$\left\langle {{\boldsymbol{a}},{\boldsymbol{s}}} \right\rangle = \left\langle {{\mathrm{BitDecomp}}}\left( {\boldsymbol{a}} \right), {{\mathrm{Powersof}}}2\left( {\boldsymbol{s}} \right) \right\rangle$；

对于任意${\boldsymbol{b}} \in \mathbb{Z}_q^{nm},\;{\boldsymbol{s}} \in \mathbb{Z}_q^n$，满足

使用上述函数，对密文矩阵${\boldsymbol{C}}$进行二进制分解，即可实现降低乘法项的密文尺寸，控制噪声增长的目的。取$m = n \cdot {\text{lo}}{{\text{g}}_2}q$，根据上述函数定义一个$m \times n$维的二进制重组矩阵

在加密的时候，生成密文${\boldsymbol{C}} = \left( {{\boldsymbol{A}},{\boldsymbol{A}} \cdot \bar {\boldsymbol{s}} + {\boldsymbol{e}}} \right) + u \cdot {\boldsymbol{G}}$，然后不直接输出${\boldsymbol{C}}$，而是输出密文分解后的二进制矩阵$\hat {\boldsymbol{C}} = {{\boldsymbol{G}}^{ - 1}}\left( {\boldsymbol{C}} \right)$。密文${{{\widehat {\boldsymbol{C}}}_1}}$与${{{\widehat {\boldsymbol{C}}}_2}}$进行乘法运算之后，${{\mathrm{Dec}}}\left( {{{{\widehat {\boldsymbol{C}}}_1}} \cdot {{{\widehat{\boldsymbol{C}}}_2}}} \right) = \left( {{{{u}}_1} \cdot {{{u}}_2}} \right) \cdot {\boldsymbol{G}} \cdot {\boldsymbol{s}} + {{{u}}_2} \cdot {{\boldsymbol{e}}_1} + {{{\widehat{\boldsymbol{C}}}_1}} \cdot {{\boldsymbol{e}}_2}$这里的$\widehat {{{\boldsymbol{C}}_1}}$为二进制矩阵，当噪声界取$\delta$时，$\widehat {{{\boldsymbol{C}}_1}} \cdot {{\boldsymbol{e}}_2}$的上界为$n \cdot {\text{lo}}{{\text{g}}_2}q \cdot \delta$，远小于${{\boldsymbol{C}}_1} \cdot {{\boldsymbol{e}}_2}$的上界$m \cdot q \cdot \delta$。

除此以外，观察到${\boldsymbol{G}}$的第1行${{\boldsymbol{G}}_1} = \left( {1,0, \cdots ,0} \right)$只有第1项是1其余为0，在解密阶段${{\mathrm{Dec}}}\left( {\hat {\boldsymbol{C}},{\boldsymbol{s}}} \right) = \hat {\boldsymbol{C}} \cdot {\boldsymbol{G}} \cdot s = u{\boldsymbol{G}} \cdot {\boldsymbol{s}} + {\boldsymbol{e}}$，则$u{\bf{G}} \cdot {\bf{s}}$的第1行有${\left( {u \cdot {\boldsymbol{G}} \cdot {\boldsymbol{s}}} \right)_1} = u{{\boldsymbol{G}}_1} \cdot s = u{\boldsymbol{s}}\left[ 1 \right]$，因为${\boldsymbol{s}}\left[ 1 \right] \in {\mathbb{Z}_q}$大概率是个远大于噪声上限的数字，所以只需计算观察结果向量的第一项，就可以得到消息$u$。

3.3.2   自举算法

目前GSW类方案主要为单比特的加密，因此自举过程不涉及密文的打包与解包，仅需同态计算解密函数，主要涉及两个步骤，第一步是用于同态解密的累加：包括内积操作和模约简，第二步是比特提取：进行同态舍入操作，最后得到自举后的新密文。

对GSW类加密方案来说，调整方案构造，使用比较短的参数就可以满足安全性，这样便于引入一些非常高效的自举技术，因此后续的一系列研究都专注于提升方案的自举性能。Jacob Alperin-Sheriff和 Chris Peikert^[44]在2014年利用对称群和置换矩阵的思想，设计了一个GSW方案的单比特快速自举算法，为了完全重新随机化误差，在构造格陷门时把使用的矩阵${{\boldsymbol{G}}^{ - 1}} = {{\mathrm{BitDecomp}}}\left( {{{\boldsymbol{I}}_N}} \right)$从一个确定性的比特分解，重新定义为一个随机抽样的矩阵。此外他们还依据中国剩余定理将大的加法群嵌入小的对称群，这样自举需要的同态操作次数就从$\tilde O\left( {{{\lambda}^3}} \right)$降到了$\tilde O\left( {\lambda} \right)$次。在2015年，Ducas和Micciancio^[45]将AP14方案的思想扩展到环上，用模4操作来同态计算两个密文的NAND与非门，构造了一个基于环GSW的同态累加器用于执行密文的自举过程，将自举速度提升到每次1 s，实验中自举1个比特单次只需要0.69 s。Ilaria Chillotti 团队^[46]在2016年对GSW密文与LWE密文、GSW密文与GSW密文的乘法做出了进一步的优化，设计了一种新的一般化乘积机制，并在此基础上改进了自举步骤，将单个门自举时间减少到0.1 s。

3.3.3   研究现状

GSW类的全同态加密方案以其优秀的自举速度被认为是目前最理想的全同态加密方案，但是GSW类不同于BGV/BFV类的向量密文结构，矩阵密文无法自然的令一个密文打包加密多条消息或者多个密文并行运算，所以主流使用的GSW类加密方案仍是单比特加密。2018年Steven Myers 和 Adam Shull^[47]提出了一种打包密文的自举算法，通过在FHEW的基础上使用递归的计算方法，将计算复杂度降低到$O\left( {{3^\rho }{\lambda ^{1{/^\rho }}}} \right),\rho = O\left( 1 \right)$。进一步，2023年Liu Feng-Hao和Wang Han^[48,49]在MS18方案打包算法的基础上，引入了适用FHEW的SIMD算法，将计算复杂度直接优化到$\tilde O\left( 1 \right)$。上述方案对提升GSW类加密方案的自举效率具有巨大理论价值，但是素数幂明文环的设置，盲旋转算法中test向量的构造等实例化参数选择，是该类方案目前的实现瓶颈，因此如何设计具有实用价值的密文打包方法和并行计算算法，进一步提升自举效率，是当前亟待解决的问题。

3.4   非精确解密场景的适应性方案

为了配合一些不需要精确解密的应用场景，Jung Hee Cheon团队^[25]在2017年提出了第1个近似同态加密方案——CKKS，该方案BGV为基础，引入正则嵌入的消息编码方式，具有支持浮点数运算的特性。

3.4.1   具体方案

CKKS主要思想是将加密噪声视为消息的一部分，跟BFV, BGV相比，CKKS的特点有两个：一是对引入的噪声跟明文加密时并未进行高低比特位上的分离，即$\left\langle {{\bf{ct}},{\bf{sk}}} \right\rangle = {\boldsymbol{m}} + {\boldsymbol{e}}$；二是解密后的明文是原始明文的近似值，即${{\mathrm{Dec}}}\left( {{{\mathrm{Enc}}}\left( {\boldsymbol{m}} \right)} \right) \approx {\boldsymbol{m}}$。这些特点让CKKS方案的使用更加灵活，可以适配多种多情况的应用场景。CKKS的密文加法与乘法与BGV类方案计算过程基本相同，故不再赘述。CKKS需要额外关注的是它的编码过程，因为其编码消息是浮点数，不同与其他全同态方案的整数消息，CKKS需要借助正则嵌入矩阵将浮点数消息编码成整数明文。对于一个待编码的消息$z = \left( {a_1} + {\mathrm{i}}{b_1}, {a_2} + {\mathrm{i}}{b_2}, \cdots ,{a_{n/2}} + {\mathrm{i}}{b_{n/2}} \right) \in {C^{n/2}}$，给定精度因子$\varDelta$，正则嵌入矩阵${\boldsymbol{\sigma}}$，函数$\pi$，$\zeta$为多项式环${\varPhi _M} = {X^n} + 1$的本源单位根，满足${\zeta ^n} = 1{\text{ }}\text{mod} M$，记编码后的明文${\boldsymbol{m}} \in R_t^n$，具体编解码公式为

编码：${\boldsymbol{m}} = {\text{Encode}}({\boldsymbol{z}},\varDelta ) = {{\boldsymbol{\sigma}} ^{ - 1}}\left\lceil {\varDelta {\pi ^{ - 1}}({\boldsymbol{z}})} \right\rceil$

解码：${\boldsymbol{z}} = {\text{Encode}}({\boldsymbol{m}},\varDelta ) = \pi \circ {\boldsymbol{\sigma}} ({\boldsymbol{m}}/\varDelta )$

其中函数$\pi$的作用是将复数向量取共轭再连接到原向量后面，即${\pi ^{ - 1}}({\boldsymbol{z}}) = ({a_1} + {\mathrm{i}}{b_1},{a_2} + {\mathrm{i}}{b_2}, \cdots , {a_{n/2}} + {\mathrm{i}}{b_{n/2}},{a_1} - {\mathrm{i}}{b_1}, \cdots ,{a_{n/2}} - {\mathrm{i}}{b_{n/2}})$。CKKS方案加密的复数域上消息向量，通过正则嵌入打包成整数环上的明文向量，后续就与其他全同态加密方案一样做整数多项式环上的同态运算。

3.4.2   自举算法

CKK方案的自举流程与BGV/BFV类方案基本相同，因为CKKS方案主要针对于无需精确解密场景的应用，所以自举过程中的比特提取步骤可以用近似模函数完成，无需进行同态的精确解密。同BGV/BFV类方案相同，CKKS也将消息存储在明文槽中，因为模切换是对密文系数进行操作，这种操作不会改变消息，所以它在自举过程中不能直接进行模切换，也需要先进行线性变换，将系数向量放入明文槽中，再通过一个从小模数换到大模数的模切换操作来完成全部自举过程，实现减小密文噪声扩大密文模数的目标。

CKKS的换模操作需要用多项式来近似模约简函数，这个近似过程中产生的近似误差是自举误差的主要来源，如表2。目前主流的思想是选择一个在原点附近与模约简函数形状相近的函数作为模约简函数与近似多项式之间的桥梁，例如sin函数^[31]。但是近似函数与模约简函数之间同样会产生近似误差，因此需要找到更接近模约简函数的近似函数。2021年，Joon-Woo Lee团队^[32]用复合函数的方法在原本sin函数近似的基础上添加了一个逆sin函数，去掉了sin函数与模约简函数之间的近似误差，但是需要额外计算一个逆sin函数的多项式近似。总体而言，此方法提高了自举精度，特别是在小明文模数的情况下具有优异表现，因为在小明文模情况下近似函数与模约简函数之间的近似误差占主导地位，此时自举精度可以达到40.5 bit，计算时间仅需94.7 s。随后的2021年，Jutla和Manohar^[33]使用了一个新的近似函数——正弦级数近似，可以实现几乎任意精度的CKKS自举，使用$n$阶正弦级数近似时误差约为$O\left(\varepsilon^{2n+1}\right)$，优于正弦函数近似误差$O\left(\varepsilon^{3}\right)$，自举精度也达到了44 bit。CKKS自举过程中由于不可避免的模切换操作引入了误差导致自举精度始终受限，2022年，Youngjin Bae团队^[34]针对该问题提出了一种新的自举模式—META BTS，是一个类似比特提取的算法，通过重复两次给定的任意自举算法，可以获得一个精度加倍的自举结果，即迭代低精度自举来获得高精度自举，在目标精度$n$足够大的情况下，$n$位精度自举的密文模数近似为$O\left( {{n^{5/4}}} \right)$。该方案的优势在于将自举算法作为黑盒，可以用于CKKS类的所有自举算法，因此如果未来出现了更先进的自举算法，则同样可以令META BTS在精度方面得到更好的结果。

表 2  CKKS 类全同态加密方案自举的不同近似函数及自举精度对比

方案名称	近似函数(方法)	自举精度(bit)
CHKKS[31]	$\sin \left( {\dfrac{{2\pi x}}{q}} \right) \approx x\text{mod} q$	24
LLLK[32]	$\left( {\dfrac{{2\pi x}}{q}} \right)\arcsin \left( {\sin \left( {\dfrac{{2\pi x}}{q}} \right)} \right) = x\text{mod} q$	40.5
JM[33]	$\dfrac{q}{{2\pi }}\mathop \sum \limits_{k = 1}^n {\beta _k}{\text{sin}}\left( {\dfrac{{2\pi kx}}{q}} \right) \approx x\text{mod} q$	44
BCCKK[24]	META BTS	255

下载: 导出CSV 

| 显示表格

3.4.3   研究现状

理想状态下只要噪声与消息相比足够小，则该噪声不会破坏消息的有效数字，但人们一直对CKKS的安全性有所质疑。Li Baiyu和Daniele Micciancio^[35]在2021年发表的论文中提出，虽然CKKS方案满足传统的IND-CPA安全，但是对于更强的带有特殊解密Oracle敌手——IND-${{\mathrm{CP}}}{{{\mathrm{A}}}^{{\mathrm{D}}}}$安全性，可以用恢复密钥攻击打破。这一结论使得人们的目光又聚焦到CKKS方案的安全性优化，2022年，Li Baiyu团队^[36]利用了noise flood技术，通过给解密后的明文添加噪声令CKKS方案满足IND-${{\mathrm{CP}}}{{{\mathrm{A}}}^{{\mathrm{D}}}}$安全性，但这一方法同时也会令解密明文损失将近一半的精度。不论是自举算法中的精度改进，还是近似解密相关安全性研究，CKKS方案始终与噪声联系密切，噪声控制分析也将是CKKS类方案的重点研究内容。

3.5   对比分析

表3列出了4条技术路线全同态加密方案的参数设置、技术特点，运算效率对比。表中的$s$为稀疏子集的大小，$S$为密钥长度，$d$为格的行列式，$N$为理想格维数，$f\left( {\lambda} \right)$为安全参数${\lambda}$的函数，$n$为环维数，$q$为密文模，$t$为明文模。首先，因为Gentry类方案基础假设中的理想格参数设置难度较大，而BGV类，GSW类，CKKS类方案都是基于更加简单易用的(R)LWE困难问题，所以这3条技术路线下的全同态加密方案都更加具有实用性且目前已被广泛应用，并且这些方案都有多个算法库支持代码实现，所以Gentry类方案由于实现存在困难逐渐退出人们的研究视野。接下来将主要对除Gentry类以外的3类全同态加密方案进行对比分析。

表 3  4条技术路线全同态加密方案对比

	Gentry类	BGV类		GSW类	CKKS类
基础假设	理想格	LWE	RLWE	(R)LWE	RLWE
密文空间	${\mathbb{Z}_d}$	$\mathbb{Z}_q^n$	$R_q^n$	$\mathbb{Z}_q^{n \times n}$	$R_q^n$
密文大小	$f\left( \lambda \right)$	$\left( {n + 1} \right)\left\lceil {\log_2 q} \right\rceil$	$2n\left\lceil {\log_2 q} \right\rceil$	${\left( {n + 1} \right)^2}{\left\lceil {\log_2 q} \right\rceil ^3}$	$2n\left\lceil {\log_2 q} \right\rceil$
明文空间	${\mathbb{Z}_2}$	${\mathbb{Z}_t}$	${R_t}$	${\mathbb{Z}_2}$	\
单个密文存储明文数	1	1	n	1	n
公钥大小	$s \cdot \left\lceil {2\sqrt S } \right\rceil \cdot {\log _2}d$	$2n\left( {n + 1} \right){\log_2}q$	$2n\left\lceil {\log_2 q} \right\rceil$	$2n\left( {n + 1} \right){\log_2}q$	$2n\left\lceil {\log_2 q} \right\rceil$
是否支持消息打包	\	否	是	暂不支持	是
是否支持SIMD	\	是	是	暂不支持	是
同态乘法噪声增长速度	${N^{{{\Omega }}\left( 1 \right)}}$	$O\left( {{n^2}} \right)$	$O\left( {{n^2}} \right)$	$O\left( n \right)$	$O\left( {{n^2}} \right)$
(平均)单比特自举时间	30 min	\	1.3 ms	13 ms	6.43 s

下载: 导出CSV 

| 显示表格

BGV类方案基于LWE和RLWE构造的全同态加密方案效率有所不同，得益于RLWE的环结构，可以令单个密文加密多个消息，提高了密文利用率，同时降低了公钥的尺寸，平均单比特的自举时间约1 ms，与以自举速度著称的GSW类方案同样做到毫秒级。虽然文中提到的一些最新成果对GSW类方案的SIMD和打包操作出理论支撑，但目前因为技术的局限性，在代码实现上仍不支持上述两种操作。

表中数据显示，GSW类方案密文的矩阵结构导致密文尺寸大于其他方案。矩阵密文的优势在于同态乘法不会有维数扩张问题，而且噪声增长的速度也会因噪声向量被分解成二进制矩阵而降低，由指数级降低为线性级。GSW类方案的经典方案构造基于LWE假设，仅在自举步骤用到RLWE的环结构，并不涉及密文的打包，因此表中数据除自举时间外都是基于LWE的方案参数。

CKKS因为近似加密的特点会把加密引入的LWE噪声看作消息的一部分，解密明文的精度由精度因子${{\varDelta }}$决定，所以与其他全同态加密方案不同，只有消息空间，没有明文空间。

在自举效率方面，Gentry类方案^[27]代码实现的效果并不理想，在72 bit的安全强度下，公钥大小约为2.3 GB，自举刷新但比特密文需要30 min。相较于基于(R)LWE的全同态加密方案中，公钥最小仅需几十MB，自举速度已经提升到毫秒级，Gentry类方案的自举速度和内存需求明显缺乏竞争力。BGV类方案在算法库Helib^[42]的实现中设定128 bit的安全参数，稀疏自举 ²可以做到平均单比特自举仅用时1.3 ms。GSW类方案在TFHE库中取安全参数为128 bit可以做到13 ms的单比特自举。CKKS类方案的自举时间与精度成正相关，所需精度越高，自举过程中用来近似模函数的近似多项式维数越高，自举时间也就越长。目前CKKS类方案的实现效果^[34]聚焦于自举后的密文精度以及同态乘法的最大深度。在算法库HEAAN中选择128 bit安全参数，精度因子$\varDelta = {2^{36}}$，取环维度${2^{15}}$时，自举所需时间为6.43 s，自举后支持的最大乘法深度为14；取环维度${2^{16}}$时，自举所需时间为16.3 s，自举后支持的最大乘法深度为29。

4.   应用实现

随着数据安全的普及，各类云服务的广泛应用，全同态加密算法拥有广阔的应用场景和发展空间，目前已经有一些团队根据上述全同态方案构造了相应的算法库，将理论成果转化为高质量实现。

Helib^[55]由IBM开发设计，是一个用C++语言编写的同态加密开源软件库，可以在Windows, macOS, Ubuntu, CentOS等操作系统平台上进行安装部署，底层依赖于NTL数论运算库和GMP多精度运算库，支持BGV和CKKS方案的实现。此外Helib还提供许多提升算法运行效率的算法代码，例如Smart-Vercauteren密文打包技术和Gentry-Halevi-Smart优化算法，支持“set”, “add”, “multiply”, “shift”等基本操作指令。2018年IBM发布的新版本Helib库，优化了重线性化算法，使效率进一步提升了15～75 倍。

Microsoft SEAL^[56]由 Microsoft 的密码学和隐私研究小组开发，是一个用C++编写的开源同态加密库，可以在多种环境中运行，支持BFV, BGV和CKKS三种同态加密方案。SEAL库的使用要求用户理解许多同态加密的特定概念，它可以进行密文的同态加法和乘法操作，但无法进行密文的比较排序等操作。

PALISADE是一个开源项目，提供格密码构建实例和最新同态加密方案的高效实现。PALISADE专为可用性而设计，支持BGV, BFV, CKKS和FHEW方案以及TFHE方案的变体，包括对应的自举算法。PALISADE还提供后量子公钥加密、代理重加密、多方计算阈值同态、基于身份的加密、基于属性的加密和数字签名等加密方案。目前PALISADE的主创团队已将该项目合并到后继者OpenFHE^[57]库中。

TFHE库基于Chillotti团队^[58]同年提出的方案进行设计，它实现了GSW方案的类同态和带自举的全同态。与其他库不同，TFHE库对电路门的数量或其组成没有限制，因此它的电路可由用户自主定义，或用带有自动电路生成的工具生成，可以实现对任意电路的密文同态运算。

HEAAN^[59]是由CKKS方案作者团队开发的一个开源算法库，支持定点算术和有理数的近似计算，支持自举算法基于CHKKS18^[31]，引入的近似误差基本同于浮点运算误差，取决于具体参数的设置。HEAAN库支持C++和NTL library语言，目前更新到V2.1版本。

OpenFHE^[57]是Duality Technologies团队在2022年发布的一个支持目前大部分全同态算法的开源算法库。OpenFHE库继承了PALISADE库的所有功能，并融合了HElib和HEAAN的特定功能，它支持用户友好模式和编译器友好模式，可以由库或外部编译器直接调用同态密文的运算算法，提供了更简单的API、模块化、跨平台支持和硬件加速器集成。

除了上述主流同态实现库之外，还有主要用于探索使用低级处理器原语的高性能同态加密的NFLlib库，探索使用GPU来加速同态加密的cuFHE库，用Go语言编写的Lattigo库等 。表4针对一些基本的使用需求对比了这些实现库的应用特点。

表 4  不同实现库的应用特点对比

实现库名称	实现语言	支持加密方案	自举	特色功能
Helib	C++	BGV, CKKS	√	支持HE 汇编语言
SEAL	C++	BFV, CKKS	√	跨平台编译
PALISADE	C++	BGV, BFV, CKKS, FHEW, TFHE	√	跨平台编译，BGV/BFV/CKKS的多方扩展
TFHE	C/C++	GSW, FHEW, TFHE	√	可编程自举
HEAAN	C++	CKKS	√	GPU加速
NFLlib	C++	\	\	基于NTT的快速格计算
cuFHE	C++	TFHE	√	CUDA加速
Lattigo	Go	BGV, BFV, CKKS	√	跨平台编译，剩余数系统(RNS)
OpenFHE	C++	BGV, BFV, CKKS, FHEW, TFHE	√	剩余数系统(RNS), BGV/BFV/CKKS的多方扩展

下载: 导出CSV 

| 显示表格

随着全同态库的功能逐渐强大、应用逐渐广泛，全同态加密方案的标准化进程也在逐步推进。同态加密标准联盟一直致力于开发同态加密的社区标准。该组织基于标准化研讨会的3份关于同态加密的安全性、API和应用白皮书，于2018年发布了《同态加密标准》的第1版，并计划在未来版本中增加用于同态加密的标准 API 和编程模型的内容。2021年，国际标准ISO/IEC 18033-8《信息技术-安全技术-第8部分：完全同态加密》立项，旨在推进全同态加密工作机制的规范化。提议的国际标准规定了全同态的加密机制：提供了定义、符号和格式，同时定义了安全模型、假设、消息空间等适合标准化的方案加密机制。

5.   总结与展望

自从Genrty开创了全同态的方案构造，经过十多年的发展，全同态加密技术正在从理论走向实际，从一个理论上的方案转变成一种实际可用的工具，也涌现了一些具体的应用场景和性能指标。多方安全计算、密码数据库、区块链隐私保护、机器学习隐私等多种应用领域不断涌现同态密码技术的身影，并将在今后继续发挥出巨大的作用。

一方面，为了适应云环境下多用户快速、稳定地存储和计算密文，全同态加密的方案设计开始面向多用户：门限全同态^[60](ThresholdFHE)，多密钥的全同态^[61]、多方参与的全同态^[62]，这些带交互的方案设计进一步拓宽了全同态加密的应用场景。

另一方面，随着计算机算力的提升，硬件数据处理能力的增强，针对全同态方案基础参数的许多实验性改进将更有实际意义:选择非2次幂的明文环次数^[63]，$t = {X^m} + b$的明文模数^[64]，比SIMD更复杂但高效的域指令多数据(Field Instruction Multiple Data, FIMD)打包^[65]等，这些技术都致力于缩减同态加密方案的内存占用，提升存储效率，具有推广到所有同态加密方案的潜力。

目前已有的4条同态加密方案技术路线各有不同的挑战和机遇：Gentry基于理想格做出的一系列全同态相关领域研究，奠定了全同态加密的理论基础，但是理想格等数学概念代码实现困难，所以相关研究逐渐遇冷。BGV类方案基于简单易用的(R)LWE假设，便于用计算机编程检验方案性能，此外还擅长多组打包密文的并行处理，因此即使自举时间相对GSW类方案更长，单比特的平均自举时间基本为同一水平。目前BGV类方案的优化方向一是加速自举算法，改进自举中最耗时的比特提取步骤，提升密文同态解密速度；二是优化降噪技术，增加同态乘法的最大深度，尽可能避免复杂的自举操作。GSW类加密方案利用矩阵的代数性质加速了密文乘法，特有的非对称噪声增长也将噪声增长速度从BGV类的指数级降低到了线性级，密文的自举性能相比其他技术路线的同态方案具有极大优势。此外根据GSW类方案的特点还可以用于构造基于身份或属性的加密方案，因为GSW类密文除了具有同态处理密文数据的性质，还支持可编程自举，可以进行非线性运算，所以将认证消息加密成GSW类密文，则可以在不泄露认证消息的前提下，对认证消息的密文进行同态操作，完成身份认证。然而目前身份认证协议主要使用CCA2-secure的传统加密方案^[66,67]，现有的全同态加密方案仅支持CCA1的安全性，因此如何令全同态加密方案满足CCA2-secure也是限制其应用领域的一个共性问题。此外GSW类加密方案如何实现消息的打包和密文的并行处理仍是尚未彻底解决的难题，因为目前的理论成果往往需要一些严苛的参数要求，所以距离代码实现投入使用仍有一段距离。CKKS类方案的主要结构与BGV类相似，因此除了BGV类方案存在的问题之外，CKKS类方案始终关注如何选择更好的近似函数提升自举精度，削弱噪声泄露的信息对方案安全性的影响两大问题。总体来说，上述全同态加密方案目前仍无法满足实际应用中云端对大量数据的密文快速处理需求，如何进一步加速理论成果转化，改善全同态加密方案实用性能，仍然是未来研究的重点。