幾分鐘搞懂全同態(tài)加密FHE：運(yùn)行模式與應(yīng)用場(chǎng)景
原文標(biāo)題：FullyHomomorphicEncryption:IntroductionandUse-Cases
原文作者：NicolasGama和SandraGuasch，SandBoxAQ
編譯：Faust，極客web3
這篇博客是對(duì)全同態(tài)加密（FHE）的系統(tǒng)性介紹，但我們并不在此深入的探討數(shù)學(xué)細(xì)節(jié)，而主要從基礎(chǔ)的機(jī)制設(shè)計(jì)角度來解釋這項(xiàng)技術(shù)，讓讀者初步理解FHE的基本運(yùn)行邏輯，并介紹FHE的幾個(gè)主要應(yīng)用模式。
上圖展示了線上投票的三種加密/解密方案，其中E()表示加密操作，而D()表示解密操作；
左側(cè)圖中，一個(gè)受信任的中間人在公布投票結(jié)果前，會(huì)對(duì)各個(gè)投票數(shù)據(jù)進(jìn)行混淆和解密，我們必須假設(shè)該中間人不會(huì)泄露隱私，且投票統(tǒng)計(jì)結(jié)果是正確無誤的；
在中間的圖中，使用了TEE，TEE能保證數(shù)據(jù)完整性和隱私保護(hù)；
而在最右側(cè)的圖中，使用了同態(tài)加密技術(shù)：加密后的投票數(shù)據(jù)可以被公開加總求和，然后再解密得到結(jié)果，算出最終的投票數(shù)
FHE（全同態(tài)加密）是緊湊型加密方案，輸出結(jié)果?(?)的密文數(shù)據(jù)大小，以及解密該結(jié)果所需的工作量，僅取決于輸入數(shù)據(jù)?對(duì)應(yīng)的原始明文，并不依賴于所采用的計(jì)算過程，這與那些非緊湊型的加密系統(tǒng)截然不同，后者往往簡(jiǎn)單地把?與函數(shù)?的源碼連接起來，然后讓接收者自己解密?并輸入到?中來完成計(jì)算任務(wù)。
在現(xiàn)實(shí)中，F(xiàn)HE外包模式通常被視作TEE等安全執(zhí)行環(huán)境的替代方案，F(xiàn)HE的安全性基于密碼學(xué)算法，而不依賴于硬件等實(shí)體設(shè)備。因此，F(xiàn)HE完全不受被動(dòng)側(cè)信道攻擊或云端服務(wù)器被攻擊的影響。想象一下，當(dāng)某人需要外包出去一些計(jì)算任務(wù)，但數(shù)據(jù)非常敏感，他可能不愿意使用搭建在AWS上的虛擬機(jī)（VM），因?yàn)檫@類基于云端的服務(wù)器背后往往存在更高級(jí)的控制人。他也可能對(duì)SGX或TEE這類東西猶豫不決，因?yàn)檫\(yùn)行TEE的主機(jī)可以監(jiān)控該計(jì)算任務(wù)在執(zhí)行時(shí)產(chǎn)生的功耗或運(yùn)行時(shí)間等，可能通過這些數(shù)據(jù)來推斷出一些信息。
然而，如果使用FHE，將計(jì)算任務(wù)外包出去的人就可以安心——因?yàn)樵贔HE的系統(tǒng)中要破解私密信息，就必須破解其用到的密碼學(xué)算法，但這在目前幾乎無法做到。
但是，雖然密碼學(xué)算法可以防止攻擊者在不知道密鑰的情況下破解?對(duì)應(yīng)的明文，但另一方面，通用延展性則允許攻擊者對(duì)輸出結(jié)果?(?)進(jìn)行修改，這相當(dāng)于一種主動(dòng)側(cè)信道攻擊：攻擊者可以對(duì)執(zhí)行加密算法的硬件進(jìn)行針對(duì)性的攻擊，影響輸出結(jié)果。這聽起來似乎很可怕，但在FHE的設(shè)計(jì)中，這類惡意攻擊可以通過在計(jì)算流程中制造冗余來進(jìn)行規(guī)避。
簡(jiǎn)要總結(jié)的話，F(xiàn)HE通常會(huì)用到幾組密鑰，包含以下幾部分：
解密密鑰（DecryptionKey）：這是整個(gè)FHE加密系統(tǒng)中的主密鑰，所有其他類型的密鑰都可以根據(jù)主密鑰來導(dǎo)出。解密密鑰通常在用戶本地生成，從不傳輸給外界，只有持有者本人能用它來解密FHE密文。這意味著密文即使在傳輸中被他人截獲，也無法被解密，除非他們擁有解密密鑰。
加密密鑰（EncryptionKey）：在FHE的公鑰模式下，加密密鑰是用來將明文轉(zhuǎn)換為密文的密鑰。當(dāng)生成初始密文的人不是解密密鑰/主密鑰的持有者時(shí)，就會(huì)使用加密密鑰來進(jìn)行加密。該密鑰通常中等大小，由一些隨機(jī)的零加密組成。由于FHE支持仿射函數(shù)（affinefunctions），足以用于加密任何消息。
在公鑰加密模式中，加密密鑰通常是公開的，任何人都可以用它來加密數(shù)據(jù)，但只有解密密鑰的持有者才能針對(duì)性的解密。
計(jì)算密鑰（EvaluationKey）：計(jì)算密鑰是用來對(duì)密文?進(jìn)行同態(tài)運(yùn)算的專用密鑰，使得FHE系統(tǒng)可以在不對(duì)密文?進(jìn)行解密的情況下，對(duì)密文進(jìn)行同態(tài)運(yùn)算。計(jì)算密鑰可以像公鑰一樣被公開發(fā)布，即使他人獲知了計(jì)算密鑰，也無法破解出密文?，而只能對(duì)密文進(jìn)行同態(tài)運(yùn)算得到一個(gè)輸出結(jié)果。
此外，當(dāng)使用計(jì)算密鑰進(jìn)行運(yùn)算時(shí)，密文的結(jié)構(gòu)保持不變，對(duì)密文?進(jìn)行同態(tài)運(yùn)算得到的結(jié)果會(huì)被重新加密為新的密文，這確保了計(jì)算過程中的隱私性，即使計(jì)算過程是公開的也不會(huì)泄露機(jī)密數(shù)據(jù)。
在上述幾種密鑰的持有者中，解密密鑰/主密鑰持有者是最敏感的，他要確保整個(gè)同態(tài)操作的執(zhí)行鏈條/流程有效無誤，最終的密文是安全的，然后解密得到明文結(jié)果。如果在FHE的操作鏈條中引入惡意操作，解密密鑰有可能會(huì)在解密時(shí)被泄露。但幸運(yùn)的是，同態(tài)操作可以公開進(jìn)行并被任何人所驗(yàn)證。
FHE的具體場(chǎng)景/模式
在本節(jié)中，我們將描述一些FHE中的常見場(chǎng)景/模式，并討論每種模式的優(yōu)缺點(diǎn)。
外包模式（OutsourcingMode）
TwoPartyComputingMode（兩方計(jì)算模式）
AggregationMode（聚合模式）
Client-ServerMode（客戶端-服務(wù)器模式）
關(guān)于同態(tài)加密的其他細(xì)節(jié)
同態(tài)加密如何確保外部計(jì)算結(jié)果是有效的？
在多方合作的場(chǎng)景中使用FHE是更容易的，因?yàn)槊總(gè)參與者都有動(dòng)機(jī)誠(chéng)實(shí)地遵循協(xié)議規(guī)定。例如，F(xiàn)HE可以在位于兩個(gè)不同國(guó)家但屬于同一公司/組織內(nèi)的兩個(gè)法人實(shí)體之間進(jìn)行加密計(jì)算并統(tǒng)計(jì)一些數(shù)據(jù)：諸如GDPR之類的法規(guī)允許你對(duì)外發(fā)布某些統(tǒng)計(jì)數(shù)據(jù)，但會(huì)禁止將所有個(gè)人數(shù)據(jù)集中存儲(chǔ)在同一物理地點(diǎn)。
在這種情況下，使用FHE是可行的，所有參與者都有動(dòng)機(jī)誠(chéng)實(shí)地遵循協(xié)議規(guī)定。而在參與方并非彼此合作的場(chǎng)景中，確保計(jì)算任務(wù)已被正確執(zhí)行的最簡(jiǎn)單方法，是引入冗余（類似于多簽/共識(shí)）。例如，在前面提到的外包和聚合場(chǎng)景中，同態(tài)計(jì)算用到的函數(shù)公式是完全公開的，并且可以是確定性的，只要兩個(gè)或更多獨(dú)立實(shí)體得出完全相同的輸出密文，那么整個(gè)計(jì)算過程就是正確的，結(jié)果也是可信的。冗余程度越高，最終結(jié)果的可信度就越高，但這需要在效率方面進(jìn)行權(quán)衡。
此外，當(dāng)承包計(jì)算任務(wù)的計(jì)算方通過對(duì)輸入和輸出密文進(jìn)行數(shù)字簽名來?yè)?dān)保FHE結(jié)果有效時(shí)，每個(gè)人都可以重跑相同的FHE計(jì)算流程，并檢查計(jì)算方給出的證明是否有效。任何計(jì)算方的欺騙行為都可以被檢測(cè)出來并被懲罰，并可以與一個(gè)公開可驗(yàn)證的證書相關(guān)聯(lián)，該證書會(huì)揭露欺騙行為和欺騙者——我們稱這種模型為強(qiáng)隱蔽安全模型。
至于完全同態(tài)簽名，是另一種驗(yàn)證計(jì)算正確性的方法，無需第三方驗(yàn)證者，但通常需要更多的軟硬件資源來參與。
FHE如何確保最終接收者只解密最終結(jié)果而非中間變量？
最簡(jiǎn)單的方法是確保解密密鑰持有者無法訪問FHE計(jì)算流程中產(chǎn)生的中間密文。在雙方計(jì)算場(chǎng)景或客戶端-服務(wù)器場(chǎng)景中，Alice對(duì)輸入結(jié)果進(jìn)行加密，Bob對(duì)密文進(jìn)行計(jì)算并將加密的輸出結(jié)果傳輸回Alice，顯然Alice只能解密最終結(jié)果，無法訪問中間變量。
在基于云端服務(wù)器的場(chǎng)景，例如線上投票系統(tǒng)中，許多參與者會(huì)在AWS等公共的云端服務(wù)器上發(fā)送加密后的投票數(shù)據(jù)，這里會(huì)用到一種手段：解密密鑰通常不會(huì)交給單個(gè)接收者，而是以秘密共享的方式分配給不同的人或機(jī)構(gòu)（類似于MPC）。在這種情況下，只有通過執(zhí)行多方計(jì)算并讓持有解密密鑰的成員之間在線通信，才能對(duì)特定密文進(jìn)行解密。如果其中某些人拒絕配合其他人，則無法進(jìn)行解密。這樣就可以通過設(shè)置相應(yīng)的閾值來提高系統(tǒng)的整體安全性。
同態(tài)加密的構(gòu)建模塊
同態(tài)加密有三種類型：部分同態(tài)加密（PHE）、分級(jí)同態(tài)加密（LHE）和完全同態(tài)加密（FHE）。部分同態(tài)加密只允許我們對(duì)某些計(jì)算任務(wù)進(jìn)行同態(tài)加密（例如求和、線性函數(shù)、雙線性函數(shù)），而分級(jí)同態(tài)加密和完全同態(tài)加密可以支持任意的計(jì)算任務(wù)。
對(duì)于LHE來說，系統(tǒng)用到/產(chǎn)生的參數(shù)依賴于要執(zhí)行的函數(shù)計(jì)算?()，并隨著該函數(shù)計(jì)算復(fù)雜性的增加而增長(zhǎng)，這反過來導(dǎo)致密文和密鑰的大小也跟著增加，會(huì)消耗更多的存儲(chǔ)和通訊資源。而FHE方案允許我們?cè)诮o定的一組參數(shù)下（也就是給定的密鑰和密文大小下），計(jì)算任何可以表示為二進(jìn)制邏輯門電路的函數(shù)。也就是說，與LHE不同，即使需要計(jì)算的任務(wù)變得越來越復(fù)雜，F(xiàn)HE方案涉及的參數(shù)（以及密鑰和密文）也不會(huì)變大。
因此，F(xiàn)HE是唯一一種能保證同態(tài)計(jì)算的內(nèi)存消耗和運(yùn)行耗時(shí)都與原始明文/任務(wù)成正比的模式。但是，F(xiàn)HE有一個(gè)技術(shù)上的問題：隨著計(jì)算的持續(xù)進(jìn)行，密文中包含的噪聲（垃圾數(shù)據(jù)）會(huì)越來越多。為了避免噪聲過多導(dǎo)致解密結(jié)果出錯(cuò)，F(xiàn)HE方案會(huì)定期執(zhí)行一種代價(jià)較高的操作，稱為自舉（bootstrapping），它可以將噪聲減少到可控水平。日后我們將對(duì)此進(jìn)行更多的介紹和科普，大家敬請(qǐng)期待！
原文鏈接：https://cryptographycaffe.sandboxaq.com/posts/fhe-01/