MENU

同态加密算法

December 12, 2020 • Read: 3024 • 编程之路,密码学

一、概述

如果我们有一个加密函数 $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 具体场景为例

img

Alice通过Cloud,以Homomorphic Encryption(以下简称HE)处理数据的整个处理过程大致是这样的:

  1. Alice对数据进行加密。并把加密后的数据发送给Cloud;
  2. Alice向Cloud提交数据的处理方法,这里用函数$f$来表示;
  3. Cloud在函数$f$下对数据进行处理,并且将处理后的结果发送给Alice;
  4. Alice对数据进行解密,得到结果。

据此,我们可以很直观的得到一个HE方案应该拥有的函数:

  1. KeyGen函数:密钥生成函数。由Alice运行,产生加密数据Data所用的密钥Key。当然了,应该还有一些公开常数PP(Public Parameter);
  2. Encrypt函数:加密函数。由Alice运行,使用Key对用户数据Data进行加密,得到密文CT(Ciphertext);
  3. Evaluate函数:评估函数。由Cloud运行,在用户给定的数据处理方法$f$下,对密文进行操作,使得结果相当于用户用密钥Key对f(Data)进行加密。
  4. 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具有乘同态性质。但是很遗憾,其没有加同态性质。

参考文章:

同态加密的实现原理是什么?在实际中有何应用? - 知乎

- - - 结束 - - -
  • 文章标题:同态加密算法
  • 文章链接:https://blog.canye365.cn/archives/286.html
  • 版权所有:本文版权归 残夜 所有,转载请注明出处!除特殊注明外 (如有侵权,请 点此联系我 )
  • Last Modified: February 9, 2021