多密鑰全同態加密研究*

李寧波, 周潭平,, 車小亮, 楊曉元,, 韓益亮,

1. 武警工程大學 密碼工程學院, 西安710086

2. 網絡與信息安全武警部隊重點實驗室, 西安710086

1 引言

隨著大數據時代的到來和云計算技術的發展, 通過互聯網產生的數據量呈現井噴式的增長. 為了能夠更加有效的處理這些數據, 越來越多的組織和用戶選擇將大量的數據上傳到云服務器端進行存放和處理.雖然云在成本和功能上有許多優勢, 但它也帶來了嚴重的機密性問題, 因為存儲在云中的數據可能很容易被云提供商甚至其他云客戶端竊取.

傳統的密碼技術雖然能夠確保數據在云端的保密存放, 但卻無法實現密文之間的運算和處理, 這給現實世界中的很多實際需求帶來了不便. 因此, 如何在保護用戶信息安全和隱私的情況下對密文數據進行計算, 是當前云環境下迫切需要解決的問題[1-3]. 全同態加密[4-10](Fully homomorphic encryption, FHE)支持對密文數據進行任意的運算處理, 具備強大的密態計算能力, 從而使個人計算機和移動設備成為對強大但不可信的云的可信但較弱的接口的前景成為可能[11-20]. 有密碼學者認為“公鑰加密開辟了密碼學的新方向, 而實用的全同態加密將催生新型分布式計算模式”[12].

傳統的全同態加密只適用于對涉及單個用戶的密文進行同態計算, 即參與計算的所有密文對應于相同的密鑰(所有的密文屬于同一個用戶), 然而在許多的現實場景中, 通常需要對多個用戶上傳到云端的數據進行安全的多方聯合計算. 例如, 他們可能希望云來計算他們數據庫上的聯合統計信息; 在數據庫集合中定位公共文件; 將多個(相互不信任的) 用戶的數據集中在一起, 通過特定的計算以實現共同的目標、達成統一的決策(此之外不泄露其它隱私信息) 等.

多方用戶計算的場景相對要復雜得多, 并且常常需要附帶一些特殊的需求. 比如: 在數據經過加密并上傳到云端之后, 用戶可以動態地選擇需要實現的計算函數以及參與計算的用戶. 其次, 在計算函數確定的情況下, 用戶希望云端在執行批量計算的同時, 能盡可能的減少參與計算的用戶的在線時間以及與用戶之間的在線交互. 最后, 對于用戶而言, 計算和通信的復雜度應該取決于用戶的輸入和云的輸出, 而與計算函數的復雜性和參與用戶的數量無關(這兩個因素可能會導致巨大的計算和通信成本)[11].

為了解決云環境下多用戶密文數據聯合計算的問題, López-Alt 等人在文獻[11] 中提出了多密鑰全同態加密(Multi-key fully homomorphic encryption, MKFHE) 的概念(如無特指, 全文中FHE 代表傳統的單密鑰全同態加密). MKFHE 支持對不同用戶(不同密鑰) 的密文進行任意的同態運算, 且運算之后的結果由參與計算的所有用戶聯合解密, 可以較好地解決多用戶密文聯合計算的問題. 目前大多數MKFHE都是基于格上困難問題構造的, 其相對于傳統的密碼體制能夠更好地應對量子計算機的威脅. 因此, 多密鑰全同態加密可以為云計算、外包計算等涉及多用戶(機構) 數據的領域, 提供信息傳輸、存儲和計算的安全, 保護用戶隱私[21,22], 從而為我國信息化系統安全防護提供有利的支撐, 具有重要的理論研究價值和應用價值. 以圖1 為例, 介紹云環境下MKFHE 在多用戶(機構) 數據安全分析方面的應用. 主要步驟如下:

(1) 不同的用戶或機構i利用各自的密鑰Keyi(i=1,··· ,N), 對各自的數據mi進行同態加密, 并將加密之后的密文(C1,··· ,CN) 上傳到云端;

(2) 云端根據所需實現的數據處理函數f, 對接收到的密文數據進行同態運算, 得到運算后的密態處理結果C;

(3) 云將密文結果C返回給所有參與計算的用戶或機構i;

(4) 各用戶或機構i接收到密文結果C后, 通過聯合解密恢復出最終的結果.

本文將依次從MKFHE 的研究現狀、MKFHE 方案的典型構造、云環境下利用MKFHE 來構造安全多方計算[23](Multi-party computing, MPC)、當前MKFHE 存在的問題以及未來發展趨勢等方面, 對多密鑰全同態加密的發展情況進行概述.

圖1 云環境下MKFHE 在多用戶數據安全分析方面的應用Figure 1 Application of MKFHE in secure data analysis of multiple parties under cloud environment

1.1 多密鑰全同態加密的定義

定義1[11](層次型多密鑰全同態加密): 給定安全參數λ, 令C為一類深度為L的運算電路, 一個層級(leveled) 多密鑰全同態加密方案ε=(Setup, KeyGen, Enc, Extend, Eval, Dec) 由以下算法組成:

初始化算法pp←E·Setup(1λ,1K,1L): 輸入安全參數λ, 參與計算的用戶數量的上界K, 電路深度的上界L, 輸出公共參數pp.

MKFHE 方案的緊湊性[24]: 對于一個層次性MKFHE 而言, 若存在一個多項式函數poly(·), 使得密文的長度|c|≤poly(λ,K,L), 且密文長度與運算電路C無關, 則稱該MKFHE 方案是緊湊的. 通常情況下, MKFHE 方案的密文長度與安全參數λ、參與方數量K和電路深度L多項式級別相關.

2 研究現狀

當前的MKFHE 方案都是在經典的全同態加密方案的基礎上發展而來, 按照不同類型MKFHE 方案出現的時間順序, 其發展可以分為四個階段: 第一階段是López-Alt 等人在2012 年首次提出的基于NTRU 密碼系統[25,26]的MKFHE 方案LTV12[11], 以及后續的一些方案[27-29](此類簡稱NTRU型MKFHE); 第二階段是2015 年Clear 和McGoldrick 在FHE 方案GSW13[30]的基礎上, 提出的支持多身份(多密鑰) 用戶密文進行同態運算的MKFHE 方案CM15[31], 以及后續的一些優化和擴展方案[32-34](此類簡稱為GSW 型MKFHE); 第三階段是2017 年中科院陳隆等人在FHE 方案BGV12[35]的基礎上, 提出的MKFHE 方案CZW17[24], 以及其它的擴展方案[36,37](此類簡稱為BGV型MKFHE);第四階段是Chen 等人在FHE 方案CGGI16[38]、CGGI17[39]的基礎上, 提出的MKFHE方案CCS19[40](簡稱TFHE 型MKFHE). 除了上述四類主流的MKFHE 之外, 還有在量子同態加密方案DSS16[41]的基礎上發展而來的MKFHE 方案Goy18[42](簡稱量子MKFHE). MKFHE 的重要研究進展見圖2.

2.1 NTRU 型FHE 和MKFHE

1996 年美密會上, Hoffstein 等人首次提出了NTRU 型PKE (Public key encryption, 公鑰加密)系統, 并于1998 年在文獻[25] 中正式對NTRU 密碼體制進行了公開發表. 此后, 許多密碼學者對該密碼體制進行了深入的研究. 2011 年歐密會上, Stehl′e 和Steinfeld 對原始的NTRU 方案改進后, 提出了SS11[26](也稱為pNE), 該方案首次對NTRU 密碼系統的可證明安全進行了完整證明, 在標準模型下將方案的安全性規約到了最壞情況下理想格上的困難問題假設. 其后的一些優化方案(NTRUEncrypt[26],NTRU-HRSS[43], NTRUPrime[44,45]) 具有加解密速度快、計算效率較高的優點, 具備較強的實用性, 是抗量子攻擊密碼算法的重要備選方案. 此后, 密碼學家圍繞NTRU 方案的安全性、功能擴展等方面進行了進一步的研究. 2016 年美密會上, Albrecht 等人針對NTRU 方案提出了一類子域攻擊[46], 雖然該類子域攻擊無法對SS11 方案進行高效攻擊, 但是對于需要設置大密文模數的NTRU 型全同態加密和多線性映射方案, 攻擊效果明顯. 2017 年PKC 上, 清華大學王小云院士團隊提出了一種基于素數階分圓多項式環的pNE 變體—YXW17 方案[47], 指出目前子域攻擊無法攻破基于素數階分圓多項式環上的NTRU方案, 并將方案的安全性規約到格上困難問題假設. 同年, 王小云院士團隊又對YXW17 方案進行了優化[48], 并大幅降低了YXW17 方案中參數尺寸.

2012 年, López-Alt 等人以云環境下多用戶密文數據的同態計算為背景, 首次給出了MKFHE 的密碼學定義, 并構造了首個基于NTRU 密碼系統的MKFHE 方案LTV12[11], 該方案的安全性基于環上誤差學習問題[49](Ring-Learning With Errors, RLWE) 和判定性小多項式比問題[11](Decisional small polynomial ratio, DSPR). 由于NTRU 型加密方案的密文結構天然具有支持多用戶(密鑰) 密文同態計算的性質, 因此可以較好地被用來構造MKFHE 方案. López-Alt 等人的工作揭開了MKFHE 研究的序幕, 也為其它密碼學者開展關于MKFHE 的研究提供了理論基礎. 2016 年, Dor?z 等人對LTV12 的參數進行了優化, 并引入FHE 中的Batching 等優化技術[50], 提出一個較高效的MKFHE 方案DHS16[27].PKC 2017 上, Chongchitmate 等人在LTV12 的基礎上構造了具備電路隱私的MKFHE 方案CO17[28],并構造了具有電路隱私性的3 輪動態安全多方計算協議. 2020 年, 武警工程大學楊曉元教授團隊利用比特丟棄技術和密文維度擴展技術, 構造了無需進行密鑰轉化的高效NTRU 型MKFHE 方案CZL+20[29],該方案無需計算密鑰, 有效降低了密鑰規模.

2.2 GSW 型FHE 和MKFHE

2013 年, Gentry 等人提出了近似特征向量方法, 并據此構造了基于誤差學習問題(Learning with errors, LWE) 問題的FHE 方案GSW13[30]. 該方案的密文同態加法和乘法只需要通過簡單的矩陣加法和乘法即可實現, 具有同態運算簡潔、不需要額外提供計算密鑰等優點. 此外, 他們在GSW13 的基礎上,分別構造了基于身份和屬性的IBFHE 方案和ABFHE 方案. 此后, 密碼學者在GSW13 的基礎上, 構造了多個效率更高的GSW 型FHE 方案[51-54], 但這些方案的密文通常是由多個(R)LWE 實例組成的矩陣, 密文尺寸較大.

2015 年美密會上, Clear 和McGoldrick 將GSW13 方案擴展到多身份(多密鑰), 提出了首個在標準模型下具備選擇性安全的GSW 型MKFHE 方案CM15[31]. 相比于LTV12 方案所依賴的非標準假設(DSPR 假設), CM15 方案的安全性基于標準假設LWE 問題[55], 因此具備更強的安全性. CM15 方案首次為如何將其它類型的FHE 方案轉化為MKFHE 提供了思路: 即首先將參與用戶的新鮮密文進行密文擴展(Ciphertext extension), 使得經過擴展后的密文對應的用戶集為所有參與計算的用戶, 然后再對其進行同態計算, 最終通過所有用戶的聯合密鑰對同態運算后的密文進行解密. 這個思路被大多基于LWE/RLWE 問題的MKFHE 方案沿用. 除此之外, CM15 方案還給出了利用任意的FHE 方案來構造一個基于身份的FHE 方案的通用轉化框架.

2016 年歐密會上, Mukherjee 和Wichs 對CM15 方案的密文擴展過程進行了簡化, 通過構造一個“Masking Scheme” 實現對密文的擴展, 提出了MW16[32]方案. 該方案允許對多密鑰密文進行一輪的分布式解密, 并可以進一步構造兩輪MPC 協議. 該協議能夠抵抗任意半惡意敵手的攻擊, 且安全性得到證明. CM15 和MW16 需要提前對參與同態計算用戶的數量進行設置, 并且在運算過程中無法實現新用戶的加入(同態計算后的密文, 無法與新加入用戶的密文進行新的同態計算), 這種類型的MKFHE 被稱為單跳(Single-hop) 型MKFHE[33].

2016 年TCC 上, Peikert 和Shiehian 提出了具備多跳(Multi-hop) 性質的MKFHE 方案PS16[33].在該方案中, 同態運算后輸出的密文能夠與新加入參與方的密文重新進行運算, 即任何參與方都可以實時、動態地加入到密文運算的過程中, 但是參與方的數量具有一定限制.

2016 年美密會上, Brakerski 和Perlman 提出了基于LWE 問題的全動態(Fully dynamic) MKFHE方案BP16[34]. 該方案允許新的參與方動態地加入到同態運算中, 因此參與方的數量不需要提前進行設定, 且擴展密文的長度隨著參與方數量的增加而線性增長, 但該方案利用自舉(bootstrapping) 來實現密文擴展, 且自舉密鑰的生成過程中仍需要對參與用戶私鑰的密文進行擴展, 從而導致密文同態運算的效率較低.

2.3 BGV 型MKFHE

在2011 年美密會上, Brakerski 等人構造了基于RLWE 問題的FHE 方案BV11a[56], 該方案的安全性可以規約到最壞情況下理想格上的困難問題. 同年, Brakerski 和Vaikuntanathan 基于LWE 問題構造了BV11b 方案[57], 在類同態加密方案的基礎上, 利用重線性化和降維降模技術構造FHE[6]. 2012年, Brakerski 等人基于BV11b 構造了BGV12 方案[35], 將重線性化技術和降維降模技術歸納為密鑰交換(Key-switching) 技術和模數交換(Modulus-switching) 技術, 并且引入了一些其它的優化方法. 隨后的一些改進方案[58-62]進一步提升了BGV 型FHE 方案的效率. 2017 年亞密會上, Cheon 等人將錯誤看成是明文的一部分, 并在特定區間利用三角函數模擬求模函數的方法, 構造了支持高效同態運行近似算術計算的全同態加密CKKS17[63], 大部分BGV 型全同態加密方案中的優化技術都可以應用到該方案.

在TCC2017 上, 中科院陳隆等人開創性地利用環上的GSW 加密方案來生成密鑰轉化過程所需的計算密鑰, 提出了首個BGV 型多跳MKFHE 方案CZW17[24], 該方案支持基于中國剩余定理的密文打包技術, 并可用于構造兩輪MPC 協議和門限解密(Threshold decryption) 協議.

2019 年, 武警工程大學李寧波等人構造了BGV 型MKFHE 方案LZY+19[36]. 該方案將CZW17方案中BGV 和GSW 擴展密文的尺寸縮減了將近一半, 并利用RBGV 和RGSW 密文之間的混合同態乘法生成計算密鑰, 大幅降低了計算密鑰生成過程中輸入密鑰的尺寸. 此外, 該方案還首次給出了定向解密的概念, 設計了可由指定用戶獲得最終解密結果的BGV 型定向解密協議, 擴展了多密鑰全同態的應用范圍, 增強了數據擁有者對于解密結果的可控性.

同年, Chen 等人對BGV 型MKFHE 中的重線性化(密鑰交換) 過程進行了優化, 構造了高效的多密鑰同態加密方案CDKS19[37], 并將該方案應用于神經網絡的隱私計算. CDKS19 方案提出了一種全新的計算密鑰生成方法(構造用戶私鑰的組合密文) 和兩種重線性化算法, 相比于CZW17 和LZY+19 方案,該方案生成計算密鑰前無需對用戶私鑰的密文進行擴展, 較大程度地降低了方案的計算復雜度, 同態運算的效率更高.

2.4 TFHE 型FHE 和MKFHE

2016 年亞密會上, Chillotti 等人基于GSW13 方案在T= (0,1] 環上的變種TGSW, 構造了全同態方案CGGI16[38]. 該方案通過構造高效的多項式指數上的加法運算, 以及TGSW 密文和常數之間的高效同態常數乘法, 將全同態加密方案中最為復雜和耗時的自舉過程的運行時間縮短到52 ms, 自舉過程中的密鑰量由1 GB 減少到24 MB. 2017 年亞密會上, Chillotti 等人在CGGI17[39]方案中進一步對CGGI16 方案中的累加過程進行了優化, 從而將自舉過程的時間再次縮減到13 毫秒, 并在此基礎上, 編寫了全同態加密軟件庫TFHE.2018 年,武警工程大學周潭平等人在ZYL+18[64]方案中通過構造增強同態常數乘法函數, 將同態累加運算次數減少了2/3, 進一步提升了自舉過程的效率. 2018 年美密會上Bourse等人[65]通過合并同類項的方法, 優化了ZYL+18 中的增強同態常數乘法函數和全同態加密算法, 并將算法應用于神經網絡的隱私計算中.

2019 年亞密會上, Chen 等人在CGGI17[39]的基礎上, 利用特殊的GSW 密文設計了高效的密文擴展算法, 實現了對計算密鑰的高效擴展, 并據此提出了多密鑰全同態加密方案CCS19[40], 該方案密文長度隨用戶數量增加呈線性增加, 同時作者編寫了多密鑰全同態加密軟件庫MKTFHE, 對MKFHE 方案的應用具有重要指導意義.

2.5 量子HE 和MKFHE

2013 年, Liang 在文獻[66]中首次提出了量子同態加密(Quantum homomorphic encryption, QHE)的思想, 并構造了一個對稱量子全同態加密(Quantum fully homomorphic encryption, QFHE) 方案. 與經典的同態加密相比, 量子同態加密的安全性更高. 2015 年美密會上, Broadbent 和Jeffery 在文獻[67]中正式給出了QHE 在公鑰加密和對稱加密系統下的定義, 并將標準模型下的語義安全擴展到量子模型下的語義安全. 2016 年美密會上, Dulek 等人提出了緊湊型QHE 方案DSS16[41], 方案能夠高效同態運行任意多項式級別的量子電路.

2018 年, Goyal 等人在DSS16 方案的基礎上, 提出了量子多密鑰同態加密的概念, 并且構造了從經典的層次型多密鑰同態加密到量子層次型多密鑰同態加密的通用轉化方法[42].

表1 對現階段四類MKFHE 方案存在的優缺點進行了分析.

3 MKFHE 方案的典型構造

本節主要對當前MKFHE 方案中的一些經典方案進行簡要的介紹.

3.1 預備知識

表1 四類MKFHE 方案分析Table 1 Analysis of advantages and disadvantages of four MKFHE schemes

3.1.2 廣義誤差學習問題

誤差學習問題(Learning with error, LWE) 和環上的誤差學習問題(Ring-learning with error,RLWE) 在形式上幾乎相同, 只是底層的環結構有所區分(整數環和多項式環), 在BGV12 方案[35]中,兩者被歸納總結為廣義誤差學習問題(General learning with error, GLWE).

LWE 問題: 當d=1 時, GLWE 問題即轉化為LWE 問題.

RLWE 問題: 當n=1 時, GLWE 問題即轉化為RLWE 問題.

3.1.3 判定性小多項式比問題

定義3 (判定性小多項式比問題)[11]: 給定多項式環R= Z[x]/Φn(x), Rq=R/qR, 以及環R上bound 為B的離散高斯分布χ=χ(λ), 判定性小多項式比假設是指難以區分以下兩個分布:

(1) 一個多項式h=tg/f,其中f=tf′+1 且在Rq上可逆,f′,g ←χ;

3.2 NTRU 型MKFHE 典型構造

作為首個被提出的多密鑰全同態加密方案, LTV12 方案[11]無論是在方案架構, 還是設計思路上都給了MKFHE 研究者很大的啟示, 這里首先對LTV12 方案進行簡要的概述.

初始化算法LTV12.Setup(1λ):

加密算法LTV12.Enc(pk,m):

(1) 輸入待加密的明文m, 隨機選取s,e ←χ;

(2) 輸出密文c:=h0s+2e+m ∈Rq0.

解密算法LTV 12. Dec (f1,L,··· ,fN,L,c):

(1) 輸入密文c ∈RqL, 以及參與到該密文生成過程的N個用戶的私鑰序列f1,L,··· ,fN,L;

3.3 GSW 型MKFHE 方案的典型構造

令cI為C的倒數第二列, 且q/4＜2l?2≤q/2,計算x=scI=erI+μ·2l?2, 如果x接近于2l?2,則返回解密結果μ=1; 如果x接近于0, 則返回解密結果μ=0.

PS 16#2·Eval(C1,C2): 同態運算的過程與GSW13 方案相同.

(2) BP16 中多跳功能的實現

與PS16 的實現方式不同, BP16 方案[34]通過自舉(bootstrapping) 技術來實現多跳, 其擴展密文長度隨著參與方數量的增加而線性增加. 此外, BP16 將解密電路轉化為一個排列分支程序(permutation branching programs)[68,69], 從而減少同態運算電路的空間復雜度. BP16 通過自舉實現多跳的簡要思路如下:

3.4 BGV 型MKFHE 方案的典型構造

在2017 年TCC 上, 中科院陳隆等人提出了第一個BGV 型MKFHE 方案CZW17[24]. 由于BGV密文特殊的結構, 其密文擴展方式相對簡潔, 且密文擴展過程不需要計算密鑰的加入, 因此較容易滿足多跳的性質. 下面簡要對BGV 型MKFHE 的構造方法進行介紹:

需要注意的是, 在同態計算密鑰evkS的生成過程中, CZW17 方案利用多項式環上的GSW 密文擴展算法對emS進行密文擴展, 擴展密文的構造思路和結構與3.2.2 節相關內容類似, 只是輔助密文X的構造方式有所不同, 然后通過RGSW 密文之間的同態乘法來生成同態計算密鑰evkS. 這里對CZW17 方案中輔助密文的構造方法介紹如下:

與MW16 構造輔助密文的方式有所不同, CZW17 方案[24]采用多項式環上的BGV 加密方案對隨機矩陣R1進行加密, 并利用BitDecomp(·) 技術和Powersof 2(·) 技術來控制密文中的噪音, 以用戶1 和用戶2 為例, 輔助密文的簡要構造思路如下:

(1) 用戶1 對隨機矩陣R1中的每個元素進行加密:

并最終計算得到解密結果:μ:=pmod 2.

BGV 型全同態加密方案中, 需要密鑰交換(key-switching) 技術對密文的維度進行控制, 而BGV 型MKFHE 密鑰交換過程中的計算密鑰evkS無法利用BGV 加密生成(涉及密文乘法), 因此CZW17 方案利用多項式環上的GSW 加密算法來生成計算密鑰. 解密階段, CZW17 設計了門限解密協議, 該協議可以被用來構造一個2 輪的MPC.

除此之外, CZW17 方案中還用到了Batching[50]技術, 來提高方案的效率. 作為一個在單密鑰全同態加密中相對比較成熟的技術, Batching 可以將多個明文打包嵌入到同一個密文中, 從而提高同態加密和運算的效率. 事實上, 由于多密鑰全同態加密是在單密鑰全同態加密的基礎上延伸而來, 因此將傳統的(單密鑰) 全同態加密中的一些優化技術“移植” 到多密鑰全同態加密中, 很大程度上具有天然的可繼承性,比如文獻[28] 就將電路隱私技術運用到MKFHE 中, 提出了具備電路隱私性的多密鑰全同態加密方案CO17. 文獻[38] 中由抽象的同態解密結構為切入點, 來對傳統的單密鑰全同態加密方案的構造方法進行分析, 從而形式化地建立起全同態加密方案的構造思路和模式, 這種方法也可以用來對MKFHE 的實現方法進行分析.

3.5 基于TFHE 庫的MKFHE 方案的構造思路

2019 年, Chen 等人利用PS16[33]中的密文擴展方法, 在TFHE 庫[38]的基礎上, 提出了其多密鑰版本CCS19[40]. 該方案密文長度隨用戶數量的線性增長, 是第一個真正意義上進行代碼實現的多密鑰全同態加密方案. 本文只介紹該方案的核心思想, 具體的方案細節見文獻[40].

影響MKFHE 方案效率的核心問題在于計算密鑰的生成. 相對于BGV 型的MKFHE, 基于TFHE庫的MKFHE 進行同態運算過程中只涉及到了密文的加法(可以通過加法構造其它門電路), 因此在聯合計算密鑰生成過程中不需要進行同態乘法操作. 進一步的, TFHE 庫使用GSW 密文作為計算密鑰, 考慮到不需要使用GSW 的密文乘法, 因此CCS19 大幅簡化了GSW 密文的結構(構造了精簡版的GSW 密文). 精簡后的GSW 密文規模較低, 計算效率高, 方便算法實現.

4 基于MKFHE 的MPC

多密鑰全同態加密支持不同用戶(密鑰) 的密文之間的同態運算, 且同態運算之后的結果由所有參與計算的用戶聯合解密, 這一特性能夠很好的應用于云環境下多用戶數據之間的安全計算, 具有廣闊的理論研究價值和應用前景. 本節給出利用MKFHE 來構造MPC 的一般過程[32].

假設參與同態運算的N個用戶為{Pk}k∈[N],令f: (x)N →x為所需實現的運算函數,d為運算電路f的深度, 安全參數為λ, 過程如下:

Preprocessing(預處理) : 參與計算的所有用戶運行pp←MKFHE.Setup(1λ,1d), 得到方案所需的一些參數pp.

Input: 每個參與方Pk的輸入明文Xk,k ∈[K]. 協議運行流程如下:

Round I. 每個參與用戶Pk執行如下步驟:

輸入公共參數pp, 生成用戶的公鑰pkk、私鑰skk、擴展密鑰ekk、同態計算密鑰evkk:

云端將同態運算后的密文結果?c發送給所有參與計算的用戶.

Round III. 所有參與計算的用戶接收到?c后, 通過運行門限解密(threshold decryption) 協議, 來得到最終所需的解密結果, 步驟如下:

(1) 每個參與方Pk計算各自的部分解密結果

值得注意的是, 基于NTRU 型MKFHE 的MPC 在執行Round II 時, 并不需要對用戶上傳到云端的密文進行擴展, 但是其解密階段目前尚無有效的門限解密協議. 基于GSW 型MKFHE 的MPC 在Round I 的密鑰生成階段無需生成計算密鑰{evkk}k∈[N].

5 總結

外包計算、安全多方計算的應用需求, 推動多密鑰全同態加密的迅速發展. 隨著全同態加密和格密碼的蓬勃發展, 基于格的多密鑰全同態加密在安全性上能夠更好的應對量子計算機的威脅, 同時相對于傳統的全同態加密, 能夠支持不同用戶(密鑰) 密文間的同態運算, 為未來實現云環境下多用戶(機構) 數據間的安全分析提供了強大的理論支撐.

5.1 存在問題

現階段MKFHE 在方案構造和實現方面尚未成熟, 還存在以下待解決的問題.

NTRU 型MKFHE:具有加解密速度快、密文尺寸小、密鑰量少、支持不同密鑰對應的密文之間進行同態運算等優勢, 但仍存在以下問題有待解決: (1)NTRU 密碼體制的安全性無法得到嚴格的證明; (2)當前NTRU 型MKFHE 方案大多基于2 的冪次階分圓多項式環進行構造, 該方案的安全性可能會受到子域攻擊的影響; (3) 多用戶聯合解密時尚無安全有效的聯合解密協議. 目前NTRU 型MKFHE 在聯合解密時需要通過復雜的交互來實現, 解密的復雜度和通信量較大, 不易于實際的應用.

GSW 型MKFHE: 具有同態運算形式相對簡單、用戶無需提前生成計算密鑰等優勢, 但仍存在以下問題有待解決: (1) 密文擴展所需要的擴展密鑰規模較大; (2) 密文擴展過程相對復雜, 存在一定的冗余;(3) 多跳功能的實現相對復雜. 密文同態運算的過程中支持新用戶密文的加入, 是面向實際應用場景的需要. 無論是PS16 方案中通過構造輔助密文來實現多跳, 還是BP16 方案中利用自舉的思想來實現多跳,計算復雜度都相對較大; (4) 進一步控制密文規模. GSW 密文的尺寸相對較大, 當多用戶參與時, CM15、MW16 以及PS16 方案中GSW 擴展密文的尺寸隨著參與用戶數量的增加而指數增長, 這會造成較高的通信和存儲成本. 雖然BP16 方案中擴展密文的尺寸隨著參與用戶數量的增加而線性增長, 但是自舉過程較為耗時和復雜, 對于方案的實現效率有較大影響.

BGV 型MKFHE: 具有密文擴展方式相對簡單、多跳功能容易實現、可構造層次型方案等優勢, 但仍存在以下問題有待解決: (1) 密鑰交換過程較為復雜. BGV 密文為向量形式, 密文間的同態運算(主要指同態乘法), 會引起密文維度指數級別的膨脹, 因此需要密鑰交換技術將同態運算后密文的維度約減到正常的水平, 但是該過程通常比較繁瑣和耗時; (2) 生成計算密鑰所需的密鑰數量較多、尺寸較大, 計算復雜度較大.

TFHE 型MKFHE: 具有加解密和自舉過程速度快、同態運算邏輯電路相對高效等優點, 但仍存在以下缺陷: (1) 擴展密文的長度隨用戶數量的增加而線性增長; (2) 同態運算仍需生成參與用戶集的計算密鑰, 該過程較為繁瑣; (3) 明文空間相對較小; (4) 同態運算算術電路的效率較低.

5.2 發展趨勢

云環境下多用戶(機構) 數據之間的安全分析, 是信息安全領域始終需要重點關注的問題. 多密鑰全同態加密支持不同用戶(密鑰) 密文間的同態運算的良好特性, 具備很大的理論研究價值和實際意義. 提升方案的效率是未來一段時間內需要重點解決的問題. 一方面, 可以考慮將傳統的(單密鑰) 全同態加密中的一些較為成熟的優化技術轉移到多密鑰全同態加密中, 提高方案的效率; 另一方面, 需要從方案的構造和實現的角度出發, 研究如何在盡可能擴展多密鑰全同態加密功能性的基礎上, 盡可能的減少方案的密文量、密鑰量以及計算復雜度, 從而進一步促進多密鑰全同態加密的實用化進程.