一、概述
如果我们有一个加密函数 $f$ , 把明文$A$变成密文$A’$, 把明文$B$变成密文$B’$，即 $f(A) = A’ ， f(B) = B’$ 。另外我们还有一个解密函数 $f^{−1}$，能够将 $f$ 加密后的密文解密成加密前的明文。
对于一般的加密函数，如果我们将$A’$和$B’$相加，得到$C’$。我们用$f^{−1}$对$C’$进行解密得到的结果一般是毫无意义的乱码。但是，如果 $f$ 是同态加密的加密函数， 我们对$C’$使用$f^{−1}$进行解密得到结果$C$， 这时候的$C = A + B$。
这样，计算加密后的数据在一定程度上等价于计算加密前的数据，企业可以在保护隐私数据不泄露的情况下对数据进行计算处理，然后得出最后的结果数据进行解密即可。
二、分类
- 加法同态：$f(A)+f(B)=f(A+B)$ $\Rightarrow$ 支持加减法运算
- 乘法同态：$f(A)×f(B)=f(A×B) $ $\Rightarrow$ 支持乘除法运算
- 全同态加密：同时满足加法同态和乘法同态。$\Rightarrow$ 支持加减乘除、多项式求值、指数、对数、三角函数。
实例：
- RSA 算法 —— 乘法同态
- Paillier —— 加法同态
- Gentry算法 —— 全同态
2009年，Gentry，一个斯坦福大学的博士生，基于理想格提出一个全同态加密方案。
三、应用领域 - 云计算
使用云计算处理数据时，直接把数据扔给云是及其不安全的，因此可以加密之后让云端进行计算，最后将计算结果返回，返回后用户解密极为最后的处理结果。
这样一方面用户拿到了计算的结果，另一方面云服务商也看不到真实的数据。
用户觉得好，云服务商也觉得好，都好。唯一的不好，就是效率，对加密数据的处理速度
0x01 具体场景为例
Alice通过Cloud，以Homomorphic Encryption（以下简称HE）处理数据的整个处理过程大致是这样的：
- Alice对数据进行加密。并把加密后的数据发送给Cloud；
- Alice向Cloud提交数据的处理方法，这里用函数$f$来表示；
- Cloud在函数$f$下对数据进行处理，并且将处理后的结果发送给Alice；
- Alice对数据进行解密，得到结果。
据此，我们可以很直观的得到一个HE方案应该拥有的函数：
KeyGen函数：密钥生成函数。由Alice运行，产生加密数据Data所用的密钥Key。当然了，应该还有一些公开常数PP（Public Parameter）；Encrypt函数：加密函数。由Alice运行，使用Key对用户数据Data进行加密，得到密文CT（Ciphertext）；Evaluate函数：评估函数。由Cloud运行，在用户给定的数据处理方法$f$下，对密文进行操作，使得结果相当于用户用密钥Key对f(Data)进行加密。Decrypt函数：解密函数。由Alice运行，用于得到Cloud处理的结果$f(Data)$。
那么，$f$应该是什么样子的呢？根据$f$的限制条件不同，HE方案实际上分为了两类：
Fully Homomorphic Encryption(FHE)：这意味着HE方案支持任意给定的f函数，只要这个$f$函数可以通过算法描述，用计算机实现。显然，FHE方案是一个非常棒的方案，但是计算开销极大，暂时还无法在实际中使用。Somewhat Homomorphic Encryption(SWHE)：这意味着HE方案只支持一些特定的f函数。SWHE方案稍弱，但也意味着开销会变得较小，容易实现，现在已经可以在实际中使用。
0x02 举个SWHE的例子
在2009年Graig Gentry给出FHE的构造前，很多加密方案都具有Somewhat Homomorphism的性质。实际上，RSA加密是乘法同态、Elgamal加密是乘法同态。Paillier加密是加法同态。不过2009年前的HE方案要不只具有加同态性，要不只具有乘同态性，但是不能同时具有加同态和乘同态。这种同态性用处就不大了，只能作为一个性质，这类方案的同态性一般也不会在实际中使用的。
在此我们看一下Elgamal加密方案，Elgamal加密方案的密文形式为：
$$ CT = (C_1, C_2) = (g^r,h^r·m) $$
其中$r$是加密过程中选的一个随机数，$g$是一个生成元，$h$是公钥。如果我们有两个密文：
$$ CT_1 = (g^{r_1},h^{r_1}·m), CT_2 = (g^{r_2},h^{r_2}·m) $$
我们把这两个密文的第一部分相乘，第二部分相乘，会得到：
$$ CT = (g^{r_1}·g^{r_2},h^{r_1}·m_1·h^{r_2}·m_2) = (g^{r_1+r_2},h^{r_1+r_2}·m_1m_2) $$
也就是说，相乘以后的密文正好是$m_1m_2$所对应的密文。这样，用户解密后得到的就是$m_1m_2$的结果了。而且注意，整个运算过程只涉及到密文和公钥，运算过程不需要知道$m_1m_2$的确切值。所以我们说Elgamal具有乘同态性质。但是很遗憾，其没有加同态性质。
参考文章：