全同態加密釋疑（二）：一個技術

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

為什麼要同態解密，前面說過噪音問題是實現全同態加密方案的最大障礙。Gentry在實現全同態加密方案時，注意到可以在Evaluate演算法中執行自己的解密函數，那麼輸入的數據是什麼呢？

解密函數當然輸入的是密鑰sk和密文c。但是不要忘了Evaluate演算法是如何定義的。Evaluate演算法是對輸入的密文c1,c2,…執行函數 f 的操作，也就是對密文進行計算，其實隱含在其中的本質是對密文做同態計算，即計算後的密文解密後要等於對明文做同樣的計算，如果這點做不到，那麼Evaluate演算法即使能對密文做很多次運算，也是沒有意義的，這點一定要清楚。

這就是兩種形態，明文態和密文態，兩種形態對應的是同一個計算電路。在明文態，輸入電路的是明文，而這些明文都是位（因為是布爾電路）。在密文態，輸入電路的就是把每一個明文變成密文就可以了（算術電路）。這是我的獨家比喻，版權所有。

而現在如果 f 是解密函數，那麼輸入的密文是什麼呢？

只要看看明文態的時候輸入的什麼就知道了。

在明文態，對於解密電路，輸入的肯定是密鑰sk的每一位二進位位，以及密文c的每一位二進位位，因為是布爾電路，所以輸入的數據都要化成二進位位的形式。

好了，現在在密文態，相應的把明文位變成密文就可以了，原來是一個位的地方現在變成了一個密文，那麼將這些密文輸入到解密電路中，結果是什麼呢？是一個密文，這個密文解密後等於在明文態對明文做同樣計算的結果。

現在我們關心的是這個從解密電路里出來的新密文和原來的密文c之間有什麼關係？

這兩個密文對應的是同樣的明文。

而我們關心的是兩個密文的噪音一樣么？

肯定是不一樣的，因為密文計算的噪音會隨著計算次數不斷增長。而從解密電路里出來的密文的噪音是一個固定值，是保持不變的。驚訝吧？

我們希望的是什麼？是解密電路里出來的密文的噪音比原密文的噪音小么？

NO！我們要求沒有這麼高。我們只要求解密電路里出來的密文的噪音，還允許再進行一次乘法計算就可以了。

為什麼？因為如果上面的要求成立的話，那麼每次密文計算前，只要通過同態解密，出來的密文就可以保證再進行一次計算，不斷循環下去，就可以做無限次計算了。當然要想做無限次計算還需要一個假設條件就是：循環安全。如果不做這個假設，我們只能做深度為L的電路計算。總之能夠保證對密文做我們想要的計算了。

所以同態解密這個技術，是實現全同態加密的一個關鍵技術，Gentry就通過它實現了全同態加密。

要想使用同態解密，必須在Evaluate演算法中能夠執行自己的解密函數才可以。很多人都納悶，解密函數不就是計算一下么，例如在整數方案里解密函數就是：(c mod p) mod2，在LWE或環-LWE上解密函數是：(<c, s> mod q) mod 2，難道不能夠執行這些函數？

事情往往沒有想像的那麼簡單，且聽下回分解。