我们前面有谈到《Paillier半同态加密算法》，半同态加密算法除了支持密文加法运算的 Paillier 算法，还有支持密文乘法计算的 RSA 算法，早期的PSI(隐私求交)和PIR(匿踪查询)都有使用基于RSA盲签名技术来实现。今天我们来谈谈能够有效支持任意函数密文计算的全同态加密算法 (fully homomorphic encryption, FHE) 。鉴于全同态加密的强大功能，一经提出便成为密码界的公开问题，被誉为“密码学圣杯”。目前可以构造全同态加密的密码学假设主要有：理想格上的理想陪集问题(Ideal Coset Problem，ICP)、整数上的近似最大公因子问题(Approximate Greatest Common Devisior, AGCD)、带错学习问题(Learning with Errors，LWE)等等。
什么是全同态？
加密能让敏感信息在存储或传输时受到保护。但是标准加密技术要求数据解密才能操作。同态加密背后的想法是不解密并直接计算加密数据。这一名字来自于数学概念同态性（Homomorphism）：一个集合的元素在保持原有元素间关系的情况下转换为另一集合的元素。全同态加密（Fully Homomorphic Encryption，简称FHE）是一种创新的加密技术，它可以实现在不解密的情况下，对加密数据进行任意计算，并得到与明文计算结果相同的加密结果。而我们说的“全”同态，需要它能同时支持密文的加法和乘法，因为所有的程序都能表示为电路的加法和乘法。
全同态加密方案可以解释为这样一种加密方案：给定一些密文，对明文的加法乘法操作都可以通过直接在密文上进行且无需要解密。
记全同态加密方案为，共有4个算法：密钥生成算法KeyGen、加密算法Enc、解密算法Dec、同态运算算法Eval，其主要工作流程为：
(1) 给定安全参数，运行密钥生成算法
，生成公钥
，私钥
，同态计算公钥
。
(2) 给定明文和公钥
，对
，运行加密算法
，生成密文
。
(3) 给定函数和一些密文
，同态计算公钥
，运行同态运算算法
，获得密文
在经过函数同态运算的密文结果
。
(4)用私钥对密文
运行解密算法
，获得相应的明文
。
其中第(3)步的同态运算算法就是同态加密方案的核心，对Eval输入密文可以实现任意函数的计算，更进一步还可以计算解密函数，这也是构造全同态加密方案的重要途径。
一个安全且合理的全同态加密方案具有4个安全性质：正确性，语义安全性，同态性，紧凑性。
全同态发展历史
2009 年Gentry首次给出了全同态加密算法的一个理论可行的蓝图，这是对全同态加密算法探索的第一个重大突破。在 Gentry 工作的基础上，全同态加密研究得到飞速发展，包括更高的计算效率、更一般的困难性假设以及更广泛的应用在内的一系列改进工作纷纷涌现。自 2009 年 Gentry 的突破性工作至今，全同态加密算法根据其构造方法可划分为四代。
第一代以 Gentry 基于理想格的方案以及 van Dijk 等基于整数的方案为代表。Gentry的全同态加密方案，找到了理想格这个既支持同态加法又支持同态乘法的工具，还开创性地提出了自举的思想，使得全同态加密方案可以通过类同态加密方案构造。但这一代算法的通病是错误增长速度过快，对算法的安全性和效率有较大负面影响。
第二代全同态加密算法起源于 2011 年 Brakerski-Vaikuntanathan 以及 Brakerski 等的工作，这一代算法基于格困难问题，使用了比第一代算法更通用的安全假设、更优的错误控制技术、更好的明文编码技术，大幅改进了密文计算效率。它率先提出了密钥切换操作控制密文乘法的维数扩展、模切换操作控制噪声增长速度的想法。在此基础上，后续的同态方案对BV11的效率和噪声控制进行了优化，并设计了适配的自举算法。
第三代全同态加密算法的研究开始于 Gentry 等的工作，由Gentry、Sahai和Waters提出了基于矩阵的近似特征向量技术的同态加密方案，这一代算法使用了与第二代不同的构造模式，在控制错误增长方面具有很好的潜力。它的技术特点是使用了矩阵的密文形式，矩阵密文做乘法避免了向量密文的维数扩张问题，同时将乘法噪声的增长速度由指数级降低到线性级。
第四代全同态加密算法以 CKKS (Cheon-Kim-Kim-Song) 算法为代表，其核心思路是使用近似计算取代原有全同态加密算法中的精确计算，以取得更高的计算效率。它适用于一些不需要精确计算的场景，在自举操作中用多项式函数近似计算替代了精确的比特提取。
下图展示了4类全同态方案诞生的时间顺序，括号内列举了其分支下的重要论文，箭头表示两类方案存在一定的相关性但发表时间有先后：BGV方案继承了Gentry类方案的主要思想，但方案构造的基础假设不同，控制噪声的技术也不同。GSW方案与BGV的基础假设相同，但改变了密文结构；CKKS方案的密文结构、同态操作与BGV基本相同，但消息空间不同、适用运算场景不同。
第一代全同态加密：Gentry 的技术路线
Gentry 开创性的给出了基于理想格设计 FHE 的技术路线，算法的安全性基于理想格上的稀疏子集和问题(sparsesubset sum problem,SSSP)。此后, Gentry 受到了 van Dijk 等工作的启发，在其博士论文中设计了基于整数全同态加密算法的雏形，这一工作在他们随后的论文中得以完善，算法基本原理如下：
令大奇数 表示整数加密方案的私钥，对于明文比特
，其对应的密文
。当随机选取整数
、
满足
时，密文
与私钥
的整数倍
接近。因此，可通过对密文执行模
运算得到
，再对结果模 2 得到
，从而实现解密。
对于上述整数加密方案，可以对两个相同密钥加密的密文执行加法或乘法运算，即有 ，
， 令
, 则
与原密文
结构相似且满足:
其中表示某个整数，
。因此当初始错误
相对于 p足够小时, 则密文加法和乘法的结果
仍可正确地解密。也就是说，该整数加密方案可支持次数较低的多项式密文运算，所得结果解密后与对明文比特执行在
上的多项式运算一致。van Dijk 等证明了该方案的安全性可以归约到近似的最大公约数问题，保证了算法的可证明安全性。
上述算法虽然能在一定程度上实现同态运算，但不满足紧凑性，即密文的大小随着评估函数次数增大。同时，该算法仅支持较低次数的多项式计算，这是由于算法中的错误随着乘法次数快速增长，当错误大于p/2时，算法就无法正确解密。van Dijk 等提出了一种解决紧凑性问题的方法: 首先公开多个不同长度的p的倍数，再使用这些公开参数进行模数转换来控制密文的增长。对于错误增长导致解密错误的问题，则需要使用自举技术 (bootstrapping) 来加以解决。
自举技术
Gentry 在其开创性工作中提出: “对于任意的同态加密算法，若算法支持评估其自身的解密函数电路 (以及一个额外的与非门)，则该算法可以转换为一个全同态加密算法。” 这句话中所提出的 “评估自身的解密函数电路” 指的正是自举技术。因此，自举技术是 Gentry 提出的全同态算法技术路线中的核心，也是当前延续 Gentry 技术路线发展而来的三代全同态加密算法实现全同态计算的关键。具体来说，对于任意的密文考虑以下函数:
函数的输入是私钥，用该私钥解密密文
得到明文
，再输出
的与非结果。如果同态加密的密文计算深度能够支持对任意密文对
执行函数
评估，则该同态加密方案为可自举的方案，能够转化为全同态方案。
第一代全同态加密的特点
第一代全同态加密的主要工作有 Gentry 基于理想格的方案、van Dijk 等基于整数的方案及其变种。这些方案的普遍缺陷是错误增长速度过快限制了同态计算的深度。具体来说，对于初始错误为 的密文，经过次数为 d 的多项式运算后，其结果中蕴含的错误大小约为
。尽管这些算法的解密函数深度较浅，但快速增长的错误依然限制了它们对自身解密函数的评估，由此引起的自举困难降低了第一代全同态加密算法的实用价值。
第二代全同态加密：BV 算法的技术路线
2011 年，Brakerski 与 Vaikuntanathan 给出了基于 LWE 及 RLWE 问题的全同态加密算法的构造方法，标志着第二代全同态加密算法的开端，其基本思想如下:
对于一个 LWE 问题的样本 以及私钥
。令
表示明文，其加密后的密文为:
，其中
表示采样自错误分布
的随机错误。当解密时，通过以下公式完成解密运算:
。容易验证当错误
时，以上加解密流程可以正确得到明文。 若将
记为
，则有
。
对于两个相同密钥加密的明文 ，
，
则有
注意到对于相同密钥加密的明文，其加法同态性是显然的，而它们的乘积可以视为一组以为私钥的 LWE 问题样本，若能够将乘积中
对应的项转换为密钥
的表达式，则可以将密文乘法 的结果转换为 LWE 问题的标准形式，从而进一步执行其他的同态计算，因此，这一转换的过程是第二代全同态加密算法的关键技术，被称为重线性化 (re-linearization technique) 或密钥转换技术 (key switching technique)。
密钥转换和模转换技术
重线性化或密钥转换技术的提出可以解决基于 LWE/RLWE 问题的第二代全同态加密算法在计算密文乘法时，密钥规模以平方的规模快速增大的问题，其核心思想是通过将原密钥中的每一项及由这些项所组成的全部二次项使用新密钥加密，使原密钥加密下的密文乘法的结果可通过新密钥的线性函数表示，此时可将结果转换为以新密钥加密的标准 LWE 问题样本。
此外，Brakerski 还提出了一项显著降低全同态加密错误增长速度的技术，称之为模转换技术 (modulus switching techinque)。其核心思想是对于 上的密文
，通过令
中的各项分别乘以
并取整，可以将密文
转换为
上的密文，此时因同态加密积累的错误总量也同步减少了约
倍。通过精心选取参数
与
的大小，能够将错误的增长速度控制在较小的规模。
第二代全同态加密的特点
第二代全同态加密算法以 2011 年 Brakerski 等 的工作为代表。第二代算法在第一代算法的基础上实现了多个实用性的优化，包括更好的错误增长控制技术、 更标准的困难性假设以及多项效率优化技术。利用错误增长控制技术可使第二代全同态加密算法中错误增长速度从密文计算深度的线性量级降为对数量级，这一技术是 “分层” 同态算法以及全同态算法得以实用化的关键。第二代全同态加密算法使用的标准困难问题假设包括容错学习问题 (learning with errors) 或 NTRU 问题等，这些问题的困难性有着更完备的归约并经历了长时间的考验, 能够为 全同态加密算法奠定更牢固的安全性基础。第二代算法在效率优化方面的改进主要包括明文打包技术 (packing) 以及自举效率优化，这些优化技术大幅改进了全同态加密算法的计算效率，使算法的密文计算效率较明文计算效率在渐进复杂度上仅付出约的额外开销，其中
表示安全强度，
为常数。
第三代全同态加密：GSW 算法的技术路线
第二代全同态加密算法的核心技术是密钥转换和模转换。2013 年Gentry 等给出了一种基于 LWE/RLWE 问题设计全同态加密算法的新思路，在他们的技术路线中，无需使用密钥转换和模转换技术仍可以有效控制同态加密的错误增长，其主要设计思路如下:
对于一个 LWE 问题的样本，令公钥为
，私钥为
。则有
。
令 表示明文，其加密后的密文为
，其中
是
域上的随机矩阵，
表示块对角矩阵。
解密时需要计算，当
且
较小时, 则有
。因此
,即可根据已知的私钥
获得明文。
对于两个相同密钥加密的明文 ,
，容易观察到:
。可知能够满足加法同态性.
而对于密文乘法，则需要定义非对称乘法规则如下: 。
即 所得结果对应于两个明文乘积的密文。
非对称密文乘法
第三代全同态加密算法的核心是非对称乘法，该技术利用了以下原理: 对于任意的整数 ，可将其表示为一组二进制向量
，即
，其中
。同理对于任意向量
,可以将
扩展为块对角矩阵
，满足
，其中
表示
中每个元素的二进制展开，记为
，显然有
。此外，由于
中各元素均取自 {0，1}，可知该矩阵的范数较小，这是确保上述非对称乘法成立的关键。
第三代全同态加密的特点
2013 年Gentry 等给出了一种不同于第二代全同态加密算法的设计思路，其核心思想是采用非对称的乘法降低错误增长速度。具体来说，该方案的同态乘法具有非对称性，即 所得的密文不同于
所得密文。在该同态乘法中，错误的增长速度也与乘法顺序有关，被乘数对错误增长速度的影响较乘数更大。利用这一性质可进一步降低密文乘法的错误增长速度，从而使第三代全同态算法在参数选取和安全性归约上更具优势、算法流程更加简洁。
第四代全同态加密：CKKS 算法的技术路线
第四代全同态算法以 CKKS 算法为代表，其加解密流程与第二代全同态加密算法类似，主要区别在于其采取了近似计算的策略，即所得计算结果附带一定的误差，这一特点虽然降低了算法的计算精度，但大幅提高了算法的运算效率，因此在一些全同态分类中将 CKKS算法及其改进称为第四代全同态加密算法。
该算法的设计思想如下：
对于一个 LWE 问题的样本 ，则公钥为
，私钥为
，评估密钥为
。令
表示明文多项式，其加密后的密文为:
，
其中表示以 0.5 的概率输出 1 或 −1 的随机函数。解密时则需要计算
。
对于两个相同密钥加密的明文， ，
，
容易验证其加法同态性: 。
对于乘法，令 ，其中
，
可以验证
即 。
第四代全同态加密的特点
在经典的同态加密算法中，为获得准确的计算结果，通常有两类明文编码方式, 一种利用密文空间中的高比特位保存明文，另一种利用密文空间中的低比特位保存明文。例如: 明文空间模 t，密文空间模 q，则前者的解密运算可表示为 ，后者的解密运算则可表示为
。为确保解密正确性, 两者均要求错误 e 较小, 这一条件限制了同态加密算法的参数选取与计算深度。而在 CKKS 算法中，解密运算表示为
，此时错误 e 与明文 m 直接求和，无法通过取整计算将错误从结果中消去。但在另一方面，由于放弃计算 m 的精确结果，CKKS 算法仅需考虑 e 与 m 的相对大小 (即相对误差)，因此能够在参数选取和计算过程中采取更直接的方法控制错误的增长速度，如：使用模转换技术同步减小明文和错误，从而令错误大小随算法深度呈线性增长而非指数增长。
小结
当前，BGV (Brakerski-Gentry-Vaikuntanathan)，BFV (Brakerski-Fan-Vercauteren)，TFHE (fully homomorphic encryption over the torus) 和 CKKS 是应用最广泛的全同态算法，涵盖了第二到四代全同态加密构造方案，值得指出的是，全同态加密算法的四代构造并非改进与替代的关系，而是各具特点和适用场景，正因如此，当前学术界呈现出上述四种算法同步发展的现状。总的来说, 第二代和第四代全同态加密算法均可通过高效的明文打包技术实现对多个明文的并行计算，非常适合计算量较大的数值计算，其中第二代适用于需要精确计算的场景而第四代面向近似计算场景；第三代全同态加密算法不支持明文打包，但其设计结构对于逻辑运算友好，能够高效地完成逻辑门形式的密文运算，如下表所示。
全同态常用加密库
Concrete：https://github.com/zama-ai/concrete
使用Rust语言实现了Zama的TFHE变体。Concrete的密码算法基于LWE问题和RLWE问题，研究证明基于这类问题的密码算法是抗量子的。
HElib：https://github.com/HomEnc/HElib
HElib 是一个实现同态加密（HE）的开源代码库。目前实现的方案是包括带有引导的 Brakerski-Gentry-Vaikuntanathan (BGV) 方案和 Cheon-Kim-Kim-Song (CKKS) 的近似数方案的实现，仓库使用了许多优化技术使同态运算更快。
SEAL：https://github.com/microsoft/SEAL
Microsoft SEAL 是一个易于使用的开源（MIT 许可）同态加密库，由 Microsoft 的密码学和隐私研究小组开发。Microsoft SEAL 是用现代标准 C++ 编写的，易于在许多不同的环境中编译和运行。
SEAL-python：https://github.com/Huelse/SEAL-Python/
SEAL-python使用pybind11为SEAL的C++代码提供python接口，方便开发者使用python进行开发。
Palisade: https://gitlab.com/palisade
Palisade是一个开源的同态加密和安全多方计算库，由新墨西哥大学和Sandia国家实验室开发。它支持多种同态加密方案，包括全同态加密、部分同态加密和同态签名等，并提供了C++和Python的API接口。
PALISADE-Python是Palisade同态加密库的Python绑定。它为Python开发者提供了使用Palisade库进行同态加密的能力。
Lattigo：https://github.com/tuneinsight/lattigo
Lattigo实现了基于RLWE的同态加密方案以及基于同态加密的多方安全计算协议。Lattigo使用go语言实现。Lattigo 旨在支持分布式系统和微服务架构中的 HE，选用go是因为其并发模型和可移植性。
HEAAN：https://github.com/snucrypto/HEAAN
HEAAN 是实现支持定点算法的同态加密 (HE) 的软件库。该库支持有理数之间的近似运算。近似误差取决于一些参数，与浮点运算误差几乎相同。
cuFHE：https://github.com/vernamlab/cuFHE
支持GPU加速的全同态加密仓库。它实现了 Chillotti 等人提出的 TFHE 方案 [CGGI16][CGGI17]。使用英伟达泰坦Xp显卡进行实验，比使用CPU进行计算的TFHE方案快20多倍。
cuYASHE：https://github.com/cuyashe-library/cuyashe
cuYASHE 是第一个在 GPGPU 上实现水平全同态方案 YASHE。该库采用 CUDA 平台以及代数技术（如 CRT、FFT 以及多项式和模约简的优化）获得显了著的性能改进。与CPU、GPU 和 FPGA 中最先进的实现方案相比，他有更优异的性能。特别是多项式乘法有 6 到 35 倍的加速。
FINAL：https://github.com/KULeuven-COSIC/FINAL
FINAL实现了论文 "FINAL: Faster FHE instantiated with NTRU and LWE"提出的全同态加密方案。
NuFHE：https://github.com/nucypher/nufhe
NuFHE是基于GPU实现的环上全同态加密方案。该库使用 CUDA 和 OpenCL 实现了 TFHE 的完全同态加密算法。与在内部使用 FFT 来加速多项式乘法的 TFHE 不同，nufhe 可以使用 FFT 或纯整数 NTT（有限域上的类似 DFT 的变换）。后者基于 cuFHE 的算术运算和 NTT 方案。
OpenFHE：https://github.com/openfheorg/openfhe-development
OpenFHE 是一个开源 FHE 库，包括所有常见 FHE 方案的有效实现。
SparkFHE：https://github.com/SpiRITlab/spark
Spark提供了基于全同态加密算法的分布式数据流。
TenSEAL：https://github.com/OpenMined/TenSEAL
TenSEAL 是一个用于对张量进行同态加密操作的库，构建在 Microsoft SEAL 之上。它通过 Python API 提供易用性，同时通过使用 C++ 实现其大部分操作来保持效率。
HEhub：https://github.com/primihub/HEhub
由原语科技推出的同态加密开源算法库 HEhub，作为 PrimiHub 开源生态的一部分。HEhub 是一个易于使用，可扩展性强且性能优秀的密码学算法库，致力于汇集各类同态加密算法及其应用。其目前包含了 BGV、CKKS、TFHE 等全同态加密算法，并将进一步集成更多同态加密方案、常用的计算逻辑以及上层应用接口。
全同态加密算法的选择
对BFV、BGV、CKKS、FHEW、TFHE五种全同态协议进行比较，可归类如下：
-
BFV/BGV：适合处理小区间上的整数向量，无精度损失；
-
CKKS：适合处理浮点数向量，精度控制在1e-6~1e-8；
-
FHEW/TFHE：适合处理分段函数/非连续函数，精度控制在1e-4。
全同态加密应用场景
外包存储及外包计算
同态加密最直接的应用场景是外包计算。该应用中，云端提供大规模存储和高性能计算服务，客户端 (如: 小型企业) 将私有数据以同态加密形式保存在云端。云端可利用自身的计算能力和同态加密性质直接对这些密文数据执行操作并将密文结果返回给客户端，客户端对密文解密即可获得需要的计算结果。这里，同态加密算法提供了一种简洁的云计算安全解决方案，既保护了云上数据的安全性，又使云平台具备了对云上数据操作的能力。
隐私信息检索及查询
另一个全同态加密的典型应用场景是面向数据库或搜索引擎的隐私信息查询。该应用中, 服务器拥有大型数据库并提供检索服务，客户端可借助全同态加密技术实现对该数据库的隐私信息检索 (private information retrieval) ，既获取服务器检索数据又避免服务器得到关于查询条目的任何信息。具体来说, 服务器可利用数据库构造密文检索函数，客户端加密需要查询的索引 i 并发送给服务器，服务器使用评估函数得到
的密文结果并将其返回客户端，客户端解密后即达到隐私信息检索的目的。类似做法也可应用于更复杂的查询操作 (如数据库 SQL 查询、 搜索引擎的自由格式查询等) 以满足更实用化的隐私检索和查询任务的需要。
通用两方安全计算
外包计算和隐私信息检索都属于安全多方计算的研究范畴，可看作通用安全多方计算研究中的两种特例。事实上，一般化的安全多方计算模型也可以通过全同态加密算法实现。在通用的两方安全计算模型中，参与方 A 持有输入 x，参与方 B 持有输入 y，两方共同计算某个已知函数 F，参与方 A 能获得结果 F(x，y)，参与方 B 得不到任何额外信息。在半诚实敌手模型中，参与方 A 可使用其公钥加密输入 x 并发送给 B，参与方 B 评估函数 并将密文结果返 回给 A。这就实现了半诚实假设下基于全同态加密的通用两方安全计算模型。在这个过程中，同态加密算法的语义安全性 (semantic security) 保证了参与方 B 无法获取额外信息。使用隐藏评估函数的同态加密方案可以防止参与方 A 获取除结果 F(x，y) 外的额外信息。利用标准的技术可以将该协议进一步转化为恶意假设下的安全多方计算协议。
除此之外，全同态加密在 Web3 中可以用于交易隐私保护、AI 隐私保护和隐私保护协处理器。其中尤其看好隐私保护 EVM，它比现存的环签名、混币技术和 ZK 都要更灵活，更适配 EVM。
关于全同态加密的学习路线可参考：陈智罡博士 - 如何学习全同态加密(致远老师-知乎) 和 全同态加密学习路线(六三老师-知乎) 。