多密鑰全同態(tài)加密研究*

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

1. 武警工程大學(xué) 密碼工程學(xué)院, 西安710086

2. 網(wǎng)絡(luò)與信息安全武警部隊重點實驗室, 西安710086

1 引言

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

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

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

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

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

(1) 不同的用戶或機(jī)構(gòu)i利用各自的密鑰Keyi(i=1,··· ,N), 對各自的數(shù)據(jù)mi進(jìn)行同態(tài)加密, 并將加密之后的密文(C1,··· ,CN) 上傳到云端;

(2) 云端根據(jù)所需實現(xiàn)的數(shù)據(jù)處理函數(shù)f, 對接收到的密文數(shù)據(jù)進(jìn)行同態(tài)運算, 得到運算后的密態(tài)處理結(jié)果C;

(3) 云將密文結(jié)果C返回給所有參與計算的用戶或機(jī)構(gòu)i;

(4) 各用戶或機(jī)構(gòu)i接收到密文結(jié)果C后, 通過聯(lián)合解密恢復(fù)出最終的結(jié)果.

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

圖1 云環(huán)境下MKFHE 在多用戶數(shù)據(jù)安全分析方面的應(yīng)用Figure 1 Application of MKFHE in secure data analysis of multiple parties under cloud environment

1.1 多密鑰全同態(tài)加密的定義

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

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

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

2 研究現(xiàn)狀

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

2.1 NTRU 型FHE 和MKFHE

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

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

2.2 GSW 型FHE 和MKFHE

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

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

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

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

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

2.3 BGV 型MKFHE

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

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

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

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

2.4 TFHE 型FHE 和MKFHE

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

2019 年亞密會上, Chen 等人在CGGI17[39]的基礎(chǔ)上, 利用特殊的GSW 密文設(shè)計了高效的密文擴(kuò)展算法, 實現(xiàn)了對計算密鑰的高效擴(kuò)展, 并據(jù)此提出了多密鑰全同態(tài)加密方案CCS19[40], 該方案密文長度隨用戶數(shù)量增加呈線性增加, 同時作者編寫了多密鑰全同態(tài)加密軟件庫MKTFHE, 對MKFHE 方案的應(yīng)用具有重要指導(dǎo)意義.

2.5 量子HE 和MKFHE

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

2018 年, Goyal 等人在DSS16 方案的基礎(chǔ)上, 提出了量子多密鑰同態(tài)加密的概念, 并且構(gòu)造了從經(jīng)典的層次型多密鑰同態(tài)加密到量子層次型多密鑰同態(tài)加密的通用轉(zhuǎn)化方法[42].

表1 對現(xiàn)階段四類MKFHE 方案存在的優(yōu)缺點進(jìn)行了分析.

3 MKFHE 方案的典型構(gòu)造

本節(jié)主要對當(dāng)前MKFHE 方案中的一些經(jīng)典方案進(jìn)行簡要的介紹.

3.1 預(yù)備知識

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

3.1.2 廣義誤差學(xué)習(xí)問題

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

LWE 問題: 當(dāng)d=1 時, GLWE 問題即轉(zhuǎn)化為LWE 問題.

RLWE 問題: 當(dāng)n=1 時, GLWE 問題即轉(zhuǎn)化為RLWE 問題.

3.1.3 判定性小多項式比問題

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

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

3.2 NTRU 型MKFHE 典型構(gòu)造

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

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

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

(1) 輸入待加密的明文m, 隨機(jī)選取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 方案的典型構(gòu)造

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

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

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

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

3.4 BGV 型MKFHE 方案的典型構(gòu)造

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

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

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

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

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

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

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

3.5 基于TFHE 庫的MKFHE 方案的構(gòu)造思路

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

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

4 基于MKFHE 的MPC

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

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

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

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

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

輸入公共參數(shù)pp, 生成用戶的公鑰pkk、私鑰skk、擴(kuò)展密鑰ekk、同態(tài)計算密鑰evkk:

云端將同態(tài)運算后的密文結(jié)果?c發(fā)送給所有參與計算的用戶.

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

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

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

5 總結(jié)

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

5.1 存在問題

現(xiàn)階段MKFHE 在方案構(gòu)造和實現(xiàn)方面尚未成熟, 還存在以下待解決的問題.

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

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

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

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

5.2 發(fā)展趨勢

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