同态加密如何计算密文

本文目录导读：

1. 加法同态加密
2. 部分乘法同态加密
3. 全同态加密
4. 总结：如何计算密文？

直接在密文上进行计算，其计算结果解密后，与在明文上直接进行相同计算的结果一致。

它可以实现：Decrypt( E(a) ⊕ E(b) ) = a + b（加法同态）或 Decrypt( E(a) ⊗ E(b) ) = a * b（乘法同态）。

具体的计算方式取决于使用的是哪种同态加密方案，以下是三种主流类型的计算原理和典型例子：

加法同态加密

这是最常见的一类,典型代表是 Paillier 算法，它只支持加法运算，但效率极高。

计算原理（模乘即加法）：

• 加密： 明文 m 被加密为密文 c = g^m * r^n mod n^2（r 是随机数）。
• 密文计算（加法）： 要计算 m1 + m2 的密文，你需要将两个密文相乘：
  • c_sum = c1 * c2 mod n^2
• 解密结果： 对 c_sum 进行解密，得到的结果就是 m1 + m2。
  • Dec(c1 * c2) = m1 + m2

数学解释： 因为 c1 = g^m1 * r1^n，c2 = g^m2 * r2^n，c1 * c2 = g^(m1+m2) * (r1*r2)^n，解密过程会忽略随机数部分，直接提取出指数上的 m1+m2。

例子（Paillier）：

• 明文：m1 = 5, m2 = 3
• 加密后：E(5) 和 E(3) （两个非常大的数字）
• 同态计算：E(5) * E(3) （执行一次模幂乘法）
• 解密结果：8

部分乘法同态加密

典型代表是 ElGamal 算法（变种）或 RSA（教科书版，但不安全需要填充），它们支持乘法。

计算原理（模乘即乘法）：

• 密文计算（乘法）： 要计算 m1 * m2 的密文，你需要将两个密文的特定部分相乘。
  • 在 ElGamal 中：c = (c1, c2)，密文乘积为 (c1_1 * c1_2, c2_1 * c2_2)。
• 解密结果： 得到 m1 * m2。

全同态加密

这是最强大也最复杂的类型（如 BFV， BGV， CKKS 方案），它同时支持任意次数的加法和乘法，计算不再是简单的模乘，而是涉及多项式环上的计算。

计算原理：

• 原始明文： 数字（如 a）会被编码成一个高次多项式（a(x) = a_0 + a_1*x + ...）。
• 加密： 对这个多项式加上噪声（随机的小多项式）并用公钥加密，得到一组多项式系数。
• 密文计算（加法和乘法）：
  • 加法： 将两个密文的多项式系数直接相加（c_add = c1 + c2）。
  • 乘法： 将两个密文多项式进行卷积（c_mul = c1 * c2），这是最耗时的操作。
• 关键问题（噪声膨胀）： 每次乘法都会使密文中的“噪声”急剧增长，当噪声超过一定阈值，解密就会失败。
• 解决方案（Bootstrap，即自举）： 当噪声太大时，通过“重加密”技术，在不解密的情况下把噪声“压缩”回很小的水平，从而允许进行无限次计算。

例子（BFV方案）：

• 明文：a = 5, b = 3
• 加密后：E(5) 和 E(3) （两个包含很多数字的向量）
• 同态加法：E(5) + E(3) （向量对应元素相加）
• 同态乘法：E(5) * E(3) （向量做张量积后进行密钥交换和重线性化）
• 解密结果：8 和 15

如何计算密文？

一句话总结：

• Paillier 同态： 密文相乘 = 明文相加。
• 全同态加密： 密文向量相加/相乘 = 明文向量相加/相乘（但需要处理噪声膨胀）。