全同態加密釋疑（一）：四個演算法（2）

繼續說全同態加密中的其他三個演算法。

Enc演算法（加密）和我們平常意義的加密是一樣的，但是在全同態加密的語境里，使用Enc演算法加密的密文，一般稱之為新鮮密文，即該密文是一個初始密文，沒有和其他密文計算過。所以新鮮密文的噪音稱之為初始噪音。這個相當重要。

Dec演算法（解密）也和我們平常理解的一樣，就是對密文的解密，但是這裡解密演算法不僅能對初始密文解密，還能夠對計算後的密文解密。但是由於部分同態加密方案中密文存在噪音，例如在整數上的全同態加密方案里，密文乘積的噪音是噪音之積，密文加法的噪音是噪音之和。所以當密文計算到一定程度，其噪音將超過上限，所以對這樣的密文解密將可能失敗。全同態加密的關鍵就是對噪音的控制，使之能對任何密文解密。

最後一個演算法：Evaluate演算法（密文計算），這個演算法是整個全同態加密四個演算法中的核心。可以做個這樣的比喻：前面三個演算法是大樓的地基，後面這個Evaluate演算法就是大樓。這個比喻在後面會體會到它的用意。密文的計算是在電路里進行的，電路是分層的，電路深度越深，層數越多，密文就能夠進行更多次的計算。隨便提一句，密文計算的次數等於電路深度的對數。什麼是計算次數？例如c1*c2，就是進行了一次計算，次數為2，c1*c2*c3就是進行了兩次計算，次數為3。在全同態加密中，我們一般用乘法次數來衡量計算次數，這是因為乘法的噪音比加法噪音增長的快很多。

Evaluate演算法有三個輸入，第一個輸入是計算公鑰Evk，就是我們在上次博文里講到的。Evk可以沒有。第二個輸入是函數f，就是Evaluate演算法所要執行的函數，可以是任意函數，因為全同態加密的目標就是對密文能夠進行任意計算。當然這個函數也可以是「解密函數」，Gentry通過觀察發現了一個秘密，等會我們說。第三個輸入是密文，理論上可以有無窮多個密文，但是這是不可能的。

所以Evaluate演算法就是將密文輸入到函數f里進行計算。我們知道在全同態加密的方案里，密文都是含有噪音的，密文的計算會導致噪音的增長，如果把函數f表示成電路，那麼Evaluate演算法實際上只能夠對有限深度L的電路進行計算，超過這個深度L的電路就不行了。所以我們把這樣的方案稱之為部分同態加密方案。由此可見Evaluate演算法的重要性，全同態加密就靠它了。還記得剛才的比喻么？Evaluate演算法相當於大樓，這個大樓的層數是有限的，而全同態加密的目標是無限高！

所以噪音問題導致了Evaluate演算法不能夠對任意電路（函數）進行計算。

而全同態加密追求的就是Evaluate演算法能夠對任意電路進行計算，怎麼辦？那只有控制噪音問題了。如何控制噪音呢？下回分解。