2.4.3 半同态加密算法

半同态加密算法是指乘法同态加密算法或者加法同态加密算法，即只能保证在密文上进行加法或乘法的其中一种操作的结果，与在明文上进行相同操作的结果是相同的。也就是说，对于满足以下要求的算法Enc_A，可以称之为加法同态加密算法，即

式中，m₁和m₂代表明文；c₁和c₂代表密文；⊕可能与实数域上的加法不同，需要根据具体的加密算法进行调整。

另外，对于满足以下要求的算法Enc_M，可以称之为乘法同态加密算法，即

式中，⊗可能与实数域上的乘法不同，需要根据具体的加密算法进行调整。

如果在半同态加密算法的两个密文上同时进行加法和乘法，那么不能得到预期的结果。因此，在机器学习中，半同态加密算法的应用场景主要是计算类型单一的机器学习算法，或者计算类型偏向某一种的机器学习算法。比如，在多方的强化学习算法中，迭代过程的大多数操作均可以用加法同态加密算法来实现。

常用的半同态加密算法主要有以下几种：Paillier加法同态加密算法[53]、ElGamal乘法同态加密算法、Goldwasser-Micali加法同态加密算法和RSA乘法同态加密算法等。以上几种半同态加密算法在计算效率上都具有良好的性能，根据其不同的特性有不同的应用场景，其中Paillier加法同态加密算法可将加/解密的计算时间控制在毫秒级，李宗育等人的结果表明，使用Paillier加法同态加密算法加密1024比特的消息只需2.3秒左右[60]。本节将主要介绍Paillier加法同态加密算法的加/解密过程，帮助读者理解公钥密码算法的工作原理及安全性保证，对其他半同态加密算法不再展开描述。

Paillier加法同态加密算法介绍。

1.密钥生成

（1）选择两个大素数p，q。

（2）计算N=p·q，以及λ=lcm（p-1，q-1）。

（3）选择一个整数，使得gcd（L（gλmod N2），N）=1，即二者互素，其中，。

公钥为〈N，g〉。

私钥为λ。

2.加密（使用公钥）

（1）选择一个随机数作为概率性加密的随机源。

（2）明文m对应密文为c=Enc（m，r）=gm·rNmod N2。

3.解密（使用私钥）

1）密文c对应的明文为

以上便是利用Paillier加法同态加密算法生成密钥、加密和解密的具体过程，其中lcm（a，b）是指a和b的最小公倍数，gcd（a，b）是指a和b的最大公约数。

该算法的安全性建立在大整数分解问题的困难性上，即我们无法将大整数N进行分解得到两个素数因子p、q。该算法的正确性是由有限域中元素的众多性质决定的，感兴趣的读者可以参考Paillier加法同态加密的原文[58]进行更深入的研究，在此不做过多的描述。

上文提到了多种半同态加密算法，由于算法的不同特性，其具体的应用场景也不同。在此，我们简单地介绍一下Paillier加法同态加密算法适合联邦学习的三个原因：概率性加密特性、同态运算属性以及相对较慢的密文扩张速度。

首先介绍一下公钥加密算法中语义安全的概念。密码分析学是一门与密码学共同演化的学科，主要研究的内容是在不知道密钥任何信息的情况下，恢复出密钥的相关信息，以达到破解密码系统的目的。在密码分析学中，对密码算法的攻击方式是复杂多样的，直接恢复出密码算法的密钥是恶意敌手的终极目标，因为恢复了密钥就可以得到所有使用该密钥加密过的消息明文，但是完成终极目标的成本极高、难度极大。因此，一些攻击者选择从密文中直接分析明文的相关信息，从而提出了选择密文攻击等更复杂的攻击方式，并在某些算法中成功地实现了攻击。为此，密码学学者提出了语义安全的概念，满足语义安全的密码算法可以防止敌手以超过50%的概率识别两个不同明文分别对应的密文。

在某些公钥密码算法的构造中，加密过程会引入一个随机源，这使得对同一个明文进行两次加密可能会得到不同的密文，这种类型的算法称为概率性加密算法；相反，如果在加密过程中没有引入随机源，那么对同一个明文进行加密的结果是不会改变的，这种类型的算法被称为确定性加密算法。显然，确定性加密算法的密文在一定程度上泄露了明文的信息，因为明文和密文是一一对应的。当得到一个确定性加密算法的密文c时，我们可以使用其公钥对一个明文序列m₁，m₂，…，m_n分别进行加密，如果加密结果c₁，c₂，…，c_n均与c不相等，那么我们便可得出结论：c对应的明文m不在明文序列m₁，m₂，…，m_n中，我们便通过密文分析出了明文的信息。另外，图2-3和图2-4直观地解释了语义安全的概念。在图片加密之前，在白色画布上有一把黑色的锁。通过某种确定性加密算法，将白色像素点加密为蓝色像素点，而黑色像素点则被加密为橙色像素点。由于确定性加密算法的特性，加密之前颜色相同的像素点在加密之后颜色还是相同的，因此从加密后的图片中我们还可以分辨出这是同一把锁，也就是说，加密后的图片还是泄露了原始图片的信息。概率性加密算法则不会产生这个问题，不同的白色像素点被加密成了不同的颜色，不同的黑色像素点的加密结果也同样是五颜六色的，因此原始图片的内容便无迹可寻。

显然，确定性加密算法都不满足语义安全，比如RSA乘法同态加密算法。概率性加密算法作为一种满足语义安全的算法，在实际应用中使用得更为广泛。其中，Paillier加法同态加密算法便是一种概率性加密算法，这也是SecureBoost等众多算法选择用Paillier加法同态加密实现半同态加密的原因之一。另外一个更重要的原因是同态加密运算类型的要求。在大多数联邦学习算法中，需要进行的同态运算主要为加法，即希望通过操作密文达到明文相加的目的。因此，以RSA、ElGamal为代表的乘法同态加密算法则不适合该场景（即使RSA乘法同态加密算法可以通过密码学的相关框架转化为语义安全的算法）。除了Paillier加法同态加密算法，Goldwasser-Micali算法也是一种加法同态加密算法，但由于该算法的密文扩张速度过快，与Paillier加法同态加密算法相比，该算法的实用性较差。因此，综合以上因素，包含FATE中SecureBoost算法在内的多种算法均选择实用性更好的Paillier加法同态加密算法作为加法同态加密算法。