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

作者：史蒂文·岳

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

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

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

全同態加密是什麼

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

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

加密體系回顧

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

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

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

![wFPu2NAgxAMjFDBuCMJAv8E1OA4mMINnrkCjZnq7.png](https://img-cdn.gateio.im/resized-social/moments-40baef27dd-3af0f1d6-dd1a6f-69ad25a "7127dd-3af0f1d6-dd1a6f-69ad25a "7111159711dfb25a6f-69ad291111 月的常見朋友有所了解一些加密演算法，比如說AES，RSA等等。大家一定也會知道一般來說加密體系分為兩種：對稱加密體系和非對稱加密體系。我們在這裡描述的三個步驟，其實通用於任何加密體系。如果是對稱的，那麼加密解密用的金鑰就是一樣的。如果是不對稱的體系的話，那麼加密用的就是公鑰（Public Key），然後解密用的是不一樣的私鑰（Private Key）。

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

![fO7JxUOZ3Zht6WdFjAq707ujysOoGIFgg5q9MpLT.png](https://img-cdn.gateio.im/resized-social/moments-40baef27dd-994bf17838-resized-social/moments-40baef27dd-994bf17838-resized-social/moments-40baef27dd-994bf17838-dd1a6f-69ad

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

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

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

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

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

![Fj2EndoBiFhIsValMYML9ECLXNVNvICrViCZKuXf.png](https://img-cdn.gateio.im/webp-social/moments-40baef27dd-27b3a846d2-dd1a6f-69ad2a.webp“7dd-27b3a846d2-dd1a6f-69ad2a“7111561”

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

舉個例子：匿名投票系統

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

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

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

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

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

不過到這裡，我們應該可以感受到同態加密演算法的強大了。我們可以這樣理解：透過同態加密演算法，使用者可以與一個不可信的遠端伺服器（雲端）進行某種安全代理運算（Secure Delegated Computation）。使用者可以透過同態加密的技術來把自己敏感的隱私輸入加密後託付給雲端，然後雲端可以在加密過後的資料上進行一定程度的運算，最後得到加密過後的使用者想要的結果，並且返還給用戶。最後用戶就可以用解密金鑰來開啟得到的結果了。在整個協定中，被代理方（雲端）始終無法看到任何和私密輸入有關的有用資訊。

### 同態加密系統的分類

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

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

部分同態加密（Partially Homomorphic Encryption)

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

![p7lpcrDyd7aW65Y7Ml4fsEonTmdU1YXBOeMxArVm.png](https://img-cdn.gateio.im/resized-social/moments-40baef27dd-a13f57e8ee-dd1a6f-69ad26a

![UgXzAmhq1SIpMnSeB547iLTlcb9DPX1Hg6tyyVoS.png](https://img-cdn.gateio.im/resized-social/moments-40baef27dd-6189ebe18d-dd1a6f-69ad

![ShHPzmYUSKbxX6nQLOfEE2WuPQ0OrMQkmqBtn7ka.png](https://img-cdn.gateio.im/resized-social/moments-40baef27dd-bd36db2f3a-dd1a6f-69adbaef27dd-bd36db2f3a-dd1a6f-69adbaef27dd-bd36db2f3a-dd1a6f-69ad2aef27115677”

![T6UlPMEcjBgcQOFKJNrDvhj6qHqNKmu5ol7aljpd.png](https://img-cdn.gateio.im/resized-social/moments-40baef27dd-e7b52bc079-dd1a6f-69adbaef27dd-e7b52bc079-dd1a6f-69addd1a6“19ad

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

近似同態加密（Somewhat Homomorphic Encryption）

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

部分同態加密的下一階段是近似同態加密，這階段距離我們想要實現的全同態更近了一步。如果我們有近似同態加密演算法的話，那麼我們就可以在密文上同時計算加法與乘法了。但要注意的是，正因為這一階段是近似同態（Somewhat Homomorphic）的，所以可以做的加法和乘法次數非常有限，可以計算的函數F 也在一個有限的範圍內。

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

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

![gqJcO2PUzQo6WkoQd9BOEIVNPY8Tza9nEQK80OaQ.png](https://img-cdn.gateio.im/resized-social/moments-40baef27dd-5bde0513c3-dd1a6f-69ad

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

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

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

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

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

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

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

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

全同態加密體系的定義

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

![DvDXf81yZmyRQmyezLQWir7IQDX0unUyIbliRqH8.png](https://img-cdn.gateio.im/resized-social/moments-40baef27dd-7a10658379-dd1a6f-69adbaef27dd-7a10658379-dd1a6f-69adbaef27dd-7a10658379-dd1a6f-69adaef27dd-15747”

![TsJed4GXWhn1UB5RvP6LRiWzZdkAGy0cCOB0N53f.png](https://img-cdn.gateio.im/resized-social/moments-40baef27dd-076bcfd24a-resized-social/moments-40baef27dd-076bcfd24a-dd1a6f-69ddad”

![0YcdqVZhD3w1iTajX3SQFxuPsCgZDebkkm08ViRK.png](https://img-cdn.gateio.im/resized-social/moments-40baef27dd-77e18d667a-ddd1

![R00RmzMDQTIXnncS5LGyiekR1K78zRfx9QtiY9q1.png](https://img-cdn.gateio.im/resized-social/moments-40baef27dd-77b635bb2b-dd1a6f-69ad

## 全同態加密的歷史回顧

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

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了。

在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並分享計算的結果。

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