環LWE上高效的多密鑰全同態加密方案

車小亮，周昊楠，楊曉元，周潭平，劉龍飛，李寧波

(1.武警工程大學 密碼工程學院，陜西 西安 710086；2.網絡和信息安全武警部隊重點實驗室，陜西 西安710086)

LOPEZ-ALT等[1]首次提出了多密鑰全同態加密(Multi-Key Fully Homomorphic Encryption，MKFHE)的概念，它支持對不同用戶(不同密鑰)的密文進行任意的同態運算，且運算之后的結果由參與計算的所有用戶聯合解密，可用于安全多方計算[2]、隱私保護[3-4]等場景，具有重要的理論研究價值和應用價值。

LTV12方案是基于NTRU密碼體制設計的首個MKFHE方案[1]，之后DOR?Z等對其全同態運算進行了優化，提出了DHS16方案[5]。CHONGCHITMATE等基于此類型的MKFHE構造了具有電路隱私特性的三輪動態安全多方計算協議的CO17方案[6]。CHE等利用比特丟棄技術和密文維度擴展方法構造了一類無需密鑰交換的NTRU型多密鑰全同態加密方案[7]。這些NTRU型MKFHE方案，密文量和密鑰量相對較少，加解密速度快，但其安全性是基于多項式環上的非標準性假設，并且無法構造高效的聯合解密協議，實際應用受限。2015年，CLEAR和MCGOLDRICK根據GSW13方案[8]提出了首個基于LWE問題的GSW(Gentry-Sahai-Waters)型MKFHE方案CM15[9]，給出了從GSW型FHE到MKFHE的轉化模式。2016年，MUKHERJEE等簡化了CM15方案，提出了滿足一輪門限解密協議的MW16方案[10]。同年，PEIKERT等提出了滿足多跳(multi-hop)功能的PS16方案[11]，BRAKERSHI等進一步縮減了密文的增長規模，提出了全動態(fully dynamic)的BP16方案[12]。這些GSW型MKFHE方案安全性高，運算過程無需進行密鑰交換，但密文規模隨用戶數量增長較快，加解密速度較慢、同態運算效率不高。2016年亞密會上，CHILLOTTI等基于GSW13方案在T=(0，1]環上的變種TGSW，構造了全同態方案CGGI16[13]，具體呈現了全同態方案自舉過程的運算效率，并于2017年編寫了全同態加密軟件庫TFHE[14]。2019年，CHEN等將TFHE框架與MKFHE結合，提出了一種TFHE型MKFHE方案CCS19[15]。但該類方案不支持打包技術，從而導致密文擴展率較大。BGV(Brakerski-Gentry-Vaikuntanathan)型MKFHE安全性基于RLWE問題，支持并行加速和密文打包技術，可實現MKFHE的快速運算。2017年，CHEN等利用環上的GSW加密方案來生成密鑰轉化過程所需的計算密鑰，提出了首個BGV型多跳MKFHE方案CZW17[16]。2019年，LI等利用RBGV和RGSW密文之間的混合同態乘法生成計算密鑰，將CZW17方案中BGV和GSW擴展密文的尺寸縮減了近一半，設計了層級的BGV型MKFHE方案LZY+19[17]。同年，CHEN等在CKKS17[18]方案和LZY+19方案的基礎上，優化了重線性化過程，構造了高效的多密鑰同態加密方案CDKS19[19]，并將該方案應用于神經網絡的隱私計算。但該類方案的密文規模隨用戶數量呈線性增長，設計全同態加密方案時生成計算密鑰量大，算法效率有待提高。

筆者通過減小密文量和密鑰量，簡化計算密鑰生成過程，來提高BGV型多密鑰全同態加密方案同態運算效率。首先，優化了計算密鑰的生成算法，降低了公鑰尺寸，縮減了生成計算密鑰的密文擴展規模；其次，引入了低位比特丟棄技術，降低了因比特分解計算產生的冗余，提高了運算效率；最后，根據優化的算法，結合低位比特丟棄技術，調整公鑰和計算密鑰的生成方式，構造了高效的BGV型MKFHE方案。

1 相關知識與關鍵技術

1.1 困難問題

基于環上的誤差學習問題(Ring Learning With Errors，RLWE)：對于安全參數λ，定義維度n=n(λ)，d=d(λ)為2的冪次，模數q=q(λ)≥2為素數，定義多項式環R=[X]/xd+1和Rq=R/qR，以及R上的錯誤分布χ=χ(λ)，環上誤差學習問題就是區分以下兩個分布是困難的：①均勻選取②選取其中

1.2 關鍵技術

1.3 BGV型多密鑰同態加密的密文擴展算法

構造計算密鑰生成算法，需要引入BGV型MKFHE密文擴展算法。根據LZY+19方案的定義，BGV型MKFHE的密文擴展算法RBGV簡述如下。

(4) RBGV.CTExt(c，K′)：定義密文組ct={c，K，l}，其中K表示密文c對應的用戶集合，l表示密文c對應的電路層級信息。設用戶集K={i1，…，ik}和K′={j1，…，jk'}，K?K′。

2 計算密鑰生成算法的優化

本節通過選取合適的共用隨機變量參數，縮減公鑰和計算密鑰密文的尺寸規模，并利用低位比特丟棄技術，構造一種效率更高的計算密鑰生成算法。

2.1 計算密鑰密文的生成

2.1.1 生成用戶的密鑰信息

2.1.2 生成計算密鑰的密文

2.1.3 構造輔助密文

2.2 計算密鑰密文的擴展運算

為了降低輔助密文di，1的維度，定義一個檢索函數。

2.2.1 密文擴展運算

對于2個用戶i，j而言，使用j的公鑰pl，j=(bl，j，al，j)對用戶i的計算密鑰密文進行擴展運算，具體如下：

步驟1 將用戶i的輔助密文di，0附加用戶j的部分公鑰信息bl，j，得到

步驟3 根據用戶j的部分公鑰信息al，j，執行檢索函數，得到

(1)

2.2.2 正確性驗證

(2)

2.3 低位比特丟棄技術的應用

2.3.1 低位比特丟棄技術的正確性

(3)

2.3.2 滿足正確性的條件

(4)

根據式(3)和式(4)，滿足低位比特丟棄技術應用的正確性，則要使下式成立：

(5)

2.4 計算密鑰的生成算法

本節重新設定了初始參數，將低位比特丟棄技術應用于計算密鑰的密文擴展運算，構造了基于環上的低維密文擴展算法。并將該算法與RBGV密文算法進行混合同態乘法運算，構造出計算密鑰的生成算法。

2.4.1 密文擴展算法

用RLDA表示構造的基于環上的低維密文擴展算法(Ring-based Expansion Algorithm with Low Dimension)，具體如下：

2.4.2 優化的計算密鑰生成算法

利用RBGV密文擴展算法和RLDA算法進行混合同態乘法運算，得到優化的計算密鑰生成算法。

對Φl，j[t]，Ψl，i[t']分別進行密文擴展，可得

(6)

(7)

2.5 算法性能分析

文中構造的計算密鑰生成算法，主要是降低了用戶的公鑰尺寸，縮減了計算密鑰的密文擴展維度。相對于LZY+19方案和CDKS19方案中的計算密鑰生成算法，其公鑰尺寸、計算密鑰的密文尺寸和擴展密文尺寸呈倍數降低，具體對比如表1所示。

表1 文中構造的計算密鑰生成算法與LZY+19和CDKS19的算法存儲開銷對比

3 高效的BGV型MKFHE方案的構造

根據優化的算法，并結合模交換技術和密鑰交換技術，構造了層級的BGV型多密鑰全同態加密方案。

3.1 方案構造

(1) MKFHE.Setup(1λ，1K，1L)：安全參數為λ，電路層數為l∈{L，…，0}，用戶數集為K，多項式環R=[X]/Φm和Rq=R/(qR)，R上的錯誤分布χ=χ(λ)的界為B。每一層電路的模數qL?qL-1?…?q0，小整數p與所有的模數互質。令βl=logql+1，設比特丟棄長度為κ<β0，對任意l∈{L，…，0}均滿足vl=βl-κ。選擇L+1個隨機公共向量輸出公共參數

(2) MKFHE.KeyGen(pp)：輸入公共參數pp，m∈{κ+1，κ+2，…，βl}，生成第j個參與方所需要的密鑰(j∈[K])。

3.2 方案分析

3.2.1 安全性分析

3.2.2 噪聲分析

DBitD(ciξ，iξ′)=((ciξ，iξ′)κ+1，(ciξ，iξ′)κ+2，…，(ciξ，iξ′)βl) 。

(8)

設比特丟棄長度取最大值κmax，此時因低位比特丟棄技術而產生的噪聲值最大。根據式(2)可得‖eM‖

(9)

因為‖eB‖小于‖eM‖，所以

3.2.3 效率分析

因為CDKS19方案是非層級的多密鑰全同態加密方案，而筆者構造的方案是層級的多密鑰全同態加密方案。在效率分析中，與層級的BGV型MKFHE方案LZY+19進行對比，構造的方案進一步簡化了計算密鑰的生成過程，并且利用低位比特丟棄技術，降低了計算冗余。以在l層完成一次同態乘法運算為例，文中方案的擴展密文尺寸、公鑰尺寸、生成計算密鑰的中間密文尺寸和產生的噪聲值等參數與LZY+19方案的對比如表2所示。

表2 文中方案與LZY+19方案的參數對比

由表2可知，擴展密文的尺寸相對于LZY+19方案沒有改變，但公鑰尺寸縮小了至少一半，生成計算密鑰的中間密文尺寸約減小為LZY+19方案的1/3，且產生的噪聲值是關于n的倍數降低。此外，文中方案引入了比特丟棄技術，計算的復雜性相對較低，所以筆者構造方案的效率高于LZY+19方案的效率。

4 結束語

筆者設計了一種更高效的BGV型MKFHE方案，滿足IND-CPA安全。相對于現有的方案，設計的新方案簡化了計算密鑰的生成過程，縮減了密鑰的尺寸，并利用低位比特丟棄技術，減小了計算冗余，使得同態運算效率得到提高。下一步，將針對如何減小方案中密文的尺寸，進一步提高同態運算效率繼續展開研究。