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

(1.武警工程大學(xué) 密碼工程學(xué)院，陜西 西安 710086；2.網(wǎng)絡(luò)和信息安全武警部隊(duì)重點(diǎn)實(shí)驗(yàn)室，陜西 西安710086)

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

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

筆者通過減小密文量和密鑰量，簡化計(jì)算密鑰生成過程，來提高BGV型多密鑰全同態(tài)加密方案同態(tài)運(yùn)算效率。首先，優(yōu)化了計(jì)算密鑰的生成算法，降低了公鑰尺寸，縮減了生成計(jì)算密鑰的密文擴(kuò)展規(guī)模；其次，引入了低位比特丟棄技術(shù)，降低了因比特分解計(jì)算產(chǎn)生的冗余，提高了運(yùn)算效率；最后，根據(jù)優(yōu)化的算法，結(jié)合低位比特丟棄技術(shù)，調(diào)整公鑰和計(jì)算密鑰的生成方式，構(gòu)造了高效的BGV型MKFHE方案。

1 相關(guān)知識(shí)與關(guān)鍵技術(shù)

1.1 困難問題

基于環(huán)上的誤差學(xué)習(xí)問題(Ring Learning With Errors，RLWE)：對(duì)于安全參數(shù)λ，定義維度n=n(λ)，d=d(λ)為2的冪次，模數(shù)q=q(λ)≥2為素?cái)?shù)，定義多項(xiàng)式環(huán)R=[X]/xd+1和Rq=R/qR，以及R上的錯(cuò)誤分布χ=χ(λ)，環(huán)上誤差學(xué)習(xí)問題就是區(qū)分以下兩個(gè)分布是困難的：①均勻選?、谶x取其中

1.2 關(guān)鍵技術(shù)

1.3 BGV型多密鑰同態(tài)加密的密文擴(kuò)展算法

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

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

2 計(jì)算密鑰生成算法的優(yōu)化

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

2.1 計(jì)算密鑰密文的生成

2.1.1 生成用戶的密鑰信息

2.1.2 生成計(jì)算密鑰的密文

2.1.3 構(gòu)造輔助密文

2.2 計(jì)算密鑰密文的擴(kuò)展運(yùn)算

為了降低輔助密文di，1的維度，定義一個(gè)檢索函數(shù)。

2.2.1 密文擴(kuò)展運(yùn)算

對(duì)于2個(gè)用戶i，j而言，使用j的公鑰pl，j=(bl，j，al，j)對(duì)用戶i的計(jì)算密鑰密文進(jìn)行擴(kuò)展運(yùn)算，具體如下：

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

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

(1)

2.2.2 正確性驗(yàn)證

(2)

2.3 低位比特丟棄技術(shù)的應(yīng)用

2.3.1 低位比特丟棄技術(shù)的正確性

(3)

2.3.2 滿足正確性的條件

(4)

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

(5)

2.4 計(jì)算密鑰的生成算法

本節(jié)重新設(shè)定了初始參數(shù)，將低位比特丟棄技術(shù)應(yīng)用于計(jì)算密鑰的密文擴(kuò)展運(yùn)算，構(gòu)造了基于環(huán)上的低維密文擴(kuò)展算法。并將該算法與RBGV密文算法進(jìn)行混合同態(tài)乘法運(yùn)算，構(gòu)造出計(jì)算密鑰的生成算法。

2.4.1 密文擴(kuò)展算法

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

2.4.2 優(yōu)化的計(jì)算密鑰生成算法

利用RBGV密文擴(kuò)展算法和RLDA算法進(jìn)行混合同態(tài)乘法運(yùn)算，得到優(yōu)化的計(jì)算密鑰生成算法。

對(duì)Φl，j[t]，Ψl，i[t']分別進(jìn)行密文擴(kuò)展，可得

(6)

(7)

2.5 算法性能分析

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

表1 文中構(gòu)造的計(jì)算密鑰生成算法與LZY+19和CDKS19的算法存儲(chǔ)開銷對(duì)比

3 高效的BGV型MKFHE方案的構(gòu)造

根據(jù)優(yōu)化的算法，并結(jié)合模交換技術(shù)和密鑰交換技術(shù)，構(gòu)造了層級(jí)的BGV型多密鑰全同態(tài)加密方案。

3.1 方案構(gòu)造

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

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

3.2 方案分析

3.2.1 安全性分析

3.2.2 噪聲分析

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

(8)

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

(9)

因?yàn)椤琫B‖小于‖eM‖，所以

3.2.3 效率分析

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

表2 文中方案與LZY+19方案的參數(shù)對(duì)比

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

4 結(jié)束語

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