一、概述
如果我们有一个加密函数 $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具有乘同态性质。但是很遗憾,其没有加同态性质。
参考文章: