白露 | 可算不可见的加密策略

1978年，Rivest、Adleman 和 Dertouzos 三位密码学巨擘首次提出了隐私同态（privacy homomorphisms）的概念^[1]。他们设想了一个使用商业分时服务来存储贷款记录的场景。在这个场景中，为了保护用户的隐私，用户的贷款数据是被加密存储的。贷款公司希望对加密的贷款数据做运算， 从而获得和贷款金额有关的数据信息，如还未偿还的贷款金额平均值等。

让我们用简化的语言来描述同态加密的基本原理。首先，密钥生成算法根据安全参数  生成公私钥对  。记明文空间为  ，密文空间为中有一组明文，分别是  ，它们通过加密算法  变换成密文空间  中的一组密文  。同样，密文可以通过解密算法  恢复为明文。拥有私钥  的用户希望计算  的值，其中  为明文空间上的  元运算（operation），例如加法或乘法等。但由于种种原因（如本地算力不足，或者需要获得某项服务）只能将计算过程交给另一个计算方来实施，用户只执行加解密操作。为了保护隐私，用户向计算者告知密文  ，而非明文。计算方在密文上执行评估（evaluate）算法  ，并将计算结果  返回给用户。同态加密的性质保证在密文上执行评估算法后，对运算结果的解密就是明文的运算结果，即  。这样，用户便可以在不泄漏明文  的信息的同时，借助计算方的算力获得  。整体流程如下图所示。

一些加密方案天然具有部分的同态性质，例如 RSA。在 RSA 中，对于明文  ，公钥  ，私钥  ，加密方计算密文  ，解密方计算  。对于两个密文  ，计算方可以计算  的密文  。因为  ，这便实现了乘法同态。

然而，我们希望同态加密系统在运算方法上的限制尽可能少（例如不仅限于只对乘法同态），可以在不解密的条件下对加密数据进行任何可以在明文上进行的运算，这便是全同态加密（fully homomorphic encryption）。在构造全同态加密方案的过程中，为了保障加解密的安全性，会向密文中注入一些噪声。但随着在密文上运算次数的增加，密文中的噪声也会不断累积，当噪声超过某个阈值后，将会导致解密失败。这个问题是前人设计有效方案的瓶颈。

2009年，Craig Gentry 在论文^[2]中提出了首个有效的全同态加密方案，通过神奇的 Bootstrapping 操作，可以限制密文中噪声的增长，避免解密失败。这种操作的原理非常巧妙：假设我们用公钥  对明文  加密，得到  ，此时密文中的噪声较低。当我们执行某个运算  对应的 evaluate 算法后，获得了  的密文  ，此时密文中的噪声较高。既然我们能对密文执行任意可以在明文上进行的运算，那么可以用另一对公私钥  对私钥  和含有高噪声的密文  再做一次加密，然后对加密结果  和  做解密同态运算，这样便得到了只含有低噪声的密文  。通过这种方法，可以刷新密文中的噪声。

在当下，同态加密已经在云计算、隐私保护机器学习、金融交易、医疗数据共享等许多领域展现出广泛的应用前景。同时，它也面临着非通用计算、计算开销大、暴露运算逻辑等问题和挑战。这些挑战将推动同态加密技术朝着更加成熟可靠的方向发展，满足更多应用场景中的隐私和安全需求。

[1] Rivest, R. L., Adleman, L., & Dertouzos, M. L. (1978). On data banks and privacy homomorphisms. Foundations of secure computation, 4(11), 169-180.

[2] Gentry, C. (2009). Fully homomorphic encryption using ideal lattices. In Proceedings of the forty-first annual ACM symposium on Theory of computing (pp. 169-178).

文 | 郑宇森

图 | 朱成轩

PKU daGAME Lab