初探全同態加密之四：Bootstrapping的原理與實現

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

在上一期的文章中，我們學習並且深入了解了GSW全同態加密系統的具體構造。通過這一構造，我們可以對加密的密文進行相加和相乘的操作，並且通過二進制分解的方法，把密文中噪聲的增加速度控制在一個可控的區間之內。（詳情點擊《初探全同態加密之三：構建GSW全同態加密系統》）

GSW的有限級數限制

Alice的珠寶店

Alice开了一家珠寶店，每天她需要把不同的珠寶（鑽石、黃金）加工拼接起來，然後把完成的首飾賣給顧客。

過了一陣子後，Alice覺得自己忙不過來，於是決定僱傭Bob作為她的員工。然而，Alice擔心Bob會趁着她不注意，偷偷的把加工完剩余的邊角料藏起來，或者是加工的時候偷工減料為自己牟利，所以一直放不下心來。

直到有一天，Alice突然想到了一個idea。

Alice买來了一個手套箱（Glove Box），就是那種做實驗用的密封的箱子，中間有兩個帶有手套的洞，手可以伸進去碰到箱子裏面。她的想法很簡單：只需要把所有的原材料全部鎖在箱子裏，然後Alice保管着可以开鎖的鑰匙，Bob就偷不走了。Bob想要加工這些原材料也很簡單，只需要把手伸進去隔着手套加工珠寶，就可以完成工作了。

這個手套箱還有一個巧妙的小設計，有一個單向的進口，外面的人可以投任何東西進來。Bob可以通過這個進口把部分的原材料從外面投入手套箱內，但是無法打开手套箱把它們取出來。

整個idea一切都很完美，正當Alice买回來了一個手套箱，准備進行實踐的時候，她突然發現了這個箱子的幾個問題：

1. 首先，套上手套的Bob的加工手藝並沒有以前那么精湛了。也許原本只需要半天的活，現在可能要磨蹭兩三天才能幹完。

2. 其次，雖然手套箱上了鎖之後，Alice就可以放心Bob不會偷走珠寶了。但是這樣的代價就是，當Bob加工完了之後，他並沒有辦法直接把加工完的珠寶拿出來給顧客，而是得等Alice過來了才能打开來。這樣一來如果Alice很忙的話，可能顧客得Alice忙完了才能拿到自己买的商品。

3. 以上的兩點問題，Alice勉強都可以接受，但是接下來的第三點是最致命的。Alice發現，這個手套箱具有一定的使用壽命，也就是說Bob只能在這個箱子裏加工珠寶L次，然後這個箱子就會壞掉，變得無法再繼續加工。如果已經達到了損耗的臨界值，然後Bob繼續嘗試使用的話，那么裏面的珠寶就有可能會徹底的被搞壞，變得無法修復。

當Alice發現手套箱的這三個特點之後，她开始思考如何有效的讓Bob使用這一新發明。

Alice的平行世界：FHE

看到這裏，想必熟悉FHE構造的讀者們一定會對Gentry舉的這個Alice的珠寶店例子非常親切。Alice發明的手套箱其實就是暗指FHE系統！我們來比較一下這兩者之間的共同性：

1. Alice擁有手套箱的鑰匙，所以可以打开盒中的東西。這代表了FHE加密系統的解密正確性。

2. Bob可以通過單向的入口把東西投入手套箱中，但是無法取出任何東西。這代表了我們討論的FHE加密系統是一個安全的public key（公鑰）的加密系統，即任意第三方都可以創造密文但不能解开密文。

3. Bob可以通過兩個手套口，任意的加工放在手套箱中的物品，但是效率比起直接加工要慢上許多。這一步對應了FHE中的同態計算（Eval）。

4. 最後，手套箱的使用壽命，以及使用了若幹次之後就會壞掉這一設定，完美的吻合了Lattice結構的FHE系統中的噪聲以及上限。想要增加使用壽命，一種方法是把盒子做的更大、更昂貴，這對應着在FHE中把對應的parameters增大。

那么現在問題來了，Alice可以如何不改進手套箱，但是增加它的使用壽命呢？我們繼續回到Alice的世界中來看看Gentry是怎么描述的。

手套箱中的奧祕

一籌莫展的Alice看着一個只能用有限次的手套箱，非常的失望。這一有限的加工次數決定了Bob可以加工的珠寶的復雜程度。按照現在這個樣子，Bob只能加工一些半成品出來，然後需要Alice去开鎖，再把半成品放到一個新的手套箱中，繼續讓Bob加工。

這樣一來，Alice基本上得全程在旁邊看着。原本僱Bob來是為了減少負擔的，沒想到現在反而還更加加重了工作壓力。

直到有一天，Alice在看Bob加工珠寶的過程中，突然靈機一動：假如我事先知道了Bob加工一個珠寶需要兩個手套箱，我能不能想辦法可以讓Bob在沒有鑰匙的情況下把未加工完的半成品從第一個手套箱中轉移到第二個手套箱中呢？

Alice回去之後想了半天，終於想出了一個絕妙的想法：

第二天，Alice准備了兩個手套箱，分別標號為A與B。Alice把A、B兩個手套箱都交給Bob，並且自己留下手套箱B的鑰匙。她唯獨做了一件不一樣的事情：把A的鑰匙丟入了B當中。

這樣一來，當Bob在手套箱A中加工珠寶達到損耗的臨界值的時候，他接下來需要做的事情就是：把手套箱A一整個塞入手套箱B中！然後，Bob就可以直接在手套箱B中拿着實現放進去的鑰匙解开裏面的A箱的鎖，然後把半成品的珠寶拿出來繼續加工了。

整個想法瞬間震驚了所有珠寶店的人，通過這樣的構造，Bob就可以不用Alice幫忙加工任意復雜度的珠寶了，兩個不夠就串三個，三個不夠就四個。唯一需要做的就是Alice需要在开始之前把對應的鑰匙丟入對應的箱子中。

為什么這樣的方案可行呢？因為一开始說到了，手套箱上安裝的單向入口可以放入任何東西，包括另一個手套箱，所以就可以層層嵌套啦。唯一需要注意的一點是，在手套箱B中解开箱A的鎖這個步驟，也會給箱B帶來一定的損耗。所以在選取鎖的時候，Alice特意選擇了不需要太大力氣可以幾步解开的鎖。

Bootstrapping初見端倪

Alice所想到的這個技巧，正是我們這一期想要討論的Bootstrapping的概念！如果拿到FHE的世界中簡單的概括的話，那就是：把一個滿噪音的FHE的密文加密進另一個FHE密文中，並且同態計算FHE的解密算法，把裏層的密文解密還原為原文，就能獲得一個全新的低噪音FHE密文。

如果乍一看有點一頭霧水，不要急，我們一步一步的來看在FHE中Bootstrapping是如何實現的。

目前來說，我們還沒能找到一個非常好的模型來研究Circular Security假設真正的安全性。這是因為在設計公鑰加密算法的時候，我們並不會考慮到公开了密鑰的密文之後會帶來什么後果。有一派的看法是，因為公鑰加密系統是Semantic Secure（語義安全的）的，所以密鑰的密文應該看起來和其他的密文沒有任何區別，所以循環安全這一假設應該很容易成立。

但是，我們近幾年已經找到了很多反例，即找到了一些一定不滿足Circular Security的加密系統。比如說我們手動的在某個加密系統中塞入一個後門，使得一旦擁有了循環密鑰，即加密了密鑰的密文之後，就可以通過這個後門來獲得密鑰的原文。但是這些加密系統都是人為的構造的，由於我們目前還沒有在現有的公鑰加密體系找到一個很自然的反例，所以我們相信Circular Security仍然是個安全的假設。

Bootstrapping的策略

看到這裏，想必大家已經對Bootstrapping的概念有了一個大概的了解。

和之前介紹FHE系統不同的是，Bootstrapping其實是一個很廣義、寬泛的概念。我們並沒有用一系列公式來展示Bootstrapping的過程，而只是介紹了這一種思路，即同態驗證解密函數。這種思路可以用於任何FHE的系統，包括BGV與GSW系統。

在深入理解Bootstrapping在GSW中到底是什么原理之前，我們先來看看，到底什么時候才需要Bootstrapping。

Bootstrapping的策略分為兩種：Gate Bootstrapping與Circuit Bootstrapping。

Gate Bootstrapping

第一種Bootstrapping的策略，就是每當我們進行一次最簡單的同態計算，我們就進行一輪的Bootstrapping把噪聲值還原到進行計算前的量。因為我們可以把計算的函數用電路表示，而電路的最基本構成元素是邏輯門（Gate），所以這種方案又被稱作Gate Bootstrapping。

熟悉邏輯電路的讀者可能會知道，所有的邏輯門都可以用一個邏輯門NAND來表示。這也就是說，只要我們可以構造出一個同態計算NAND並且再進行一輪Bootstrapping的構造，我們就可以把這個構造作為一個邏輯計算模塊，然後用這個模塊構造出任何電路。因為Bootstrapping確保了噪聲不會超過臨界值，所以我們可以用這種方法來進行任何深度的電路的同態計算。

基於Gate來構造的Bootstrapping較為簡單，我們在同態計算一個程序的時候，只需要寫一個編譯器，把這個程序轉換成電路，再把電路分解為單個的邏輯門，然後把每個邏輯門再拆分成NAND，就搞定了。這樣的結構等於是在應用層隱藏了Bootstrapping這件事情，因為每次進行NAND計算的時候，噪音值就已經被重新刷新了。

Circuit Bootstrapping

第二種Bootstrapping的思路和我們之前討論的思路比較相似。我們首先使用原本的FHE系統同態計算我們想要計算的電路，直到達到了噪音臨界值。然後我們再進行一輪Bootstrapping來“刷新”噪聲值，以便進行後續的同態計算。

這種結構和Gate的思路相反，把Bootstrapping的概念直接暴露在了應用層。我們在進行計算的時候可以根據目前的噪聲值來選擇是否要進行Bootstrapping。這樣的好處在於，如果我們需要同態驗證的電路的復雜度不是很高的話，我們就可以很快速的進行Leveled同態計算，而不需要花額外的時間來通過Bootstrapping來刷新噪聲。

Bootstrapping的實現

了解完Bootstrapping的原理與策略之後，接下來我們終於可以來結合之前所學的看一看，如何在我們之前看到的GSW同態體系中運用Bootstrapping的概念了。

我們先重新回顧一下GSW的加密與解密結構。

這個問題解決了之後，剩下來的就是把Dec轉換成MBP然後進行同態計算了，這一部分我們就不多說了。

當BV二人根據這個結構提出Bootstrapping的方案之後，大家逐漸找到了一條可以真正實現Bootstrapping的路，並且开始用代碼來實現。到2014年，Halevi與Shoup在HElib（IBM的FHE庫）中使用類似的概念進行Bootstrapping計算，並且可以在半個小時左右的時間內進行一次Bootstrapping，使用的參數的存儲空間達到了幾十個GB左右。

實際的Bootstrapping方案（Practical Bootstrapping）

看到這裏的朋友們可能會不禁吐槽到，Bootstrapping這么簡單的概念，居然需要在電腦上花上半個小時的時間，並且佔用這么大的空間才能完成。沒錯，早期的FHE之所以不能投入應用，就是因為Bootstrapping的开銷實在是太大了。並且拋开Bootstrapping不說，我們光是用GSW這樣龐大的LWE矩陣來加密一個bit，就基本上代表已經沒有什么效率可言了。

然而，這一切在2014年後开始發生了改變。

2015年的時候，Ducas與Micciancio提出了全新的【DM15】構造，屬於Gate Bootstrapping的方案（即提供了一個NAND+Bootstrapping的實現），並且基於GSW系統。這一構造被稱作為FHEW，標准參數下只需要0.69秒就可以完成一輪Bootstrapping！

在DM15中，作者發現GSW的解密過程中最令人頭疼的第二步，其實並不需要實現完整的Comparator Circuit，可以通過一個更加簡單的Accumulator（累加器）來實現。這一發現直接就大大簡化了第二步所需要的計算量。主要的思路在於，如果我們合理的選擇模組q的值，那么第二步比較判斷的過程，就完全可以通過觀察密文二進制分解之後的最高位是1還是0來完成，而不需要與q/4來進行比較了。

緊接着，在2016年的【CGGI16】中，TFHE誕生了，繼承了FHEW的特點，不過進行了一系列更加優化的操作，把Bootstrapping的時間壓縮到了0.05秒之內。在2017年的follow up 【CGGI17】中，又把這一下限壓到了0.013秒！

TFHE所用到的技巧也非常巧妙，它的核心也是觀察到FHEW所用的Accumulator的構造，發現如果把密文映射到Torus 

T（環面空間）中，那么構成這個Accumulator的構造更加簡單。因為整個計算空間是一個環形的，只需要通過一個盲旋轉（blind rotation）的操作，就可以提取出密文的最高位的值。

至於FHEW與TFHE的具體實現與證明，我們在這裏就不多說了，以後有時間的話可以再开一篇，詳細討論一下這兩種方案。

FHE庫的比較

到這裏，我們大概已經知道了FHE的大致發展了。從09年Gentry提出了這一概念之後，學術界和業界都在爭相在計算機上實現FHE。除了我們這期提到的FHEW與TFHE之外，還有HElib，SEAL，cuFHE等等非常有名的开源庫。

這些庫之間並沒有特別多的好壞比較，更多的只是他們適應於不同的使用需求。比如說有的庫會使用很多浮點操作，有的庫會使用CUDA加速，有的庫會使用GPL License下的其他插件（比如FFTW），所以不能用來閉源开發等等。由於時間關系，筆者就沒有一一去測試了，把這個機會留給大家去嘗試一下。

寫在最後

到這裏，我們【初探全同態加密】這一專題就到此結束啦。我們來快速回顧一下這4期覆蓋的內容：

1. 什么是加密系統，與什么是加密系統的同態性質。

2. 同態加密的分類與特性。

3. 全同態加密的定義的歷史。

4. 格密碼學入門以及LWE問題的介紹。

5. 基於LWE問題的Regev加密系統。

6. GSW全同態加密體系的三次嘗試：矩陣特徵值，加入噪音，二進制分解。

7. Bootstrapping是什么，以及具體實現策略。

8. 如何基於GSW進行Bootstrapping，以及現有的實現方案。

9. FHE庫的大致一覽。

這么一看，這四期已經涵蓋了非常多的內容了！如果看到這裏大家覺得對之前的概念有點生疏的話，不妨回去再看一遍，鞏固一下知識。

距離上一篇FHE文章已經過去了很久，這段時間筆者都在努力的補更多關於格密碼學的知識，在過程中重新學習一遍這些講過的概念。每次重新學這些概念的時候，都會發現每次的理解都會變得不一樣，也會發現很多見過的構造其實都有非常巧妙的相似之處。

如果看完了FHE之後，還想了解一下基於格密碼學的更多高級的構造，比如ABE，NIZK，iO等等，希望大家也可以關注一波筆者在更新的【格密碼學進階】專題～

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