然而，根據我們對於模組q和噪聲取值B的選擇，我們只能對一組GSW加密的密文進行有限次數的Eval運算。由於乘法會導致噪音增加的更快，所以同樣的parameters可以進行更多次加法計算。
當噪聲的取值範圍逐漸逼近士q/4之後，我們的密文就變成了一個“飽和”的密文，不能夠進行任何同態計算了。因為一旦進行計算的話，代表0的一頭與代表1的一頭的噪音區間就會重疊在一起，這樣我們在解密的時候，就不能透過一個簡單的thresholding（即比較最後的結果是否接近0的一頭還是q/2的一頭）來完美還原出一開始的原文了。
這也就是說，GSW加密系統是有限級數同態的（Leveled FHE），這在上一期我們也講到了。那如果我們需要計算一個深度為L的電路C，需要怎麼使用GSW來實現呢？
第一種最簡單的方法，莫非於我們根據需要計算的深度L來選擇對應的q與B。這樣一來，我們就可以確保整個系統可以同態計算C並且噪音區間不會爆掉。這其實對於大多數的應用來說已經非常足夠了。唯一美中不足的是，當我們要計算的電路複雜度（深度）變得非常大的時候，我們選擇的模組也會相對著變得非常大，這對於計算與儲存的效率來說是大打折扣的。
一直無法計算未知或者無限深度的電路C這一件事情一直很煩擾著我們。有沒有什麼辦法可以不用改變模組與噪音的大小，但是可以擴大有限級數系統的計算範圍呢？如果更嚴謹的來問的話：有沒有什麼方法可以讓模組q與噪音B的選擇獨立（independent）於我們計算的電路大小C呢？
這個時候，就輪到Bootstrapping登場了。
Bootstrapping的概念
Bootstrapping是FHE界的開山鼻祖Craig Gentry在2009年提出的一個idea。Gentry本人其實寫過一篇非常方便理解這個idea的介紹性paper：Computing Arbitrary Functions of Encrypted Data。我們這裡就基於Gentry在原文中的表述方法來嘗試深入瞭解一下。
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
目前來說，我們還沒能找到一個非常好的模型來研究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的加密與解密結構。
同態解密GSW密文
解密的第一步非常簡單，我們要做的就只是做一次線性相乘，並且在已知了C的值的情況下，我們只需要做純同態加法，不需要做任何乘法。所以這一步對於密文的噪音增長的影響是非常小的。
真正有問題的是第二步，因為就像在計算zkSNARK的LPCP的時候，我們為了構造R1CS程式，要把電路轉化為數學運算電路（Arithmetic Circuit）一樣（具體可以參照零知識證明一系列文章），整個系統的效率是非常低下的。
低效率還帶來了一個更大的問題：整個解密電路的複雜度會變得非常高，甚至高於我們真正想要進行同態計算的電路。為了使得Bootstrapping之後的密文的噪音值會“降低”到一個比原來更低的值，我們就需要被迫擴大GSW的模組和其他引數，使得我們能夠成功的在噪音區間內同態計算Dec。
這樣一來，原本使用Bootstrapping的意義就沒了，因為我們本來是希望不擴大太多的引數，讓我們可以同態計算更復雜的電路。但是如果Dec過於複雜，雖然我們最後還是可以得到一個FHE系統，即可以計算無限深度的電路，但是效率非常低下，很有可能99%的計算都在用來計算Bootstrapping上。
使用Barrington's Theorem進行Bootstrapping
在GSW構造被提出之後，Brakerski與Vaikuntanathan試圖尋找一個比較合理的Bootstrapping方案，即找到一個可以有效解決中Dec第二步的方法。他們選擇的方法是首先用邏輯電路來表達解密函式Dec，然後再使用Barrington's Theorem把這個邏輯電路轉化為一系列的Matrix Branching Program（矩陣分叉程式，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），所以不能用來閉源開發等等。由於時間關係，筆者就沒有一一去測試了，把這個機會留給大家去嘗試一下。
