全同态加密释疑（三）：为什么不能运行自己的解密电路

陈智罡

前面说过，要想降低密文计算带来的噪音，可以通过同态解密的方式得到一个新的密文，这个新密文的噪音是恒定的，所以使得我们可以进行下一次计算，每次计算后都通过同态解密约减噪音，就能够获得全同态加密了。然而同态解密是需要Evaluate算法能够运行自己的解密函数的，在早期的全同态加密方案中（Gentry09，DGHV），包括BV11方案如果最后一步不使用模维数约减的话，Evaluate都不能够运行自己的解密函数。

很多同学学到这里的时候，都很纳闷，解密函数不就是一些加法乘法模运算么，为什么计算不了，难道还有计算不了的函数？这个问题是问我的人最多的，今天给大家好好解释一下。

所谓的运行不了自己的解密函数，是有语境的，准确的说是“Evaluate算法不能够运行自己的解密函数”，而Evaluate算法的输入是什么？同态解密时，Evaluate算法输入的是解密电路，还有往解密电路里输入的一些密文，这些密文是由密钥和密文的每一位加密而成的，上次博文详细说过这事。那么Evaluate算法做的工作是什么呢？

Evaluate算法做的工作就是让这些密文在解密电路里计算，是密文的计算，记住了！由于密文计算过程会产生噪音，所以密文只能够进行有限次的计算，超过这个界就会产生解密的错误。所以如果解密电路的深度小于方案所允许计算的深度（这里方案所允许计算的深度指的是Somewhat同态方案的计算能力），那么就可以完成同态解密的工作。但是如果解密电路的深度大于方案所允许计算的深度，那么就悲催了，我们就不能够使用同态解密这个方法去降低密文的噪音。怎么办？

Gentry在他的论文里发明了一种方法叫“压缩解密电路”，就是把解密电路的深度降低，从而满足“解密电路的深度小于方案所允许计算的深度”，这样就可以使用同态解密技术了，方案就可以启动了！压缩解密电路是要付出代价的，同时需要一个假设“稀疏子集和问题”，该问题没有被很好的研究过，所以是假设。不过目前的方案已经不需要压缩解密电路了，例如BGV方案，Bra12方案，这些方案都能够运行自己的解密电路，所以不需要压缩的方法了。

同态解密的技术成就了全同态加密的诞生，然而其效率却非常低，所以后面诞生了模交换技术。至于什么是模交换技术，下回分解。