多密鑰全同態(tài)加密的研究現(xiàn)狀與發(fā)展趨勢(shì)

祁正華，何菲菲，張海桃，譚小輝

(南京郵電大學(xué) 計(jì)算機(jī)學(xué)院，江蘇 南京 210023)

全同態(tài)加密（Fully Homomorphic Encryption，F(xiàn)HE）的思想源于“隱私同態(tài)”，由Rivest 等［1］在1978 年首次提出。 FHE 指在不解密的情況下對(duì)密態(tài)數(shù)據(jù)進(jìn)行各種運(yùn)算，其結(jié)果在解密后與對(duì)明文進(jìn)行相應(yīng)運(yùn)算的結(jié)果是一樣的（見圖1）。 同態(tài)加密的本質(zhì)是圖1 所示的交換圖表。 FHE 真正從根本上解決了將數(shù)據(jù)及操作委托給第三方時(shí)的保密問題。

圖1 同態(tài)加密交換圖

隨著Rainbow 和SIKE 相繼被破解而雙雙隕落，基于格的密碼學(xué)成為后量子時(shí)代抗量子密碼的重要組成部分。 FHE 方案大多是以格上困難問題作為基礎(chǔ)，從而FHE 也是后量子密碼（Post-Quantum Cryptography，PQC）的組成之一。 目前，基于格的逐漸成為歐美國家在密碼領(lǐng)域爭(zhēng)奪的“戰(zhàn)略制高點(diǎn)”，能夠在大數(shù)據(jù)與云計(jì)算等新型服務(wù)模式下發(fā)揮重要作用［2］。

2009 年，由IBM 實(shí)驗(yàn)室的Gentry 構(gòu)造了第一個(gè)真正意義的FHE 方案［3］，方案的設(shè)計(jì)是基于理想格（Ideal Lattice）上的有界編碼問題（Bounded Distance Decoding Problem，BDDP）和稀疏子集和問題（Sparse Subset Sum Problem，SSSP）。

2011 年，Brakerski 等［4］提出BV 方案，首次利用容錯(cuò)學(xué)習(xí)（Learning with Errors，LWE）假設(shè)實(shí)現(xiàn)了FHE 并在Ring-LWE 假設(shè)下實(shí)現(xiàn)了FHE。 BV 方案采用重線性化技術(shù)和密鑰交換技術(shù)降低了密文的噪聲，優(yōu)化了Gentry［3］提出的方案，但同時(shí)由于密鑰交換技術(shù)需要在公鑰生成階段引入額外的信息，也因此使得BV 方案的存儲(chǔ)開銷增大。 2012 年，Brakerski 等［5］又提出了BGV 方案，該方案同樣也使用了密鑰交換技術(shù)，但不需要壓縮解密電路，提高了算法的計(jì)算效率，同時(shí)也降低了方案的安全性假設(shè)。之后，Gentry 等［6］首次利用近似特征向量的方法，提出了密文形式為矩陣的FHE 方案（GSW 方案），且該方案未使用密鑰交換技術(shù)，因此減少了存儲(chǔ)開銷，同時(shí)由于矩陣相乘不會(huì)改變維數(shù)，進(jìn)而不會(huì)使得密文相乘的噪聲大幅增加。 以上方案都是單密鑰加密方案，不能滿足不同密鑰密文之間的運(yùn)算，安全多方計(jì)算（n個(gè)參與方共同計(jì)算一個(gè)函數(shù)，計(jì)算完畢后每個(gè)參與方只知道自己的輸入輸出）在全同態(tài)加密方面得不到應(yīng)用。

2012 年，López-Alt 等［7］提出了第一個(gè)多密鑰全同態(tài)加密（MKFHE）方案，支持對(duì)不同用戶（不同密鑰）的密文進(jìn)行任意的同態(tài)運(yùn)算，且運(yùn)算之后的結(jié)果由參與計(jì)算的所有用戶聯(lián)合解密，可以較好地解決多用戶密文聯(lián)合計(jì)算的問題。 該方案建立在一個(gè)與NTRU 相關(guān)的非標(biāo)準(zhǔn)假設(shè)上，但該方案的復(fù)雜度太高，且復(fù)雜度隨著用戶的增長(zhǎng)呈指數(shù)增長(zhǎng)。 2015年，Clear 等［8］基于GSW 方案［6］構(gòu)造了一個(gè)MKFHE方案，方案的安全性可以規(guī)約到LWE 問題，該方案是第一個(gè)建立在標(biāo)準(zhǔn)假設(shè)上的多密鑰全同態(tài)加密方案。 2016 年，Mukherjee 等［9］簡(jiǎn)化了Clear 等［8］的方案，同樣是基于GSW 方案［6］、安全性歸約到LWE問題假設(shè)，不同之處在于Mukherjee 等［9］擴(kuò)展了方案的結(jié)構(gòu)，使得擴(kuò)展之后的方案可以進(jìn)行一輪交互的分布式計(jì)算，但不足之處在于該方案只允許單跳運(yùn)算。 為了解決這個(gè)問題，Peikert 等［10］構(gòu)造了擁有多跳的MKFHE，不必提前獲得參與方的信息，且與Mukherjee 等［9］構(gòu)造的方案相比，方案生成的密文尺寸更短。 與此同時(shí)，Brakerski 等［11］同樣基于GSW方案［6］設(shè)計(jì)出了多跳的MKFHE，它允許參與方動(dòng)態(tài)的加入，可支持任意數(shù)量的運(yùn)算以及多項(xiàng)式級(jí)別的參與方參與運(yùn)算。 為提高多跳的MKFHE 的同態(tài)運(yùn)算效率，荀艷梅等［12］基于Peikert 等［10］的MKFHE方案并結(jié)合密鑰策略屬性基全同態(tài)加密，構(gòu)造了一個(gè)多跳多策略屬性基全同態(tài)短密文加密方案，且該方案的密文擴(kuò)展更容易實(shí)現(xiàn)。 2019 年，Li 等［13］基于BGV 方案［5］構(gòu)造MKFHE 方案，方案對(duì)密文長(zhǎng)度進(jìn)行了縮減，提高了運(yùn)算效率，同時(shí)也提出了一個(gè)直接解密協(xié)議，解除了計(jì)算密文只能由所有參與方的私鑰解密的限制，但也只限于理論層面，還未投入到實(shí)際應(yīng)用。 為了再次提高全同態(tài)加密方案的計(jì)算效率，同年，Chen 等［14］基于TFHE 方案提出了一個(gè)MKFHE 方案，首次對(duì)全同態(tài)加密進(jìn)行了概念驗(yàn)證。

1 基本概念

1．1 符號(hào)說明

對(duì)于一個(gè)自然數(shù)n∈N，［n］ 表示｛1，2，…，n｝，?n」 表示小于n但最接近于n的整數(shù)，「n?表示大于n但最接近于n的整數(shù)，「n」表示對(duì)n四舍五入近似取整，Z 表示整數(shù)集，Zq表示模q剩余類。v［i］表示向量中的第i個(gè)元素，A［i，j］ 表示矩陣中第i行第j列的元素，［A ｜Ax］ 表示矩陣和向量的水平連接，〈a，b〉表示兩個(gè)向量的內(nèi)積。 對(duì)于分布B，x←B表示x從分布B中均勻取值。 對(duì)于向量x ＝（x1，x2，…，xn），lp范數(shù)是指，無窮范數(shù)是指‖x‖∞＝max（｜x1｜，｜x2｜，…，｜xn ｜），l1范數(shù)是指｜， 若無下標(biāo)則記為2-范數(shù)。

令Φm（x） 為分圓多項(xiàng)式，則Rq ＝R／qR ＝Z（x）／〈Φm（x）〉 表示分圓多項(xiàng)式環(huán)，環(huán)中元素可表示為

1．2 相關(guān)定理

定理1容錯(cuò)學(xué)習(xí)問題（LWE）。 對(duì)于一個(gè)秘密向量上的LWE 分布As，χ指的是均勻選取，選取e←χ，輸出（A，b ＝A·s ＋emodq）。

定理2判定性容錯(cuò)學(xué)習(xí)問題（DLWE）。 設(shè)為m個(gè)相互獨(dú)立的采樣，每個(gè)采樣都是按照以下兩種方式生成的：（1） 從中隨機(jī)取樣；（2） 從分布As，χ中取樣。 DLWE 問題是指判定中的每個(gè)樣本是從哪種方式中取樣的。

定理3環(huán)上容錯(cuò)學(xué)習(xí)問題（RLWEΦ，q，χ）。 對(duì)于一個(gè)秘密向量s∈Rq，RLWE 分布Ls，χ是指定義為Rq ×Rq上按如下方式生成的概率分布，隨機(jī)選取a∈Rq，e∈R服從概率分布χ，計(jì)算（a，b ＝a·s ＋e）。

定理4判定性容錯(cuò)學(xué)習(xí)問題（DRLWE）。 判斷（a，b） 是從分布Ls，χ中采樣還是從Rq × Rq中采樣。

定理5DSPRΦ，q，χ問題是指難以區(qū)分以下兩個(gè)多項(xiàng)式，一是多項(xiàng)式h ＝2g／f，其中f ＝2f′ ＋1 且在Rq上可逆，f′，g←χ；二是在上隨機(jī)均勻采樣得到多項(xiàng)式h。

定理6一個(gè)整數(shù)上的分布｛χn｝n∈N， 如果，稱該分布是B －有界的，其中negl（λ） 是一個(gè)可忽略函數(shù)。

定理7設(shè)gT＝（1，2，22，…，2l－1） ∈Zl，l ＝「logq?，Gadget 矩陣G ＝In?gT∈Zn×nl，則對(duì)任意的，均存在一個(gè)隨機(jī)有效的可計(jì)算函數(shù)G－1：同時(shí)x為關(guān)于參數(shù)O（1） 的亞高斯隨機(jī)向量，且a ＝［Gx］q。 例如，若a ＝(7 1 5)T，有Gadget 矩陣

定理7 很容易擴(kuò)展到矩陣上，如定理8 所示。

定理8設(shè)gT＝（1，2，22，…，2l－1） ∈Zl，l ＝「logq?，Gadget 矩陣G ＝In?gT∈Zn×nl，則對(duì)任意的， 均存在一個(gè)隨機(jī)有效的可計(jì)算函數(shù)同時(shí)矩陣的任意行向量xi均為關(guān)于參數(shù)O（1） 的亞高斯隨機(jī)向量，且AT＝［GXT］q。 例如，若Gadget 矩 陣G同 定 理 7， 存 在X ＝且AT＝［GXT］q，或A ＝［XGT］q。

1．3 關(guān)鍵技術(shù)

模交換技術(shù)（ModulusSwitch（） ）：模交換技術(shù)可以將模q下的密文c轉(zhuǎn)換成較小的模p（p ＝qmod 2） 下密文c′，保證在同樣私鑰正確解密條件下，噪聲規(guī)模減小p／q倍，即ModulusSwit ch（c，q，p）：輸入c∈Rq和一個(gè)更小的模數(shù)p，輸出的一個(gè)密文無限接近于c′ ＝（p／q）·c∈Rp且滿足c′ ＝cmod 2。

密鑰交換技術(shù)（SwitchKey（））：將對(duì)應(yīng)的密文由（解密密鑰為sk1） 轉(zhuǎn)換成為密文（解密密鑰為sk2）。

比特分解技術(shù)： 比特分解技術(shù)是指用BitDecomp（·） 和Powersof2（·） 這兩個(gè)函數(shù)對(duì)數(shù)據(jù)進(jìn)行比特位展開。 令l ＝「logq?， 則其具體表達(dá)分別為

BitDecomp（x∈，q）： 輸入多項(xiàng)式x ＝（x1，x2，…，xn）和 模q， 輸 出 （x1，0，x1，1，…，x1，l－1，…，xn，0，xn，1，…，xn，l－1） ∈｛0，1｝n－l， 其 中xi，j為xi進(jìn)行二元比特分解之后的第j比特。

Powersof2（y∈，q）： 輸入多項(xiàng)式y(tǒng) ＝（y1，輸 出 （y1，2y1，…，2l－1y1，…，yn，

例如， 若x ＝（7，9），y ＝（2，6），l ＝4， 則BitDecomp（x，q）＝（1，1，1，0，1，0，0，1）。

自舉（Bootstrapping）技術(shù)：當(dāng)同態(tài)操作進(jìn)行至噪聲達(dá)到閾值而無法再進(jìn)行操作時(shí)， 將此時(shí)的密文與對(duì)應(yīng)私鑰的密文進(jìn)行同態(tài)解密的操作。 即將自己解密函數(shù)作為FHE．Eval算法中的輸入函數(shù)，將達(dá)到噪聲上限的密文與該密文解密秘鑰中的每一位加密結(jié)果作為FHE．Eval算法中的輸入密文，則執(zhí)行FHE．Eval算法會(huì)生成一個(gè)與該密文對(duì)應(yīng)相同明文的“新鮮”密文，從而可以繼續(xù)進(jìn)行密文同態(tài)運(yùn)算。當(dāng)密文再次達(dá)到噪聲上限時(shí)，可以再進(jìn)行一次同態(tài)解密運(yùn)算，依次遞歸，在KDM 安全假設(shè)下，即可獲得純FHE 方案。 自舉后可以得到支持繼續(xù)同態(tài)操作的低噪聲密文。 自舉是目前最有效的消減密文噪聲的操作，也是迄今為止實(shí)現(xiàn)全同態(tài)加密的唯一途徑。

自舉算法的形式化描述如下：

設(shè)加密方案中存在兩對(duì)密鑰對(duì)（pk1，sk1） 和（pk2，sk2）、 明文為μ， 則令c1為μ關(guān)于sk1的密文、表示用pk2逐比特加密sk1得到， 并將添加至加密方案的公鑰中。 令解密電路為D， 自舉算法執(zhí)行流程如圖2 所示。

圖2 自舉算法執(zhí)行流程圖

1．4 格上困難問題

格是指n維空間Rn具有周期性結(jié)構(gòu)的點(diǎn)的集合。

近似最短向量問題：定義格的任意一個(gè)格基B，近似因子γ ＝γ（n） ≥1，則近似最短向量問題是指找到一個(gè)非零格基向量B·x，使得對(duì)于任意的非零y，‖B·x‖≤γ（n）‖B·y‖成立。

近似最近向量問題：給定格的一個(gè)格基B、 目標(biāo)向量t，找出一個(gè)格基向量B·x，使得對(duì)于任意的y，‖B·x － t‖≤γ‖B·y － t‖成立。

定義格Λ的逐次最小量為λ（Λ）＝inf｛r ｜表示以原點(diǎn)為球心、r為半徑的閉球，span（Λ） 表示格Λ生成的線性空間。

最短線性無關(guān)向量問題：尋找格中n個(gè)線性無關(guān)向量v1，v2，…，vn， 使得對(duì)于任意的i∈［n］，‖vi‖≤γ·λi（Λ） 成立。

2 全同態(tài)加密及多密鑰全同態(tài)加密

基于全同態(tài)加密的多密鑰全同態(tài)加密的發(fā)展過程同全同態(tài)加密一樣分為3 個(gè)階段，下面分析各階段的核心方法。

2．1 以Gentry 的突破性工作為基礎(chǔ)

這一階段全同態(tài)加密方案構(gòu)造的思路是：首先構(gòu)造一個(gè)部分（Somewhat）FHE 方案，即方案僅支持低多項(xiàng)式次數(shù)的密文同態(tài)計(jì)算。 然后，在稀疏子集和問題的假設(shè)下，通過“壓縮解密電路”使方案變成“自舉的”，從而通過迭代調(diào)用自舉技術(shù)，對(duì)隨著同態(tài)運(yùn)算達(dá)到噪聲閾值的新密文進(jìn)行同態(tài)解密來約減噪聲，使其允許至少再進(jìn)行一次同態(tài)運(yùn)算，最后在循環(huán)安全性假設(shè)（KDM）下獲得真正意義上的FHE方案。

在同態(tài)運(yùn)算過程中噪聲的主要來源是同態(tài)乘法運(yùn)算，其產(chǎn)生的噪聲呈指數(shù)級(jí)別增長(zhǎng)。 為解決噪聲增長(zhǎng)過快問題，需要將密文和密鑰重新按位加密，之后再將得到的密文輸入同態(tài)解密電路中，但這要求當(dāng)同態(tài)運(yùn)算電路深度大于解密電路深度時(shí)要通過壓縮電路和逐比特加密降低噪聲來實(shí)現(xiàn)全同態(tài)，這也限制了同態(tài)解密技術(shù)的使用。 由此可見，這一階段僅實(shí)現(xiàn)單密鑰全同態(tài)加密過程就十分復(fù)雜，因此，多密鑰全同態(tài)加密不適合基于此階段的方案進(jìn)行構(gòu)造。 此 階 段 的 代 表 性 方 案 有 SV （ 10）［15］、SS（10）［16］、LMSV（11）［17］等。

2．2 基于LWE 和RLWE 的多密鑰全同態(tài)加密方案

這一階段全同態(tài)加密方案的構(gòu)造思路是先構(gòu)造一個(gè)層次型的同態(tài)加密方案，再通過一定的技術(shù)手段達(dá)到無限運(yùn)算。 層次型的加密方案在進(jìn)行同態(tài)乘法運(yùn)算時(shí)同樣會(huì)使得噪聲呈指數(shù)級(jí)別的增長(zhǎng)，例如，n維的數(shù)據(jù)進(jìn)行一次同態(tài)乘法之后會(huì)產(chǎn)生n2維的噪聲，兩次同態(tài)乘之后會(huì)產(chǎn)生n4維的噪聲，因此需要對(duì)噪聲做一定的處理才能達(dá)到全同態(tài)。 2012 年Brakerski 等［5］提出了用密鑰交換技術(shù)來解決維數(shù)膨脹問題，用模交換技術(shù)控制噪聲從而使其達(dá)到全同態(tài)，在一定程度上擺脫了對(duì)自舉的依賴，但最終要實(shí)現(xiàn)無限次的運(yùn)算還需要自舉技術(shù)。 此階段出現(xiàn)的方案有Bra（12）［18］、BV（14）［19］等。

以這一階段的方案作為基礎(chǔ)方案構(gòu)造的多密鑰全同態(tài)加密方案可分為NTRU 型和BGV 型兩大類。NTRU 型的MKFHE 是最早被提出的，BGV 型的MKFHE 是最晚被提出的。

2.2.1 NTRU 型MKFHE 的構(gòu)造及優(yōu)化

作為首個(gè)被提出的多密鑰加密方案類型，對(duì)后來MKFHE 的構(gòu)造起著至關(guān)重要的作用，NTRU 型多密鑰加密方案［7］的基本構(gòu)造過程如下。

（1） 初始化NTRU．Setup（1λ）： 安全參數(shù)為λ，選擇整數(shù)n ＝n（λ）， 定義分圓多項(xiàng)式環(huán)R ＝Z（x）／xn ＋1， 其中xn ＋1 為2 的冪次階分圓多項(xiàng)式，n為2 的冪次。 定義多項(xiàng)式環(huán)Rq ＝R／qR，R中上界為B ＝B（λ） 的錯(cuò)誤分布χ。 定義一系列遞減的模數(shù)q0＞q1＞…＞qL，令B?qL，i∈｛0，1，2，…，L｝。

（2） 密鑰生成NTRU．KeyGen（1n，1L）： 產(chǎn)生公鑰、私鑰和同態(tài)計(jì)算密鑰，其中L為運(yùn)算深度。

（3） 加密NTRU．Enc（pk，μ）： 將明文數(shù)據(jù)加密為c ＝hs ＋e ＋μ的形式，其中h為公鑰，s，e←χ。

（4） 同態(tài)運(yùn)算NTRU．Eval（c1，c2）：此階段需要計(jì)算密鑰的參與，用計(jì)算密鑰結(jié)合模交換技術(shù)或密鑰交換技術(shù)進(jìn)行同態(tài)運(yùn)算。

（5） 解 密NTRU．Dec（sk1，sk2，…，skn，c?）： 其中c?為經(jīng)過同態(tài)計(jì)算產(chǎn)生的新鮮密文。

其安全性基于DSPRΦ，q，χ和RLWEΦ，q，χ問題。

當(dāng)前對(duì)NTRU 型MKFHE 的優(yōu)化主要是抑制噪聲的增長(zhǎng)速度、優(yōu)化方案的安全性或在同態(tài)計(jì)算時(shí)減少計(jì)算密鑰的交換次數(shù)甚至消除計(jì)算密鑰的交換等。 李瑞 琪 等［20］便 利 用 工 具 向 量（g ＝（1，ω，其中ω為基，lq ＝「logωq?） 和比特分解技術(shù)構(gòu)造了一個(gè)同態(tài)運(yùn)算過程不需要計(jì)算密鑰的層次型的NTRU 型MKFHE，提高了方案的運(yùn)算效率，構(gòu)造的方案相比原方案密鑰的生成方式?jīng)]有改變，只是在加密過程中先對(duì)“0”進(jìn)行加密，其具體的優(yōu)化過程如下。

RNTRU．Enc（pk，μ）：隨機(jī)抽取lq組si，ei←χ用于計(jì)算NTRU．Enc（h，0） 來得到lq個(gè)“0 的密文”，然后將lq個(gè)0 的密文組成一個(gè)向量，最后輸出密文

RNTRU．Dec（sk，c）：用聯(lián)合私鑰Fk ＝f1f2…fn（其中，為用戶i的私鑰） 進(jìn)行解密，可得明文μ ＝NTRU．Dec（Fk，c［1］）。

此時(shí)對(duì)進(jìn)行同態(tài)運(yùn)算之后的密文進(jìn)行解密便可不再需要計(jì)算密鑰，直接用私鑰與密文做內(nèi)積即可得到明文。 下面以解密同態(tài)乘（cMult ＝c1g－1（c2） ∈為例進(jìn)行論證，使用f＾＝f1·f2解密cMult時(shí)需計(jì)算f＾·cMult［1］，因此可令g－1c2得到的矩陣為可得

已知f ＝pf′ ＋1，f′←χ，因此可得f1≡1 modp、f2≡1 modp，又知g［1］＝1、c1，0［1］、c2，0［1］ 是“0”的密 文，因 此f1·c1，0［1］modp ＝0，f2·c2，0［1］modp ＝0，所以可得f＾·cMult［1］modp ＝μ1μ2，因此同態(tài)乘法運(yùn)算過程不需要計(jì)算密鑰的參與得證，同態(tài)加法運(yùn)算過程同理。

除直接對(duì)同態(tài)運(yùn)算過程優(yōu)化外，還可采用間接方式。 例如，車小亮等［21］通過改變NTRU 型加密方案的底層結(jié)構(gòu)對(duì)其安全性和效率進(jìn)行了優(yōu)化，將現(xiàn)有方案底層的分圓多項(xiàng)式環(huán)擴(kuò)展到素?cái)?shù)次分圓多項(xiàng)式環(huán)上，可以抵御更多的子域攻擊。 然后通過擴(kuò)展密文維度消除密鑰交換技術(shù)，并結(jié)合模交換技術(shù)構(gòu)造一個(gè)高效的層級(jí)的NTRU 型MKFHE。 其具體的優(yōu)化過程如下。

對(duì)安全性的優(yōu)化：只是將原方案中的分圓多項(xiàng)式用素?cái)?shù)次分圓多項(xiàng)式替代，其他多項(xiàng)式時(shí)間算法不變。 定義素?cái)?shù)次分圓多項(xiàng)式環(huán)為R ＝參數(shù)n和q ＝q（λ） 為素整數(shù)。 根據(jù)文獻(xiàn)［22］可知，素?cái)?shù)次分圓多項(xiàng)式可以抵抗更多的子域攻擊。

對(duì)效率的優(yōu)化：上面對(duì)安全性的優(yōu)化只是改變了底層結(jié)構(gòu)，并沒有改變同態(tài)運(yùn)算的結(jié)構(gòu)，仍需要密鑰交換來完成全同態(tài)，且產(chǎn)生的噪聲同時(shí)受第i層和第i ＋1 層聯(lián)合解密私鑰的影響，導(dǎo)致噪聲增長(zhǎng)過快。 因此，車小亮等［21］又通過將明文μ轉(zhuǎn)化為向量的形式μ′ ＝（μ，2μ，…，2l－1μ） 擴(kuò)展密文多項(xiàng)式，并結(jié)合比特分解技術(shù)，優(yōu)化NTRU 型多密鑰同態(tài)運(yùn)算結(jié)構(gòu)，以消除同態(tài)運(yùn)算過程中的密鑰交換操作。NTRU 型MKFHE［7］最初的加密方案與車小亮等［21］所提優(yōu)化后的方案對(duì)比如表1 所示。

表1 原方案與優(yōu)化后的方案對(duì)比表

表1 從密文形式、同態(tài)加法和同態(tài)乘法3 方面進(jìn)行對(duì)比分析。 從表1 中可以看出二者有兩方面的區(qū)別，一方面是在密文形式方面的唯一區(qū)別：明文是否為向量；另一方面是由于優(yōu)化的方案引入了比特分解技術(shù)，因此同態(tài)計(jì)算過程中省去了密鑰交換，從而也使得同態(tài)計(jì)算過程更加簡(jiǎn)便高效。

此外，由于層級(jí)的加密方案每層密文維數(shù)不同，車小亮等［21］又提出了去尾函數(shù)來統(tǒng)一維數(shù)。 去尾函數(shù)表示去掉向量的li＋1→li項(xiàng)，使li維向量轉(zhuǎn)換成li＋1維向量至此一個(gè)可以抵御更多子域攻擊、不需要密鑰交換的NTRU 型全同態(tài)加密被構(gòu)造完成。

原始的NTRU 型解密是在解密之前先進(jìn)行密鑰交換，再用聯(lián)合私鑰與密文做內(nèi)積，導(dǎo)致解密噪聲較大。 車小亮等［23］便從方案的解密結(jié)構(gòu)入手，設(shè)計(jì)了兩種解密結(jié)構(gòu)來降低解密噪聲，一種是降低多項(xiàng)式系數(shù)來降低噪聲，另外一種是通過擴(kuò)展密文維度消除密鑰交換的過程。 第一種優(yōu)化的解密形式為（2／q）Fkc ＝μ ＋Error，但這種解密形式依然需要密鑰交換；第二種優(yōu)化的解密形式為Fk（c）＝μ ＋Error，其中c：＝Powersof2（μ）＋hs ＋2e，這一優(yōu)化需要在解密之前對(duì)密文進(jìn)行比特分解轉(zhuǎn)換。 以同態(tài)乘法為例則：cMult＝ BitDecomp（c1）·c2， 設(shè)c2）。

2.2.2 BGV 型MKFHE 的構(gòu)造及優(yōu)化

BGV 型的多密鑰全同態(tài)加密方案的密文結(jié)構(gòu)相對(duì)比較特殊，密文擴(kuò)展過程不需要計(jì)算密鑰的加入，但當(dāng)前對(duì)BGV 型MKFHE［24］的研究還很缺乏。其基本構(gòu)造流程如下。

（1） 初始化BGV．SetUp（1λ，1L）： 在NTRU 型MKFHE 初始化的基礎(chǔ)上增加了電路深度L。

（2） 密鑰生成BGV．KeyGen（1n，1L）： 產(chǎn)生公私鑰以及生成計(jì)算密鑰所需的相關(guān)密文ems。

（3） 加密BGV．Enc（pk，μ）： 加密形式為c ＝其中

（4） 解密BGV．Dec（sk，c）： 解密形式為μ←modqlmodp， 其中表示用戶的私鑰合集，cs表示用戶集合s的密文。

（5） 密文擴(kuò)展BGV．Extand（ct，S′）： 輸出新鮮密文其中密文組待擴(kuò)展用戶集S′ ＝｛j1，…，jk′｝（s∈s′）。 密文擴(kuò)展的具體步驟為將cs劃分為k個(gè)子向量cs ＝（ci，1｜c(diǎn)i，2｜…｜c(diǎn)i，k） ∈，此外令其對(duì)應(yīng)的用戶集為S′，如果用戶集S′中的用戶j也在用戶集S中，則令否則

由于BGV 型MKFHE 通常有較大的密鑰量且計(jì)算密鑰的生成過程較為復(fù)雜，因此，對(duì)該類型多密鑰全同態(tài)加密方案的優(yōu)化主要是減少密鑰量或簡(jiǎn)化計(jì)算密鑰的生成過程。 2019 年，Li等［13］首先通過構(gòu)造了一個(gè)嵌套型的BGV 密文和一個(gè)可分離的GSW 擴(kuò)展密文使擴(kuò)展密文的尺寸縮小一半， 然后將RBGV 密文和RGSW 密文的混合同態(tài)乘法應(yīng)用于計(jì)算密鑰的生成過程，以此來減少密文的輸入輸出，提高運(yùn)算效率。 優(yōu)化方案的初始化函數(shù)、密鑰生成函數(shù)、加密函數(shù)都同原始的BGV 型函數(shù)同理，優(yōu)化的部分為計(jì)算密鑰的生成以及解密部分，具體的優(yōu)化的步驟如下所示。

計(jì)算密鑰的生成：分為生成擴(kuò)展密文RBGV、生成擴(kuò)展密文RGSW 和生成計(jì)算密鑰3 部分。

（1） 生成擴(kuò)展密文RBGV．Extand（）： 算法同BGV．Extand（） 一樣，只不過原始BGV 型在密文擴(kuò)展時(shí)將密文cs劃分為了k個(gè)子向量，而本方案中將cs劃分為了k ＋1 個(gè)子向量。

（2） 生 成 擴(kuò) 展 密 文RGSW．Extand（）： 與GSW．Extand（） 的一般構(gòu)造算法的不同之處是密鑰生成函數(shù)及本方案新加入了一個(gè)多項(xiàng)式時(shí)間算法EncRand（r，P）。 本方案中私鑰sk ＝（1，－ z）T， 公鑰其中β ＝；多項(xiàng)式時(shí)間算法EncRand（r，P） 表示在密文擴(kuò)展過程中生成隨機(jī)性加密，在函數(shù)中輸入，輸出F ＝其中f1［i］＝b［i］ri ＋pe′1［i］＋。 從而可得到加密形式為RGSW．Enc（μ，p）＝C ＝rP ＋pE ＋μG。 輸出擴(kuò)展密文

其中，Ci ＝［Ci，0，Ci，1］為用戶i的RGSW．Enc（）型密文，Xj ＝［Xj，0，Xj，1］＝［BitDecomp（bj － bi）Fi］。

（3） 生成計(jì)算密鑰：用密文RBGV 與密文RGSW 的混合同態(tài)乘法替代兩個(gè)RBGV 型密文相乘可以降低計(jì)算過程中產(chǎn)生的噪聲，此外用戶密鑰的系數(shù)限制在｛－1，0，1｝之間，從而密鑰交換規(guī)程中便不再需要比特分解和模交換技術(shù)。

定 義 函 數(shù)則從 而 可 得 計(jì) 算 密 鑰evks ＝｛κm，ξ｝。 其中定義RGSW 的密文C2與RBGV 的密文c1的 混 合 同 態(tài) 乘 為BitDecomp（c1）C2。

原BGV 方案中ems是由多項(xiàng)式環(huán)上的GSW 加密方案來對(duì)參與計(jì)算的用戶的私鑰進(jìn)行加密的，而在本 方 案 中

解密部分的優(yōu)化：

提出了一個(gè)定向解密協(xié)議，增強(qiáng)了數(shù)據(jù)擁有者對(duì)自己明文的控制能力，通過在參與同態(tài)計(jì)算的用戶的中間解密結(jié)果中添加對(duì)“0”的加密來實(shí)現(xiàn)。 以用戶i要得到解密結(jié)果為例說明定向解密協(xié)議的執(zhí)行步驟。 首先，各自解密自己所對(duì)應(yīng)的密文（類似于門限解密）；之后各參與方用用戶i的公鑰對(duì)“0”加密得到密文ci，各參與方計(jì)算ci的和以及上一步中各自的部分解密密文得，并發(fā)送給用戶i；最后用戶i對(duì)求和并解密C（μ1，…，μk）modqlmodp。

隨后車小亮等［25］也對(duì)于以上兩種問題提出了優(yōu)化方法，將低位比特丟棄技術(shù)（利用比特分解進(jìn)行多項(xiàng)式乘法運(yùn)算時(shí)，丟棄一定量的低位比特信息不做處理，不影響最終運(yùn)算結(jié)果的正確性，函數(shù)DBitDecomp（bj）＝Dk（BitDecomp（bj）） 表示把向量bj的1 →k位舍棄）應(yīng)用于計(jì)算密鑰的密文擴(kuò)展，從而得到一個(gè)優(yōu)化的計(jì)算密鑰生成算法，進(jìn)而提高方案的運(yùn)算效率。 定義優(yōu)化后的算法為L(zhǎng)DA 算法，原算法為BGV 算法則，用LDA 和BGV 的混合同態(tài)乘法運(yùn)算可得到優(yōu)化的計(jì)算密鑰，過程如下。

（1） 定義函數(shù)Ψl，i［t］ 和函數(shù)φl，i［t′］：當(dāng)t ＝0時(shí)，Ψl，i［t］＝BGV．Enc（pl－1，i，1）， 否 則Ψl，i［t］＝當(dāng)t′ ＝0 時(shí)，φl，i［t′］＝LDA．Enc（pl－1，i，1），否則φl，i［t′］＝LDA．Enc（pl－1，i，其中pl－1，i為輔助公鑰集、為擴(kuò)展私鑰；LDA．Enc（pl，i，zl，i）：輸入私鑰多項(xiàng)式zl，i和公鑰pl，i ＝（bl，i，al，i）， 輸 出 密 文（rl，ibl，i ＋pel，i ＋zl，i，rl，ial，i ＋pe′ l，i）。

（2） 對(duì)函數(shù)Ψl，i［t］ 和φl，i［t′］ 進(jìn)行密文擴(kuò)展，LDA．Extands－1（φl，i［t′］，k）。 其 中k為 用 戶 集。LDA．Extand（ci，0，K）： 輸 入ci，0（zl，i）、 輔 助 密 文dl，i（zl，i） 和用戶公鑰集，則對(duì)于任意非用戶i可進(jìn)行計(jì)算以下3 步，首先計(jì)算DBitDecomp（bl，j） ·di，0， 再 計(jì) 算μ。

（3） 獲 得 計(jì) 算 密 鑰evk，evk ＝｛km ＝

優(yōu)化的結(jié)果相比原加密方案的公鑰尺寸和計(jì)算密鑰密文量都相對(duì)減少，計(jì)算密鑰的生成效率有所提高。

2．3 基于近似特征向量的多密鑰全同態(tài)加密方案

第二代全同態(tài)加密使用的密鑰交換技術(shù)是每次在進(jìn)行同態(tài)乘法之前用一個(gè)高維矩陣乘以密文，因此需要存儲(chǔ)大量的高維矩陣，從而使存儲(chǔ)開銷增大。第三代全同態(tài)加密以GSW 方案［6］為代表，該類型的加密方案將密文加密為矩陣的形式，使得數(shù)據(jù)的運(yùn)算全部為簡(jiǎn)單的矩陣運(yùn)算，因此不會(huì)出現(xiàn)維數(shù)膨脹問題。 雖然該種類型的方案在構(gòu)造的過程中同樣也引入了噪聲，但不需要密鑰交換技術(shù)或模交換技術(shù)就可以實(shí)現(xiàn)全同態(tài)，只需要選擇合適的參數(shù)就能控制噪聲，使其達(dá)到正確解密的條件。 此階段出現(xiàn)的加密方案有CM（15）［8］、MW（16）［9］等。 正是此類方案計(jì)算簡(jiǎn)便、結(jié)構(gòu)簡(jiǎn)單，使得基于近似特征向量的多密鑰全同態(tài)加密方案［26］被廣泛研究，其構(gòu)造過程如下。

（1） 初始化GSW．SetUp（1λ，1L）：定義安全參數(shù)λ、模數(shù)q ＝q（λ）、參數(shù)n ＝n（λ）、m ＝O（nlogq）∈Z以及錯(cuò)誤分布χ ＝χ（λ），其中χ的邊界為B，令l ＝「logq?、N ＝nl。

（2） 密鑰生成GSW．KeyGen（）： 生成公鑰和私鑰。

（3） 加密GSW．Enc（pk，μ）： 生成密文形式為其中A為公鑰矩陣，R為在加密過程中均勻選取的一個(gè)隨機(jī)矩陣，G ＝In?gT為工具 矩 陣，In為 單 位 矩 陣，gT＝（1，21，22，…，2l－1）。

（4） 密文擴(kuò)展GSW．Extand（）： 此種類型的MKFHE 方案在進(jìn)行同態(tài)運(yùn)算之前要先進(jìn)行密文擴(kuò)展，否則無法參與同態(tài)運(yùn)算。

（5） 同態(tài)運(yùn)算GSW．Eval（C1，C2）： 同態(tài)加法運(yùn)算算法為密文矩陣直接相加，即C1＋C2，同態(tài)乘法運(yùn)算需要引入原像函數(shù)G，即C1G－1（C2）。

（6） 解密GSW．Dec（sk，C）： 私鑰與密文做內(nèi)積，結(jié)果為近似特征向量的形式，即sC ＝eR ＋μsG，其中s為解密密鑰，e←χm。

當(dāng)前對(duì)基于近似特征向量構(gòu)造的MKFHE 的優(yōu)化主要是對(duì)方案計(jì)算效率、密鑰生成等的優(yōu)化。2017 年Li 等［27］提出了一種新的密文擴(kuò)展技術(shù)——改進(jìn)的線性組合程序（iLCP），用于提高方案的運(yùn)算效率，除了密文擴(kuò)展算法同GSW 型方案不同外，其他多項(xiàng)式算法均相同。 密文擴(kuò)展算法的具體構(gòu)造流程如下。

（2） 定義矩陣函數(shù)Ca，b， 當(dāng)a ＝b時(shí)，Ca，b ＝C＃（C＃為對(duì)明文處理之前明文的密文）；當(dāng)a ＝i≠j且b ＝j(luò)時(shí)，Ca，b ＝X（j）；否則，Ca，b ＝0。 從而擴(kuò)展密文即為Ca，b的一系列子矩陣。

2020 年，唐春明等［28］又對(duì)此類型加密方案公鑰生成不具有獨(dú)立性問題進(jìn)行了優(yōu)化。 MW（16）［9］方案中的密文擴(kuò)展是在CRS 模型下完成的，每個(gè)參與方都共享一個(gè)隨機(jī)矩陣B來生成公鑰，因此用戶與用戶之間的獨(dú)立性不存在。 對(duì)此Kim 等［29］提出了KLP（18）方案，盡管本方案的密文擴(kuò)展操作不需要CRS，但擴(kuò)展方法操作復(fù)雜，致使方案的計(jì)算效率較低。 唐春明等［28］便結(jié)合以上兩種方案的優(yōu)勢(shì)并用工具矩陣對(duì)隨機(jī)對(duì)角陣進(jìn)行編碼構(gòu)造了一個(gè)高效的MKFHE。 其具體的構(gòu)造過程如下。

（1） 初始化函數(shù)SetUp（）：與上面相同，只是不生成公共隨機(jī)矩陣B。

（2） 密鑰生成函數(shù)KeyGen（）： 私鑰的生成方式與上面相同，公鑰也與前面類似，只不過是原方案從初始化函數(shù)中選擇B， 而本方案要在這一函數(shù)中從中選取矩陣B。

（3） 加密函數(shù)Enc（pk，μ）：與原方案相同。

（4） 密文擴(kuò)展函數(shù)Extand（）：此函數(shù)共分4 個(gè)階段進(jìn)行。 首先用工具矩陣對(duì)隨機(jī)對(duì)角矩陣R進(jìn)行編碼得；然后用得到的編碼生成擴(kuò)展密文所需的輔助信息之后用私鑰tj和輔助信息X做內(nèi)積的形式對(duì)輔助信息 進(jìn) 行 解 碼 操 作， 得AiR）＝tjAiR ＋ej（modq），最后定義擴(kuò)展密文

3 展望

本文對(duì)多密鑰全同態(tài)加密的發(fā)展及其優(yōu)化過程進(jìn)行了梳理和分析。 不同學(xué)者針對(duì)各類型最初的MKFHE 的局限性提出了不同的優(yōu)化方案［30－32］，李寧波等［31］主要側(cè)重于原始加密體制的構(gòu)建；文獻(xiàn)［32］主要側(cè)重推動(dòng)多密鑰全同態(tài)加密發(fā)展的自舉技術(shù)。 原始方案的進(jìn)一步優(yōu)化使得優(yōu)化后的方案具有更高的運(yùn)算效率、存儲(chǔ)開銷普遍降低以及加密過程更加簡(jiǎn)便等優(yōu)勢(shì)，對(duì)MKFHE 的發(fā)展也起著至關(guān)重要的作用，文獻(xiàn)［33］應(yīng)用優(yōu)化后的MKFHE 方案提高電力物聯(lián)網(wǎng)數(shù)據(jù)的安全性。 目前優(yōu)化后的方案仍面臨一些問題和挑戰(zhàn)：

（1） 提高多密鑰加密方案的安全性。 目前構(gòu)造的大部分方案的安全性均只滿足選擇密文攻擊的不可區(qū)分性安全，部分高效的多密鑰加密方案只能夠抵抗被動(dòng)敵手攻擊的選擇明文不可區(qū)分性安全。 目前還不存在滿足自適應(yīng)選擇密文攻擊的不可區(qū)分性安全的加密方案。 因此，高效的自適應(yīng)選擇密文攻擊的不可區(qū)分性安全的多密鑰加密方案將會(huì)對(duì)密碼學(xué)的發(fā)展具有重大意義。 另外，云環(huán)境下用戶之間的數(shù)據(jù)“交易”越來越密切，多用戶數(shù)據(jù)之間的安全性分析也成為了信息安全領(lǐng)域重點(diǎn)關(guān)注的問題。

（2） 提高方案的綜合效率。 綜合效率仍是制約多密鑰全同態(tài)加密發(fā)展的一個(gè)因素。 將單密鑰密文擴(kuò)張成多密鑰密文時(shí)擴(kuò)展操作過于復(fù)雜，且擴(kuò)展后的密文體積也隨著參與方的數(shù)量隨之增大，給計(jì)算存儲(chǔ)都帶來了挑戰(zhàn)。 此外只能執(zhí)行單比特運(yùn)算，效率偏低。 這些都限制了多密鑰全同態(tài)加密的實(shí)用價(jià)值。 下一步，需要在盡可能擴(kuò)展多密鑰全同態(tài)加密功能性的基礎(chǔ)上，針對(duì)如何減小方案中密文的尺寸，盡可能地減少方案的密文量、密鑰量以及計(jì)算復(fù)雜度，進(jìn)一步提高同態(tài)運(yùn)算效率和存儲(chǔ)效率等繼續(xù)展開研究，將傳統(tǒng)的單密鑰的成熟的優(yōu)化技術(shù)應(yīng)用到多密鑰之中，從而進(jìn)一步促進(jìn)多密鑰全同態(tài)加密的實(shí)用化進(jìn)程。

（3） 探索多密鑰全同態(tài)加密在安全多方計(jì)算中的應(yīng)用。 由于格具有天然的抗量子攻擊的優(yōu)勢(shì)，因而在后量子時(shí)代成為安全多方計(jì)算協(xié)議的設(shè)計(jì)思路之一。 同時(shí)作為安全多方計(jì)算重要分支的私有信息檢索（PIR），未來具有非常高的研究前景。 將基于格的多密鑰加密方案應(yīng)用于安全多方計(jì)算可有效抵御外界的攻擊，也是當(dāng)前密碼學(xué)研究熱點(diǎn)問題之一。如何設(shè)計(jì)行之有效的全同態(tài)密碼學(xué)算法獲得通行輪次更低計(jì)算開銷更小的安全多方計(jì)算協(xié)議仍是一個(gè)公開問題。

（4） 構(gòu)建MKFHE 在標(biāo)準(zhǔn)模型下的研究方案。隨機(jī)語言模型下，MKFHE 方案中涉及到的哈希函數(shù)是安全的一個(gè)隱患。 滿二秩差分編碼函數(shù)FRD和最新的基于格的可編程哈希函數(shù)PHF 的研究成果可為MKFHE 在標(biāo)準(zhǔn)模型下的研究提供良好的幫助。

（5） 提供MKFHE 中多用戶身份的驗(yàn)證，將加密方案和簽名方案相結(jié)合，構(gòu)建多密鑰全同態(tài)加密簽名一體化方案。 加密簽名一體化方案能夠公用系統(tǒng)參數(shù)，簡(jiǎn)化方案步驟，進(jìn)一步提高方案效率。 目前基于格的簽密方案研究非常少，也是未來研究的全新挑戰(zhàn)。

總之，目前信息安全日益受到更多關(guān)注，無論密碼學(xué)前沿的MKFHE，還是其他安全方案，都迫切需要將理論在實(shí)際應(yīng)用中平穩(wěn)落地。