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

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

- 作者：[小土刀](https://wdxtub.com/about)
- 发布日期：2020-12-02
- 原文（引用请使用此链接）：https://wdxtub.com/blog/flt/flt-03
- 所属系列：flt 联邦学习之旅
- 标签：联邦学习、同态加密
- 许可：CC BY-NC-SA 4.0（https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh）
- 正文中的站内图片路径以 https://wdxtub.com 为根目录。

> 阅读提示：这是 2021 年整理的联邦学习笔记。源码解析与示例依赖当时的 FATE 版本，具体版本以正文说明为准，使用前请核对运行环境。

---

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

## 白话同态加密

虽然同态加密即使现在听起来也很陌生，但是其实这个概念来自 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 版](https://github.com/wdxtub/federated-learning-note/blob/main/flt-03/paillier_sample.py)
2. [Golang 版](https://github.com/Roasbeef/go-go-gadget-paillier)

注：实际实现的过程中，一般不会直接实现 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=\frac{{L(C^\lambda mod N^2)}}{{{L(g^\lambda mod N^2)}}modN$$

### 加法同态

对于任意明文 $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 版](https://github.com/wdxtub/federated-learning-note/blob/main/flt-03/rsa_sample.py)

### 密钥生成

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 为（为了区别使用大写）：

$$A^e\ \%\ n = B$$

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

### 解密

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

$$B^d\ \%\ n = A$$

### 乘法同态

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

```python
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
```

## 写在最后

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

## 参考链接

+ [知乎：同态加密的实现原理是什么？在实际中有何应用？](https://www.zhihu.com/question/27645858/answer/37598506)
+ [Paillier同态加密的介绍以及c++实现](https://www.cnblogs.com/ranzhong/p/13654485.html)
+ [Paillier Python 包](https://python-paillier.readthedocs.io/en/develop/)
+ [Pailler 论文原文](http://link.springer.com/content/pdf/10.1007%2F3-540-48910-X_16.pdf)
+ RSA 算法原理 [（一）](http://www.ruanyifeng.com/blog/2013/06/rsa_algorithm_part_one.html) [（二）](http://www.ruanyifeng.com/blog/2013/07/rsa_algorithm_part_two.html)
+ [RSA算法原理简介](https://blog.csdn.net/ws_kfxd/article/details/86426306)
+ [深入理解RSA算法](https://www.jianshu.com/p/2af68dabd093)
+ [RSA乘法同态加密的python实现](https://blog.csdn.net/u014418725/article/details/82883220)

