0%

【联邦学习之旅】03 同态加密与 Paillier/RSA

上一讲我们简单了解了联邦学习评分卡,接下来的几讲我们会更多关注联邦学习背后的基础概念,这次就先从同态加密说起。

白话同态加密

虽然同态加密即使现在听起来也很陌生,但是其实这个概念来自 1978 年,由 RSA 算法的发明者的 R 和 A 以及 Dertouzos 提出。具体的定义如下:

A way to delegate processing of your data, without giving away access to it.

翻译成人话就是传统的加密方法和数据处理方法是互斥的,比如我需要计算两个数字的和(1 和 2),如果加密了之后,就无法对密文进行计算;如果想要进行计算,就必须知道这两个数字是 1 和 2。如果数据拥有方和计算方是同一方,那么知道 1 和 2 没啥问题;但如果数据拥有方和计算方并非同一方,并且数据拥有方还不想让计算方知道这两个数字是 1 和 2,这个时候就是同态加密发挥作用的时候了。

同态加密将数据的处理和数据本身解耦了:计算方拿到的是加密之后的数字,但是依然可以相加,相加之后把结果告诉数据拥有方,最终数据拥有方解密就可以知道最终的计算结果。

同态加密的这个特点使得云服务厂商非常在意,因为这一举解决了用户担心云服务厂商窃取数据的担心(因为加密了除了计算没法做其他事情),并且因为加密计算本身耗费更多计算资源,还可以变相提高营收。

总结一下:同态加密使得数据可以在加密的状态下进行计算,至于支持什么计算,如何进行计算,我们接下来继续讲。

定义同态加密

先假设一个场景:我想要处理一大批数据,如果在本地用明文要 100 个小时,这个时间太长了,所以我需要借助云计算的力量。但是因为这批数据很敏感,包括了我从小到大每一分每一秒的心情和各类身体指标,我不希望云计算平台能够直接获取到,这样我就感觉自己没有隐私了,所以我需要使用同态加密,让云计算平台在加密的情况下计算(假设只需要 1 个小时),我拿到加密计算的结果再解密得到真实结果。那么问题来了,这个过程需要几步?

  1. 我在本地生成用来加密数据的 Key
  2. 我用 Key 和 Encrypt 算法加密本地的数据,记为 EncData = Encrypt(Key, Data)
  3. 我告诉云平台需要如何计算数据,记为函数 F()
  4. 云平台进行计算 Evaluate,即 Evaluate(F(), EncData) = Encrypt(Key, F(Data)),记为 ProEncData
  5. 云平台将 ProEncData 发回给我
  6. 我用密钥进行解密 Decrypt,得到 F(Data) = Decrypt(Key, ProEncData),也就是最终结果

在以上六个步骤中,至少有四个函数是必须的:

  1. 生成密钥的函数:本地执行,生成密钥
  2. Encrypt 函数:本地执行,加密数据,加密之后的数据不会暴露源数据的信息
  3. Evaluate 函数:用来执行用户给定的计算函数 F(),是唯一由云平台运行的函数
  4. Decrypt 函数:本地执行,解密数据

根据支持的 F() 的不同,同态加密分成了两类:

  1. Fully Homomorphic Encryption, FHE:这种方式下,任何 F() 都可以,只要这个算法能够被计算机实现即可。不过这个计算开销非常大,目前暂无实际应用。注:Gentry 在 2009 年给出过一个实现
  2. Somewhat Homomorphic Encryption, SWHE:这种方式下,只支持某些特定的 F()(比如只支持加法/乘法,并且只能执行有限次数)。这个方案有比较大的限制,但也因此计算开销较小,已经可以在实际中使用
    1. 乘法:RSA, Elgamal
    2. 加法:Paillier

接下来我们会详细看看 Paillier 算法和 RSA 算法,对加法同态和乘法同态有更加深入的理解。

Paillier 算法

因为有了前面的分析,我们知道一个同态加密算法需要四个函数:密钥生成、加密、解密、同态运算,针对 Paillier 算法,我们一项一项来看一下。

这里我们也准备了不同语言版本的实例:

  1. Python 版
  2. Golang 版

注:实际实现的过程中,一般不会直接实现 gcd 和 lcm 函数,而是采用一些替代的计算,具体参考上面链接中的源码。

密钥生成

总共有如下几个步骤:

  1. 随机选择两个质数 p 和 q 满足 $|p|=|q|=\tau$,这个条件保证了 p 和 q 的长度相等。
  2. 计算 $N=pq$ 和 $\lambda=lcm(p-1,q-1)$,注:lcm 表示最小公倍数
  3. 随机选择 $g\in Z_{N^2}^*$,满足 $gcd(L(g^\lambda mod N^2),N)=1$,注:gcd 表示最大公约数;Z 表示整数,下标表示该整数集合里有多少个元素;$L(x)=\frac{x-1}{N}$
  4. 公钥为 $(N,g)$
  5. 私钥为 $\lambda$

加密

对于任意整数 $m\in Z_N$,任意选择随机数 $r\in Z_N^*$,密文 $C=E(m)=g^mr^NmodN^2$

解密

对于密文 $C\in Z_{N^2}^*$,解密得到明文 m 的计算如下:

加法同态

对于任意明文 $m_1, m_2\in Z_N$,假设 $E(m_1)=g^{m_1}r_1^NmodN^2$ 和 $E(m_2)=g^{m_2}r_2^NmodN^2$,有

$$E(m_1)E(m_2)=g^{m_1+m_2}(r_1r_2)^NmodN^2=E(m_1+m_2modN)$$

这个性质表明 Paillier 加密方案具有加法同态性。

RSA 算法

RSA 算法作为最为知名的非对称加密算法,想必大家都有一定的了解,这里我们仍然以针对密钥生成、加密、解密、同态运算四个步骤,一项一项来看一下。同样可以参考下面的代码实例:

  1. Python 版

密钥生成

  1. 随机找两个质数 P 和 Q,越大越安全,并计算乘积 $n=P*Q$。P 和 Q 的乘积的二进制位数代表 RSA 加密的位数,一般来说都要有 1024 或 2048 位。
  2. 计算 n 的欧拉函数 $\phi(n)$,表示在小于等于 n 的正整数中,与 n 构成互质关系的数的个数。比如 1~8 中,和 8 互质的有 1,3,5,7,所以 $\phi(8)=4$,如果 p 和 q 为质数,那么他们的乘积的欧拉函数有一个特殊的性质,公式为 $\phi(n)=\phi(P*Q)=\phi(P-1)\phi(Q-1)=(P-1)(Q-1)$
  3. 选取 e,要大于 1 小于 $\phi(n)$,并且 e 与 $\phi(n)$ 要互质
  4. 计算出一个整数 d,使得 $(ed-1)\ \%\ \phi(n)=0$,即 $e*d$ 除以 $\phi(n)$ 的余数为 1,实际上转化为找到二元一次方程 $ed+k\phi(n)=1$ 的一组解(求 d 和 k),具体使用的是扩展欧几里得算法

于是我们可以得到:

  • 公钥 (n, e)
  • 私钥 (n, d)

在这样的条件下,如果想要根据 n 和 e 算出 d,就只能暴力破解,位数越长,玻璃破解时间越长。

加密

我们现在有个这么几个关键的数值:n, e, d。要使用公钥 (n, e) 加密,首先要求被加密的数字必须是整数且小于 n(如果是字符串,可以逐个取 ascii 码或 unicode 值,并且中间用非数字和字母分割即可)。假设我们需要加密的数字是 A,则加密之后的 B 为(为了区别使用大写):

如果没有 d,那么是很难从 B 中恢复 A 的。

解密

如果我们拥有私钥 (n, d),那么对于 B,就可以通过下面的公式计算出 A:

乘法同态

相对 Paillier 来说还要更加简单一些,我们只要把两个加密后的数字相乘即可,代码片段如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
print('接下来加密计算 2 x 20')
print('加密 2')
enc1 = rsa.core.encrypt_int(2, public_key.e, public_key.n)
print(enc1)
print('加密 20') # 40471062776583530669631608186743860028386032505372124150562694293213549812024
enc2 = rsa.core.encrypt_int(20, public_key.e, public_key.n)
print(enc2) # 16915103439566807805446086181091224947678993169521653470724152014464992293178

print('相乘')
result = enc1 * enc2
print(result) # 684572213175112282577113686759405066981454950839007710126450052851088805616753069318980764721622690261112227625923822693220128510206043466290770597572272

print('解密结果')
decrypt_result = rsa.core.decrypt_int(result, private_key.d, public_key.n)
print(decrypt_result) # 40

写在最后

这一讲我们结合实际的例子熟悉了同态加密,接下来我们会继续介绍联邦学习相关的底层技术,让大家知其然更知其所以然。

参考链接