同态加密是一种允许直接对加密数据执行计算而无需解密密钥加密方案。从理论上讲其功能强大且在学术上很具有吸引力，但是实际使用门槛较高。

原文标题：《隐私保护计算技术指南 4》
撰文：陈智罡

概述

同态加密是指具有特殊代数结构的一系列加密方案，该结构允许直接对加密数据执行计算而无需解密密钥。

自 1970 年代以来，支持单一算术运算（加法或乘法）的加密方案就已广为人知，通常被称为单同态。Rivest，Adleman 和 Dertouzos 意识到同态性质的实用价值 , 并就此领域进行了探索研究。

2009 年，Craig Gentry 提出了第一个全同态加密方案。该方案允许对加密数据执行加法和乘法。

这是一项重要的发明，因为原则上，这种加密方案可以允许对加密数据计算任意布尔和算术电路，而无需向执行计算的一方透露输入数据或结果。取而代之的是，结果只能由有权访问密钥的特定方（通常是输入数据的所有者）解密。

该功能使同态加密成为用于云存储和计算安全的强大工具，并且是依赖于此类功能的高级加密和协议的基础。

尽管从理论上讲其功能强大且在学术上很具有吸引力，但第一代全同态加密方案在性能和密钥大小方面的原因，使其无法得以实践应用，只处于理论阶段。

在接下来的几年中，为发明和实现更简单，更快的同态加密方案，学术领域进行了大量工作。这项工作最终由 IBM 研究院发布了全同态加密库 HElib。该库将先前的同态加密实现的性能提高了几个数量级。如今，有多个开源的同态加密库可用，它们实现了适用于不同应用程序的各种同态加密方案。

关于术语的注意事项

虽然原则上全同态加密方案允许对加密数据进行任意计算，但实际上几乎所有有效的实现方式都使用所谓的「分层模式」下的全同态加密 (Leveled FHE)，其中加密方案配置为仅支持特定大小或有界大小的计算，通常会导致性能极大的提升。

为简单起见，在本文中，我们自由地使用术语同态加密（HE）来指全同态加密（FHE）或层次型全同态加密。

应用实例

同态加密提供了强大的后量子安全和独特的非交互式密文计算功能，但是会导致较高计算开销和消息大小的扩展。

因此，理想的应用场景应该是在具有相对较小但关键的加密计算组件，包括持久性存储方面。并且其功能很难或者不可能使用其他方法来实现。

典型的应用实例是在医疗领域。其中法规强制执行严格的患者数据隐私措施，但是医院和诊所可能仍希望使第三方服务提供商能够分析，评估或计算其数据，而无需花费大量金钱以及耗时的法律程序。例如，服务提供商可以提供图像分析服务以在 MRI 扫描中检测肿瘤。可以直接对同态加密数据进行计算分析，从而避免医疗数据泄漏给服务提供商的问题。

对于数据存储提供商而言，潜在的应用程序是对加密的客户数据执行分析。例如，客户可能想使用云存储服务来存储大型加密数据库，而不必为简单的计算查询而下载整个数据库，因为这会带来不必要的本地计算配置与成本，并可能使整个数据集暴露于潜在的低安全性计算环境中。

相反，所有可能的数据汇总都应由云存储提供商直接以加密形式执行，以避免不必要地将数据暴露给客户端计算机。

另一个有希望的应用是在隐私数据交集和隐私信息检索协议中。在隐私数据交集中，客户端和服务器拥有唯一的标识符集（例如，名称，电子邮件地址，电话号码），并希望在它们的集合中找到共同的项目。例如，两家公司可能希望找到他们共同的客户。

当一组中的某一组比另一组小得多时，同态加密可以为该问题提供有效的解决方案。

在这种情况下，可以对较小的集合进行同态加密，然后发送给另一方，后者可以将加密后的数据与其集合做匹配计算。在私人信息检索中，当事方之一可以检索与匹配项相关联的数据，而无需数据所有者知道检索了什么数据（如果有的话）。在这种类型的协议中，对数据集合的大小有上限的限制，并且所有通信和计算都必须与这些上限成比例。

敌手模型和安全性争论

如今，所有具有实用性能或接近实用性能的同态加密方案都基于有错误学习（LWE）或环上错误学习（RLWE）的困难问题。换句话说，如果可以有效地破坏这些困难问题，则可以有效地解决 LWE 或环 LWE 的特定问题。由于对 LWE 和环 LWE 进行了广泛的研究，并认为现代计算机无法解决这些困难问题，因此有充分的理由相信这些同态加密方案是安全的。

由于同态加密是一种特殊的加密算法，而不是指的协议，因此其安全性定义仅规定，当给定密文后没有密钥的敌手将无法获得有关明文的任何信息。即使允许敌手选择任意数量的明文加密，此特性也将保留。此性质也称为 CPA。

但是，当允许敌手获取自己选择的数据解密时，其安全性不成立。确实，对于同态加密的安全使用，至关重要的是，除非有关可信数据的信息不会发生不良行为，否则绝不要将有关解密数据的信息传递回相应的加密数据的信息源。这包括看似无害的信息，例如重复执行协议的请求，拒绝为服务付费或揭示行为的任何变化，这些变化可能取决于加密计算的结果。

这样的反向通信信道的存在可能最坏地导致完整的密钥恢复攻击，并且降低安全级别。因此，应将涉及单用户的数据外包存储和计算视为同态加密的主要用例。在收到计算结果之后，密钥所有者不得基于解密结果执行任何服务提供商可以观察到的操作，以避免上述攻击。

另一个微妙之处是大多数同态加密方案都不提供输入隐私：如果计算依赖于两个或更多方的私有加密输入，则不能保证加密方案可以保护这些输入免受密钥所有者的攻击。同态加密在本质上也很特殊，截获密文的任何人都可以修改底层的明文。除非例如密文是由发送者加密签名的。

目前同态加密的使用门槛较高，没有加密专家的帮助，就不可能从中建立安全协议。多数基于同态加密的协议只能在半诚实的安全模型中被证明是安全的。但是也有例外，其中通过将同态加密与其他原语结合起来可以实现更强大的安全模型。

使用技术的成本

同态加密的使用至少带来三种类型的成本：消息扩展，计算成本和工程成本。

在同态加密系统中，由于编码效率较低（将实际数据转换为可以加密的明文元素）以及密文本身扩展（密文大小与明文大小之比），加密数据通常比未加密数据大得多。

根据使用情况，编码效率低下的范围可能从理想情况（根本没有扩展）到在编码方法选择不当时以数万或数十万规模的扩展率。消息扩展原则上可以任意大，但是实际上，根据使用情况，可以预期扩展因子为 1 到 20 倍。因此，在大多数情况下，人们不应该考虑使用同态加密来加密大量数据，而应仔细考虑所需的加密计算确切需要哪些数据，而仅对其进行加密。

同态加密的计算成本与未加密的计算相比显著。准确的成本在很大程度上取决于加密方案的参数以及吞吐量或等待时间。也就是说，大多数同态加密方案都支持对加密数据进行向量化的批处理计算，如果可以充分利用批处理功能，则可以将吞吐量提高 1000–100000x。

开发具有同态加密的复杂系统可能是一项挑战，应始终在专家的帮助下完成，这样的解决方案的初始成本可能很高。造成这种情况的原因有两个：如前所述，如果没有特殊的专业知识，则很难理解和评估安全模型；而如果不深入了解其工作原理，则可能难以充分利用可用的同态加密库。

还应注意，同态加密很难或不可能与现有系统集成。相反，此技术的复杂应用程序可能需要对现有数据管道，数据操作过程和算法以及数据访问策略进行实质性更改。

可用性

最常用的全同态加密方案是 Brakerski-Gentry-Vaikuntanathan （BGV）和 Brakerski-Fan-Vercauteren （BFV）方案。两者都允许对有限域元素的向量进行加密计算。

最近，CKKS 方案计划已获得普及。CKKS 方案允许对实数或复数进行近似加密计算，非常适合统计和机器学习应用。

不同方案之间的权衡比较复杂，即使对于本领域的专家而言也可能难以理解。对于非常大和非常小的计算，BGV 方案比 BFV 方案具有性能优势，但是在许多其他情况下，技术的差异可以忽略不计。另一方面，与 BFV 方案相比，BGV 方案更加复杂并且学习曲线更陡峭。CKKS 方案的性能与 BGV 相当，但学习起来可能更具挑战性。但是，它提供了其他方案无法提供的功能。

BGV 方案在 IBMResearch 的 HElib 库和新泽西理工学院的 PALISADE 库 / 框架中实现。BFV 在 MicrosoftSEAL，PALISADE 和 FV-NFLlib 库中实现。CKKS 在 Microsoft SEAL，HEAAN 和 HElib 中实现。

虽然 BGV，BFV 和 CKKS 在理论上都允许对加密数据进行任意计算，但是在预先确定电路深度并选择加密方案参数以实现计算的分层模式下，它们通常效率更高。

相反，TorusFHE （TFHE）方案对按位加密的输入进行操作，并尝试进行优化以实现任意计算。在需要按位加密输入的情况下，例如在涉及加密数字比较，排序或类似非多项式运算的计算中，诸如 TFHE 之类的方案可能是最有效的解决方案。TFHE 方案具有相同名称的库。