多密鑰全同態加密的研究現狀與發展趨勢

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

(南京郵電大學 計算機學院，江蘇 南京 210023)

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

圖1 同態加密交換圖

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

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

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

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

1 基本概念

1．1 符號說明

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

令Φm（x） 為分圓多項式，則Rq ＝R／qR ＝Z（x）／〈Φm（x）〉 表示分圓多項式環，環中元素可表示為

1．2 相關定理

定理1容錯學習問題（LWE）。 對于一個秘密向量上的LWE 分布As，χ指的是均勻選取，選取e←χ，輸出（A，b ＝A·s ＋emodq）。

定理2判定性容錯學習問題（DLWE）。 設為m個相互獨立的采樣，每個采樣都是按照以下兩種方式生成的：（1） 從中隨機取樣；（2） 從分布As，χ中取樣。 DLWE 問題是指判定中的每個樣本是從哪種方式中取樣的。

定理3環上容錯學習問題（RLWEΦ，q，χ）。 對于一個秘密向量s∈Rq，RLWE 分布Ls，χ是指定義為Rq ×Rq上按如下方式生成的概率分布，隨機選取a∈Rq，e∈R服從概率分布χ，計算（a，b ＝a·s ＋e）。

定理4判定性容錯學習問題（DRLWE）。 判斷（a，b） 是從分布Ls，χ中采樣還是從Rq × Rq中采樣。

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

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

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

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

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

1．3 關鍵技術

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

密鑰交換技術（SwitchKey（））：將對應的密文由（解密密鑰為sk1） 轉換成為密文（解密密鑰為sk2）。

比特分解技術： 比特分解技術是指用BitDecomp（·） 和Powersof2（·） 這兩個函數對數據進行比特位展開。 令l ＝「logq?， 則其具體表達分別為

BitDecomp（x∈，q）： 輸入多項式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比特。

Powersof2（y∈，q）： 輸入多項式y ＝（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）技術：當同態操作進行至噪聲達到閾值而無法再進行操作時， 將此時的密文與對應私鑰的密文進行同態解密的操作。 即將自己解密函數作為FHE．Eval算法中的輸入函數，將達到噪聲上限的密文與該密文解密秘鑰中的每一位加密結果作為FHE．Eval算法中的輸入密文，則執行FHE．Eval算法會生成一個與該密文對應相同明文的“新鮮”密文，從而可以繼續進行密文同態運算。當密文再次達到噪聲上限時，可以再進行一次同態解密運算，依次遞歸，在KDM 安全假設下，即可獲得純FHE 方案。 自舉后可以得到支持繼續同態操作的低噪聲密文。 自舉是目前最有效的消減密文噪聲的操作，也是迄今為止實現全同態加密的唯一途徑。

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

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

圖2 自舉算法執行流程圖

1．4 格上困難問題

格是指n維空間Rn具有周期性結構的點的集合。

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

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

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

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

2 全同態加密及多密鑰全同態加密

基于全同態加密的多密鑰全同態加密的發展過程同全同態加密一樣分為3 個階段，下面分析各階段的核心方法。

2．1 以Gentry 的突破性工作為基礎

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

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

2．2 基于LWE 和RLWE 的多密鑰全同態加密方案

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

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

2.2.1 NTRU 型MKFHE 的構造及優化

作為首個被提出的多密鑰加密方案類型，對后來MKFHE 的構造起著至關重要的作用，NTRU 型多密鑰加密方案［7］的基本構造過程如下。

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

（2） 密鑰生成NTRU．KeyGen（1n，1L）： 產生公鑰、私鑰和同態計算密鑰，其中L為運算深度。

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

（4） 同態運算NTRU．Eval（c1，c2）：此階段需要計算密鑰的參與，用計算密鑰結合模交換技術或密鑰交換技術進行同態運算。

（5） 解 密NTRU．Dec（sk1，sk2，…，skn，c?）： 其中c?為經過同態計算產生的新鮮密文。

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

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

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

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

此時對進行同態運算之后的密文進行解密便可不再需要計算密鑰，直接用私鑰與密文做內積即可得到明文。 下面以解密同態乘（cMult ＝c1g－1（c2） ∈為例進行論證，使用f＾＝f1·f2解密cMult時需計算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，因此同態乘法運算過程不需要計算密鑰的參與得證，同態加法運算過程同理。

除直接對同態運算過程優化外，還可采用間接方式。 例如，車小亮等［21］通過改變NTRU 型加密方案的底層結構對其安全性和效率進行了優化，將現有方案底層的分圓多項式環擴展到素數次分圓多項式環上，可以抵御更多的子域攻擊。 然后通過擴展密文維度消除密鑰交換技術，并結合模交換技術構造一個高效的層級的NTRU 型MKFHE。 其具體的優化過程如下。

對安全性的優化：只是將原方案中的分圓多項式用素數次分圓多項式替代，其他多項式時間算法不變。 定義素數次分圓多項式環為R ＝參數n和q ＝q（λ） 為素整數。 根據文獻［22］可知，素數次分圓多項式可以抵抗更多的子域攻擊。

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

表1 原方案與優化后的方案對比表

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

此外，由于層級的加密方案每層密文維數不同，車小亮等［21］又提出了去尾函數來統一維數。 去尾函數表示去掉向量的li＋1→li項，使li維向量轉換成li＋1維向量至此一個可以抵御更多子域攻擊、不需要密鑰交換的NTRU 型全同態加密被構造完成。

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

2.2.2 BGV 型MKFHE 的構造及優化

BGV 型的多密鑰全同態加密方案的密文結構相對比較特殊，密文擴展過程不需要計算密鑰的加入，但當前對BGV 型MKFHE［24］的研究還很缺乏。其基本構造流程如下。

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

（2） 密鑰生成BGV．KeyGen（1n，1L）： 產生公私鑰以及生成計算密鑰所需的相關密文ems。

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

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

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

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

計算密鑰的生成：分為生成擴展密文RBGV、生成擴展密文RGSW 和生成計算密鑰3 部分。

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

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

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

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

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

原BGV 方案中ems是由多項式環上的GSW 加密方案來對參與計算的用戶的私鑰進行加密的，而在本 方 案 中

解密部分的優化：

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

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

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

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

（3） 獲 得 計 算 密 鑰evk，evk ＝｛km ＝

優化的結果相比原加密方案的公鑰尺寸和計算密鑰密文量都相對減少，計算密鑰的生成效率有所提高。

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

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

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

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

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

（4） 密文擴展GSW．Extand（）： 此種類型的MKFHE 方案在進行同態運算之前要先進行密文擴展，否則無法參與同態運算。

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

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

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

（2） 定義矩陣函數Ca，b， 當a ＝b時，Ca，b ＝C＃（C＃為對明文處理之前明文的密文）；當a ＝i≠j且b ＝j時，Ca，b ＝X（j）；否則，Ca，b ＝0。 從而擴展密文即為Ca，b的一系列子矩陣。

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

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

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

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

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

3 展望

本文對多密鑰全同態加密的發展及其優化過程進行了梳理和分析。 不同學者針對各類型最初的MKFHE 的局限性提出了不同的優化方案［30－32］，李寧波等［31］主要側重于原始加密體制的構建；文獻［32］主要側重推動多密鑰全同態加密發展的自舉技術。 原始方案的進一步優化使得優化后的方案具有更高的運算效率、存儲開銷普遍降低以及加密過程更加簡便等優勢，對MKFHE 的發展也起著至關重要的作用，文獻［33］應用優化后的MKFHE 方案提高電力物聯網數據的安全性。 目前優化后的方案仍面臨一些問題和挑戰：

（1） 提高多密鑰加密方案的安全性。 目前構造的大部分方案的安全性均只滿足選擇密文攻擊的不可區分性安全，部分高效的多密鑰加密方案只能夠抵抗被動敵手攻擊的選擇明文不可區分性安全。 目前還不存在滿足自適應選擇密文攻擊的不可區分性安全的加密方案。 因此，高效的自適應選擇密文攻擊的不可區分性安全的多密鑰加密方案將會對密碼學的發展具有重大意義。 另外，云環境下用戶之間的數據“交易”越來越密切，多用戶數據之間的安全性分析也成為了信息安全領域重點關注的問題。

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

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

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

（5） 提供MKFHE 中多用戶身份的驗證，將加密方案和簽名方案相結合，構建多密鑰全同態加密簽名一體化方案。 加密簽名一體化方案能夠公用系統參數，簡化方案步驟，進一步提高方案效率。 目前基于格的簽密方案研究非常少，也是未來研究的全新挑戰。

總之，目前信息安全日益受到更多關注，無論密碼學前沿的MKFHE，還是其他安全方案，都迫切需要將理論在實際應用中平穩落地。