我們都知道，如果要構建一個加密系統，往往都需要一個金鑰（Key）。透過這個金鑰，我們可以一頭把明文的資訊加密成密文，然後在另一頭透過金鑰再把密文變回原來的樣子。如果沒有這個Key的話，其他的人很難知道我們到底傳遞了什麼資訊。
上文的圖例基本展示了所有常見加密體系的全貌。所有的加密體系，如果用比較正式的描述方法，無疑是做了三件事：
對加密演算法有所瞭解的朋友，肯定會知道常見的一些加密演算法，比如說AES，RSA等等。大家肯定也會知道一般來說加密體系分為兩種：對稱加密體系和非對稱加密體系。我們這裡描述的這三個步驟，其實通用於任何加密體系。如果是對稱的，那麼加密和解密用的金鑰就是一樣的。如果是非對稱的體系的話，那麼加密用的就是公鑰（Public Key），然後解密用的是不一樣的私鑰（Private Key）。
在密碼學研究中，每當我們看到一個新的系統的定義之後，接下來往往都要陳述這個系統所應具有的屬性（Properties）。
首先，我們第一個要實現的屬性是正確性（Correctness）。正確性代表說，如果我擁有一個正確的金鑰，那麼我就可以透過解密演算法Decryption來把密文還原成原文。我們往往都使用概率的方法來表示解密的成功率：
上面的等式代表了，如果我們擁有正確的金鑰，那麼解密演算法可以還原加密演算法生成的密文的機率是100%。
我們要實現的第二個屬性是語義安全（Semantic Security）。
具體對於語義安全的定義，我們在這裡不多做解釋了。但是我們可以理解為，如果我們擁有任意兩個不同的原文所對應的密文，那麼我們是無法區分到底哪個密文是對應了哪個原文的：
瞭解完加密體系是怎麼一回事之後，我們可以來關注一下這個看似像隨機生成的亂碼一樣的密文。我們都知道，光看密文字身，我們什麼資訊都不會得到。但是這是不是就代表，如果沒有金鑰只有密文，我們什麼都不能做了呢？
答案我們都知道：其實並不是。
對於這種屬性，我們稱之為加法同態。意思就是說，加密過後的密文與以前的原文保持著一種微妙的代數關係。如果我們把密文累加起來，我們就可以獲得把原文相加起來加密過後的新密文。同理可得，加法同態之餘，還存在著乘法同態的加密演算法。一個乘法同態的演算法生成的密文，我們可以相乘起來，然後獲得原文之間相乘之後的結果所對應的密文。整個過程中，我們不需要知道任何和金鑰有關的資訊，純粹只是把看似像隨機亂碼的密文組合起來。
舉個例子：匿名投票系統
下面，我們來舉一個例子，生動的描述一下同態加密的實用性。
我們都知道線上投票是怎樣的——假如一個公司的老闆想要發起一波投票，選擇公司是否要採取996的制度。那麼老闆可以讓IT設定一個伺服器，讓員工提交自己的選擇：投0代表不想，投1代表想。最後投票階段結束之後，老闆就可以把所有的投票加在一起。如果最後所有票的總和超過了員工人數的一半，那麼公司就會開始996。
這個投票機制看起來很簡單，但是有一個很大的隱私問題：假如老闆心中就想讓全員996，然而只是故意發起了這個投票來釣魚執法，看看哪個員工不願意加班，那麼老闆可以悄悄委託自己的小弟在網路上偷聽，把每一個員工提交的選擇都記錄下來，最後看到底是誰投了0。這樣一來，員工都十分害怕，不敢吐露自己的心聲。
如果我們可以使用加法同態的加密演算法的話，那麼這個問題就很好解決了。
這樣一來，我們就成功的用加法同態的特性實現了投票計數系統，並且老闆就算派人監聽網路，也只能看到加密過後的密文，並沒有辦法知道每個人到底投了什麼票。
當然，這個系統還非常的不完整，比如IT部門可以直接幫助老闆把每個人的投票解密開來，然後記錄成一個文件。對於這個問題還有別的密碼學工具可以幫我們來解決。由於篇幅原因就在這裡不多說明啦。
不過到這裡，我們應該可以感受到同態加密演算法的強大了。我們可以這樣理解：透過同態加密演算法，使用者可以與一個不可信的遠端伺服器（雲端）進行某種安全代理計算（Secure Delegated Computation）。使用者可以透過同態加密的技術來把自己敏感的隱私輸入加密後託付給雲端，然後雲端可以在加密過後的資料上進行一定程度的計算，最後得到加密過後的使用者想要的結果，並且返還給使用者。最後使用者就可以用解密金鑰來開啟得到的結果了。整個協議中，被代理方（雲端）始終都無法看到任何和私密輸入有關的有用資訊。
同態加密體系的分類
大致瞭解了兩種最基礎的同態性質之後，其他的概念就變得非常容易理解了。如果系統性的來看，同態加密體系大致上被分為四類：部分同態、近似同態、有限級數全同態與完全同態。
下面，我們就來依次看一下每一個類別的具體定義。
部分同態加密 （Partially Homomorphic Encryption)
同態加密最初級的階段被稱為部分同態加密，定義就是密文只有一種同態特性。這一階段就包括了我們上文所描述的加法同態與乘法同態兩種模式。
ElGamal加密實現方法大致如下：
同理我們也可以應用於乘法同態加密的演算法上——F就只能把所有的私密輸入相乘起來，但是沒有辦法做任何線性組合（加法）。乘法同態的例子其實也非常常見，我們大家都熟悉的RSA加密就是一個乘法同態的系統。
RSA加密的實現方法大致如下：
我們就得到了這兩條訊息相乘之後所對應的密文！這就是乘法同態性質了，我們可以接著這條密文繼續往上疊加新的密文，這樣一來我們就可以得到密文之間任意的相乘。
近似同態加密（Somewhat Homomorphic Encryption）
就如同我們在上一段所說，如果我們又想讓私密輸入相乘，又想得到它們之間的線性組合的話，單純的部分同態加密演算法（RSA，ElGamal）是無法完成的。所以我們就需要來到下一階段。
部分同態加密的下一階段是近似同態加密，這一階段距離我們想要實現的全同態更近了一步。如果我們有近似同態加密演算法的話，那麼我們就可以在密文上同時計算加法與乘法了。但是需要注意的是，正因為這一階段是近似同態（Somewhat Homomorphic）的，所以可以做的加法和乘法次數非常有限，可以計算的函式也在一個有限的範圍內。
近似同態加密這一階段常見的例子並不多，如果說最好理解的例子的話，那就應該是基於配對（Pairing）的迴圈群加密演算法了。
上文我們簡單的討論過基於普通迴圈群的ElGamal加密演算法。我們都知道這一演算法是加法同態的，也就是說可以得到任意密文之間的線性組合。事實上，在某些特殊的迴圈群中，我們還可以找到一些薄弱的乘法同態性質。
這樣一來，我們就變相的得到了前兩個值的冪之間的乘積組合！再搭配ElGamal加密中可以把兩個值的冪做線性組合的屬性的話，那麼我們就得到了一個全同態的系統了。
事實上，現實並沒有那麼美好，因為Pairing這一特殊屬性並不會出現在所有的迴圈群當中。所以如果我們把兩個可以做Pairing的群中的值透過Pairing相乘起來，對映到了一個新的群GT當中之後，那麼新的群並不一定能找到對應的Pairing屬性！
這也就是說，透過擁有Pairing屬性的迴圈群，我們只能做非常有限的乘法計算。假如說我們當前的群支援Pairing，但是新的對映群gt並不支援任何Pairing，那就代表瞭如果我們要基於當前的體系進行同態加密運算，可以運算的函式F雖然可以包涵任意的線性組合，但是隻能包涵最多一層乘法在裡面。
這一侷限性證明了這個系統是近似同態的，因為我們不能計算任意邏輯和深度的函式F。
有限級數全同態加密 （Fully Leveled Homomorphic Encryption）
來到下一個階段之後，我們距離全同態的目標更進一步了。
這一階段被稱之為有限級數全同態加密。在這一階段的話，我們已經可以對密文進行任意的加法乘法組合了，沒有任何對於次數的侷限性。
但是之所以被稱之為有限級數全同態的原因是，這個階段的演算法會引入一個新的複雜度上限L的概念，這一複雜度上限約束了函式F的複雜度。如果我們可以把F用二進位制電路C來表示的話，那麼C的深度和大小一定要在L的範圍之內，即：
也就是說，如果L相對來說比較大的話，那麼我們就可以進行各種各樣較為簡單（低複雜度）的同態運算了。有限級數同態加密的演算法也是下一階段全同態加密的奠基石，當我們實現了L複雜度以內的全同態之後，實現完全同態也不遠了。
我們可以瞭解一下這個複雜度的上限L是怎麼來的。首先，我們可以想象一下，假如有一個全同態加密的演算法，可以對密文進行任何的加法與乘法的運算。但是這個演算法在加密的時候會在密文裡面加入一定的隨機噪音。
當噪音在可控範圍內的時候，那麼解密演算法就可以很容易從密文還原回原文。但是當我們疊加密文在一起進行同態計算的時候，每一個密文裡面自帶的噪音會被疊加擴大。如果我們只是對密文進行比較簡單的邏輯，那麼疊加起來的噪音還在一個可以接受的範圍。但是如果我們過於複雜地堆疊密文在一起，那麼一旦噪音的範圍超過了臨界值，那麼就會徹底的覆蓋掉原來的原文，從而導致解密會失敗。
在這個場景中，這個同態加密系統可以接受的噪音上限轉換為疊加的邏輯的複雜度的話就是L了。這就是為什麼我們只可以進行復雜度小於L的計算，因為一旦複雜度超過L，我們就再也無法還原回原來的原文了。
全同態加密 （Fully Homomorphic Encryption，FHE）
千呼萬喚使出來，最後就到我們拭目以待的全同態加密（FHE）了。
就像名字所說的一樣，一個全同態加密的系統沒有任何計算方法的限制，我們可以在沒有金鑰的情況下，把密文任意的組合起來，形成新的密文，並且新的密文，無論計算的複雜度，都可以完美的被還原成原文。
當我們達到這一階段的時候，之前提到的安全代理計算就變得可行了。如果可以找到一個效率比較高的全同態加密體系的話，我們可以安全的把所有本地的計算全部代理到雲端，並且不會洩露任何一丁點資料！
全同態加密體系的定義
在開始下文對於全同態歷史的討論之前，我們可以系統性的定義一下全同態系統的正式定義。一個全同態加密系統，一共擁有四個演算法：
全同態加密體系的性質
現在我們來看看這個系統的屬性（Properties）。首先，這個體系必須得是正確的（Correctness）。
這一類全同態系統還有一個更大的弊端，也就是最後得到的密文並無法完全掩蓋住運算電路F的具體細節。在這個醫院的使用場景中，有可能醫院自己最值錢的就是這套資料分析系統。如果白白的把自己的F發回給了使用者，那自己的辛苦勞動成果就被別人輕易竊取了。
綜上所述，只要滿足正確、語義安全、簡短這三個要素，我們就擁有一個有意義（Non-trivial）的全同態加密體系了。
全同態加密的歷史回顧
在開始學習全同態加密演算法到底是怎麼實現的之前，我們不妨來看看全同態加密這個概念到底是怎麼來的。
FHE（全同態）的概念其實在上世紀70年代末就已經被提出了。1978年，密碼學界的幾個大牛Rivest，Adleman和Dertouzos在他們的論文On Data Banks and Privacy Homomorphisms中第一次提到了對於密文進行一定的計算，可以間接地對原文進行操作的系統構想。到後來這一想法就被重新總結命名為全同態加密了。
由此可見，全同態加密這一概念已經被提出了很久了。令人驚訝的是，1976年，也就是論文發表的兩年前，Diffle-Hellman金鑰交換協議才剛剛被提出！由此可見密碼屆大牛的想象力還是非常豐富的。
當FHE的概念被提出來之後，整個學術界都為之所動，開始了長達幾十年的搜尋，試圖找到一個擁有全同態性質的完美演算法。但是這幾十年下來，人們試遍了所有可以想到的選擇，但是找不到一個又能滿足全同態所有條件，並且安全性可以被輕易證實的選項。
直到2009年，在斯坦福讀書的PhD Craig Gentry突然靈光一現，攻破了FHE演算法的難關。在他的博士畢業論文中，他第一次給出了一個合理並且安全的全同態加密系統！這一系統基於理想格（ideal lattice）的假設。Gentry09提出來的全同態系統，我們往往稱之為第一代全同態加密系統。
在Gentry的論文中，他還提到了一個至關重要的概念叫做Bootstrapping。Bootstrapping是一種對於密文的特殊處理技巧，處理過後竟然可以把一個噪音接近臨界值的密文“重新重新整理”成一個噪音很低的新密文。透過Bootstrapping，一個有限級數的系統的噪音可以永遠不超過臨界值，從而變成了全同態的系統。這樣一來，我們就可以同態計算任意大小的了。
在Gentry的重大突破之後，整個密碼圈又一次陷入了瘋狂，大家都開始爭相基於Gentry提出的想法尋找更加高效率和全能的全同態體系。
在2011年的時候，兩位大佬Brakerski和Vaikuntanathan提出了一個新的全同態加密體系，這一體系基於格（lattice）加密的另一種假設Learning With Errors（LWE）。在同一年，Brakerski，Gentry與Vaikuntanathan這三人一起把這個體系做完了，並且正式發表出來。他們發明的全同態系統簡稱為BGV系統。BGV系統是一個有限級數的同態加密系統，但是可以透過Bootstrapping的方式來變成全同態系統。BGV系統相比起Gentry09提出的系統，使用了更加實際一點的LWE假設。一般來說我們都把BGV系統稱之為第二代全同態加密系統。
2013年，Gentry又捲土重來了。Gentry，Sahai和Waters三個大佬推出了新的GSW全同態加密系統。GSW系統和BGV相似，本身具有有限級數全同態性質，基於更加簡單的LWE假設，並且透過Bootstrapping可以達到全同態。我們一般把GSW系統稱為第三代全同態加密系統。
2013年之後，密碼圈基本上就百花齊放了。基於原來的三代全同態系統之上，出現了各種各樣新的設計，致力於最佳化和加速BGV與GSW系統的執行效率。IBM基於BGV系統開發了一個開源的全同態運算庫HElib，並且成功的移植到各大移動平臺上。與此同時，還有另外一個開源專案TFHE也非常值得注意。TFHE是基於GSW系統，又加以了各種最佳化與加速，現在也非常的有名。
在開發傳統的全同態庫之外，也有很多團隊在研究如何透過GPU，FPGA，ASIC等異構硬體來更好的加速全同態加密演算法的計算。比如cuFHE就是一個比較有名的基於CUDA的GPU加速全同態加密系統。
站在今天的角度上，一路看來，全同態體系的大門被Gentry大神敲開已經過去了11年了。現在業界對於FHE的研究百花齊放，不少人都在不同的角度和應用需求上在研究全同態系統。直到今天，我們已經擁有了多種可行的FHE實現方法，但是現在大家還在不斷追求的是FHE系統運轉的效率。拿現在最前沿的FHE庫來說，在移動平臺上同態計算一些比較簡單的邏輯可能要少則花上幾十毫秒，多則花費幾十秒的時間。這些時間單位對於計算機系統來說是極其緩慢的。
如何可以讓FHE系統更加高效率的在異構平臺上執行，仍然是一個未解之謎。如果這道難題一旦被解決了，那麼把所有的電腦運算都轉為全同態，代理在第三方的雲端上進行計算，都是伸手可得的未來。
FHE與MPC的關係
在結束文章之前，我還想補充說明一下FHE與MPC之間的關係。MPC即Secure Multi-Party Computation，就是可信多方計算。通常代表的是有多方擁有自己的私密輸入，不想洩露給別人，但是他們想使用自己的輸入一起計算一個函式並分享計算的結果。
MPC其實已經是一個非常廣為人知，並且被研究了很久的一個領域了。自從上個世紀密碼學家姚期智推出了他的Garbled Circuits之後，MPC領域獲得了非常廣的認可，並且也有很多突破。現在我們已經擁有很多可以使用的MPC庫，並且也具有一定的執行效率了。
如果瞭解MPC的朋友，看到全同態加密系統的艱辛歷史之後，也許會有很多疑問：為什麼不可以直接透過一個MPC協議來代替全同態加密呢？
的確，一個MPC協議可以完全代替一個FHE協議。我們只需要把使用者和私密輸入作為一個協議中的一個Party，再把遠端的代理計算伺服器作為另一個Party，就滿足了MPC協議執行的條件，只需要透過一定的互動，就可以實現代理計算，並且伺服器也看不到私密輸入。
但是有很重要的一點我們忽略了：由於MPC是有互動性的，所以需要使用者和伺服器共同進行計算與交流才可以完成協議。這也就和FHE代理計算最根本的需求衝突了。如果使用者需要一直保持線上完成協議，並且也要付出一部分算力的話，那其實計算根本就沒有被“代理”出去，雙方只是為了資訊的安全性而在做更多的計算。這也說明了為什麼MPC領域已經得到重大突破了，但是FHE的領域仍然是一片未知，因為他們兩個系統解決的是完全不同的問題。
下一站：GSW全同態加密系統
看到這裡，想必大家已經對於全同態加密系統有了非常透徹的理解。
下一站，我們可以一起來學習一下前文提到的GSW全同態加密系統。雖然說這是全同態系統的第三代，但是我認為Gentry09，BGV，GSW這三套系統中用到假設最少，構造最簡單，並且最容易理解的就是GSW了。並且現在也有很多開源庫（如TFHE）就是基於GSW系統構建的。
由於篇幅原因，我們就在這裡結束這一篇文章吧。下一篇文章，我們可以首先學習一下GSW系統的基礎：基於格（lattice）的加密體系與LWE問題。一旦瞭解了LWE問題之後，GSW解決的問題就變得非常清晰了。
