同态加密算法是一种具有特殊性质的加密算法，其特殊性质主要表现在对密文的可操作性上。具体来说，使用同一个同态加密算法得到的两个密文，可以在不解密的情况下，进行加法或乘法操作，其结果与直接在明文状态下进行加法或乘法之后再进行加密的结果是相同的。如果使用传统的加密算法(如AES)直接讲敏感数据加密后发给合作方，那么在失去了统计特征的密文上，机器学习将无法有效地学习，同态加密算法很好地解决了这个问题。

更具体的说，同态加密又可分为

• 半同态加密(Partial Homomorphic Encryption, PHE)：只能在一种运算上(加或乘法)保持同态性
• 全同态加密(Full Homomorphic Encryption, FHE)：加法和乘法两种运算上均满足同态性

  半同态加密

  半同态加密算法是指乘法同态加密算法或加法同态加密算法，即只能保证在密文上进行加法或乘法的其中一种操作的结果，与在明文上进行相同操作的结果是相同的。

  加法同态加密算法

  对于满足以下要求的算法，可以称之为加法同态加密算法，即
  
  
  
  式中，和代表明文；和代表密文；可能与实数域上的加法不同，需要根据具体的加密算法进行调整

  乘法同态加密算法

  对于满足以下要求的算法，可以称之为加法同态加密算法，即
  
  
  
  式中，和代表明文；和代表密文；可能与实数域上的乘法不同，需要根据具体的加密算法进行调整

  常用半同态加密

  在机器学习中，半同态加密算法的应用场景主要是计算类型单一的机器学习算法，或者计算类型偏向某一种的机器学习算法。比如，在多方的强化学习算法中，迭代过程的大多数操作均可以用加法同态加密算法来实现。

常用的半同态加密算法主要有：Paillier加法同态加密算法、ElGamal乘法同态加密算法、Goldwasser-Micali加法同态加密算法和RSA乘法同态加密算法。这里以Paillier加法同态加密算法为例介绍加/解密过程。

1. 密钥生成
   1. 选择两个大的素数，
   2. 计算，以及
   3. 选择一个整数，使得即二者互素，其中
   4. 公钥为，私钥为
2. 加密(使用公钥)
   1. 选择一个随机数作为概率性加密的随机源
   2. 明文对应密文为
3. 解密(使用私钥)
   1. 密文对应的明文为

以上便是利用Paillier加法同态加密算法生成密钥、加密和解密的具体过程，其中是指和的最小公倍数，是指和的最大公约数。该算法的安全性建立在大整数分解问题的困难性上，即我们无法将大整数进行分解得到两个素数因子、。该算法的正确性是由有限域中元素的众多性质决定的。

全同态加密

半同态加密算法仅支持密文上的某一种运算，但机器学习场景的计算过程是相当复杂的，比如某些非线性激活函数。如果想在数据的密文状态上完成非线性激活函数的运算，那么半同态加密算法无法保证结果的正确性，因此便产生了对全同态加密算法的需求。

全同态加密算法是指在不解密的情况下，可以进行任意次的加法和乘法操作，同时保证在解密后与明文做相同的结果是相等的。从理论上讲，能够进行任意次的加法和乘法操作，便意味着可以使用电路等方法实现其他任意复杂的运算。但由于这个过于理想的属性，从半同态加密算法到全同态加密算法的发展道路不是一帆风顺的，目前同态加密的实际应用依然以半同态加密为主。