导 读

同态加密是数据加密中最常见的加密方案之一，也是MPC常用的通用算法之一，主要由同态性质和加密性质两个性质构成。加密性质可保证被加密的数据无法被其他方复原，同态性质能让加密数据可以直接进行计算，且保证运算结果的正确性。近年，微软等互联网巨头纷纷成立同态加密的研究院，并对其进行研究。

传统的MPC（安全多方计算）需要依靠交互实现数据安全保护，而同态加密这项算法不依托于别人，属于非交互式安全多方计算，这种加密方案的数学性质极其优美，基于此可快速构建出对应的隐私计算方案。

▲ 数学定义

同态性质使用数学的语言表达，即如果存在一个映射f：

我们称映射f具有同态性质，如果只满足性质1则称为加法同态，如果只满足性质2则称为乘法同态。

同态加密的含义分为两层，即同态性质和加密性质。同态性质保证了密文的可运算行，加密性质则保证了密文的安全性。其中，加密性质要求一个映射输出的结果必须是不可区分的。也就是说，对于x和y而言，f(x)和f(y)对观看者来说必须是无法区分的，如果映射f(x)=x（一个最简单的全同态函数），则该映射对数据x就没有起到加密的效果。因此，构建一个具有同态性质又具有加密性质的映射是同态加密中的难点。

▲ 同态加密的分类

同态加密分为三大类：半同态加密，部分同态加密和全同态加密。

1）半同态加密：仅支持密文乘或者加的操作；

2）部分同态加密：支持无限次密文加法和有限次密文乘法或者无限次密文乘法和有限次密文加法的操作；

3）全同态加密：支持无限次密文乘法和加法的操作。

半同态加密这种加密方案满足密文计算的性质，但是在实际场景中，仅使用加或者乘的操作是无法满足需求的，为了解决这个问题，就有了部分同态加密。部分同态加密克服了半同态加密的部分缺点，支持无限次加和有限次乘（或无限次乘和有限次加），但只能支持有限次乘法（加法）的操作，还是不足够灵活。全同态则加密则彻底解决了灵活性的问题，可以满足无限次的乘法和加法，但是性能也随之降低。

单纯从数学定义上阐述同态加密稍显枯燥，下文，以首个全同态的算法发明者Gentry的举出例子出发，我们代入一个“名画修复”的场景，更深入的了解同态加密的技术特性，以及同态加密三个分类之间的关系。（以下案例是笔者虚构，可能与真实场景不同，仅供参考）

名画的修复过程

一位阔绰的名画收藏者，入手了一张“破损的名画”（假定为：数据A），所谓的破损即有几处地方缺失，不久前他找到了“名画的缺失部分”（假定为：数据B）非常兴奋，希望找人修复名画。

传统的方式是将画和碎片交给专人修复（即明文在云服务器上进行数据A和B的运算），但是这样可能会出现修复者见财起意偷偷调换画作的可能（即数据被云服务器厂商盗取），对此收藏者非常担心，也不想承担这样的风险。

于是他想到了一个办法，把破损的名画和名画缺失碎片锁到了箱子里面（“箱子”类比可信的“数据加密”环境），然后箱子开两个口，口上装上手套（如下图），修复人员想要修复名画只需要把手伸进手套就可以进行修复了（即密文运算的过程）。

图片来源自网络

名画修复的过程需要使用到胶水、画笔等工具，（我们把密文加法比作胶水，密文乘法比作画笔与颜料）而箱子又是密封好的，因此我们需要提前将这些工具放入箱子中（即同态加密中的准备环节，如公私钥生成等）。

▲ 半同态加密

半同态加密的场景，我们可以设想为：如果箱子内只准备了胶水，那么修复人员就只能将画作进行粘贴的操作（即密文加法），如果在箱子里只准备画笔，那么修复人员就只能进行画作的颜色或者描边的操作（即密文乘法）。

▲ 部分同态加密

部分同态加密场景设定：在使用颜料（密文乘法）修复名画的过程中，如果颜料不小心粘到箱子上，会干扰修复人员的视线，导致修复精确度下降，这种情况类比：部分同态的噪声，随着修复的进行，精确度将越来越低。因此，部分同态加密只能支持有限次的乘法操作，超过使用的阈值后会因为有太多干扰影响修复结果。

▲ 全同态加密

为了解决上述颜料污染的问题（即加密过程中出现部分同态噪声的问题），收藏家想到了一个解决办法。在修复过程中，如果箱子上的颜料会影响修复时，就重新准备一个箱子，装入除了胶水，画笔和颜料之外，还有第一个箱子开锁的钥匙，然后把第一个箱子装入第二个箱子中，使用里面的钥匙打开第一个箱子的锁，取出画作在第二个箱子中进行修复，因为第二个箱子是全新的，所以不会影响到后续的修复工作。这种方式通过不断的嵌套新的箱子解决部分同态噪声爆炸的问题，我们将这种方式类比全同态加密的操作过程。

总结

综上，我们分析了同态加密的技术特点与使用场景，同态加密的性质听起来固然优美，但也存在明显的缺陷。首先，除自射外，从明文空间向密文空间中不存在完美的全同态映射，但是仅自射是无法满足完备的加密的性质，因此同态加密会存在不同程度的噪声，精确性会受到影响；其次，同态加密的发挥性能所产生的开销很大，对计算资源的要求也很高，这也是制约其大规模使用的最主要因素。

经过科学家们的不断探索，同态加密已经得到很大优化，现阶段其效率相比于最初提高了很多，但是距离真正的工业化落地仍有很长的路要走。与传统的安全多方计算相比，同态加密多应用于云外包计算时的数据隐私保护场景，利用云端机器的强大性能，保护数据安全隐私。根据笔者浅见，同态加密在联合建模等有隐私要求且依托于云端算力的场景中有很大的应用场景，数据隐私+云外包会是同态加密一个很好的方向。

作者简介

刘毅恒 来自数据网格实验室BitXMesh团队，一个鲜为人知的知名程序员