隐私计算--20--同态加密概述

一、同态加密的概念

同态加密是基于数学难题的计算复杂性理论的密码学技术。对经过同态加密的数据进行处理得到一个输出，将这一输出进行解密，其结果与用同一方法处理未加密的原始数据得到的输出结果是一样的。举个例子，把1加密成A，把2加密成B，然后A+B的结果等于C，然后C能够正确解密为3。

了解密码学的人都知道，加密后的密文是不能直接进行计算的，而这正是同态加密所解决的问题。

同态加密的这种先计算后解密可等价于先解密后计算的特性，对于保护信息的安全具有重要意义，包括：

● 利用同态加密技术可以先对多个密文进行计算之后再解密，不必对每一个密文解密而花费高昂的计算代价；
● 利用同态加密技术可以实现无密钥方对密文的计算，密文计算无须经过密钥方，既可以减少通信代价，又可以转移计算任务，由此可平衡各方的计算代价；
● 利用同态加密技术可以实现让解密方只能获知最后的结果，而无法获得每一个密文的消息，可以提高信息的安全性。

二、加法同态与乘法同态

加法同态，如果：E(x+y)=E(x) + E(y)或者x+y=D( E(x)+E(y) )成立，并且不泄漏 x 和 y，则加法同态成立；

乘法同态，如果：E(x*y)=E(x) * E(y)或者x*y=D( E(x)*E(y) )成立，并且不泄漏 x 和 y，则乘法同态成立。

三、同态加密的分类

同态加密方法分为三类：部分同态加密（PHE），些许同态加密（SHE）和全同态加密（FHE）。通常来讲，对于同态加密方法，计算的复杂度是随功能性一同增长的。

3.1、部分同态加密（PHE）

对于部分同态加密方法，（M，⊙M）和（C，⊙C）都是群。 *** 作符⊙C能够无限次数地用于密文。PHE是一种群同态技术。特别地，若⊙M是加法运算符，则该方案可被称为加法同态的，若⊙M是乘法运算符，则该方案被称为乘法同态的。这里需要注意的是，部分同态加密是说要么实现加法，要么实现乘法，所以才被称为部分同态加密。如果加法和乘法都支持，那就是全同态加密了。

3.2、些许同态加密（SHE）

些许同态加密方法指一同态加密方法中的一些运算 *** 作（如加法和乘法）只能执行有限次。一些文献中也定义SHE为只有有限数量的某些电路（如跳转程序、混淆电路）能够支持进行任意次数的运算。例如BV、BGN和IP。

SHE方法为了安全性，使用了噪声数据。每一次在密文上的 *** 作会增加密文上的噪声量，而乘法 *** 作是增加噪声量的主要技术手段。当噪声量超过一个上限值后，解密 *** 作就不能得出正确结果了，这就是为什么绝大多数的SHE方法会要求限制计算 *** 作的次数。

那如何降低噪音呢？我们来引入一个假设：如果解密的时候，输入的不是密文，而是对密文加密后的密文，同样的，密钥也不是解密密钥，而是加密后的密钥，解密会输出什么东西呢？

答案是一个新的密文，该新密文依然是对原明文的加密。最重要的是新密文的噪音总是恒定的。

这也就意味着每次密文计算后，如果使用同态解密 *** 作，将会输出一个噪音恒定的新密文，这个新密文可以继续计算，计算后再同态解密，再计算，周而复始，无穷尽也，所谓任意计算实现了。

3.3、全同态加密（FHE）

全同态加密方法允许对密文进行无限次数的加法运算和乘法运算 *** 作。值得注意的是，要实现任意的函数计算，加法和乘法 *** 作是唯二所需要的 *** 作。FHE分为四种：Ideal Lattice-based FHE、Approximate-GCD based FHE、LWE-based FHE和NTRU-like FHE。

目前的FHE建立在SHE的基础之上，并通过实现代价高昂的自助法 *** 作实现。Bootstrap *** 作通过执行解密、密文上的加密 *** 作和对密钥加密来对密文进行重加密，以减少密文在后续计算中的噪声量。

由于自助法的代价高昂，FHE方案十分缓慢且在实践中往往比传统的安全多方计算方法要差的多。因此，目前主流的方向还是发现满足特定需求的、更有效的SHE方法，而非去发掘FHE方法。

此外，FHE还需假设循环安全性（或称KDM安全性），即通过使用公共密钥来加密隐私密钥，从而使隐私密钥变得安全。然而，没有FHE能够被证明在任何功能下都是安全的，并且FHE具有针对不可区分的选择密文攻击的安全性。

四、同态加密应用

我们来举一个例子说明同态加密在实际中的应用场景。

首先，我们来假设一个场景，XH（协和医院）是一家医院，ALY（阿里云）是一家云计算企业。

XH想把自己的一些医疗数据通过ALY这家云计算企业，使用大数据分析，得到一些数学模型。

如果是之前的合作模式，那么XH就需要向ALY提供所有的医疗明文数据，也就是说ALY可以完完全全地浏览这些医疗数据。而医疗数据很多是跟隐私相关的，那么按照传统的模式无法保障数据隐私安全。

但是这时候同态加密出现了，XH可以将医疗数据加密后发给ALY。ALY收到的是密文数据，并且在没有密钥的情况下无法解密，也就是说ALY无法看到这些具体的医疗数据。

此时关键来了，依靠同态加密算法，ALY仍旧可以对这些密文数据进行同态密文计算（因为目前的数据分析方法大多是数理统计方法）。计算之后的结果也是密文，将计算结果传回给XH，XH收到以后使用自己的密钥进行解密，就能够获得明文下的模型了。

这样就可以在不影响数据计算正确率的情况下，完美地保护了数据隐私安全。