原文標題：Fully Homomorphic Encryption: Introduction and Use-Cases
原文作者：Nicolas Gama 和Sandra Guasch，SandBoxAQ
編譯：Faust，極客web3
這篇部落格是全同態加密（FHE）的系統性介紹，但我們並不在此深入的探討數學細節，而主要從基礎的機制設計角度來解釋這項技術，讓讀者初步理解FHE的基本運行邏輯，並介紹FHE的幾個主要應用模式。
當提到「加密」時，人們最先聯想到的應用程式場景通常是靜態加密和傳輸中加密。前者將資料加密後儲存在硬體設備中，如硬碟、行動設備，或是基於雲端的伺服器，在這種模式下，只有被授權的人能查看或改寫解密後的明文內容。而傳輸中加密，目的是讓透過網路傳輸的資料只能被指定的人解讀，即便資料透過公共路由器或通道來傳輸，中間人也無法私自解密出明文。
上述兩個場景都依賴加密演算法，同時也會額外保證資料的完整性，即資料在傳輸過程中沒有被中間人篡改，這稱為「認證加密」：一旦資料被加密後，資料傳輸過程中的參與者無法私自解密出明文（保密性），任何中間人都不能隨意篡改原始的密文（完整性/真實性）。
至於某些多方協作的場景，需要對密文進行一些複雜的處理，這屬於隱私保護技術的範疇，全同態加密（FHE）就是其中之一。我們可以舉出一個線上投票的案例：假設在一次總統選舉中，選民可以將自己的投票結果進行加密，然後提交給某個中間實體，該中間人將所有投票結果統一收集起來，算出每個總統候選人的得票數，最後隻公佈一個最終選舉結果。
但不幸的是，當我們使用前面提到的「認證加密」方案時，負責統計投票結果的中間人要解密出所有人的投票資料明文，才能執行統計票數的任務，但這樣就會讓每個人的投票結果都暴露出來，無法保護隱私。理論上，我們可以對大家的投票數據進行混洗（某些電子投票協議確實會這麼做），但與紙質選票不同，傳統密碼學機制在保證數據完整性（不被篡改）的同時，很很難把加密後的選票資料與對應的選民身分分開。
在線上投票方案中，我們可以在負責計票的中間人周圍添加一道硬體隔離牆，例如TEE(可信賴執行環境)。這種技術使得惡意攻擊者很難與計票程式展開互動，但硬體層面的漏洞可能讓解密密文的金鑰從TEE中洩漏出來，而且與軟體中包含的錯誤不同，硬體設計上的漏洞無法輕易修復。
綜上，為了應對上述場景，我們可以引入全同態加密（FHE）技術。 FHE是一種特殊形式的加密方案，允許在不解密密文的情況下直接對密文進行函數計算，以獲得該函數輸出的加密後的結果，這樣就可以保護隱私。
在FHE的場景下，函數? 的數學構造是公開的，因此輸入密文? 輸出結果?(?) 的處理流程是公開信息，可以在雲端執行，而不會洩露任何隱私。這裡要注意， ? 和?(?) 都是被加密過的密文，需要由金鑰來解密，大多數時候兩者對應的解密金鑰是相同的。
上圖展示了線上投票的三種加密/解密方案，其中E( ) 表示加密操作，而D( ) 表示解密操作；
左側圖中，一個受信任的中間人在公佈投票結果前，會對各個投票資料進行混淆和解密，我們必須假設該中間人不會洩露隱私，且投票統計結果是正確無誤的；
在中間的圖中，使用了TEE，TEE能保證資料完整性和隱私保護；
而在最右邊的圖中，使用了同態加密技術：加密後的投票資料可以被公開加總求和，然後再解密得到結果，算出最終的投票數
FHE（全同態加密）是緊湊型加密方案，輸出結果?(?) 的密文資料大小，以及解密該結果所需的工作量，僅取決於輸入資料? 對應的原始明文，並不依賴於所採用的計算過程，這與那些非緊湊型的加密系統截然不同，後者往往簡單地把? 與函數? 的源碼連接起來，然後讓接收者自己解密? 並輸入到? 中來完成計算任務。
在現實中，FHE外包模式通常被視為TEE等安全執行環境的替代方案，FHE的安全性是基於密碼學演算法，而不依賴硬體等實體設備。因此，FHE完全不受被動側通道攻擊或雲端伺服器被攻擊的影響。想像一下，當某人需要外包出去一些運算任務，但資料非常敏感，他可能不願意使用搭建在AWS上的虛擬機器（VM），因為這類基於雲端的伺服器背後往往存在更高級的控制人。他也可能對SGX或TEE這類東西猶豫不決，因為運行TEE的主機可以監控該計算任務在執行時產生的功耗或運行時間等，可能透過這些數據來推斷出一些資訊。
然而，如果使用FHE，將計算任務外包出去的人就可以安心——因為在FHE的系統中要破解私密信息，就必須破解其用到的密碼學演算法，但這在目前幾乎無法做到。
但是，雖然密碼學演算法可以防止攻擊者在不知道金鑰的情況下破解? 對應的明文，但另一方面，通用延展性則允許攻擊者對輸出結果?(?) 進行修改，這相當於一種主動側頻道攻擊：攻擊者可以對執行加密演算法的硬體進行針對性的攻擊，影響輸出結果。這聽起來似乎很可怕，但在FHE的設計中，這類惡意攻擊可以透過在運算流程中製造冗餘來進行規避。
簡單總結的話，FHE通常會用到幾組密鑰，包含以下幾部分：
解密金鑰（Decryption Key）：這是整個FHE加密系統中的主金鑰，所有其他類型的金鑰都可以根據主金鑰來匯出。解密金鑰通常在用戶本地生成，從不傳輸給外界，只有持有者本人能用它來解密FHE密文。這意味著密文即使在傳輸中被他人截獲，也無法被解密，除非他們擁有解密金鑰。
加密金鑰（Encryption Key）：在FHE的公鑰模式下，加密金鑰是用來將明文轉換為密文的金鑰。當產生初始密文的人不是解密金鑰/主金鑰的持有者時，就會使用加密金鑰來進行加密。這個密鑰通常中等大小，由一些隨機的零加密組成。由於FHE支援仿射函數（affine functions），足以用於加密任何訊息。
在公鑰加密模式中，加密金鑰通常是公開的，任何人都可以用它來加密數據，但只有解密金鑰的持有者才能針對性的解密。
計算金鑰（Evaluation Key）：計算金鑰是用來對密文? 進行同態運算的專用金鑰，使得FHE系統可以在不對密文? 進行解密的情況下，對密文進行同態運算。計算金鑰可以像公鑰一樣被公開發布，即使他人獲知了計算金鑰，也無法破解出密文? ，而只能對密文進行同態運算得到一個輸出結果。
此外，當使用計算金鑰進行運算時，密文的結構保持不變，對密文? 進行同態運算得到的結果會被重新加密為新的密文，這確保了計算過程中的隱私性，即使計算過程是公開的也不會洩漏機密資料。
在上述幾種金鑰的持有者中，解密金鑰/主金鑰持有者是最敏感的，他要確保整個同態操作的執行鏈/流程有效無誤，最終的密文是安全的，然後解密得到明文結果。如果在FHE的操作鏈條中引入惡意操作，解密金鑰有可能會在解密時被洩漏。但幸運的是，同態操作可以公開進行並被任何人驗證。
FHE的具體場景/模式
在本節中，我們將描述一些FHE中的常見場景/模式，並討論每種模式的優缺點。
外包模式（Outsourcing Mode）
在此圖中，左側橘色的鑰匙符號象徵解密金鑰（及其持有者Alice）。 FHE密文透過與解密金鑰相同顏色的鎖來表示。貢獻私密資料的一方以圓柱體表示：
在這裡，只有Alice貢獻了私密數據。而在Bob這邊，同態計算函數和計算密鑰是公開的，計算方案由綠色框表示，以確定性的方式進行，每個人都可以在本地重跑計算過程，並檢測Bob給出的輸出結果是否有錯誤
上述外包模式也是FHE的第一個歷史性應用案例，旨在將普通的雲端運算轉變為類似SGX和TEE的私密運算，但上述FHE演算法的安全性是基於密碼學演算法，而非硬體層面的安全措施。在這種設定下，Alice擁有一些私密數據，但其運算能力有限，Bob擁有運算能力強大的雲端伺服器，而Bob不貢獻任何額外的私密數據。
Alice可以把計算任務?() 的輸入參數進行加密，得到密文? 並將其傳送給Bob，Bob隨後以同態加密的方式運算出?(?)的結果，並將加密後的結果送回給Alice。
鑑於目前的硬體設備性能，FHE外包模式的實際推廣比較緩慢——如果要執行的計算任務?() 的複雜度是非線性的，對?() 進行FHE運算的耗時將達到原始計算的100萬倍，記憶體開銷大概會提高1000倍。目前許多組織正在開發FHE專用硬體以降低其運算成本，例如Darpa DPRIVE專案或CryptoLight。
目前，FHE外包模式實際上主要用於PIR（私有資訊檢索）場景，其中公共伺服器控制者Bob擁有一個大型的公共資料庫，客戶端Alice會發起讀取資料的請求，但又不想讓Bob知道自己想查關於哪些人的數據。這類PIR場景受益於同態加密操作的線性和緊湊性，同時計算成本可以保持在合理範圍內。
下面這個表格總結了FHE外包模式的優缺點。
Two Party Computing Mode（兩方計算模式）
該圖使用了與之前相同的顏色設定。這次，Bob在計算流程中貢獻了一些私密資料。而Bob一方的計算流程不再是公開可驗證的，用紅色框表示，這種模式應僅限於通訊雙方均為honest-but-curious的場景：
也就是說，在協議執行過程中，參與者（如Bob）會嚴格按照給定步驟進行計算，不會故意輸出錯誤結果或破壞協議的執行。但Bob是「好奇」的，會盡可能從接觸到的密文或其他中間數據中推斷出敏感訊息，但這並不會篡改協議的執行過程
在FHE兩方計算的模式中，唯一的差別在於Bob會在計算過程中貢獻一些私密數據，也就是把自己的私密數據加入FHE計算過程中。在這種情況下，FHE是很好的兩方計算解決方案，具有最小的通信複雜度，並且可以透過其機制設計提供強有力的保證：Bob不會窺探到Alice的私密數據，而Alice也不會窺探到Bob的私密資料。
該場景的一個潛在應用案例是密碼學中的“百萬富翁問題”，假設Alice和Bob是兩位百萬富翁，他們想知道誰更富有，但又不想讓對方知道自己具體有多少資產。該問題的解決方案通常用於現實的電子商務應用場景。
Aggregation Mode（聚合模式）
聚合模式是對外包模式的改進，將來自多個參與者的資料以緊湊（輸出結果不會隨著輸入參數數量的增加而增長）且公開可驗證的方式進行聚合。典型的用例包括聯邦學習和線上投票系統。
Client-Server Mode（客戶端伺服器模式）
這種模式是對前面提到的雙方計算模式的改進，其中伺服器會為多個擁有獨立金鑰的客戶端提供FHE計算服務。 FHE可以用於私有AI模型運算服務，例如，客戶端有私密數據，伺服器端有私有的AI模型或服務）。伺服器擁有的私有AI模型是以明文形式儲存在本地的，然後每個客戶端都有自己的私密數據，希望放到AI模型中進行運算。最終每個客戶端可以使用自己的金鑰解析出自己所提交資料的運算結果。
關於同態加密的其他細節
同態加密如何確保外部計算結果是有效的？
在多方合作的場景中使用FHE是更容易的，因為每個參與者都有動機誠實地遵循協議規定。例如，FHE可以在位於兩個不同國家但屬於同一公司/組織內的兩個法人實體之間進行加密計算並統計一些數據：諸如GDPR之類的法規允許你對外發布某些統計數據，但會禁止將所有個人資料集中儲存在同一實體地點。
在這種情況下，使用FHE是可行的，所有參與者都有動機誠實地遵循協議規定。而在參與者並非彼此合作的場景中，確保計算任務已被正確執行的最簡單方法，是引入冗餘（類似於多簽/共識）。例如，在前面提到的外包和聚合場景中，同態計算用到的函數公式是完全公開的，並且可以是確定性的，只要兩個或更多獨立實體得出完全相同的輸出密文，那麼整個計算過程就是正確的，結果也是可信的。冗餘程度越高，最終結果的可信度就越高，但這需要在效率方面進行權衡。
此外，當承包計算任務的計算方透過對輸入和輸出密文進行數位簽章來擔保FHE結果有效時，每個人都可以重跑相同的FHE計算流程，並檢查計算方給出的證明是否有效。任何計算方的欺騙行為都可以被檢測出來並被懲罰，並可以與一個公開可驗證的證書相關聯，該證書會揭露欺騙行為和欺騙者——我們稱這種模型為強隱蔽安全模型。
至於完全同態簽名，是另一種驗證計算正確性的方法，無需第三方驗證者，但通常需要更多的軟硬體資源來參與。
FHE如何確保最終接收者只解密最終結果而非中間變數？
最簡單的方法是確保解密金鑰持有者無法存取FHE計算流程中產生的中間密文。在雙方運算場景或客戶端伺服器場景中，Alice對輸入結果進行加密，Bob對密文進行計算並將加密的輸出結果傳回Alice，顯然Alice只能解密最終結果，無法存取中間變數。
在基於雲端伺服器的場景，例如線上投票系統中，許多參與者會在AWS等公共的雲端伺服器上發送加密後的投票數據，這裡會用到一種手段：解密金鑰通常不會交給單個接收者，而是以秘密共享的方式分配給不同的人或機構（類似MPC）。在這種情況下，只有透過執行多方計算並讓持有解密金鑰的成員之間在線通信，才能對特定密文進行解密。如果其中某些人拒絕配合其他人，則無法進行解密。這樣就可以透過設定相應的閾值來提高系統的整體安全性。
同態加密的建置模組
同態加密有三種：部分同態加密（PHE）、分級同態加密（LHE）和完全同態加密（ FHE）。部分同態加密只允許我們對某些計算任務進行同態加密（例如求和、線性函數、雙線性函數），而分級同態加密和完全同態加密可以支援任意的計算任務。
對於LHE來說，系統用到/產生的參數依賴於要執行的函數計算?()，並隨著該函數計算複雜性的增加而增長，這反過來導緻密文和金鑰的大小也跟著增加，會消耗更多的儲存和通訊資源。而FHE方案允許我們在給定的一組參數下（也就是給定的密鑰和密文大小下），計算任何可以表示為二進位邏輯閘電路的函數。也就是說，與LHE不同，即使需要計算的任務變得越來越複雜，FHE方案涉及的參數（以及金鑰和密文）也不會變大。
因此，FHE是唯一能保證同態計算的記憶體消耗和運行耗時都與原始明文/任務成正比的模式。但是，FHE有一個技術上的問題：隨著計算的持續進行，密文中包含的雜訊（垃圾資料）會越來越多。為了避免噪音過多導致解密結果出錯，FHE方案會定期執行一種代價較高的操作，稱為自舉（bootstrapping），它可以將噪音減少到可控水平。日後我們將對此進行更多的介紹和科普，大家敬請期待！
原文連結：https://cryptographycaffe.sandboxaq.com/posts/fhe-01/
