---

一、FHE的定义与性质

1、核心算法

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

2、性质

1. 正确性：
    若对 ∀ m 1 , m 2 , . . . , m t ∈ { 0 , 1 } ，及 ∀ C ∈ C ，有 D e c ( s k , c ∗ ) = C ( m 1 , m 2 , . . . , m t ) \forall m_1,m_2,...,m_t \in \{0,1\}，及 \forall C \in C，有Dec(sk,c^*)=C(m_1,m_2,...,m_t) ∀m1​,m2​,...,mt​∈{0,1}，及∀C∈C，有Dec(sk,c∗)=C(m1​,m2​,...,mt​)，则称该加密方案 关于同态电路族 C 中的 任意运算函数 C 是正确的. 可用 交换图 表述如 图3 所示。
2. 紧凑性：
    对于任意的 安全参数 λ，若存在一个 多项式 P，使得同态加密方案的解密算法能够用一个 规模至多为 P(λ) 的 电路 D 来表示，那么称该同态加密方案是紧凑的。即满足紧凑性意味着该方案的 解密电路 独立于 t 和 C。
3. 安全性：
    同态加密的安全性通过 语义安全 来定义。用基于游戏的范式可表述为：若对任意多项式时间敌手 A，式 (1) 在 λ 上可忽略，称该加密方案是不可区分选择明文攻击安全的 (IND-CPA安全)。

---

二、构造思想

 全同态加密方案的构造重点在于实现 密文域 上 任意次数的 加法和乘法同态运算。一般构造的初始方案均为 SHE 方案，因在 加密和密文运算过程中 会引入 “噪声” 用于掩饰明文信息，随着 密文同态运算次数越多 噪声值越大，当 噪声达到某一“临界” 就会 解密失败，因此能支持的同态运算次数有限。如何将 SHE方案 转化为 FHE方案 是为关键，目前大多借助 自举技术 来实现。
 自举技术 本质上是通过 同态解密运算，即执行 参数电路C = 解密电路D (函数 Dec 的电路表现形式) 的函数 Eval，将密文刷新为一个 噪声值更低 的“新鲜”密文，如此不会因为噪声干扰导致解密失败，即可继续进行同态运算，从而实现不限次同态运算，示意图如图 4 所示。
 同态加密过程中 私钥被加密后 作为 公共参数 予以公开，并作为 函数 Eval 的 输入，因此被称为 计算公钥；另外出现了 明文 被 双重加密 的状态，其中 第1次加密 (看作***“内层加密”) 的结果是 第2次加密 (看作“外层加密”***) 的 明文输入。同态解密的 过程可看作 是在 双重加密 状态下解了 内层加密保留外层加密 的过程，如图 5 所示 (基于上述例子)。

---

三、全同态加密研究进展

 现有 主流 FHE 方案 的 困难假设 主要基于 2 种困难问题：一种是 基于格困难问题，另一种是 整数上基于近似最大公约数 (approximate greatest common divisor, AGCD) 困难问题。其中 基于格困难问题的 FHE 方案 发展迅速，目前已发展至 第4代，尤其以 基于 ® LWE 问题假设的方案 发展最为迅速 (如第2，3，4代)，另外，还有一个 基于 NTRU 的研究分支。

 本节首先介绍 Gentry09 提出前 仅支撑部分同态运算 的典型加密方案，再对 基于格困难问题的 4代 典型 FHE 方案 进行研究分析，最后对 基于整数、NTRU 的 FHE 方案 进行简要分析. 经典 FHE方案的分类及继承关系如 图6 所示，其中 虚线框内的方案基于格困难问题。

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

 由于对密文同态运算的支持能力不足 (详见表1) 或安全性的问题，Pre-FHE 方案均未实现对密文数据进行 任意多项式函数的同态运算，其中不乏中有 基于格的不完全同态加密方案。尤其是首个 FHE方案 提出前的近几年，但多为加法同态加密方案。

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

 第1代 FHE方案 的 局限性 在于：

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

3、基于LWE的 第2代 FHE方案

 第2代 FHE方案 的构造仍需 先获得一个SHE方案，而后通过 自举技术 实现 完全同态，但构造过程较 第1代 FHE方案 主要有 4点改进：

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

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

 第3代 FHE方案 延续了 第2代 FHE方案 基于 (R)LWE 的 安全性假设，但较 第2代FHE方案 有3点 改进：

1. 同态运算更加高效 (为矩阵的加、乘运算)，且不会引起密文维度的膨胀，无需借助其他技术来 控制密文维度的增长；
2. 密文噪声的控制更加简洁、有效，无需借助 模交换技术 实现；
3. 摆脱了对 计算公钥 的依赖，且 自举性能 总体上较 第2代 FHE方案 的构造更加简洁且性能有极大提升。

 但 第3代 FHE方案 局限性 在于：
4. 不支持 SIMD同态操作；
5. 自举实现 依赖的 安全假设 强度较第2代有所 弱化，但 困难问题的 近似因子仅为 维度n 的多项式；
6. 和 第2代 FHE方案 一样，若要实现全同态，仍 依赖自举技术。

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

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

5、其他 FHE方案

5.1、基于整数的 FHE方案

 基于格的 FHE方案 理论性较强不易被理解，因此 基于简单代数结构上的 FHE研究 似乎是必然。2010年，即首个 FHE方案 提出后的 第2年，基于整数的 FHE方案 (即 DGHV方案) 被提出，用 整数模运算 代替了 格上复杂的矩阵和向量运算，该方案完全遵循 Gentry09构造思路，其 SHE阶段 的构造依赖于 AGCD困难假设，及时证明了 复杂的 FHE方案 也可以 基于简单的代数结构 构造。

5.2、基于 NTRU 的 FHE方案

 由于 NTRU 加密算法 密钥生成较容易，加密、解密的速度 比 RSA，ECC等著名算法 快很多，且 安全性 依赖于 格中 SVP 的困难性，因此，也被用来构造 FHE方案 (以下称为 NTRU-FHE)，但在 安全性 方面颇有争议。
 2012年，LTV12 首次构建 NTRU-FHE 方案，由于 NTRU 加密体制 本身的安全性 可证明要求参数的选择符合一定分布条件以实现公钥统计意义上的均匀性，而该 NTRU-FHE方案 要实现同态运算且安全性可证明，需要引入一个非标准的安全性假设，即 决策小多项式比 (decisional small polynomial ratio, DSPR) 假设。

6、主流 FHE方案 对比分析

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

---

四、全同态加密应用进展

1、算法实现库

  从 第2代 FHE方案 开始，即有了相应的 算法实现库，主流算法库及其支持的 FHE方案 如表3所示。
 现有 FHE算法库 大多基于 C++，可在 Linux，MacOS，Windows 操作系统环境执行；大多支持 第4代 的 CKKS (及其变体) 方案；且基本由欧美国家主导实现，如表4所示。

2、典型应用场景

 技术赋能应用