全同态加密释疑（二）：一个技术

陈智罡

在全同态加密（Fully Homomorphic Encryption）方案中，有一个非常重要技术：同态解密。

为什么要同态解密，前面说过噪音问题是实现全同态加密方案的最大障碍。Gentry在实现全同态加密方案时，注意到可以在Evaluate算法中执行自己的解密函数，那么输入的数据是什么呢？

解密函数当然输入的是密钥sk和密文c。但是不要忘了Evaluate算法是如何定义的。Evaluate算法是对输入的密文c₁,c₂,…执行函数 f 的操作，也就是对密文进行计算，其实隐含在其中的本质是对密文做同态计算，即计算后的密文解密后要等于对明文做同样的计算，如果这点做不到，那么Evaluate算法即使能对密文做很多次运算，也是没有意义的，这点一定要清楚。

这就是两种形态，明文态和密文态，两种形态对应的是同一个计算电路。在明文态，输入电路的是明文，而这些明文都是位（因为是布尔电路）。在密文态，输入电路的就是把每一个明文变成密文就可以了（算术电路）。这是我的独家比喻，版权所有。

而现在如果 f 是解密函数，那么输入的密文是什么呢？

只要看看明文态的时候输入的什么就知道了。

在明文态，对于解密电路，输入的肯定是密钥sk的每一位二进制位，以及密文c的每一位二进制位，因为是布尔电路，所以输入的数据都要化成二进制位的形式。

好了，现在在密文态，相应的把明文位变成密文就可以了，原来是一个位的地方现在变成了一个密文，那么将这些密文输入到解密电路中，结果是什么呢？是一个密文，这个密文解密后等于在明文态对明文做同样计算的结果。

现在我们关心的是这个从解密电路里出来的新密文和原来的密文c之间有什么关系？

这两个密文对应的是同样的明文。

而我们关心的是两个密文的噪音一样么？

肯定是不一样的，因为密文计算的噪音会随着计算次数不断增长。而从解密电路里出来的密文的噪音是一个固定值，是保持不变的。惊讶吧？

我们希望的是什么？是解密电路里出来的密文的噪音比原密文的噪音小么？

NO！我们要求没有这么高。我们只要求解密电路里出来的密文的噪音，还允许再进行一次乘法计算就可以了。

为什么？因为如果上面的要求成立的话，那么每次密文计算前，只要通过同态解密，出来的密文就可以保证再进行一次计算，不断循环下去，就可以做无限次计算了。当然要想做无限次计算还需要一个假设条件就是：循环安全。如果不做这个假设，我们只能做深度为L的电路计算。总之能够保证对密文做我们想要的计算了。

所以同态解密这个技术，是实现全同态加密的一个关键技术，Gentry就通过它实现了全同态加密。

要想使用同态解密，必须在Evaluate算法中能够执行自己的解密函数才可以。很多人都纳闷，解密函数不就是计算一下么，例如在整数方案里解密函数就是：(c mod p) mod2，在LWE或环-LWE上解密函数是：(<c, s> mod q) mod 2，难道不能够执行这些函数？

事情往往没有想象的那么简单，且听下回分解。