全同态加密（fully homomorphic encryption，FHE）支持对密态数据进行任意计算而无需事先解密，计算后的结果仍是加密状态，且解密后就是用户想要的结果，即与“对明文数据进行对应计算”的结果相同. 可以理解为，FHE方案能够为任意数据处理功能构建一个“程序”，该“程序”无需解密输入数据，密态输入且密态输出，运行过程全密态，因此可在不受信任的一方运行. 这一特性很大程度上解决了各应用场景下，互不信任的2方或多方之间进行数据处理时的数据安全和隐私保护问题，使得FHE具有很强的通用性. 首个真正的FHE方案由Gentry于2009年提出^[1]，但由于该方案的实现效率远远达不到应用要求，给大家留下了FHE方案性能低的刻板印象. 经过十几年的努力，目前FHE研究及应用取得了重大突破，已从最初的概念验证变为可实际应用的工具.

本文首先介绍相关概念定义，并从自举（bootstraping）、同态解密切入阐述FHE方案的一般构造思想，其次分析讨论不同阶段FHE的研究进展及局限性，随后从算法库实践、标准化进展、典型应用等方面介绍FHE的应用进展，最后总结并展望FHE亟待解决问题和发展方向.

1.   概念定义

1.1   概念理解

1）同态. 2个代数结构间的一种映射$\delta :A \to B$，满足$\delta \left( {x{ * _A}y} \right) = \delta \left( x \right){ * _B}\delta \left( y \right)$. 由于$x{ * _A}y = z \Rightarrow$ $\;\delta \left( x \right){ * _B}\delta \left( y \right) = \delta \left( z \right)$，所以代数结构$\left\langle {A,{ * _A}} \right\rangle$和$\left\langle {B,{ * _B}} \right\rangle$在该映射下相关结构保持不变，可以理解为同态是2个代数结构（如群、环、域或向量空间）之间的保持结构不变的映射. 可以用交换图表述同态的概念，如图1所示，从左上角出发，“先右再下”和“先下再右”2条途径都可以得到右下角的结果，即对任意$x,y \in A$，“先${ * _A}$运算再$\delta$映射”与“先$\delta$映射再${ * _B}$运算”的结果相同，即满足交换性. 例如，取$\delta \left( x \right) = {{\rm e}^x}$时，交换图可具体表述为如图2所示. 此时$A$为$\mathbb{R}$，$B$为${\mathbb{R}^ + }$（大于0的实数集合），${ * _A}$为“+”，${ * _B}$为“×”.

图  1  同态交换示意图

Figure  1.  Schematic diagram of homomorphic exchange

下载: 全尺寸图片 幻灯片

图  2  同态交换示例

Figure  2.  Example of homomorphic exchange

下载: 全尺寸图片 幻灯片

2）同态加密. 同态加密是指满足同态性质的加密算法，即该加密算法的密文空间和明文空间之间的映射（解密函数）对特定运算满足同态性质. 因此同态加密支持对密文空间进行特定功能的运算（用函数$f$表示），且解密后的结果与直接对明文空间进行对应运算的结果相同. 若$f$只能由加法构成，即仅支持加法运算，称为加同态，如Paillier算法^[2]；若$f$只能由乘法构成，即仅支持乘法运算，称为乘同态，如RSA算法^[3]. 一般称仅支持加法或乘法运算的加密方案为部分同态加密. 若$f$可由加法和乘法构成，但支持的运算次数有限，则称为近似同态加密（somewhat homomorphic encryption，SHE）.

3）FHE. FHE是指支持密文域上任意运算的同态加密算法. 而同态加密算法定义在域上的任意运算均可用加法和乘法构造，因此称同时满足加同态和乘同态的加密算法为FHE算法. 即FHE应能同时支持不限次的加法和乘法运算，可实现对密态数据任意有意义的操作，其形式化定义详见1.2节.

需要注意的是，此处的加法和乘法不等同于加减乘除中的加法和乘法，而是一种一般性表达，如布尔函数中的与（AND）运算和异或（XOR）分别对应此处的乘法和加法. 事实上，任意逻辑运算均可通过AND和XOR运算组合表达，任意算术运算均可通过加法和乘法运算组合表达，即任意运算均可通过加法和乘法运算的组合来实现.

4）层级全同态加密（leveled FHE，LFHE）. 若支持一定复杂度范围内的任意运算，则称为LFHE. 此处复杂度理解为将该运算用电路形式表示时其电路深度的大小，即电路深度应不超过某个值$L$. 而任意运算可理解为由加法和乘法任意构成.

事实上，现有同态加密方案中经常用运算电路$C$来表示$f$. 因为不管是布尔电路还是算术电路，其包含的操作仅仅是电路门所对应的逻辑操作或算术操作，没有选择、判断、循环等复杂操作，因此应用于同态加密研究时非常便利. 在密码学研究尤其是在计算复杂性研究中，经常使用电路来表示运算或算法，如此，一个函数可以等效为一个电路模型，电路模型下可通过电路深度和门电路个数来衡量计算复杂度. 本文将使用电路来表示运算或函数.

5）格与基. 格是欧氏空间${{\mathbb{R}}^m}$中$n\left( {m \geqslant n} \right)$个线性无关向量组${{\boldsymbol{b}}_1},{{\boldsymbol{b}}_2},…,{{\boldsymbol{b}}_n}$所有整系数线性组合的集合：

即格是${\mathbb{R}^m}$中一类具有周期性结构离散点的集合. 称${{\boldsymbol{b}}_1}{{,}}\,{{\boldsymbol{b}}_2}, …, {{\boldsymbol{b}}_n}$为$n$维格$\varLambda$的一组基（即格基），${\boldsymbol{B}} \in {\mathbb{R}^{m \times n}}$是格基的矩阵表示. 事实上，格基可以不唯一，且不同格基之间可通过一个行列式为$\pm 1$的矩阵进行转换.

6）容错学习（learning with errors，LWE）问题. 给定矩阵${\boldsymbol{A}} \in \mathbb{R}_q^{m \times n}$和向量${\boldsymbol{b}} = {\boldsymbol{As}} + {\boldsymbol{e}}\left( {\text{mod} q} \right)$，求解随机的秘密向量${\boldsymbol{s}} \in \mathbb{Z}_q^n$是困难的. 其中$q$是模数（通常取较大的素数），${\boldsymbol{e}} \in \mathbb{Z}_q^m$是一个小的误差向量. LWE问题可看作是求解带噪声的线性方程组问题，由Regev^[4]于2005年提出，是一个被充分研究的密码学假设，由于目前尚无有效的量子算法求解LWE问题，因此基于LWE问题构造的加密方案被认为是抗量子攻击的. 若${\boldsymbol{A}},{\boldsymbol{s}},{\boldsymbol{e}}$取自特定环上，则转化成LWE问题的变体，称为R-LWE问题. 其主要特点是：一般情形下（average-case）解决 LWE问题并不比在最坏情形下（worst-case）解决一些著名格近似问题简单.

1.2   FHE定义

1）核心算法. 目前FHE方案均基于公钥密码体制，一个FHE方案除了包含公钥密码体制中的3个基础算法外，还包含1个实现同态计算功能的算法，即包含4个概率多项式算法：密钥生成算法$KeyGen\left( {} \right)$、加密算法$Enc\left( {} \right)$、解密算法$Dec\left( {} \right)$、同态计算算法$Eval\left( {} \right)$.

①密钥生成算法. 该算法为随机算法，$\left( {{\boldsymbol{pk}},{\boldsymbol{sk}}} \right) \leftarrow$$KeyGen$$( {{1^\lambda }})$，以安全参数${1^\lambda }$为输入，输出公钥${\boldsymbol{pk}}$和私钥${\boldsymbol{sk}}$.

② 加密算法. 该算法为随机算法，${\boldsymbol{c}} \leftarrow Enc\left( {{\boldsymbol{pk}},m} \right)$，以公钥${\boldsymbol{pk}}$和消息$m \in \left\{ {0,1} \right\}$为输入，输出密文${\boldsymbol{c}}$.

③ 解密算法. 该算法为确定性算法，$m \leftarrow Dec\left( {{\boldsymbol{sk}},{\boldsymbol{c}}} \right)$，以私钥${\boldsymbol{sk}}$和密文${\boldsymbol{c}}$为输入，输出消息$m \in \left\{ {0,1} \right\}$.

④同态计算算法. 该算法为随机算法，${{\boldsymbol{c}}^ * } \leftarrow Eval$$\left( {\boldsymbol{pk}}, \right.$$\left.C,{{\boldsymbol{c}}_1},{{\boldsymbol{c}}_2},…,{{\boldsymbol{c}}_t} \right)$，以公钥${\boldsymbol{pk}}$、运算电路$C \in \mathcal{C}$和${{\boldsymbol{c}}_1}, {{\boldsymbol{c}}_2},…,{{\boldsymbol{c}}_t}$为输入，输出密文${{\boldsymbol{c}}^ * }$. 其中，$\mathcal{C}$为一个电路族，${{\boldsymbol{c}}_i} \leftarrow Enc\left( {{\boldsymbol{pk}},{m_i}} \right)$，$i = 1,2,…,t$.

2）正确性. 若对$\forall$${m_1},{m_2},…,{m_t} \in \left\{ {0,1} \right\}$，及$\forall C \in \mathcal{C}$，有$Dec\left( {{\boldsymbol{sk}},{{\boldsymbol{c}}^ * }} \right) = C\left( {{m_1},{m_2},…,{m_t}} \right)$，则称该加密方案关于同态电路族$\mathcal{C}$中的任意运算函数$C$是正确的. 可用交换图表述如图3所示.

图  3  FHE交换图

Figure  3.  FHE exchange diagram

下载: 全尺寸图片 幻灯片

每个同态加密方案均对应一个电路族$\mathcal{C}$，只有函数$C \in \mathcal{C}$时，先调用$C$再解密和先解密再调用$C$是可交换的，即该方案关于$C$是同态的. 若$C$是任意的，即构造的同态加密方案对任意运算均满足正确性（即图3所示的可交换性），则该方案是全同态的.

3）紧凑性. 对于任意的安全参数$\lambda$，若存在一个多项式$P$，使得同态加密方案的解密算法能够用一个 规模至多为$P\left( \lambda \right)$的电路$D$来表示，那么称该同态加密方案是紧凑的，即满足紧凑性意味着该方案的解密电路独立于$t$和$C$.

4）安全性. 同态加密的安全性通过语义安全来定义. 用基于游戏的范式可表述为：若对于任意多项式时间敌手$\mathcal{A}$，式（1）在$\lambda$上可忽略，称该加密方案是不可区分选择明文攻击安全的（IND-CPA安全）.

其中$\left( {{\boldsymbol{pk}},{\boldsymbol{sk}}} \right) \leftarrow KeyGen( {{1^\lambda }})$. 即选择明文攻击（chosen plaintext attacks，CPA）是安全的，意味着0与1的密文对于敌手$\mathcal{A}$是不可区分的，所以安全的同态加密算法应为概率算法（每个明文将对应多个密文）.

2.   构造思想

同态加密方案的构造总体上分为同态性满足和安全性满足两大实现. 构造实践中，可以先寻求同态性的满足，使得解密函数具有同态性，而后寻求方案的安全性满足. 也可以先建立一个密码学安全假设，然后在此假设下构建公钥加密方案，而后通过引入其他操作（即构造函数$Eval$）使方案满足同态性. 二者的区别在于前者可以选择更多的数学结构用于同态加密方案的构造，后者则基于相对完备的密码学假设提前保障安全性，只是可能很难快速构造出满足同态性的方案.

Rothblum^[5]给出了一种通用方法，可将明文空间为$\left\{ {0,1} \right\}$的任意满足语义安全的私钥同态加密方案转化为满足语义安全性的公钥同态加密方案. 该方法简化了方案的安全性证明，为基于同态映射来构建语义安全的同态加密方案提供了思路.

FHE方案的构造重点在于实现密文域上任意次数的加法和乘法同态运算. 一般构造的初始方案均为SHE方案，因在加密和密文运算过程中会引入“噪声”用于掩饰明文信息，随着密文同态运算次数越多、噪声值越大，当噪声达到某一“临界”就会解密失败，因此能支持的同态运算次数有限. 如何将SHE方案转化为FHE方案是关键，目前大多借助自举技术来实现.

2.1   自举技术

自举技术本质上是通过同态解密运算，即执行参数电路$C$为解密电路$D$（函数$Dec$的电路表现形式）的函数$Eval$，将密文刷新为一个噪声值更低的“新鲜”密文，如此不会因为噪声干扰导致解密失败，即可继续进行同态运算，从而实现不限次同态运算，自举过程示意图如图4所示.

图  4  自举过程示意图

Figure  4.  Illustration of bootstraping process

下载: 全尺寸图片 幻灯片

图4的同态解密过程中，解密电路$D$将作为函数$Eval$的执行参数，同态解密最右侧的“不新鲜”密文，得到最左侧噪声值更低的“新鲜”密文，且每次同态解密运算前后的密文对应同一个明文，即${{\boldsymbol{c}}_1}$和${\boldsymbol{c}}_1^ *$对应相同的明文，${{\boldsymbol{c}}_2}$和${\boldsymbol{c}}_2^ *$对应相同的明文.

值得注意的是，同态解密过程可以消除解密电路$D$对应的加密运算当初引入的噪声，但由于函数$Eval$是在密文空间执行的，因此还会引入新的噪声. 因此需要保证新引入的噪声大小允许方案继续执行密文同态运算，这就要求解密电路的深度要小于起初构造的SHE方案所允许的密文计算深度. 也就是说，方案实现自举过程的前提是函数$Eval$可运行方案自身的解密电路. 当不能运行时，就要采取措施使其解密电路的深度变小，Gentry09^[1]采用了一个“压缩（squashing）”技术去实现，代价是增加一个安全性假设——稀疏子集和问题（sparse subset sum problem，SSSP），不过目前的方案已能够运行自身解密电路，如BGV^[6]方案、Bra12^[7]方案等.

2.2   同态解密

自举的关键环节是同态解密，即在密文空间执行解密函数，该函数用加密的私钥去解密加密后的密文，输出一个噪声值更低的“新鲜”密文，即明文对应的另一个密文. 实现原理以Gentry09^[1]为例，说明如下：

明文空间为$\left\{ {0,1} \right\}$，即明文是单个比特，且有2个不同的公私钥对$({\boldsymbol{p}}{{\boldsymbol{k}}_1},{\boldsymbol{s}}{{\boldsymbol{k}}_1})$和$({\boldsymbol{p}}{{\boldsymbol{k}}_2},{\boldsymbol{s}}{{\boldsymbol{k}}_2})$，私钥由用户自行保管，公钥公开发布.

1）用户将明文消息$m$的密文${\boldsymbol{c}} \leftarrow Enc({\boldsymbol{p}}{{\boldsymbol{k}}_1},m)$发送至服务器；

2）用户用另一个公钥${\boldsymbol{p}}{{\boldsymbol{k}}_2}$对私钥${\boldsymbol{s}}{{\boldsymbol{k}}_1}$进行逐比特加密，得到密文序列$\overline {{\boldsymbol{s}}{{\boldsymbol{k}}_1}}$（即加密的密钥），并发送至服务器；

3）服务器用公钥${\boldsymbol{p}}{{\boldsymbol{k}}_2}$对密文${\boldsymbol{c}}$进行逐比特加密，得到密文序列${\boldsymbol{\bar c}}$（即双重加密状态的密文）；

4）服务器用加密的私钥$\overline {{\boldsymbol{s}}{{\boldsymbol{k}}_1}}$同态解密双重加密的密文${\boldsymbol{\bar c}}$，由同态加密的正确性定义得：

即经过同态解密，密文${{\boldsymbol{c}}^ * }$是明文消息$m$用另一个公钥${\boldsymbol{p}}{{\boldsymbol{k}}_2}$加密的结果，和${\boldsymbol{c}}$一样是“新鲜”密文，均具有较低的噪声值. 该过程可扩展至${\boldsymbol{c}}$为“不新鲜”密文时的情形，即可对经过多次同态运算的高噪声密文经同态解密后刷新为低噪声的“新鲜”密文，如图4所示.

注意到，同态加密过程中私钥被加密后作为公共参数予以公开，并作为函数$Eval$的输入，因此被称为计算公钥；另外出现了明文被双重加密的状态，其中第1次加密（看作“内层加密”）的结果是第2次加密（看作“外层加密”）的明文输入. 同态解密的过程可看作是在双重加密状态下解密内层保留外层加密的过程，如图5所示.

图  5  同态解密示意图

Figure  5.  Homomorphic decryption schematic diagram

下载: 全尺寸图片 幻灯片

3.   FHE研究进展

现有主流FHE方案的困难假设主要基于2种困难问题：一种是基于格困难问题，另一种是整数上基于近似最大公约数（approximate greatest common divisor，AGCD）困难问题. 其中基于格困难问题的FHE方案发展迅速，目前已发展至第4代，尤其以基于R-LWE问题假设的方案发展最为迅速（如第2，3，4代），另外，还有一个基于NTRU的研究分支. 本节首先介绍Gentry09^[1]提出前仅支撑部分同态运算的典型加密方案，再对基于格困难问题的4代典型FHE方案进行研究分析，最后对基于整数、NTRU的FHE方案进行简要分析. 经典FHE方案的分类及继承关系如图6所示，其中虚线框内的方案基于格困难问题.

图  6  FHE研究脉络示意图

Figure  6.  FHE research venation schematic diagram

下载: 全尺寸图片 幻灯片

3.1   支持部分同态的Pre-FHE方案

本文将只满足加同态或乘同态的加密方案，以及SHE方案统称为不完全同态加密方案. 自1978年Rivest等人提出隐私同态加密的概念（即FHE构想）以来，FHE方案的探索研究历程可总结为对密文域上的任意多项式函数实现同态运算的过程. 在2009年Gentry构造出第1个真正的FHE方案之前，所有的同态加密方案均为不完全同态加密方案，如RSA^[3]，Rabin^[8]，EIGamal^[9]算法是仅支持不限次乘法运算的乘同态加密算法，即支持任意多元单项式函数的同态运算；Paillier^[2]算法和文献[10–19]是仅支持不限次加法运算的加同态算法，即支持任意多元一次多项式函数的同态运算；SYY99^[20]支持任意NC¹复杂类电路（Fan-in度为$O\left( 1 \right)$，电路深度为$O( {\log n} )$），IP07^[21]支持任意有限长度的分支程序（branching programs），包括NC¹中的电路（因任意NC¹类复杂度计算均可被多项式大小的分支程序执行），文献[20–21]是仅支持有限次加法和乘法的SHE方案，即支持的多项式函数项数和次数有限. BGN05^[22]支持不限次的加法和至多1次乘法运算，即支持任意多元二次多项式函数的同态运算，且具备同态运算后密文大小保持不变的优点. MGH08^[23]支持不限次加法和有限次乘法运算，即支持任意多元$d$次多项式函数的同态运算；此外，Polly Cracker方案^[24]和GP06^[25]等曾尝试构建一个FHE方案，但均被证实存在严重安全漏洞^[26-27]. 还有基于对称加密机制的探索^[28-29]但很快也被指出有安全漏洞^[30-31].

由于对密文同态运算的支持能力不足（详见表1）或安全性的问题，Pre-FHE方案均未实现对密文数据进行任意多项式函数的同态运算，但此阶段的同态加密研究已然为首次成功构建FHE方案奠定了坚实基础，其中不乏中有基于格的不完全同态加密方案^[15-19]. 尤其是首个FHE方案提出前的近几年，但多为加法同态加密方案.

表  1  不完全同态加密方案

Table  1.  Imperfect Homomorphic Encryption Scheme

同态加密方案	支持的加、乘运算次数	支持的多项式运算
RSA[3]	不限次乘法	任意多元单项式
文献[8]	不限次乘法	任意多元单项式
文献[9]	不限次乘法	任意多元单项式
文献[2]	不限次加法	任意多元一次多项式
GM82[10]	${\mathbb{Z}_2}$上的不限次加法	任意多元一次多项式
文献[11]	不限次加法	任意多元一次多项式
文献[12]	不限次加法	任意多元一次多项式
文献[13]	不限次加法	任意多元一次多项式
文献[14]	不限次加法	任意多元一次多项式
GK05[15]	不限次加法	任意多元一次多项式
AKK07[16]	不限次加法	任意多元一次多项式
CGP08[17]	不限次加法	任意多元一次多项式
CB08[18]	不限次加法	任意多元一次多项式
AS08[19]	不限次加法	任意多元一次多项式
SYY99[20]	有限次加法和乘法	有限项多项式
IP07[21]	有限次加法和乘法	有限项多项式
BGN05[22]	不限次加法，至多1次乘法	任意多元二次多项式
MGH08[23]	不限次加法，有限次乘法	任意多元$d$次多项式

下载: 导出CSV 

| 显示表格

3.2   基于理想格的第1代FHE方案

第1代FHE方案是指以Gentry09^[1]为基础基于理想格的FHE方案，其构造过程为：首先基于理想格构建一个SHE方案，其安全性基于固定环上理想格的最近向量问题（closest vector problem，CVP）；其次通过压缩解密电路使得方案可自举，安全性依赖于SSSP假设；而后基于压缩后的解密电路通过同态解密实现自举，从而实现全同态，其中自举过程是实现全同态的关键，同时也极大地增加了计算量.

该方案实现了FHE理论性的重大突破，但在实际应用中存在许多瓶颈：1）该方案在密钥生成算法中有个遗留问题，即如何生成拥有良好格基的理想格；2）压缩解密电路的过程中引入了一个未被充分研究的安全性假设（即SSSP）；3）计算量过大导致性能太低的问题，这也是最典型问题. 因此，后续有许多基于该方案的改进研究：Gentry10给出了一个新的密钥生成算法^[32]，并通过量子最坏情况/平均情况归约提高SSSP假设的安全性；同年SS10^[33]进一步完善了Gentry10提出的密钥生成算法，并对SSSP假设做了更深入的分析，并提出一种解密电路深度更小（为原方案的平方根）的概率解密算法以降低方案计算复杂度；OYKU10^[34]，SS11^[35]，GH11a^[36]等均对Gentry09^[1]的密钥生成算法进行了优化.GH11b^[37]和GHS12^[38]则专注于对自举过程的性能优化，但由于私钥向量由$n$维约减到1维，增加了遭受Key Recovery攻击的概率. 此外，Smart等人^[39]在Gentry09方案的基础上，提出具有相对较小尺寸密钥和密文的FHE方案SV10，但密钥生成性能很差且后续不再生成密钥对，意味着该方案是个SHE方案. SV10首次在FHE语境下正式分析批处理的可能性，并指出只要参数选择合理即可支持单指令多数据（single instruction multiple data，SIMD）操作，但当时此方案的参数并不支持SIMD操作. 通过调整SV10^[39]和GH11a^[36]中的参数，利用中国剩余定义提出支持SIMD操作的FHE方案SV11^[40]，该方案沿用了GH11a的密钥生成算法，并通过SIMD操作实现了重加密的并行执行. M12^[41]提出了一种具有更大明文空间的SHE方案，但密钥生成算法复杂度稍有增加.

文献[32–41]方案均针对Gentry09提出的FHE构造框架进行优化，直到2011年基于LWE假设的FHE方案被提出，至此，FHE的研究进入第2个阶段.

第1代FHE方案的局限性在于：1）构造较为复杂且不易理解；2）噪声增长速度和密文膨胀较快，且自举程序性能太差，导致FHE方案的研究更多停留在理论研究阶段，不具备实际操作意义；3）为了使FHE方案可自举，需压缩解密电路、降低方案的性能和引入了未被充分研究的SSSP安全假设.

3.3   基于LWE的第2代FHE方案

第2代FHE方案首次基于LWE问题假设构造FHE方案，2011年，CRYPTO2011和FOCS2011先后提出基于R-LWE问题和标准LWE问题假设的FHE方案. BV11a^[42]的SHE方案的构造基于LPR10^[43]提出的公钥加密方案实现，密钥生成时无需生成格基，其安全性量子规约到理想格上的最坏情形困难问题，方案后续关于解密电路的压缩方法和自举实现仍沿用了Gentry09^[1]的做法. BV11b^[44]的SHE方案采用的重线性化（relinearization）技术基于Regev05^[4]构造，其安全性归约到任意格上的最坏情况下短向量问题（short vector problem，SVP）的困难性^[45]，而在此之前所有基于格的FHE方案构造均依赖于各种环中的理想. 此外，BV11b不再采用Gentry09的解密电路压缩方法，提出一种新的维-模约减（dimension-modulus reduction）技术使得方案可自举，而无需引入额外的安全性假设；并提出一种模交换（modulus switching）技术来控制密文噪声的膨胀，且“降噪”过程无需第1代方案中的“计算公钥”，实现更简单、高效. 不久，BGV方案^[6]在ITCS2012被提出，该方案的参数大小与同态运算电路的深度而非阶数（degree）相关，性能上有了极大提升，此外提出密钥切换（key switching）技术来控制密文维数的膨胀，并证明了BV11b^[44]提出的模交换技术可在不借助自举程序的情形下实现密文“降噪”，使得LFHE方案的构造无需依赖Gentry09的自举程序，一定程度上缓解了FHE方案构造对自举程序的依赖.

BGV方案中密钥切换作为关键环节，需借助2个子算法：比特分解算法$BitDecomp\left( \; \right)$和2的幂次算法$Powerof2\left( \; \right)$来实现，伪代码描述如算法1和算法2^[6,46]所示.

算法1. $BitDecomp\left( {{\boldsymbol{x}},q} \right) \to {\boldsymbol{u}}$将$n$维模$q$整数向量${\boldsymbol{x}} = \left( {{x_1},{x_2},…,{x_n}} \right)$分解为二进制表示形式.

{$BitDecomp\left(\boldsymbol x,q\right)$

for $\left(i=1;i\le n;i++\right)$

将${x}_{i}$表示为二进制；

将${x}_{i}$的第$j$比特写入${\boldsymbol u}_{j}$的第$i$分量；

end for

$\boldsymbol u\leftarrow \left({\boldsymbol u}_{0},{\boldsymbol u}_{1},{…},{\boldsymbol u}_{\lceil {\rm lb}q\rceil -1}\right)$；

return $\boldsymbol u$；

}

算法2. $Powerof2\left( {{\boldsymbol{x}},q} \right) \to {\boldsymbol{v}}$的输出为$n$维模$q$整数向量${\boldsymbol{x}} = \left( {{x_1},{x_2},…,{x_n}} \right)$乘以2的不同次幂.

$Powerof2\left(\boldsymbol x,q\right)$

{

for $\left(i=0；i\le \lceil {\rm lb}q\rceil -1；i++\right)$

${\boldsymbol v}_{i}=\boldsymbol x\cdot {2}^{i}$；

end for

$\boldsymbol v\leftarrow \left({\boldsymbol v}_{0},{\boldsymbol v}_{1},{…},{\boldsymbol v}_{\lceil {\rm lb}q\rceil -1}\right)\text{mod} q$；

return $\boldsymbol{v}$；

}

对于等长的向量${\boldsymbol{c}}$和${\boldsymbol{s}}$，有性质1：

性质1. $\left\langle {BitDecomp\left( {{\boldsymbol{c}},q} \right),Powerof2\left( {{\boldsymbol{s}},q} \right)} \right\rangle = \left\langle {{\boldsymbol{c}},{\boldsymbol{s}}} \right\rangle \text{mod} q$.

性质1可以应用到密钥切换过程：首先利用$S withKeyGen\left( \; \right)$算法，输出一个附加信息${{\boldsymbol{\tau }}_{{{\boldsymbol{s}}_1}}}{ \to _{{{\boldsymbol{s}}_2}}}$用于密钥切换算法$S witchKey\left( \; \right)$，伪代码描述如算法3和算法4所示.

算法3. $S witchKeyGen\left( {{{\boldsymbol{s}}_1},{{\boldsymbol{s}}_2}} \right) \to {{\boldsymbol{\tau }}_{{{\boldsymbol{s}}_1}}}{\to _{{{\boldsymbol{s}}_2}}}$输入2个不同长度的密钥${{\boldsymbol{s}}_1}$（${n_1}$维）和${{\boldsymbol{s}}_2}$（${n_2}$维），输出的附加信息${{\boldsymbol{\tau }}_{{{\boldsymbol{s}}_1}}}{ \to _{{{\boldsymbol{s}}_2}}}$是一个矩阵.

$S witchKeyGen\left({\boldsymbol s}_{1},{\boldsymbol s}_{2}\right)$

{

${\boldsymbol{A}} \leftarrow PubKeyGen\left( {{\boldsymbol{params}},{{\boldsymbol{s}}_2}} \right)$；$/*{{\boldsymbol{s}}_2}$对应的公钥 　${\boldsymbol{A}}$*/

${\boldsymbol{v}} \leftarrow Powerof2\left( {{{\boldsymbol{s}}_1},q} \right)$；

将向量${\boldsymbol{v}}$（按列）加到矩阵${\boldsymbol{A}}$的首列，得到矩阵${\boldsymbol{B}}$；

${\boldsymbol{\tau }}_{{{\boldsymbol{s}}_1}{ \to {{{\boldsymbol{s}}_2}}}} \leftarrow {{\boldsymbol{B}}^{\rm T}}$；

${\rm{return}}\;{\boldsymbol{\tau }}_{{{\boldsymbol{s}}_1}{\to {{{\boldsymbol{s}}_2}}}}$.

}

算法4. ${{\boldsymbol{c}}_2} \leftarrow S witchKey\left( {{{\boldsymbol{\tau }}_{{{\boldsymbol{s}}_1}}}{{_ \to }_{{{\boldsymbol{s}}_2}}},{{\boldsymbol{c}}_1}} \right)$将可用密钥${{\boldsymbol{s}}_1}$解密的密文${{\boldsymbol{c}}_1}$切换为可用${{\boldsymbol{s}}_2}$解密的密文${{\boldsymbol{c}}_2}$.

$S witchKey\left({\boldsymbol \tau }_{{\boldsymbol s}_{1}}{{}_{\to }}_{{\boldsymbol s}_{2}},{\boldsymbol c}_{1}\right)$

{

${\boldsymbol c}_{2}\leftarrow {\tau }_{{\boldsymbol s}_{1}}{{}_{\to }}_{{\boldsymbol s}_{2}}\times BitDecomp\left({\boldsymbol c}_{1}\right)$；

return ${\boldsymbol c}_{2}$.

}

结合算法3、算法4和性质1，得到性质2.

性质2. $\langle {\boldsymbol c}_{2},{\boldsymbol s}_{2}\rangle =\left(2\langle BitDecomp\left({\boldsymbol c}_{1},q\right),{\boldsymbol e}_{2}\rangle + \langle {\boldsymbol c}_{1},{\boldsymbol s}_{1}\rangle \right) \text{mod} q$，其中错误向量${{\boldsymbol{e}}_2}$在生成公钥${\boldsymbol{A}}$过程中随机抽样而得，且满足${\boldsymbol{A}}{{\boldsymbol{s}}_{{2}}} = 2{{\boldsymbol{e}}_2}$. 由于第1项的内积较$q$非常小（因为${{\boldsymbol{e}}_2}$很小），因此有$\left\langle {{{\boldsymbol{c}}_2},{{\boldsymbol{s}}_2}} \right\rangle = \left\langle {{{\boldsymbol{c}}_1},{{\boldsymbol{s}}_1}} \right\rangle \text{mod} q$，结合BGV方案的解密算法，性质2意味着经过密钥切换，${{\boldsymbol{c}}_2}$经过${{\boldsymbol{s}}_2}$解密后的结果与${{\boldsymbol{c}}_1}$经过${{\boldsymbol{s}}_1}$解密后的结果相同. 如此，可将同态运算后维度扩张的密文经密钥切换后刷新至低维度.

BGV被提出的当年，Bra12^[7]利用张量乘积技术构造了一个标度不变（scale-invariant）的FHE方案，即无需利用复杂的模交换技术即可使得密文噪声随同态计算呈线性增长而非指数级增长，其安全性基于GapSVP的困难性. FV12^[47]（即BFV方案）对Bra12^[7]进行了优化，将其推广到基于R-LWE问题假设，通过分析各种同态运算所引入噪声的严格最坏边界，确定SHE方案应能处理的最小电路深度，确保自举过程结束后还能处理1次乘法运算，从而实现全同态；此外还提出2个更优的重线性化版本使得密钥更小且运算速度更快. 随后也有一些针对Bra12^[7]的优化方案^[48-50]. 2016年，BEH16^[51]提出一个基于BFV方案的Full-RNS （residue number systems）变体，该方案能与乘法和解密过程中涉及的逐系数除法和舍入操作更好地兼容. 2020年，赵秀凤等人^[52]基于BV11a^[41]提出密钥独立消息（key dependent message，KDM）安全的非对称版本FHE方案，即循环安全的公钥FHE方案. 在EUROCRYPT2023，GIK23^[53]通过利用模${p^{\rm{e}}}$零多项式的代数结构特点，将影响FHE自举过程关键性能的数字提取函数进行稀疏表示，实现方案BGV和BFV的自举加速，比当前最先进BGV的自举速度提高2倍以上（仅限于特定参数下的对比）.

第2代FHE方案除了上述安全性和性能方面的提升，还有一个重大突破即支持SIMD操作. SV11^[39]首次提出基于R-LWE的FHE方案同样支持SIMD操作. GHS12^[38]采用SV11^[39]的密文封装技术实现了基于BGV^[6]的SIMD操作，即可通过将多个明文比特消息封装在每个密文的多个槽（slots）中进行批处理，并可利用自同构性质对各个槽进行置换，如此各个槽中的数据也可互相运算，且方案的性能开销与安全参数优化呈多重对数关系. BGH13^[54]提出利用PVW08的封装方法将多个明文比特封装到一个Regev加密方案^[4]的密文中获得一个封装的密文，进而实现对打包密文的SIMD同态操作，PVW08^[55]相比SV11^[39]的密文封装技术，不只可用于基于R-LWE的FHE方案，还可用于基于标准LWE的FHE方案，虽然性能上有一定牺牲，从此将SIMD同态操作拓展至任意基于LWE的FHE方案.

第2代FHE方案的构造仍需先获得一个SHE方案，而后通过自举技术实现完全同态，但构造过程较第1代FHE方案主要有4点优势：1）SHE方案的构造基于LWE问题假设，不直接依赖于格构造（密钥生成算法显然无需考虑格基的生成），但其安全性可量子规约到任意格上的最坏情形困难问题；2）函数$Eval$可执行方案自身的解密电路，实现自举无需引入额外的安全性假设，即无需对解密电路进行压缩；3）可不依赖自举程序获得LFHE方案；4）可以处理封装的密文而不只是1个明文比特的密文. 总体上较第1代FHE方案安全性更强、构造更简单、高效且支持SIMD操作. 但其局限性在于：1）增加了存储开销，因密钥切换技术的实现需借助$BitDecomp\left( \; \right)$和$Powerof2\left( \; \right)$两个子模块来实现，导致密钥尺寸的膨胀；2）自举实现要求方案底层的格问题在近似因子为超多项式增长时仍保持困难性，安全假设强度过大^[56]；3）方案若要支持任意次同态运算，仍需借助自举技术.

3.4   基于近似特征向量的第3代FHE方案

2013年，Gentry等人^[57]在CRYPTO2013提出基于近似特征向量的FHE方案（即GSW方案^[57]），并实现了基于身份的FHE方案和基于属性的FHE方案，标志着第3代FHE方案的诞生. GSW中的同态运算均为简单的矩阵加法和乘法运算，本质上解决了密文维数膨胀的问题，且通过对噪声项中的高范数矩阵分解为低范数二进制比特矩阵，有效控制噪声增长，又因运行函数$Eval$时无需计算公钥，所以该方案更简单、更高效，但要实现全同态仍需借助自举程序. 2014年，BV14^[58]指出基于GSW可用更短的参数实现FHE，因此噪声增长更慢，且安全性与基于格的常规PKE相当，随后，Brakerski等人^[58]在ITCS2014提出利用Barrington定理^[59]来改进GSW中的自举程序，即利用分支程序（branching program）来实现同态运算. 然而同年AP14^[60]便指出该方法非常低效，并通过将解密电路转换为算术电路（非GSW的布尔电路），高效构造深度较小的解密电路，且无需用Barrington定理将其转换为分支程序，从而得到一种性能更优且误差增长更慢的自举方法；同时利用MP12^[61]提出的工具矩阵（gadget matrix）给出一个技术层面更简单的GSW变体，后续关于GSW的典型优化方案均基于该变体，且自举愈加高效. 现结合AP14，采用工具矩阵${\boldsymbol{G}}$（而非原始GSW采用的$Flatten\left( \; \right)$，$BitDecomp\left( \; \right)$，$Powerof2\left( \; \right)$等算法），给出层级GSW方案的简要描述为：

1）参数生成. $G.Init\left( {{1^\lambda },{1^l}} \right) \to \left( {q,n,N,\chi } \right)$，其中$\lambda$为安全参数，$l$为层级数. 输出模数$q$，维数$n$，向量个数$N$（一般大于$2n{\rm{lb}}{\kern 1pt} q$），$\mathbb{Z}$上的噪声分布高斯函数$\chi$，令${\boldsymbol{params}} = \left( {q,n,N,\chi } \right)$.

2）密钥生成. $G.KeyGen\left( {{\boldsymbol{params}}} \right) \to \left( {{\boldsymbol{pk}},{\boldsymbol{sk}}} \right)$：

①随机选取$n$维向量${\boldsymbol{t}} \leftarrow \mathbb{Z}_q^n$并计算$\boldsymbol{sk}=\boldsymbol{s} \leftarrow (1,-\boldsymbol{t})^{\rm{ }}$；

②随机选取矩阵${\boldsymbol{B}} \leftarrow \mathbb{Z}_q^{N \times n}$，噪声向量${\boldsymbol{e}} \leftarrow {\chi ^N}$，设${\boldsymbol{b}} \leftarrow {\boldsymbol{Bt}} + {\boldsymbol{e}} \in \mathbb{Z}_q^N$，令${\boldsymbol{b}}$右连接矩阵${\boldsymbol{B}}$记为${\boldsymbol{A}}$，即${\boldsymbol{A}} \leftarrow\left[ {{\boldsymbol{b}}|{\boldsymbol{B}}} \right]$$\in \mathbb{Z}_q^{N \times \left( {n + 1} \right)}$，输出${\boldsymbol{pk}} \leftarrow {\boldsymbol{A}}$（这里有${\boldsymbol{As}} = {\boldsymbol{e}}$）.

3）加密. $G.Enc\left( {{\boldsymbol{params}},{\boldsymbol{pk}},m} \right) \to {\boldsymbol{C}},m \in \left\{ {0,1} \right\}$：

①令${\boldsymbol{G}}$为$\left( {n + 1} \right) \times M$阶工具矩阵，并随机选取矩阵${\boldsymbol{R}} \leftarrow {\left\{ {0,1} \right\}^{N \times M}}$；

②计算并生成密文${\boldsymbol{C}} \leftarrow m{\boldsymbol{G}} + {{\boldsymbol{A}}^{\rm T}}{\boldsymbol{R}}( {\text{mod} q} ) \in \mathbb{Z}_q^{\left( {n + 1} \right) \times M}$.

4）解密. $G.Dec\left( {{\boldsymbol{params}},{\boldsymbol{sk}},{\boldsymbol{C}}} \right) \to m$：

①令$i$满足$q/4 < {2^{i - 1}} \leqslant q/2$，${{\boldsymbol{C}}_i}$为密文${\boldsymbol{C}}$的第$i$列，在$\left( { - q/2,} \right.\left. {q/2} \right]$范围内计算$x \leftarrow \left\langle {{{\boldsymbol{C}}_i},{\boldsymbol{s}}} \right\rangle \left( {\text{mod} q} \right)$，请注意$\left\langle {{{\boldsymbol{C}}_i},{\boldsymbol{s}}} \right\rangle = {{\boldsymbol{C}}_i}{\boldsymbol{s}} = m{{\boldsymbol{G}}_i}{\boldsymbol{s}} + {{\boldsymbol{R}}_i}{\boldsymbol{As}} = {2^{i - 1}}m + {{\boldsymbol{R}}_i^{\rm T}}{\boldsymbol{e}}$；

②输出$|\lfloor x/2^{i-1}\rceil|$. 注意此处如果$\left| x \right| < {2^{i - 2}} \leqslant q/4$则返回0，如果$\left| x \right| > {2^{i - 2}}$则返回1.

5）同态加法运算. $G.Add\left( {{{\boldsymbol{C}}_1},{{\boldsymbol{C}}_2}} \right)$:

6）同态乘法运算. $G.Mult\left( {{{\boldsymbol{C}}_1},{{\boldsymbol{C}}_2}} \right)$：

计算${{\boldsymbol{G}}^{ - 1}}\left( {{{\boldsymbol{C}}_2}} \right) \in {\left\{ {0,1} \right\}^{M \times M}}$，并输出${{\boldsymbol{C}}_1}{{\boldsymbol{G}}^{ - 1}}\left( {{{\boldsymbol{C}}_2}} \right)$. 注意此处有

2014年，DM14^[62]（即FHEW方案）将AP14^[60]提出的自举方法有效实例化，自举时间降到1 s以下^[63]. 2016年，GINX16^[64]提出内存需求更小的自举方法，随后基于环面（torus）的变体方案CGGI16^[65-67]（即TFHE方案）将自举方法实例化，自举时间更是降到0.1 s以下，将第3代FHE方案研究推进高潮. 自此，AP自举^[60]和GINX^[64]自举成为第3代FHE方案的主流自举方法，前者支持任意密钥分发，后者只需要更小的同态计算密钥. MP21^[68]对这2种方法进行了详细的比较，指出当LWE密钥服从高斯（或均匀）分布时，AP方法更快，而GINX方法在二元LWE密钥的情形下领先. 随后，KDE21^[69]和BIP22^[70]通过降低一半的计算量，对GINX进行了改进，但只针对三元密钥，无法扩展至更大的密钥，其中KDE21证明了此前只适用第3代FHE方案的盲旋转（rotation）技术，也可用于第2代的BGV，BFV等方案. JP22^[71]提出了一个GINX变种，它是MP21^[68]和KDE21^[69]中自举方法的推广，而且仍对二元和三元密钥最有效. 在CRYPTO2023，XZD23^[72]从NTRU假设出发，基于类GSW方案提出一个新的盲旋转算法，进而构造出一个性能更优（耗时112 ms），且同态计算密钥更小的自举算法. 在EUROCRYPT2023，YDA23^[73]针对类FHEW方案提出的新自举方法兼具AP和GINX这2种主流自举方法的优点，在运行时间和密钥大小方面较已知类FHEW自举方法效果更佳（PALISADE/OpenFHE实现），且噪声增长更小.

第3代FHE方案延续了第2代FHE方案基于(R)LWE的安全性假设，但较第2代FHE方案有3点改进：1）同态运算更加高效（为矩阵的加、乘运算），且不会引起密文维度的膨胀，无需借助其他技术来控制密文维度的增长；2）密文噪声的控制更加简洁、有效，无需借助模交换技术实现；3）摆脱了对计算公钥的依赖，且自举性能总体上较第2代FHE方案更加简洁且有极大提升. 但第3代FHE方案的局限性在于：1）不支持SIMD同态操作；2）自举实现依赖的安全假设强度较第2代有所弱化，但困难问题的近似因子仅为维度$n$的多项式^[56]；3）和第2代FHE方案一样，若要实现全同态仍依赖自举技术.

3.5   支持浮点数运算的第4代FHE方案

现实中大多运算涉及实数或复数（计算机中用浮点数表示），其运算结果往往只需保留一部分有效数字来满足精度要求即可，前3代FHE方案建立在离散空间的精确算术运算上，在处理浮点数运算及带有舍入的运算时并不适用. 第4代FHE方案的主要特点即支持浮点数同态运算. 2017年，Cheon等人^[74]在ASIACRYPT2017上提出能处理浮点数的FHE方案（即CKKS方案），此方案加密时对明文进行舍入，解密时输出满足精度要求的近似值，即解密结果无需和明文完全一致；在乘法同态运算时，通过重缩放（rescaling）技术，在保证计算精度的同时将密文模数增长从指数增长变为线性增长；并通过使用批处理技术提高方案计算效率. 但该方案为SHE方案，于是Cheon等人^[75]在EUROCRYPT2018基于Gentry09^[1]的自举技术提出一种新的刷新密文的技术，将上述的SHE方案扩展为FHE方案. 该技术用正弦函数作为模约减运算的近似，并提出一个有效的同态计算策略使得每一次迭代只需1次乘法运算，因此计算开销随解密电路的深度增大呈线性增长，并以SIMD的方式实现了对封装密文的并行计算. 同年，基于CKKS方案^[74]的Full-RNS变体（简称RNS-CKKS）^[76]被提出，但其采用的是文献[75]中的自举方法，自举精度远达不到实际需求. 2019年，Chen等人^[77]又将方案每个明文槽的均摊（amortized）自举时间提升了2个数量级（从1 s降到0.01 s）. 2020年，Han等人^[78]基于文献[77]中改进的自举方法对RNS-CKKS方案的自举进行了改进，通过减少密钥切换过程中临时模的数量，实现了同等安全级别且不借助自举技术的情况下支持更深电路的同态计算；同时提出一种新的多项式逼近方法求解加密状态下的正弦函数以实现CKKS的自举程序；并基于SHE实现了Full-RNS变体的自举FINAL程序. KPP20^[79]提出更低误差的RNS-CKKS方案，消除了加密和密钥切换操作中由于噪声引起的近似误差. 在EUROCRYPT2021，LLLK21^[80]以及在文献[78]的基础上利用最优极小极大多项式逼近和反正弦函数实现了RNS-CKKS自举精度的提升；BMPH21^[81]则提出一个新自举方法，针对出现的稀疏R-LWE密钥攻击问题，提出一种不需要稀疏密钥的RNS-CKKS自举方法，该方法的效率、准确度更优. 同时，BD21^[82]针对CKKS发起密钥恢复攻击，指出CKKS不能充分捕获被动攻击，攻击者可通过对解密消息进行噪声分析从而泄露密钥信息，因此需要并提出一个比传统IND-CPA安全性更强的模型（IND-CPA^D），同时指出CKKS不满足IND-CPA^D安全. 随后KDE21^[69]通过引入小的重缩放误差而非CKKS自举过程引入的近似误差，针对上述被动攻击提出一个性能更优更安全的自举算法. 在ASIACRYPT2021，Cho等人^[83]提出一种支持近似计算的密文转换框架（即RtF框架），在服务器端将对称密文转换为基于CKKS的同态密文，减少了客户端的计算和通信负载（在客户端实现了1.6 µs的延迟和21.7 MBps的吞吐量，分别比CKKS提升9085倍和17.8倍）且有着更小的密文膨胀率（1.23~1.54，至少降为CKKS的1/23）. 次年EUROCRYPT2022，Ha等人^[84]提出一种新的密文转换框架Rubato，该框架将噪声引入到对称密码中，显著降低了乘法同态运算的复杂度，同等对比RtF框架，客户端和服务器端吞吐量分别提高了22.9%和32.2%，但增加了约1.6%的密文膨胀率；JM22^[85]通过对模函数进行一种新的低误差正弦级数逼近以实现高精度的自举程序，并提出用泰勒级数逼近该正弦函数从而逼近模函数，即可实现基于CKKS任意精度的自举；LLK22^[86]提出通过将误差方差最小化实现SHE的高精度自举方法. CRYPTO2022，BDM22^[87]在BD21^[82]研究的基础上，提出利用差分隐私保护机制对任意支持浮点运算的FHE方案实现IND-CPA^D安全，并基于CKKS方案进行了实现.

事实上，CKKS的构造基于第2代的BGV^[6]方案，其本质的不同在于是否支持浮点数运算，所以也有研究者认为CKKS属于第2代FHE方案. 第4代FHE方案由于对准确性允许一定误差，使得CKKS比其他基于(R)LWE的FHE方案，构造更加简单且性能也有很大提升. 近期的研究大多基于CKKS进行优化，尤其是在自举程序的性能和精确度方面，以及降低计算和通信开销方面. 目前，最新的自举性能表现为每比特微秒级，较第1代FHE方案的每比特千秒级性能提升了9个数量级.

3.6   其他FHE方案

1）基于整数的FHE方案

基于格的FHE方案理论性较强且不易被理解，因此基于简单代数结构上的FHE研究似乎是必然的. 2010年，即首个FHE方案提出后的第2年，基于整数的FHE方案^[88]（即DGHV方案）被提出，用整数模运算代替了格上复杂的矩阵和向量运算，该方案完全遵循Gentry09^[1]构造思路，其SHE阶段的构造依赖于AGCD困难假设，及时证明了复杂的FHE方案也可以基于简单的代数结构构造. 随后基于整数的DHE方案大多基于DGHV构造. 2011年，CMNT11^[89]通过利用二次型加密（quadratic encryption）代替线性加密对DGHV进行了优化，其主要贡献在于将公钥尺寸由$\tilde {\mathcal{O}}\left( {{\lambda ^{10}}} \right)$降低至$\tilde {\mathcal{O}}\left( {{\lambda ^7}} \right)$. 2012年，CNT12^[90]在CMNT11的基础上进一步优化二次型加密技术，将公钥尺寸由$\tilde {\mathcal{O}}\left( {{\lambda ^7}} \right)$降低至$\tilde {\mathcal{O}}\left( {{\lambda ^5}} \right)$^[91]，且对BGV^[6]中的模交换技术进行调整使其能应用于DGHV，使得基于整数的SHE构造也可不依赖自举过程. 随后，YXW12^[92]又将公钥尺寸由$\tilde {\mathcal{O}}\left( {{\lambda ^5}} \right)$优化至$\tilde {\mathcal{O}}\left( {{\lambda ^3}} \right)$. 2013年，CCK13^[93]采用GHS12^[38]中的批处理技术提出整数域上支持批处理的方案，使得$l = \tilde {\mathcal{O}}\left( {{\lambda ^3}} \right)$个明文比特消息可以封装单个密文中进行处理，从而提升计算效率. 2014年，CLT14^[94]基于Bra12^[7]构造了整数上的标度不变FHE方案. 2015年，CS15^[95]同样基于AGCD提出了一种安全性不再依赖SSSP假设的方案，该方案性能优于此前所有的基于AGCD的FHE方案. 同年，NK15^[96]将方案的明文空间从比特空间扩展至${Z_q}$（其中$q$为任意素数），同时降低了明文空间为比特空间时同态乘的算法复杂度，且该方案可扩展为支持批处理的方案. 2016年，熊婉君等人^[97]在DGHV方案基础上，利用Gentry09的FHE构造基本思路，提出一个公钥更短、效率更高的FHE方案，该方案将明文空间由$\left\{ {0,1} \right\}$扩展到${\left\{ {0,1} \right\}^l}$，但仍依赖SSSP假设. 2018年，王彩芬等人^[98]将方案的参与者由“1对1”推广至“多对1”，即“多方加密，1方解密”，与已有方案相比扩展了数据传输量且提高了效率. CHK19^[99]将自举过程中同态乘的执行次数从$O\left( {{\lambda ^4}} \right)$减少至$O\left(\mathrm{l\mathrm{og}}^2\lambda\right)$，使自举过程执行效率更高. 此外，还有一些其他的基于整数的FHE方案，如文献[100–104].

2）基于NTRU的FHE方案

由于NTRU加密算法密钥生成较容易，加密、解密的速度比RSA，ECC等著名算法快很多，且安全性依赖于格中SVP的困难性，因此，也被用来构造FHE方案（以下称为NTRU-FHE），但在安全性方面颇有争议. 2012年，LTV12^[105]构建NTRU-FHE方案，由于NTRU加密体制本身的安全性可证明要求参数的选择符合一定分布条件以实现公钥统计意义上的均匀性^[106]，而该NTRU-FHE方案要实现同态运算且安全性可证明，需要引入一个非标准的安全性假设，即决策小多项式比（decisional small polynomial ratio，DSPR）假设. 随后，YASHE方案^[107]基于Bra12^[7]的构造思想，消除了LTV12中的DSPR假设，构造了一个标度不变、无需模交换操作的变体方案. 文献[108–109]对LTV12进行了优化实现. 然而，文献[110–111]实现了针对LTV12^[105]和YASHE^[107]的密钥恢复攻击；ABD16^[112]实现了对LTV12和YASHE的子域格攻击（subfield lattice attacks）. 随后，KF17^[113]指出子域格攻击是基于NTRU格内密集子格（sublattice）的存在而实现的，即这类攻击基于NTRU格自身的结构，不能通过将代数结构切换到另一个多项式环来解决，且难以评估这类攻击对NTRU安全性的影响，因此，很难对基于NTRU的FHE方案的安全级别进行正确估计. 因此在ASIACRYPT2019，GGH19^[114]针对自动机提出将多项式环切换为一个矩阵形式的环，这个基于矩阵NTRU假设的FHE方案很快就在IACR2020被指出容易受到子格攻击^[115]. 2020年，车小亮等^[116]提出一种可更好抵御子域格攻击、效率更优的NTRU-FHE方案，并将现有方案底层2的幂次分圆多项式环扩展应用到素数次分圆多项式环上. 文献[105–116]方案均需要依赖一个过度延伸（overstretched）的NTRU参数，因此易受子域格攻击，在ASIACRYPT2021，DW21^[117]针对过度延伸的NTRU假设，较KF17^[113]进行了更详细的分析，在ASIACRYPT2022，在FINAL22^[118]基于DW21^[117]的分析，构建了2个NTRU参数落在过度延伸范围外的FHE方案，第1个方案完全基于NTRU，与包括TFHE^[64]在内的FHE方案相比性能相当；第2种方案基于NTRU和LWE假设，比TFHE^[64]的自举速度快28%. 虽然FINAL22^[118]对是否可基于NTRU构造安全、高效的FHE方案给出了较为正向的回应，但“过度延伸”的NTRU假设仍需进一步深入分析直至被充分研究.

3.7   主流FHE方案对比分析

该节主要从安全性（含依赖的数学困难问题）和性能等方面对当前主流FHE方案进行对比分析，如表2所示. 其中性能部分选取了FHE方案中计算复杂度最高的自举过程，并分别选取自举运行时间和每比特的均摊耗时，即自举运行时间/（明文槽数量×剩余可用层级数），为统一度量. 而第2代和第4代由于自举过程中明文槽数量和剩余可用层级数不一定相同，所以每次自举耗时（即倒数第2列）并不能真正衡量其性能优劣，相对而言以每比特的均摊耗时（即最后1列）作为衡量更为合理. 表2中所列实验数据基于当前公开文献整理，其中第4代的数据均是基于CKKS方案的实验数据.

表  2  主流FHE方案对比分析

Table  2.  Comparative Analysis of Main FHE Schemes

阶段	FHE方案	安全性	依赖困难问题	自举性能
				单次自举耗时/s	均摊耗时/(ms/bit)
第1代	Gentry09[1]	不可证明	CVP问题和SSSP问题	1800	/
第2代	BGV12[6,119]	CPA	R-LWE问题	11	0.9
	GIK23[53]	CPA	R-LWE问题	70	1.1
第3代	FHEW14[62]	CPA	R-LWE问题	<1	/
	TFHE16[67]	CPA	R-LWE问题	<0.1	/
	XZD23[72]	CPA	R-LWE问题	0.112	/
	YDA23[71]	CPA	R-LWE问题	0.08	/
第4代	CCS19 [77,120]	CPA	R-LWE问题	78.7	0.95
	HK20[121]	CPA	R-LWE问题	52.8	0.46
	JKA21 [122]	CPA	R-LWE问题	135.4	0.11(1-CPU)
				0.527	423×10−6(1-GPU)
注：/表示不支持SIMD.

下载: 导出CSV 

| 显示表格

当前，在安全性方面，大多数FHE方案依赖于格上的困难问题，由于FHE具备密文同态运算的属性，同态特性意味着延展性（malleability），因此FHE体制不可能抵抗适应性选择密文攻击，即不可能达到IND-CCA2安全^[46]. 目前大多数FHE方案只给出了抵抗适应性选择明文攻击的证明，即达到IND-CPA安全. 在性能方面，较第1代FHE方案已有质的提升，尤其是基于GPU的实现，但相较于明文运算，基于FHE的密文运算在大规模推广应用过程中性能还需进一步提升.

4.   全同态加密应用进展

4.1   算法库实现

从第2代FHE方案开始，即有了相应的算法实现库，主流算法库及其支持的FHE方案如表3所示.

表  3  主流FHE算法库及其支持的FHE方案

Table  3.  Main FHE Algorithm Libraries and Their Supported Schemes of FHE

算法库	方案
	BGV	BFV	FHEW	TFHE	CKKS
TFHE[123]		√	√	√	√
FHEW[124]			√
HElib[125]	√				√
SEAL[126]	√	√			√
cuFHE[127]				√
HEAAN[128]					√
Lattigo[129]	√	√			√
PALISADE[130]	√	√	√	√	√
Concrete[131]				√
Pyfhel[132]	√	√			√
OpenFHE[133]	√	√	√	√	√
HEhub[134]	√			√	√

下载: 导出CSV 

| 显示表格

表3中，cuFHE库支持GPU加速，可比使用CPU（实现TFHE）快20多倍；Concrete库是实现了TFHE方案^[64]的一个变体方案（增强版），而TFHE库是对TFHE原始方案的实现；Pyfhel是一个Python版本的同态算法库，其基于SEAL/PALISADE/HElib等C++库开发，当前版本只支持SEAL库；PALISADE由美国防部高级研究计划局（DARPA）资助建立，由政府注册的非盈利组织NumFOCUS于2019年开始赞助，后逐步迁移至OpenFHE开源项目. OpenFHE提供更简单的API、模块化实现、跨平台支持和硬件加速器集成，整合了多个现有FHE算法库的设计理念，同时不断引入新的设计思想，由来自PALISADE，HElib，HEAAN，FHEW库的作者设计，目前已支持所有主流的FHE方案，包括BGV^[6]，BFV^[47]，CKKS^[74]，FHEW^[62]，TFHE^[64]方案，且支持多种自举程序设计；OpenFHE项目得到了DARPA的支持，由NumFOCUS直接赞助，且定期举办关于FHE和OpenFHE的网络研讨会. Google公司更是开源了首个通用FHE的转译器（transpiler），可以将普通的C++程序转译为基于TFHE同态库的同态程序，将明文运算转换为了同态密文运算.

此外，还有诸如基于GPGPU实现YASHE^[107]方案的cuYASHE、基于FINAL22^[118]实现的FINAL库、基于大整数实现的libScarab、基于GPU实现TFHE的NuFHE，以及提供FHE算法分布式数据流的Spark-FHE等开源实践.

现有FHE算法库大多基于C++，可在Linux，MacOS或Windows操作系统环境执行；大多支持第4代的CKKS（及其变体）方案；且基本由欧美国家主导实现，如表4所示.

表  4  各FHE算法库其他信息对照表

Table  4.  Comparison Table of Other Information of Each FHE Algorithm Library

算法库	开发语言	OS环境	发布年份	开发者/组织
TFHE	C++，C	Linux， MacOS	2016	Nicolas，Gama
FHEW	C++	Linux， MacOS， Windows	2017	Leo，Ducas等
HElib	C++	Ubuntu， MacOS	2018	IBM
SEAL	C++	Linux， MacOS， Windows， FreeBSD， Android	2018	微软
cuFHE	Cuda， C++， python	Ubuntu， MacOS， Windows	2018	Gizemscetin等
HEAAN	C++	Ubuntu	2018	三星
Lattigo	Go	Linux， FreeBSD， MacOS， Windows	2019	EPFL实验室
PALISADE	C++	Ubuntu， CentOS， Windows	2019	Duality
Concrete	Rust	Linux， MacOS， WSL	2020	Zama
Pyfhel	Python， Cython	Linux， WSL	2021	Ibarrondo等
OpenFHE	C++	Linux， MacOS， Windows	2022	Duality主导
HEhub	C++	Linux， MacOS	2022	原语科技

下载: 导出CSV 

| 显示表格

4.2   标准化进展

2017年7月，首个专注于FHE标准化的自发性组织——同态加密标准化开放联盟 ¹成立，该组织由来自企业、学术界和政界的相关领域研究人员共同发起. 目前，该联盟已举办5届FHE标准化会议，参与成员包括微软、三星SDS、英特尔、Duality、IBM、谷歌、万事达卡、阿里巴巴集团等企业，以及NIST，ITU等机构的代表和波士顿大学、麻省理工学院等各大高校的学者. 其中，首届FHE标准化研讨会于联盟成立之初在微软研究院举办，开启了FHE标准草案的编写工作，并发布了全同态加密安全标准、API标准、应用标准3份白皮书，这3份白皮书也是后来发布的FHE标准草案的主要参考依据.

FHE标准草案于2018年3月发布，并于11月更新，目前最新版本为1.1，即11月的更新版本. 草案的内容主要包括同态加密方案的标准化和安全参数2个部分：第1部分主要对BGV^[6]，BFV^[47]和GSW^[57]推荐的3个FHE方案进行了规范描述，其中还描述了一些基本功能函数（如参数生成、公私密钥及计算密钥生成、加密、解密、同态加、同态乘、密文刷新、有效性校验等）的定义，以及语义安全（IND-CPA）、紧致性、有效解密等算法性质，并对分布式加密、主动攻击、同态计算隐私、密钥演化、侧信道攻击、基于身份的加密也有一定的讨论；第2部分主要针对LWE和R-LWE困难问题给出安全参数建议，其中还分析了针对这2个困难问题的多种攻击算法，包括著名的BKZ算法^[135].

4.3   典型应用场景

1） 技术赋能应用

① FHE在云计算中的应用. 在云服务模式下，加密数据很难甚至无法被云应用或程序处理，所以目前大多数据并未加密存储，其安全性和隐私问题面临巨大挑战. FHE技术可在不泄露敏感信息的前提下完成对云端密态数据的处理，如私有信息检索、隐私保护数据挖据、加密数据检索等，而云服务商等不受信任的一方则无法获得明文或用户隐私信息，即云计算的对象及结果全程加密，即便IT基础设施遭遇攻击，也可在不依赖外围防御的情况下保障数据不被泄露. 2020年DARPA启动基于FHE硬件加速的“虚拟环境数据保护（data protection in virtual environments）”计划DPRIVE，英特尔公司、微软公司等参与其中；12月，IBM Security宣布推出一项基于FHE的云计算新服务，为用户设计、提供基于FHE的云计算安全解决方案. 此外，亚马逊AWS云服务利用FHE对DynamoDB中存储的数据进行密态处理.

② FHE在大数据中的应用. 在数据要素市场化配置趋势下，多来源数据的计算场景增多，如何在保证数据机密性的基础上实现数据的流通共享和合作开发利用，成为大数据应用面临的基本挑战. 此外，大数据中的计算形式复杂、多样，特定计算场景下的隐私保护算法通常不能满足各类大数据应用需求，因此需要一个较为通用的方案从本质上解决大数据应用隐私保护的问题. FHE的出现为解决以上需求提供了有效思路，如加密数据在进行多方安全计算时，需要在聚合节点先解密，计算完成后再加密传输，实现了数据传输的安全，但是不能保证数据计算的安全. 引入FHE后，可实现明文数据及其衍生计算结果全程以密态形式呈现，同时又能得到大数据分析得来的有价值的结果.

③ FHE在人工智能中的应用. 人工智能以数据为“燃料”，如何实现在保护数据安全和隐私的基础上，尽可能释放人工智能所有功能是很有价值的问题. 如不同行业、部门甚至组织内部不同业务线之间往往因数据安全或隐私顾虑形成数据壁垒，所以只能依赖有限数量或者较单一的数据进行独立训练，导致无法建模或模型无法趋于全局最优. 而FHE的引入可以缓解这种尴尬，如在多方参与的机器学习中，支持对多来源的基础数据和模型加密后，一直以密文形态参与学习或其他处理，且处理结果仍然保密，由此实现基于FHE的隐私保护机器学习. 英特尔公司是这方面的主要实践者之一，并与微软公司合作于2018年12月发布基于SEAL算法库的开源版同态加密转换器（HE-transformer），支持人工智能系统对敏感数据进行操作，可应用于如谷歌公司TensorFlow，Facebook PyTorch等开源框架上的神经网络实现，也是英特尔神经网络编译器nGraph的同态加密后端.

④ FHE在区块链中的应用. 由于调用智能合约时使用的参数全集需明文公开，否则其他节点无法验证合约执行结果是否正确，如此不能保证合约调用者合约信息的隐私性，而许多智能合约的应用场景都有隐私保护的需求，如电子竞选/选举投票、多方参与的竞拍竞价、医疗健康合约等，信息持有者通过调用智能合约提供相关信息时会有顾虑. 引入FHE后，可在数据上链前调用FHE算法库，将数据加密后再上链，链上的密文数据也可通过调用FHE算法库实现支撑同态运算的智能合约，合约执行结果仍是密文，返至业务层后再通过FHE算法库进行解密^[56].

2） 行业场景应用

①金融-信贷风控. 信贷风控可能需要来自央行征信数据、信用卡数据、人社部参保数据、教育部学籍数据、房管局房屋不动产信息以及法院黑名单信息等外部数据进行综合评估，而外部合作方和信贷风控方因数据合规要求或其他安全考虑，一般不会把自己掌握的数据传送给对方. 传统的处理方式即合作方独立建模，并将建模结果进行融合，此方式虽然保护了隐私，但建模效果较差可能导致评估并不准确，FHE的引入或可促进合作方之间的数据共享流通. 此外，还可采用纵向联邦学习进行共同建模从而实现更精准的风控，但要实现联邦学习过程中中间结果或参数的安全传输和计算，可引入FHE保障联邦学习过程的数据隐私性，从而保障信贷风控中多个参与方的数据安全.

② 互联网-私有信息处理. 首先是私有信息检索（PIR），当进行一些敏感信息检索时，若不想让服务器知道自己想从数据库中检索什么信息，可借助FHE实现私有信息检索，即存储和查询都使用加密数据，检索结果也是加密的，由服务器返回用户后用户解密获得检索结果；其次是隐私集合求交（PSI），多个参与方各自持有私有数据，可通过FHE实现多个参与方数据求交，而不泄露交集外的其他任何信息，已在纵向联邦学习、好友发现、计算广告投放实际效果等方面有实际应用. 此外，人脸、指纹、视网膜等个人生物特征数据等具有唯一性且不可再生的个人数据，在互联网中常被用于身份识别和认证，一旦泄露无法追回并变更，将会带来不可逆的隐私保护问题，可借助FHE实现加密存储和密态处理，在不泄露隐私的情况下依然可以进行生物特征识别与认证.

③医疗-基因数据分析. 大多国家或地区对基因数据共享有着较为严格的管控，而在进行生物学、复杂疾病、流行病学等方面的研究时往往需要大规模的基因数据样本，而FHE支持对密态基因数据进行有意义的操作，一方面可以促进基因数据的开放共享，另一方面可用于实现不同参与方之间的联邦学习、多方安全计算等，促进基因组学领域的合作与研究突破. 2014年美国国立卫生研究院布局基因组学领域的数据隐私计算，并发起世界顶级隐私计算赛事iDASH，每年均有FHE相关基因数据安全分析赛题.

④能源-电网数据分析. 电网数据被篡改可能导致电网控制和配电失灵，造成大规模停电事件. 专门的监控机构将监控智能电网中每个节点产生的数据，且可能会将监控和计算工作外包给云平台，但前提是进行电网数据监控和计算的云平台本身应是安全、可信的. 为对电网数据实现基于云平台的安全监控和计算，可利用FHE将智能电网中每个节点的测量值加密后发至云平台，云平台直接对密文数据进行处理而无需提前解密，处理结果以密文形式发送至电网决策中心（解密后）进行分析决策，攻击者即便窃取了数据也无法知道内容是什么，即便对数据进行篡改、伪造等操作也可被检测发现.

⑤政府-电子选举. 基于FHE设计的电子选举方案允许计票方在不掌握投票者投票内容的前提下对投票结果进行统计，也允许参与投票的公民确认他们的投票已被计数且未被更改，既保护了投票者的隐私，又保证了投票结果的公正. 2019年，微软公司于Build开发者大会上发布了一款基于同态加密的开源电子投票开发包Electionguard ²，支持对选举过程进行端到端验证，投票结果可在网上公布，也支持第三方机构进行验证，并允许选民确认他们的选票被正确计算. 此外，FHE也可应用于政务数据的开放共享，以支持政务数据参与要素化配置，释放价值潜能.

当然，FHE在这些行业领域还有其他应用，如金融行业基于客户多维信息的精准营销，医疗行业基于个人医疗及相关数据的个性化治疗等，此外在教育、工业、电信等行业领域也有应用场景. 无需回避的是，FHE在应用推广中还面临一些问题，如虽然FHE发展迅速，但性能问题暂时依然是影响其大规模推广应用的主要因素；部分应用场景可能只涉及简单的数据操作，此时或许半同态（加同态或乘同态）是一种更好的选择，前提是需要事先了解涉及哪些类型的计算.

5.   总　　结

综上所述，针对FHE的研究发展迅速，效率方面有了质的突破，在各行业领域的应用也在逐步拓展. 首先介绍相关概念定义，并从自举、同态解密切入阐述FHE方案的一般构造思想. 其次分析讨论不同阶段FHE的研究进展及局限性. 最后从算法库实践、标准化进展、典型应用等方面介绍FHE的应用进展. 随着数据安全和隐私保护需求的多样化、专业化，对相关技术各方面的能力也提出了更高要求，结合FHE方案的研究进展，建议未来相关的主要研究方向关注4个方面：

1） 自举程序性能进一步优化

自举技术是当前将SHE方案转变为FHE方案的关键技术，也是唯一途径. 但由于过程中频繁调用同态解密，其成为制约现有FHE方案性能的主要因素之一，虽然经过10余年的发展，自举程序的执行效率较首次提出已有质的提升，但在市场推广应用过程中，性能问题往往是用户选择其他替代方案的主要原因. 当然，FHE的性能还有其他影响因素，如是否可以进一步减缓密文噪声膨胀的速度以实现更低频度的自举程序调用，以及每次自举程序调用可以“支撑”更深电路的同态运算；是否支持多比特处理以及利用FHE专用硬件加速等.

2） FHE自身安全性可证明

现代密码学以可证明安全为基石，由于FHE具备密文同态运算的属性，同态特性意味着延展性（malleability），因此FHE体制不可能达到IND-CCA2安全. 目前，大多FHE方案只能给出IND-CPA级别的安全性证明，能证明达到IND-CCA1级别的FHE方案少见^[46]. 此外，在FHE方案发展的过程中，也出现了针对现有方案的攻击，如密钥恢复攻击、侧信道攻击. 尤其是基于NTRU的FHE，在实现全同态的过程中，其“过度延伸”的安全假设还需进一步深入分析.

3）FHE方案间互相切换支持

如用户当前使用第3代FHE方案逐比特处理数据，由于需求变化需要采用支持浮点数运算的第4代FHE方案，如何透明、安全、高效地实现2个方案间的切换是个值得深入研究的问题. 事实上，不只在不同应用阶段、不同应用场景，应用方都可能会部署应用不同的FHE方案，可能会面临频繁的不同方案下的密文间互操作，可以探索研究支持不同方案间的互切换的方法，即支持在密文上使用同态解密函数，将某个方案的密文转换为另一个方案的密文，从而实现2个方案间的切换.

4）全新的FHE构造思路

距首个FHE方案提出仅有10余年，因此FHE研究大有可为，可以跳出现有构造思想，基于不同的困难问题假设、代数结构、数学性质等提出全新的构造思路，虽然难度非同一般.

作者贡献声明：白利芳提出了论文整体架构和思路，并负责主要研究内容的撰写和修订；祝跃飞审阅论文的整体架构和思路，并提出指导意见；李勇军负责论文部分内容的撰写和修订；王帅负责论文图表、文献的整理，以及论文整体的检查和修订；杨晓琪负责论文部分内容的撰写和修订.