編者按：本文來自安比實驗室（ID：secbitlabs），Odaily經授權轉載。

編者按：本文來自

安比實驗室（ID：secbitlabs）

，Odaily經授權轉載。

編者按：本文來自

安比實驗室（ID：secbitlabs）

，Odaily經授權轉載。

二級標題

編者按：本文來自

安比實驗室（ID：secbitlabs）

，Odaily經授權轉載。

• 二級標題

• 前一陣子在斯坦福學習了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）。

首先，我們第一個要實現的屬性是正確性（Correctness）。正確性代表說，如果我擁有一個正確的密鑰，那麼我就可以通過解密算法來把密文還原成原文。我們往往都使用概率的方法來表示解密的成功率：

上面的等式代表了，如果我們擁有正確的密鑰，那麼解密算法可以還原加密算法生成的密文的機率是100%。

我們要實現的第二個屬性是語義安全（Semantic Security）。

具體對於語義安全的定義，我們在這裡不多做解釋了。但是我們可以理解為，如果我們擁有任意兩個不同的原文所對應的密文，那麼我們是無法區分到底哪個密文是對應了哪個原文的：

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

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

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

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

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

但是在眾多的加密算法當中，有一類算法生成的密文有一種特殊的同態屬性：假如我們使用加密算法得到了數字1 的密文，然後我們又得到了數字2 的密文。這個時候，如果我們把密文相加起來，恰恰是的密文！

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

舉個例子：匿名投票系統

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

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

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

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

首先，IT 可以先使用KeyGen 算法生成一對加密解密的鑰匙pk,sk，然後把公鑰分發給每個員工。

隨後，每個員工把自己的選擇（1 或0）通過加密算法加密成密文，然後把密文發送到IT 的服務器上：

最後，IT 部門可以把每個人的選擇全部加起來，得到一個組合的密文，並且把這個密文發給老闆。最後老闆用解密的密鑰打開這個密文，得到了最後的投票結果：

這樣一來，我們就成功的用加法同態的特性實現了投票計數係統，並且老闆就算派人監聽網絡，也只能看到加密過後的密文cti，並沒有辦法知道每個人到底投了什麼票。

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

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

同態加密體系的分類

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

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

部分同態加密（Partially Homomorphic Encryption)

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

如果放到之前說的安全代理計算的場景下看，假如我們有私密輸入，然後我們希望雲端可以幫我們計算(x1,x2,...)，那麼我們可以把雲端對於這些輸入做的計算使用函數來表示。

假如說我們可以通過一個加法同態加密的算法來計算的話，那麼代表了這個函數肯定就只能包含私密輸入的任意線性組合（加法運算）。一個可行的例子就是把各項私密輸入乘以一個常數，然後相加起來：

但是如果我們想讓兩個輸入相乘起來的話，那麼上述的加法同態算法就無能為力了。只能是所有私密輸入的線性組合。

常見的加法同態加密算法就是基於循環群的ElGamal 加密算法。

ElGamal 是基於Diffie-Hellman 密鑰交換協議為基礎而產生的一個非常方便的公鑰加密算法，採用的是循環群的特性。由於篇幅的原因，我們就在這裡不詳細解釋循環群的定義了，我們只需要知道每一個群都可以找到一個生成元

然後這個生成元可以進行冪的計算。 ElGamal 加密實現方法大致如下：

首先我們

具體ElGamal 的正確性和安全性我們就不論證了。但是看到這個加密體系的加密方式之後，由於都是冪運算，我們可以發現ElGamal 潛在的加法同態的特性。

同理我們也可以應用於乘法同態加密的算法上——就只能把所有的私密輸入相乘起來，但是沒有辦法做任何線性組合（加法）。乘法同態的例子其實也非常常見，我們大家都熟悉的RSA 加密就是一個乘法同態的系統。

RSA 加密的實現方法大致如下：

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

近似同態加密（Somewhat Homomorphic Encryption）

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

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

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

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

這樣一來，我們就變相的得到了前兩個值的冪之間的乘積組合！再搭配ElGamal 加密中可以把兩個值的冪做線性組合的屬性的話，那麼我們就得到了一個全同態的系統了。

事實上，現實並沒有那麼美好，因為Pairing 這一特殊屬性並不會出現在所有的循環群當中。所以如果我們把兩個可以做Pairing 的群中的值通過Pairing 相乘起來，映射到了一個新的群當中之後，那麼新的群並不一定能找到對應的Pairing 屬性！

這也就是說，通過擁有Pairing 屬性的循環群，我們只能做非常有限的乘法計算。假如說我們當前的群支持Pairing，但是新的映射群GT 並不支持任何Pairing，那就代表瞭如果我們要基於當前的體系進行同態加密運算，可以運算的函數雖然可以包涵任意的線性組合，但是只能包涵最多一層乘法在裡面。

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

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

也就是說，如果L 相對來說比較大的話，那麼我們就可以進行各種各樣較為簡單（低複雜度）的同態運算了。有限級數同態加密的算法也是下一階段全同態加密的奠基石，當我們實現了複雜度以內的全同態之後，實現完全同態也不遠了。

二級標題

我們可以了解一下這個複雜度的上限L 是怎麼來的。首先，我們可以想像一下，假如有一個全同態加密的算法，可以對密文進行任何的加法與乘法的運算。但是這個算法在加密的時候會在密文裡面加入一定的隨機噪音。

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

二級標題

二級標題

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

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

二級標題

二級標題

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

二級標題

全同態加密體系的性質

也就是說，如果我們任意選擇一個電路F，並且任意選擇一組原文消息m1,m2,...。如果我們擁有一開始KeyGen 算法生成的密鑰的話，那麼：

二級標題

其次，這個系統需要達到語義安全。這一定義我們上文已經闡述過了。

最後，為了讓全同態加密體系變得有實際的使用意義，我們必須還得加一條額外的規定：簡短性（Compactness）。

為什麼需要加上這個簡短性的特性呢？因為如果沒有這個要求，我們可以非常輕易的做出一個毫無意義的（作弊的）全同態系統：

二級標題

如果沒有對與Eval 輸出大小的限制的話，那麼我們反复疊加多次Eval 之後，得到的密文大小將會越來越大。最後解密的時候，只需要把所有的原始密文解開，然後算一下就行了。這就好比是一個用戶把自己的健康信息加密了，讓醫院去判斷他有沒有生病，醫院直接原封不動的把密文送回來，然後把自己的整套數據模型加上醫療課本也發回來，跟用戶說，你自己去算吧，是一個意思。

這一類全同態系統還有一個更大的弊端，也就是最後得到的密文並無法完全掩蓋住運算電路F 的具體細節。在這個醫院的使用場景中，有可能醫院自己最值錢的就是這套數據分析系統。如果白白的把自己的F 發回給了用戶，那自己的辛苦勞動成果就被別人輕易竊取了。

綜上所述，只要滿足正確、語義安全、簡短這三個要素，我們就擁有一個有意義（Non-trivial）的全同態加密體係了。

二級標題

全同態加密的歷史回顧

FHE （全同態）的概念其實在上世紀70 年代末就已經被提出了。 1978 年，密碼學界的幾個大牛Rivest，Adleman 和Dertouzos在他們的論文On Data Banks and Privacy Homomorphisms中第一次提到了對於密文進行一定的計算，可以間接地對原文進行操作的系統構想。到後來這一想法就被重新總結命名為全同態加密了。

由此可見，全同態加密這一概念已經被提出了很久了。令人驚訝的是，1976 年，也就是論文發表的兩年前，Diffle-Hellman 密鑰交換協議才剛剛被提出！由此可見密碼屆大牛的想像力還是非常豐富的。

當FHE 的概念被提出來之後，整個學術界都為之所動，開始了長達幾十年的搜索，試圖找到一個擁有全同態性質的完美算法。但是這幾十年下來，人們試遍了所有可以想到的選擇，但是找不到一個又能滿足全同態所有條件，並且安全性可以被輕易證實的選項。

在Gentry 的論文中，他還提到了一個至關重要的概念叫做Bootstrapping。 Bootstrapping 是一種對於密文的特殊處理技巧，處理過後竟然可以把一個噪音接近臨界值的密文「重新刷新」成一個噪音很低的新密文。通過Bootstrapping，一個有限級數的系統的噪音可以永遠不超過臨界值，從而變成了全同態的系統。這樣一來，我們就可以同態計算任意大小的了。

二級標題

在Gentry 的重大突破之後，整個密碼圈又一次陷入了瘋狂，大家都開始爭相基於Gentry 提出的想法尋找更加高效率和全能的全同態體系。

2013 年之後，密碼圈基本上就百花齊放了。基於原來的三代全同態系統之上，出現了各種各樣新的設計，致力於優化和加速BGV 與GSW 系統的運行效率。 IBM基於BGV 系統開發了一個開源的全同態運算庫HElib，並且成功的移植到各大移動平台上。與此同時，還有另外一個開源項目TFHE也非常值得注意。 TFHE 是基於GSW 系統，又加以了各種優化與加速，現在也非常的有名。

二級標題

在開發傳統的全同態庫之外，也有很多團隊在研究如何通過GPU，FPGA，ASIC等異構硬件來更好的加速全同態加密算法的計算。比如cuFHE就是一個比較有名的基於CUDA 的GPU 加速全同態加密系統。

如何可以讓FHE 系統更加高效率的在異構平台上運行，仍然是一個未解之謎。如果這道難題一旦被解決了，那麼把所有的電腦運算都轉為全同態，代理在第三方的雲端上進行計算，都是伸手可得的未來。

二級標題