初探全同態加密：FHE的定義與歷史回顧

作者：Steven Yue，原刊於作者知乎

前一陣子在斯坦福學習了CS355（高階密碼學）的課程。給我們上課的是Dan的三個PhD學生Dima Kogan，Florian Tramer和Saba Eskandarian。三個PhD講師各有特色，研究的方向也非常不同。Dima主攻隱私保護技術PIR（Private Information Retrieval），Florian主攻ML和區塊鏈方面的研究，而Saba主攻零知識證明。

CS355這一門課幾乎涵蓋了從古至今密碼學領域的所有內容。從最早的單向函數（One-way Function），到橢圓方程（ECC）和Pairing，最後到一些近幾年比較熱的MPC、零知識、私有信息檢索（PIR）、全同態算法等等。由於前兩天剛剛結課，趁着知識內容還在淺層記憶中沒有忘掉，整理了一波筆記。課程內容非常有趣，其余的內容以後有時間跟大家慢慢分享～

這一期，我們來講一講最近很火的全同態加密（FHE）與伴隨而來的格加密（Lattice-based Encryption）技術。

全同態加密是什么

相信很多朋友已經多少聽說過全同態加密（Fully Homomorphic Encryption/FHE）的大名了。近幾年對於個人隱私保護的話題越來越多，包括同態加密在內的一系列密碼學應用技術也得到了很廣泛的普及。

為了更好的了解這個話題，我想要再對全同態加密這個定義稍作介紹一下。

加密體系回顧

在开始之前，我們先溫習一下最最傳統的加密體系。

我們都知道，如果要構建一個加密系統，往往都需要一個密鑰（Key）。通過這個密鑰，我們可以一頭把明文的信息加密成密文，然後在另一頭通過密鑰再把密文變回原來的樣子。如果沒有這個Key的話，其他的人很難知道我們到底傳遞了什么信息。

上文的圖例基本展示了所有常見加密體系的全貌。所有的加密體系，如果用比較正式的描述方法，無疑是做了三件事：

對加密算法有所了解的朋友，肯定會知道常見的一些加密算法，比如說AES，RSA等等。大家肯定也會知道一般來說加密體系分為兩種：對稱加密體系和非對稱加密體系。我們這裏描述的這三個步驟，其實通用於任何加密體系。如果是對稱的，那么加密和解密用的密鑰就是一樣的。如果是非對稱的體系的話，那么加密用的就是公鑰（Public Key），然後解密用的是不一樣的私鑰（Private Key）。

在密碼學研究中，每當我們看到一個新的系統的定義之後，接下來往往都要陳述這個系統所應具有的屬性（Properties）。

語義安全的主要意義在於旁觀者無法區分兩條加密的消息。那么如果有入侵者竊聽網絡，看到了我發出的加密信息，只要我使用的加密體系是語義安全的，那么我就可以確信入侵者無法從密文中得到關於加密內容的任何信息。

滿足了上述兩條屬性之後，一個加密體系就變得健全啦。

同態加密：偶然的特殊性質

了解完加密體系是怎么一回事之後，我們可以來關注一下這個看似像隨機生成的亂碼一樣的密文。我們都知道，光看密文本身，我們什么信息都不會得到。但是這是不是就代表，如果沒有密鑰只有密文，我們什么都不能做了呢？

答案我們都知道：其實並不是。

對於這種屬性，我們稱之為加法同態。意思就是說，加密過後的密文與以前的原文保持着一種微妙的代數關系。如果我們把密文累加起來，我們就可以獲得把原文相加起來加密過後的新密文。同理可得，加法同態至於，還存在着乘法同態的加密算法。一個乘法同態的算法生成的密文，我們可以相乘起來，然後獲得原文之間相乘之後的結果所對應的密文。整個過程中，我們不需要知道任何和密鑰有關的信息，純粹只是把看似像隨機亂碼的密文組合起來。

舉個例子：匿名投票系統

下面，我們來舉一個例子，生動的描述一下同態加密的實用性。

我們都知道在线投票是怎樣的——假如一個公司的老板想要發起一波投票，選擇公司是否要採取996的制度。那么老板可以讓IT設置一個服務器，讓員工提交自己的選擇：投0代表不想，投1代表想。最後投票階段結束之後，老板就可以把所有的投票加在一起。如果最後所有票的總和超過了員工人數的一半，那么公司就會开始996。

這個投票機制看起來很簡單，但是有一個很大的隱私問題：假如老板心中就想讓全員996，然而只是故意發起了這個投票來釣魚執法，看看哪個員工不愿意加班，那么老板可以悄悄委托自己的小弟在網絡上偷聽，把每一個員工提交的選擇都記錄下來，最後看到底是誰投了0。這樣一來，員工都十分害怕，不敢吐露自己的心聲。

如果我們可以使用加法同態的加密算法的話，那么這個問題就很好解決了。

當然，這個系統還非常的不完整，比如IT部門可以直接幫助老板把每個人的投票解密开來，然後記錄成一個文檔。對於這個問題還有別的密碼學工具可以幫我們來解決。由於篇幅原因就在這裏不多說明啦。

不過到這裏，我們應該可以感受到同態加密算法的強大了。我們可以這樣理解：通過同態加密算法，用戶可以與一個不可信的遠程服務器（雲端）進行某種安全代理計算（Secure Delegated Computation）。用戶可以通過同態加密的技術來把自己敏感的隱私輸入加密後托付給雲端，然後雲端可以在加密過後的數據上進行一定程度的計算，最後得到加密過後的用戶想要的結果，並且返還給用戶。最後用戶就可以用解密密鑰來打开得到的結果了。整個協議中，被代理方（雲端）始終都無法看到任何和私密輸入有關的有用信息。

同態加密體系的分類

大致了解了兩種最基礎的同態性質之後，其他的概念就變得非常容易理解了。如果系統性的來看，同態加密體系大致上被分為四類：部分同態、近似同態、有限級數全同態與完全同態。

下面，我們就來依次看一下每一個類別的具體定義。

部分同態加密（Partially Homomorphic Encryption)

同態加密最初級的階段被稱為部分同態加密，定義就是密文只有一種同態特性。這一階段就包括了我們上文所描述的加法同態與乘法同態兩種模式。

我們就得到了這兩條消息相乘之後所對應的密文！這就是乘法同態性質了，我們可以接着這條密文繼續往上疊加新的密文，這樣一來我們就可以得到密文之間任意的相乘。

近似同態加密（Somewhat Homomorphic Encryption）

就如同我們在上一段所說，如果我們又想讓私密輸入相乘，又想得到它們之間的线性組合的話，單純的部分同態加密算法（RSA，ElGamal）是無法完成的。所以我們就需要來到下一階段。

部分同態加密的下一階段是近似同態加密，這一階段距離我們想要實現的全同態更近了一步。如果我們有近似同態加密算法的話，那么我們就可以在密文上同時計算加法與乘法了。但是需要注意的是，正因為這一階段是近似同態（Somewhat Homomorphic）的，所以可以做的加法和乘法次數非常有限，可以計算的函數 F$\mathrm{<span\; style="font-family:\; sans-serif;"> 也在一個有限的範圍內。</span>}$

近似同態加密這一階段常見的例子並不多，如果說最好理解的例子的話，那就應該是基於配對（Pairing）的循環群加密算法了。

上文我們簡單的討論過基於普通循環群的ElGamal加密算法。我們都知道這一算法是加法同態的，也就是說可以得到任意密文之間的线性組合。事實上，在某些特殊的循環群中，我們還可以找到一些薄弱的乘法同態性質。

這一局限性證明了這個系統是近似同態的，因為我們不能計算任意邏輯和深度的函數F。

有限級數全同態加密（Fully Leveled Homomorphic Encryption）

來到下一個階段之後，我們距離全同態的目標更進一步了。

這一階段被稱之為有限級數全同態加密。在這一階段的話，我們已經可以對密文進行任意的加法乘法組合了，沒有任何對於次數的局限性。

全同態加密（Fully Homomorphic Encryption，FHE）

千呼萬喚使出來，最後就到我們拭目以待的全同態加密（FHE）了。

就像名字所說的一樣，一個全同態加密的系統沒有任何計算方法的限制，我們可以在沒有密鑰的情況下，把密文任意的組合起來，形成新的密文，並且新的密文，無論計算的復雜度，都可以完美的被還原成原文。

當我們達到這一階段的時候，之前提到的安全代理計算就變得可行了。如果可以找到一個效率比較高的全同態加密體系的話，我們可以安全的把所有本地的計算全部代理到雲端，並且不會泄露任何一丁點數據！

全同態加密體系的定義

在开始下文對於全同態歷史的討論之前，我們可以系統性的定義一下全同態系統的正式定義。一個全同態加密系統，一共擁有四個算法：

全同態加密的歷史回顧

在开始學習全同態加密算法到底是怎么實現的之前，我們不妨來看看全同態加密這個概念到底是怎么來的。

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，一個有限級數的系統的噪音可以永遠不超過臨界值，從而變成了全同態的系統。這樣一來，我們就可以同態計算任意大小的F$\mathrm{<span\; style="font-family:\; sans-serif;">了。</span>}$

在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，就是可信多方計算。通常代表的是有多方擁有自己的私密輸入，不想泄露給別人，但是他們想使用自己的輸入一起計算一個函數 F$\mathrm{<span\; style="font-family:\; sans-serif;">並分享計算的結果。</span>}$

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解決的問題就變得非常清晰了。

鄭重聲明：本文版權歸原作者所有，轉載文章僅為傳播信息之目的，不構成任何投資建議，如有侵權行為，請第一時間聯絡我們修改或刪除，多謝。