原文標題：FullyHomomorphicEncryption:IntroductionandUse-Cases

原文作者：NicolasGama和SandraGuasch，SandBoxAQ

編譯：Faust，極客web3

這篇博客是對全同態(tài)加密（FHE）的系統(tǒng)性介紹，但我們并不在此深入的探討數(shù)學細節(jié)，而主要從基礎的機制設計角度來解釋這項技術(shù)，讓讀者初步理解FHE的基本運行邏輯，并介紹FHE的幾個主要應用模式。

上圖展示了線上投票的三種加密/解密方案，其中E()表示加密操作，而D()表示解密操作；

左側(cè)圖中，一個受信任的中間人在公布投票結(jié)果前，會對各個投票數(shù)據(jù)進行混淆和解密，我們必須假設該中間人不會泄露隱私，且投票統(tǒng)計結(jié)果是正確無誤的；

在中間的圖中，使用了TEE，TEE能保證數(shù)據(jù)完整性和隱私保護；

而在最右側(cè)的圖中，使用了同態(tài)加密技術(shù)：加密后的投票數(shù)據(jù)可以被公開加總求和，然后再解密得到結(jié)果，算出最終的投票數(shù)

FHE（全同態(tài)加密）是緊湊型加密方案，輸出結(jié)果?(?)的密文數(shù)據(jù)大小，以及解密該結(jié)果所需的工作量，僅取決于輸入數(shù)據(jù)?對應的原始明文，并不依賴于所采用的計算過程，這與那些非緊湊型的加密系統(tǒng)截然不同，后者往往簡單地把?與函數(shù)?的源碼連接起來，然后讓接收者自己解密?并輸入到?中來完成計算任務。

在現(xiàn)實中，F(xiàn)HE外包模式通常被視作TEE等安全執(zhí)行環(huán)境的替代方案，F(xiàn)HE的安全性基于密碼學算法，而不依賴于硬件等實體設備。因此，F(xiàn)HE完全不受被動側(cè)信道攻擊或云端服務器被攻擊的影響。想象一下，當某人需要外包出去一些計算任務，但數(shù)據(jù)非常敏感，他可能不愿意使用搭建在AWS上的虛擬機（VM），因為這類基于云端的服務器背后往往存在更高級的控制人。他也可能對SGX或TEE這類東西猶豫不決，因為運行TEE的主機可以監(jiān)控該計算任務在執(zhí)行時產(chǎn)生的功耗或運行時間等，可能通過這些數(shù)據(jù)來推斷出一些信息。

然而，如果使用FHE，將計算任務外包出去的人就可以安心——因為在FHE的系統(tǒng)中要破解私密信息，就必須破解其用到的密碼學算法，但這在目前幾乎無法做到。

但是，雖然密碼學算法可以防止攻擊者在不知道密鑰的情況下破解?對應的明文，但另一方面，通用延展性則允許攻擊者對輸出結(jié)果?(?)進行修改，這相當于一種主動側(cè)信道攻擊：攻擊者可以對執(zhí)行加密算法的硬件進行針對性的攻擊，影響輸出結(jié)果。這聽起來似乎很可怕，但在FHE的設計中，這類惡意攻擊可以通過在計算流程中制造冗余來進行規(guī)避。

簡要總結(jié)的話，F(xiàn)HE通常會用到幾組密鑰，包含以下幾部分：

解密密鑰（DecryptionKey）：這是整個FHE加密系統(tǒng)中的主密鑰，所有其他類型的密鑰都可以根據(jù)主密鑰來導出。解密密鑰通常在用戶本地生成，從不傳輸給外界，只有持有者本人能用它來解密FHE密文。這意味著密文即使在傳輸中被他人截獲，也無法被解密，除非他們擁有解密密鑰。

加密密鑰（EncryptionKey）：在FHE的公鑰模式下，加密密鑰是用來將明文轉(zhuǎn)換為密文的密鑰。當生成初始密文的人不是解密密鑰/主密鑰的持有者時，就會使用加密密鑰來進行加密。該密鑰通常中等大小，由一些隨機的零加密組成。由于FHE支持仿射函數(shù)（affinefunctions），足以用于加密任何消息。

在公鑰加密模式中，加密密鑰通常是公開的，任何人都可以用它來加密數(shù)據(jù)，但只有解密密鑰的持有者才能針對性的解密。

計算密鑰（EvaluationKey）：計算密鑰是用來對密文?進行同態(tài)運算的專用密鑰，使得FHE系統(tǒng)可以在不對密文?進行解密的情況下，對密文進行同態(tài)運算。計算密鑰可以像公鑰一樣被公開發(fā)布，即使他人獲知了計算密鑰，也無法破解出密文?，而只能對密文進行同態(tài)運算得到一個輸出結(jié)果。

此外，當使用計算密鑰進行運算時，密文的結(jié)構(gòu)保持不變，對密文?進行同態(tài)運算得到的結(jié)果會被重新加密為新的密文，這確保了計算過程中的隱私性，即使計算過程是公開的也不會泄露機密數(shù)據(jù)。

在上述幾種密鑰的持有者中，解密密鑰/主密鑰持有者是最敏感的，他要確保整個同態(tài)操作的執(zhí)行鏈條/流程有效無誤，最終的密文是安全的，然后解密得到明文結(jié)果。如果在FHE的操作鏈條中引入惡意操作，解密密鑰有可能會在解密時被泄露。但幸運的是，同態(tài)操作可以公開進行并被任何人所驗證。

FHE的具體場景/模式

在本節(jié)中，我們將描述一些FHE中的常見場景/模式，并討論每種模式的優(yōu)缺點。

外包模式（OutsourcingMode）

TwoPartyComputingMode（兩方計算模式）

AggregationMode（聚合模式）

Client-ServerMode（客戶端-服務器模式）

關(guān)于同態(tài)加密的其他細節(jié)

同態(tài)加密如何確保外部計算結(jié)果是有效的？

在多方合作的場景中使用FHE是更容易的，因為每個參與者都有動機誠實地遵循協(xié)議規(guī)定。例如，F(xiàn)HE可以在位于兩個不同國家但屬于同一公司/組織內(nèi)的兩個法人實體之間進行加密計算并統(tǒng)計一些數(shù)據(jù)：諸如GDPR之類的法規(guī)允許你對外發(fā)布某些統(tǒng)計數(shù)據(jù)，但會禁止將所有個人數(shù)據(jù)集中存儲在同一物理地點。

在這種情況下，使用FHE是可行的，所有參與者都有動機誠實地遵循協(xié)議規(guī)定。而在參與方并非彼此合作的場景中，確保計算任務已被正確執(zhí)行的最簡單方法，是引入冗余（類似于多簽/共識）。例如，在前面提到的外包和聚合場景中，同態(tài)計算用到的函數(shù)公式是完全公開的，并且可以是確定性的，只要兩個或更多獨立實體得出完全相同的輸出密文，那么整個計算過程就是正確的，結(jié)果也是可信的。冗余程度越高，最終結(jié)果的可信度就越高，但這需要在效率方面進行權(quán)衡。

此外，當承包計算任務的計算方通過對輸入和輸出密文進行數(shù)字簽名來擔保FHE結(jié)果有效時，每個人都可以重跑相同的FHE計算流程，并檢查計算方給出的證明是否有效。任何計算方的欺騙行為都可以被檢測出來并被懲罰，并可以與一個公開可驗證的證書相關(guān)聯(lián)，該證書會揭露欺騙行為和欺騙者——我們稱這種模型為強隱蔽安全模型。

至于完全同態(tài)簽名，是另一種驗證計算正確性的方法，無需第三方驗證者，但通常需要更多的軟硬件資源來參與。

FHE如何確保最終接收者只解密最終結(jié)果而非中間變量？

最簡單的方法是確保解密密鑰持有者無法訪問FHE計算流程中產(chǎn)生的中間密文。在雙方計算場景或客戶端-服務器場景中，Alice對輸入結(jié)果進行加密，Bob對密文進行計算并將加密的輸出結(jié)果傳輸回Alice，顯然Alice只能解密最終結(jié)果，無法訪問中間變量。

在基于云端服務器的場景，例如線上投票系統(tǒng)中，許多參與者會在AWS等公共的云端服務器上發(fā)送加密后的投票數(shù)據(jù)，這里會用到一種手段：解密密鑰通常不會交給單個接收者，而是以秘密共享的方式分配給不同的人或機構(gòu)（類似于MPC）。在這種情況下，只有通過執(zhí)行多方計算并讓持有解密密鑰的成員之間在線通信，才能對特定密文進行解密。如果其中某些人拒絕配合其他人，則無法進行解密。這樣就可以通過設置相應的閾值來提高系統(tǒng)的整體安全性。

同態(tài)加密的構(gòu)建模塊

同態(tài)加密有三種類型：部分同態(tài)加密（PHE）、分級同態(tài)加密（LHE）和完全同態(tài)加密（FHE）。部分同態(tài)加密只允許我們對某些計算任務進行同態(tài)加密（例如求和、線性函數(shù)、雙線性函數(shù)），而分級同態(tài)加密和完全同態(tài)加密可以支持任意的計算任務。

對于LHE來說，系統(tǒng)用到/產(chǎn)生的參數(shù)依賴于要執(zhí)行的函數(shù)計算?()，并隨著該函數(shù)計算復雜性的增加而增長，這反過來導致密文和密鑰的大小也跟著增加，會消耗更多的存儲和通訊資源。而FHE方案允許我們在給定的一組參數(shù)下（也就是給定的密鑰和密文大小下），計算任何可以表示為二進制邏輯門電路的函數(shù)。也就是說，與LHE不同，即使需要計算的任務變得越來越復雜，F(xiàn)HE方案涉及的參數(shù)（以及密鑰和密文）也不會變大。

因此，F(xiàn)HE是唯一一種能保證同態(tài)計算的內(nèi)存消耗和運行耗時都與原始明文/任務成正比的模式。但是，F(xiàn)HE有一個技術(shù)上的問題：隨著計算的持續(xù)進行，密文中包含的噪聲（垃圾數(shù)據(jù)）會越來越多。為了避免噪聲過多導致解密結(jié)果出錯，F(xiàn)HE方案會定期執(zhí)行一種代價較高的操作，稱為自舉（bootstrapping），它可以將噪聲減少到可控水平。日后我們將對此進行更多的介紹和科普，大家敬請期待！

原文鏈接：https://cryptographycaffe.sandboxaq.com/posts/fhe-01/