幾分鐘搞懂全同態加密FHE：運行模式與應用場景
原文標題：FullyHomomorphicEncryption:IntroductionandUse-Cases
原文作者：NicolasGama和SandraGuasch，SandBoxAQ
編譯：Faust，極客web3
這篇博客是對全同態加密（FHE）的系統性介紹，但我們并不在此深入的探討數學細節，而主要從基礎的機制設計角度來解釋這項技術，讓讀者初步理解FHE的基本運行邏輯，并介紹FHE的幾個主要應用模式。
上圖展示了線上投票的三種加密/解密方案，其中E()表示加密操作，而D()表示解密操作；
左側圖中，一個受信任的中間人在公布投票結果前，會對各個投票數據進行混淆和解密，我們必須假設該中間人不會泄露隱私，且投票統計結果是正確無誤的；
在中間的圖中，使用了TEE，TEE能保證數據完整性和隱私保護；
而在最右側的圖中，使用了同態加密技術：加密后的投票數據可以被公開加總求和，然后再解密得到結果，算出最終的投票數
FHE（全同態加密）是緊湊型加密方案，輸出結果?(?)的密文數據大小，以及解密該結果所需的工作量，僅取決于輸入數據?對應的原始明文，并不依賴于所采用的計算過程，這與那些非緊湊型的加密系統截然不同，后者往往簡單地把?與函數?的源碼連接起來，然后讓接收者自己解密?并輸入到?中來完成計算任務。
在現實中，FHE外包模式通常被視作TEE等安全執行環境的替代方案，FHE的安全性基于密碼學算法，而不依賴于硬件等實體設備。因此，FHE完全不受被動側信道攻擊或云端服務器被攻擊的影響。想象一下，當某人需要外包出去一些計算任務，但數據非常敏感，他可能不愿意使用搭建在AWS上的虛擬機（VM），因為這類基于云端的服務器背后往往存在更高級的控制人。他也可能對SGX或TEE這類東西猶豫不決，因為運行TEE的主機可以監控該計算任務在執行時產生的功耗或運行時間等，可能通過這些數據來推斷出一些信息。
然而，如果使用FHE，將計算任務外包出去的人就可以安心——因為在FHE的系統中要破解私密信息，就必須破解其用到的密碼學算法，但這在目前幾乎無法做到。
但是，雖然密碼學算法可以防止攻擊者在不知道密鑰的情況下破解?對應的明文，但另一方面，通用延展性則允許攻擊者對輸出結果?(?)進行修改，這相當于一種主動側信道攻擊：攻擊者可以對執行加密算法的硬件進行針對性的攻擊，影響輸出結果。這聽起來似乎很可怕，但在FHE的設計中，這類惡意攻擊可以通過在計算流程中制造冗余來進行規避。
簡要總結的話，FHE通常會用到幾組密鑰，包含以下幾部分：
解密密鑰（DecryptionKey）：這是整個FHE加密系統中的主密鑰，所有其他類型的密鑰都可以根據主密鑰來導出。解密密鑰通常在用戶本地生成，從不傳輸給外界，只有持有者本人能用它來解密FHE密文。這意味著密文即使在傳輸中被他人截獲，也無法被解密，除非他們擁有解密密鑰。
加密密鑰（EncryptionKey）：在FHE的公鑰模式下，加密密鑰是用來將明文轉換為密文的密鑰。當生成初始密文的人不是解密密鑰/主密鑰的持有者時，就會使用加密密鑰來進行加密。該密鑰通常中等大小，由一些隨機的零加密組成。由于FHE支持仿射函數（affinefunctions），足以用于加密任何消息。
在公鑰加密模式中，加密密鑰通常是公開的，任何人都可以用它來加密數據，但只有解密密鑰的持有者才能針對性的解密。
計算密鑰（EvaluationKey）：計算密鑰是用來對密文?進行同態運算的專用密鑰，使得FHE系統可以在不對密文?進行解密的情況下，對密文進行同態運算。計算密鑰可以像公鑰一樣被公開發布，即使他人獲知了計算密鑰，也無法破解出密文?，而只能對密文進行同態運算得到一個輸出結果。
此外，當使用計算密鑰進行運算時，密文的結構保持不變，對密文?進行同態運算得到的結果會被重新加密為新的密文，這確保了計算過程中的隱私性，即使計算過程是公開的也不會泄露機密數據。
在上述幾種密鑰的持有者中，解密密鑰/主密鑰持有者是最敏感的，他要確保整個同態操作的執行鏈條/流程有效無誤，最終的密文是安全的，然后解密得到明文結果。如果在FHE的操作鏈條中引入惡意操作，解密密鑰有可能會在解密時被泄露。但幸運的是，同態操作可以公開進行并被任何人所驗證。
FHE的具體場景/模式
在本節中，我們將描述一些FHE中的常見場景/模式，并討論每種模式的優缺點。
外包模式（OutsourcingMode）
TwoPartyComputingMode（兩方計算模式）
AggregationMode（聚合模式）
Client-ServerMode（客戶端-服務器模式）
關于同態加密的其他細節
同態加密如何確保外部計算結果是有效的？
在多方合作的場景中使用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/