革命与进化：全同态加密

• 作者： 大卫·阿彻

目前，越来越多的计算被外包给公共云，比如Amazon的GovCloud和Elastic Compute Cloud、PackSpqce等等。这是计算机硬件的新“零工”经济。但这些云计算机跟其他任何计算机一样容易受到攻击，从而使敏感数据的隐私受到威胁。本文就此分析了实用同态加密在云计算中的应用及其存在的限制。本文作者大卫·阿彻，由格密链社区的马佳敏翻译。

随着国家网络武器越来越多地被业余和专业(低等级)网络犯罪分子所利用，对这些基于云的系统的外部威胁继续增加。此外，云的供应商对这些机器有着很高权限，这造成了内部威胁，对隐私构成更大的风险。

但为什么隐私会受到威胁呢?当然，我们都非常聪明，能够在数据进出基于云的系统时对其进行加密。TLS，以及其他协议，为我们解决了这个问题(如果我们记得使用它的话)。以及在这些不受信任的云服务器上保持数据加密性。对吧?即使我们解决了这两个问题，仍然存在一个无保护的攻击面：我们必须解密数据才能在其上进行计算，而且我们的计算结果在加密之前仍然是“可见的”。因此，即使在我们最好的日子里，当我们使用发送到云的数据时，隐私也处于危险之中。

我们能在云中的数据保持加密性的同时计算它吗?这个想法听起来像科幻小说。从定义上看，被模糊到像白噪声一样的数据如何能被用于任何类型的计算?直到最近，这个问题都没有好的答案。然而，在过去的几年中，实用同态加密(HE)和安全多方计算的出现有望提供一种解决方案。HE对加密输入进行计算，保持内部变量的私密性，甚至对能够查看正在运行的程序内部的观察者也是如此，并生成只有持有正确加密密钥的用户才能访问的加密输出。它提供的安全保障，和我们熟悉的密码学方案相同(基于一些同样困难的数学问题)，例如保护我们静态数据的分组密码和实现传输安全性的公钥体制。

如今，加密社区可以用HE来展示什么?无需可信的中央服务器即可以流率进行IP语音通信，因为除了接收者的电话外，语音流从未被解密。在不解密的情况下检查加密的文件中是否存在选定的字符串。面部识别，其中面部图像在整个过程中保持加密。对加密数据进行线性回归等分析。用加密的输入图像快速书写字符识别。有些原型非常快，有些非常慢。更简单的程序往往执行得更好，但并不总是如此。

这个看似神奇的技术是如何运作的?像所有的计算一样，它开始于一个要运行的程序，以及一组关于我们需要该程序的输入、变量和输出的安全性的选择。但并不是每个程序都可以使用HE进行转换，因为这种转换要求程序首先被转换成一个电路：一个相互连接的逻辑(AND或NOT)或算术(加法和乘法)门的集合。我们将避免深入到Galois Field理论中，但这足以说明这些电路要么是布尔电路，所有的值是0或1，要么是算术电路，其中的值是整数。我们可以使用这些布尔或算术字段来表示许多类型的数据：字符串、位向量、整数、定点数，以及额外的工作，浮点数。许多简单的程序语句很容易转换成这样的电路。然而，当程序中的控制流依赖于数据时，问题就出现了——也就是说，当程序流(如循环或其他条件语句)依赖于程序中变量的值而不是常量时。因此，尽管许多程序和数据类型可以在HE中表示，但是存在一些限制。

一旦我们有一个程序可以转换成合适的电路，我们需要加密电路的输入数据。他之所以工作是因为一种叫做同态的数学性质。粗略地说，同态是一个映射，其中一个域中的每个元素对应另一个域中的一个元素，同样的数学运算(在我们的例子中是加法和乘法)适用于每个元素，这些运算的结果在它们之间来回传递。HE中的加密是将一个域(例如32位整数)映射到另一个域(例如，具有非常大的模数的整数)的过程，其方式是保持这种同态。下图显示了HE的工作原理。首先，敏感数据的所有者生成由公钥和私钥组成的密钥对。其次，所有者(或敏感数据的可信存储库)使用公钥来加密数据，将其映射到新域。第三，不受信任的计算机接收加密数据(由于它没有获得私钥而无法解密)并计算其上的预期程序。第四，该计算的加密结果由持有私钥的人解密。

FHE使用的加密引入了一个值得注意的问题，它解释了HE的部分性能成本：嵌入域中的每个操作都引入了“噪音”。当信息通过我们电路中的每一个门时，噪音就会积累起来，在某些时候，我们就失去了将输出解密为有效明文的能力。这个问题最初导致同态加密仅仅是一个理论。今天，我们使用了两种方法来防止噪音变得太大：如果事先进行适当的配置，可以容纳深度电路的分层方案;bootstrapping，一个在不失去隐私的情况下重置噪音的过程。这些工具为我们提供了一种新的功能：全同态加密(FHE)，它可以在任何深度的电路上使用，只受用户的耐心限制。

FHE既然如此优秀，为什么它在今天没有被广泛使用呢?除了可以转换成适用于FHE的电路的各种程序的限制之外，FHE还有两个显著的限制：用户耐心(我指的是性能)和密文扩展。我将在这里使用标准的汽车警告：您的里程可能有所不同。对于是什么让明文计算速度变慢，人们的直觉通常无法深入了解FHE领域的性能。然而，一般来说，当我们在非常大的领域做数学时，它需要更长的时间。此外，加密输入到这些字段需要时间，当噪声变得太大时，bootstrapping也需要时间。因此，相对于密文计算，FHE计算可能需要很长时间。在2011年，很长一段时间意味着这种计算要么是不可能完成的，要么可能需要多达12个数量级的计算时间。今天，很长时间可能意味着比“无云”计算长1000倍到100万倍——而且事情还在继续改善。除了性能方面的考虑之外，将数据从我们计算的自然字段(如32位或64位整数)加密到FHE中使用的字段会导致显著的扩展：最终产生的密文比相关的明文大得多。几年前，这种扩张是典型的数千倍。最近，膨胀系数更接近一个数量级：不是微不足道，而是有了很大改善。

我在前一段中撒了谎。广泛使用FHE还有一个更重要的要求：使其易于使用。正如您可能预期的那样，将程序转换为电路、仔细配置FHE计算、管理加密和解密以及其他复杂性，使得编程FHE应用程序成为少数专家研究人员的领域。为了使FHE实际应用，我们需要尽可能无缝地将FHE功能集成到现有的编程环境中;允许程序员用相同的语言写，以表达正常和FHE计算;将程序转换成有效电路的繁琐过程自动化;使非专家所需配置参数的选择变得简单;并且透明地处理加密和解密过程，以便从程序员的角度来看，调用FHE保护函数与调用普通代码没有区别。

在过去的九个月里，一个来自Galois,Inc.和新泽西理工学院的联合团队一直在研究解决这些需求的方法。这项工作由美国情报高级研究计划局(IARPA)赞助，目的是在易用性方面开创新方法，并为进一步的实质性改进奠定基础。为了提供无缝集成，他们将FHE能力构建到Julia科学编程语言中。为了简化编程，他们教会了Julia编译器从通常的Julia函数中生成FHE代码，就像程序员通常编写的那样(在语法中添加了一些内容)。为了使电路转换过程自动化，他们集成了Galois工具，这些工具使用符号执行来自动地将程序对变量的操作转换成公式，然后这些公式被自动地表示为FHE电路。并添加了幕后支持来处理加密、云中的FHE计算和返回结果的解密，以便使用FHE函数与使用其他Julia函数一样简单。支持这种“前端”工作的是一个高价值的“后端”：创建一个大型的、功能齐全的FHE原语库，编译器套件调用它来提供程序执行所需的复杂数学。

最近在JuliaCon和政府赞助商举行的RAMPARTS网站成果展示中表明，他们已经走了很远。尽管如此，他们仍然还有很多事情要做，例如需要对库接口和配置设置进行标准化，以便FHE能够利用许多现有库。为了减少密文的扩展和提高性能，需要进一步研究FHE密码理论。此外，还需要开发应用程序的实际示例，以展示FHE如何在现实世界的问题上有效地进行安全计算。

在任何地方，对隐私的需求都是显而易见的，在敏感数据上的计算被外包给不可信的计算机，就像现代云计算那样。随着网络威胁越来越多、越来越复杂，失去这种隐私的风险继续增加。即使在我们最好的日子里，我们仍然会将数据暴露在这些威胁之下，至少要计算足够长的时间，以避免妥协。FHE提供了一种保护隐私的方法，即在数据仍然加密的情况下对其进行计算。在FHE普及之前，还有一段路要走：我们需要更好的性能和对易用性的重视。但是，所有零工经济都是由新技术驱动的。