李瑞琪, 賈春福

1. 南開大學(xué) 網(wǎng)絡(luò)空間安全學(xué)院, 天津300350

2. 天津市網(wǎng)絡(luò)與數(shù)據(jù)安全技術(shù)重點(diǎn)實(shí)驗(yàn)室, 天津300350

1 引言

全同態(tài)加密(Fully Homomorphic Encryption, FHE) 是一種新型密碼學(xué)工具, 其支持在加密信息上進(jìn)行任意函數(shù)運(yùn)算, 并且解密后得到的結(jié)果與在明文上執(zhí)行相應(yīng)運(yùn)算的結(jié)果一致. 全同態(tài)加密的特性使其能夠廣泛應(yīng)用于云計(jì)算、物聯(lián)網(wǎng)等多種計(jì)算場景. 同態(tài)加密的思想最初由Rivest 等人[1]在1978 年提出(最初的概念被稱作“privacy homomorphism”), 但在此之后一直都沒有具體的構(gòu)造方法, 直到2009 年Gentry 才構(gòu)造出了第一個(gè)全同態(tài)加密方案[2,3]. 在Gentry 的開創(chuàng)性工作之后, 一系列關(guān)于全同態(tài)加密的研究成果相繼出現(xiàn)[4-8].

多密鑰全同態(tài)加密(Multi-Key Fully Homomorphic Encryption, MKFHE) 是FHE 在多用戶場景下的一種推廣, 其支持多方用戶以各自的密鑰對消息進(jìn)行加密, 得到的密文可以一起參與運(yùn)算, 運(yùn)算結(jié)束后將各參與方的密鑰收集起來得到聯(lián)合密鑰, 再用聯(lián)合密鑰對結(jié)果密文進(jìn)行解密. MKFHE 在安全多方計(jì)算中有著重要應(yīng)用. 當(dāng)前有關(guān)MKFHE 方案構(gòu)造的研究主要可以分為以下三類:

· 基于NTRU 方案. López 等首次提出了MKFHE 的概念,并且構(gòu)造了第一個(gè)MKFHE 方案[8](下稱LTV12 方案), 該方案是基于NTRU 加密體制[9,10]的. 作者利用重線性化(relinearization)和模交換(modulus switching) 技術(shù)獲得一個(gè)層級多密鑰全同態(tài)加密(leveled MKFHE) 方案.

· 基于Gentry-Sahai-Waters (GSW) 方案. 2015 年, Clear 等[11]構(gòu)造了一個(gè)以GSW 方案[7,12]為基礎(chǔ)的MKFHE 方案, 隨后Mukherjee 等[13]對Clear 的方案進(jìn)行了改進(jìn). 由于這兩個(gè)方案需要在進(jìn)行密文運(yùn)算前就確定所有參與的用戶, 因此這兩個(gè)方案被稱作單跳的(single-hop). 相對應(yīng)地, Peikert 等[14]在2016 年提出了多跳的(multi-hop)MKFHE 方案(下稱PS16 方案), 其支持運(yùn)算得到的結(jié)果密文繼續(xù)參與到接下來的計(jì)算中, 也支持新用戶中途加入運(yùn)算. 同年, Brakerski等[15]提出了與多跳類似的概念——全動(dòng)態(tài)(fully dynamic), 并構(gòu)造了一個(gè)全動(dòng)態(tài)的MKFHE 方案(下稱BP16 方案), 該方案支持任意用戶在任意時(shí)刻加入運(yùn)算. 多跳與全動(dòng)態(tài)的區(qū)別僅在于是否需要在同態(tài)計(jì)算前輸入?yún)⑴c運(yùn)算的用戶數(shù)的上限.

· 基于Brakerski-Gentry-Vaikuntanathan (BGV) 方案. 2017 年, Chen 等[16]提出了一個(gè)基于BGV[5]方案的MKFHE 方案(下稱CZW17 方案). 該方案支持加密環(huán)中的元素而不只是1 比特, 并且該方案能夠加入批處理機(jī)制.

上述三種類型的方案推動(dòng)了MKFHE 的研究, 但仍然存在著一定的問題. 這些方案存在的最主要問題是, 參與運(yùn)算的用戶除了生成公私鑰以及對消息進(jìn)行加解密外, 還需產(chǎn)生大量額外的參數(shù)以保證多密鑰的同態(tài)密文計(jì)算能夠進(jìn)行, 例如LTV12 方案、BP16 方案和CZW17 方案中需要用戶生成運(yùn)算密鑰(evaluation key), PS16 方案則需要用戶生成extension key 或冗余的密文, 這增加了用戶端的計(jì)算開銷.另外, 基于BGV 和基于GSW 的方案都需要進(jìn)行密文擴(kuò)張, 因?yàn)檫@兩類方案中解密密鑰的維數(shù)會隨著用戶數(shù)的增加而增加, 這使得密文的尺寸也要隨之增加才能正確解密.

為了解決上述問題, 我們提出了一種新的多密鑰同態(tài)加密方案, 利用工具向量和相應(yīng)的分解函數(shù)將NTRU 方案轉(zhuǎn)化成leveled MKFHE 方案. 本文所提方案的主要優(yōu)勢在于:

· 用戶端只需要生成公鑰和私鑰以及對消息進(jìn)行加解密, 并不需要生成evaluation key 或其他額外的參數(shù), 減輕了用戶端的計(jì)算負(fù)擔(dān).

· 使用比特分解技術(shù)來構(gòu)造HE 方案,這使得密文加法和乘法能夠簡單地實(shí)現(xiàn),不需要加入其它輔助技術(shù)(如relinearization);也使得NTRU 直接轉(zhuǎn)化為leveled MKFHE 方案,從而不需要modulus switching 技術(shù). 整個(gè)方案更加簡潔、易于實(shí)現(xiàn).

· 不需要進(jìn)行密文擴(kuò)張, 即密文的(最大) 尺寸是不變的.

· 支持加密環(huán)中的元素而并不只是1 比特, 因而本方案可以擴(kuò)展成支持批處理的MKFHE 方案.

另外,我們的方案是一個(gè)leveled MKFHE 方案,仍需要利用Gentry 的bootstrapping 定理將leveled MKFHE 方案轉(zhuǎn)化為一個(gè)完全的MKFHE 方案.

2 預(yù)備知識

本文中我們使用加粗大寫字母表示矩陣, 如M; 使用加粗小寫字母表示向量, 如v. 在矩陣中, M[i,j]表示位于第i 行第j 列的元素; 在向量中, v[i] 表示向量中的第i 個(gè)元素. 矩陣和向量中的元素標(biāo)號從1開始. 本文中運(yùn)算符“·” 表示矩陣乘法, 包括矩陣-矩陣乘法和標(biāo)量-矩陣乘法(向量可以看作n×1 或者1×n 的矩陣).

其中δ 是一個(gè)只與環(huán)R 有關(guān)的常數(shù), 稱作環(huán)常數(shù).

2.1 離散高斯分布

我們將均值為0、標(biāo)準(zhǔn)差為r 的離散高斯分布記作DZn,r. 在本文中唯一需要用到的有關(guān)離散高斯分布的性質(zhì)是, 從DZn,r中抽取的樣本的范數(shù)大概率在某一范圍內(nèi). 由此我們可以定義如下的概念:

定義1[8]如果一族分布{χn}n∈N滿足

則稱其為B 界分布.

而離散高斯分布有如下性質(zhì):推論1[8]令R=Z[x]/〈φm(x)〉. 令χ 為R 上的B 界分布, 設(shè)f1,f2,··· ,fk←χ, 有

2.2 RLWE 問題與DSPR 假設(shè)

環(huán)上帶錯(cuò)學(xué)習(xí)問題(Ring Learning With Errors, RLWE) 最初是由Lyubashevsky 等[17]提出的, 判別版本的RLWE 問題定義如下:

定義2[17]設(shè)U(X) 為集合X 上的均勻分布. 給定一個(gè)秘密多項(xiàng)式s ∈Rq, 一個(gè)R 上的分布χ, 我們定義一個(gè)Rq× Rq上的分布As,χ: 隨機(jī)選取a ←U(Rq), 隨機(jī)抽取一個(gè)差錯(cuò)e ←χ, 輸出(a,b = a·s+e). 判別版本的RLWE 問題(記作DRLWEq,χ) 定義為: 當(dāng)s ←U(Rq) 時(shí), 區(qū)分As,χ與U(Rq×Rq) 兩個(gè)分布.

下面的定理闡述了問題DRLWEq,χ的困難性, 即區(qū)分As,χ與U(Rq×Rq) 這兩個(gè)分布是困難的.

2.3 多密鑰同態(tài)加密

一個(gè)多密鑰同態(tài)加密方案包含四個(gè)算法(KeyGen, Enc, Dec, Eval), 具體描述如下:

· (pk, sk)←KeyGen(1λ): 給定安全參數(shù)λ, 輸出公鑰pk 和私鑰sk;

· c ←Enc(pk,m): 輸入消息明文m 和公鑰pk, 輸出密文c;

· m:=Dec(sk1,sk2,···,skN,c): 輸入密文c, 以及密文所對應(yīng)的運(yùn)算參與方的私鑰sk1,sk2,···,skN,輸出消息明文m;

· (c*,S) := Eval(C,(c1,S1),(c2,S2),··· ,(ct,St)): 算法的輸入包括一個(gè)電路C, 以及t 個(gè)元組(ci,Si),i ∈{1,··· ,t}. 每個(gè)元組中包括一個(gè)密文ci和其對應(yīng)的用戶(密鑰) 集合Si. 算法的輸出為結(jié)果密文c*和其對應(yīng)的用戶(密鑰) 集合S =∪Si(在用戶(密鑰) 集合中可以找到任意參與運(yùn)算的用戶的公私鑰).

2.4 Bootstrapping

Gentry 在文獻(xiàn)[2,3] 中提出了“bootstrapping” 技術(shù), 該技術(shù)利用重加密的思想更新密文, 從而控制噪聲膨脹以保證解密正確性, 進(jìn)而實(shí)現(xiàn)任意次的密文同態(tài)運(yùn)算. Gentry 的bootstrapping 定理也可以用于多密鑰的場景. 具體來說, 該技術(shù)要求HE 方案能夠?qū)Α霸鰪?qiáng)解密電路(augmented decryption circuit)”進(jìn)行處理, 同時(shí)也需要該HE 方案具有弱循環(huán)安全性(weakly circular secure). 有關(guān)bootstrapping 技術(shù)的更多細(xì)節(jié)參見文獻(xiàn)[2,3].

定義4 令E 為一個(gè)多密鑰同態(tài)加密方案. 該方案的增強(qiáng)解密電路fc1,c2定義為

定義5 如果一個(gè)公鑰加密方案在敵手獲得其私鑰的所有比特的密文時(shí)仍然是IND-CPA 安全的, 則稱該方案具有弱循環(huán)安全性.

結(jié)合定義4 和5, 可以得到多密鑰版本的bootstrapping 定理如下:

定理2 如果一個(gè)多密鑰同態(tài)加密方案能夠同態(tài)運(yùn)行其增強(qiáng)解密電路, 并且具有弱循環(huán)安全性, 那么該方案就能轉(zhuǎn)化為一個(gè)完全的多密鑰全同態(tài)加密方案.

2.5 工具向量和比特分解函數(shù)

2.6 中國剩余定理與批處理

中國剩余定理(Chinese Remainder Theorem, CRT) 是一個(gè)重要的工具, 該定理內(nèi)容如下:

定理3[23]設(shè)R 是一個(gè)環(huán), I1,I2,··· ,Ik是R 中兩兩互素的理想, 于是有

每一個(gè)Zp[x]/fi(x) 可以看作一個(gè)“明文槽”, 利用該同構(gòu)可以將k 個(gè)Fpd中的明文用Rp中的一個(gè)元素來表示, 并且有如下性質(zhì): 設(shè)(a0,a1,··· ,ak-1),(b0,b1,··· ,bk-1) ∈(Fpd)k是兩組明文, 它們對應(yīng)的Rp中的元素分別是a,b, 于是計(jì)算a+b 相當(dāng)于計(jì)算(a0+b0,a1+b1,··· ,ak-1+bk-1), 計(jì)算ab 相當(dāng)于計(jì)算(a0b0,a1b1,··· ,ak-1bk-1). 利用上述原理, 文獻(xiàn)[24] 提出了支持SIMD (Single Instruction Multiple Data) 操作的HE 方案.

在此基礎(chǔ)上, 文獻(xiàn)[25] 利用Rp上的自同構(gòu)映射a(x)a(xj) 并結(jié)合Bene?/Waksman 置換網(wǎng)絡(luò),可以使明文槽中的元素進(jìn)行任意置換(permutation). 具體來說, 伽羅瓦群Gal(Q[x]/φm(x)) 中的元素為自同構(gòu)映射xi,i ∈Z*m, 該伽羅瓦群包含了一個(gè)子群G ={xxpi|i=0,1,··· ,d-1}. 文獻(xiàn)[25] 證明了商群H =Gal(Q[x]/φm(x))/G 可以使明文槽中存儲的消息進(jìn)行輪換(rotation). 因此, 以群H 所包含的自同構(gòu)映射為基礎(chǔ)再結(jié)合Bene?/Waksman 置換網(wǎng)絡(luò), 可以實(shí)現(xiàn)明文槽中元素的任意置換.

3 基于NTRU 的多密鑰同態(tài)加密方案

3.1 NTRU 方案

我們首先介紹NTRU 方案, 這是構(gòu)造我們的MKFHE 方案的基礎(chǔ).

給定安全參數(shù)λ, 設(shè)存在多項(xiàng)式時(shí)間的算法輸出以下參數(shù): 素?cái)?shù)q =q(λ), 分圓多項(xiàng)式φm(x)(次數(shù)為n=n(λ)=φ(m)), B(λ) 界分布χ. 方案的明文空間為M=Rp, p 為小整數(shù)(例如2 或3), 方案所涉及到的所有運(yùn)算均在環(huán)Rq=Zq[x]/〈φm(x)〉 中進(jìn)行. NTRU 方案由以下三個(gè)算法組成:

· NTRU.KeyGen(1λ): 隨機(jī)抽取多項(xiàng)式f′,g ←χ, 令f :=pf′+1. 如果f 在Rq中不可逆, 那么重新抽取f′. 輸出公鑰和私鑰

· NTRU.Enc(pk,μ): 隨機(jī)抽取多項(xiàng)式s,e ←χ. 輸出密文

· NTRU.Dec(sk,c): 計(jì)算μ′=f ·c ∈Rq, 輸出

當(dāng)‖fc‖∞≤q/2 時(shí), 解密的結(jié)果是正確的, 這是由于此時(shí)fc mod q =fc.

3.2 基于NTRU 的多密鑰同態(tài)加密方案

這一小節(jié)介紹我們的基于NTRU 的多密鑰同態(tài)加密方案.

給定安全參數(shù)λ, 設(shè)存在多項(xiàng)式時(shí)間的算法, 輸出素?cái)?shù)q = q(λ), 分圓多項(xiàng)式φm(x)(次數(shù)為n =φ(m) = n(λ)), B(λ) 界分布χ. 設(shè)基為ω, ?q=, 工具向量為g = (1,ω,ω2,··· ,ω?q-1), 明文空間為M = Rp, 令p 為小整數(shù)且滿足p ≤ω ＜q, 所有的運(yùn)算均在Rq中進(jìn)行. 我們的多密鑰同態(tài)加密方案包括以下四個(gè)算法:

· MKHE.KeyGen(1λ): 調(diào)用NTRU.KeyGen(1λ), 輸出公鑰和私鑰

· MKHE.Enc(pk,μ): 隨機(jī)抽取?q組si,ei←χ 用于計(jì)算NTRU.Enc(h,0) 來得到?q個(gè)“0 的密文”, 然后將得到的?q個(gè)0 的密文組成一個(gè)向量c0∈, 最后輸出密文

· MKHE.Dec(sk1,sk2,···,skN,c): 析取每個(gè)私鑰ski得到ski= fi, 令聯(lián)合私鑰為sk := f =f1f2···fN. 計(jì)算并輸出明文

· MKHE.Eval(C,(c1,S1),(c2,S2),···,(ct,St)): 設(shè)密文c1對應(yīng)的用戶(密鑰) 集合為S1, 密文c2對應(yīng)的用戶(密鑰) 集合為S2. 密文加法為

密文乘法為

同時(shí), 也需要輸出cadd和cmult對應(yīng)的用戶(密鑰) 集合S =S1∪S2.

4 方案分析

本節(jié)將對我們提出的MKFHE 方案的有關(guān)性質(zhì)進(jìn)行分析.

4.1 同態(tài)性分析

從而乘法正確.

在文獻(xiàn)[8] 的最初構(gòu)造中, 密文c2+需要使用聯(lián)合私鑰f2·解密, 而密文c+～c2需要使用聯(lián)合私鑰f ·解密, 也就是說聯(lián)合私鑰會隨著運(yùn)算電路的變化而變化. 但我們希望聯(lián)合私鑰僅與參與用戶有關(guān), 而與運(yùn)算電路無關(guān). 在文獻(xiàn)[8] 中, 作者利用relinearization 技術(shù)解決了這個(gè)問題. 而在本文中, 我們的MKFHE 方案不需要額外添加任何技術(shù)就可以使得聯(lián)合私鑰只與參與用戶有關(guān), 不受運(yùn)算電路的影響.下面我們來說明這一點(diǎn).

事實(shí)上只需證明在本方案中, 僅使用私鑰f 就能正確解密密文cmult=c·g-1(c) 即可.

與上文類似, 我們可將c·g-1(c) 表示為

以上的推導(dǎo)說明了無論有多少個(gè)用同一公鑰加密的密文相乘, 解密時(shí)只需使用原私鑰, 這就意味著本方案中的聯(lián)合私鑰與運(yùn)算電路無關(guān).

4.2 安全性分析

4.3 噪聲分析

在這一小節(jié)中, 我們將分析執(zhí)行同態(tài)運(yùn)算的過程中, 密文噪聲的增長情況. 首先, 對密文的噪聲進(jìn)行定義:

定義6 設(shè)c 為一個(gè)密文, f 為其對應(yīng)的私鑰. 密文c 的噪聲定義為

對于所有NTRU 類型的方案, 解密正確需要滿足條件‖f ·c‖∞≤q/2. 因此在本方案中, 正確解密需要保證密文噪聲滿足noise(c)≤q/2.

下面的引理給出了執(zhí)行一次同態(tài)運(yùn)算后密文噪聲的增長幅度.

引理3 令c,c′是兩個(gè)密文, 它們對應(yīng)的明文分別是μ,μ′, 對應(yīng)的用戶(密鑰) 集合分別為S1,S2. 令c 和c′之間執(zhí)行一次同態(tài)運(yùn)算(加法或乘法) 后得到的密文所對應(yīng)的用戶(密鑰) 集合為S =S1∪S2, 且S 中包含N 個(gè)用戶(密鑰). 解密cadd=c+c′和cmult=c·g-1(c′) 可以分別得到μ+μ′和μ·μ′. 如果noise(c)≤E,noise(c′)≤E, 那么進(jìn)行一次同態(tài)運(yùn)算后, 有noise(cadd),noise(cmult)＜(2pωnδB)2NE,參數(shù)p,ω,δ,n,B 的定義見3.2 節(jié).

證明: 已知每個(gè)用戶最初的私鑰fi的范數(shù)上界為pB+1, fS=fi. 根據(jù)推論1 可知‖fS‖∞≤δN-1(pB+1)N＜δN-1(2pB)N. 對于加法有

本方案是一個(gè)leveled MKFHE 方案.

證明: 引理3 給出了一次同態(tài)運(yùn)算后密文噪聲的增長情況, 于是我們可以從初始密文中的噪聲E0＜4p2δB2開始計(jì)算L 層(乘法) 運(yùn)算后密文噪聲的大小. 經(jīng)過L 層運(yùn)算后, 密文噪聲增長為為了能夠正確解密，我們需要保證(2pωnδB)2NL+2≤q/2. 已知p = O(1),ω = O(1),B = poly(n), 并且文獻(xiàn)[3] 指出大多數(shù)情況下環(huán)常數(shù)δ 滿足δ =poly(n)(這就要求我們選取滿足此項(xiàng)要求的分圓多項(xiàng)式).根據(jù)上述條件可得

4.4 完全的多密鑰全同態(tài)加密

上文中我們得到的方案是一個(gè)leveled MKFHE 方案. 在這一小節(jié)中我們將說明, 可以利用Gentry所提出的bootstrapping 定理, 將leveled MKFHE 方案轉(zhuǎn)化為完全的MKFHE 方案.

Gentry 在其開創(chuàng)性的工作[2,3]中提出了bootstrapping 定理, 該定理指出如果一個(gè)同態(tài)加密方案能夠同態(tài)運(yùn)行自己的增強(qiáng)解密電路, 那么該方案就能夠轉(zhuǎn)化為一個(gè)完全的全同態(tài)加密方案. 因此, 需要對本方案的解密電路的深度進(jìn)行衡量. 下面的引理給出了本方案解密電路深度的上界.

引理5 本方案的解密電路可以用GF(2) 上的深度為O(log N·(log log q+log n)) 的算術(shù)電路來實(shí)現(xiàn).

證明: 假設(shè)c 是密文, 其對應(yīng)的私鑰集合為{f1,f2,··· ,fN}, 那么解密c 的過程可以表示為

文獻(xiàn)[4] 已經(jīng)證明, 兩個(gè)Rq中的多項(xiàng)式的乘法可以通過深度為O(log log q+log n) 的布爾電路來實(shí)現(xiàn). N 個(gè)多項(xiàng)式相乘可以通過深度為log N 的二叉樹來實(shí)現(xiàn), 因此解密過程的布爾電路的深度為

根據(jù)上文的結(jié)論, 我們得到定理5.

從而得到定理中的結(jié)論.

4.5 批處理

利用中國剩余定理和文獻(xiàn)[24] 中提出的SIMD 技術(shù), 可以將本方案轉(zhuǎn)化為一個(gè)支持批處理的多密鑰同態(tài)加密方案. 當(dāng)選取合適的參數(shù)p 和分圓多項(xiàng)式時(shí), 我們可以通過CRT 將一組明文(μ1,μ2,··· ,μk)映射為一個(gè)多項(xiàng)式μ=CRT(μ1,μ2,··· ,μk), 然后將μ 加密得到密文c. 根據(jù)同態(tài)加密和CRT 映射的特性, 并行加法和乘法可以分別通過密文加法和乘法實(shí)現(xiàn). 因此在本小節(jié)中, 我們將主要討論如何進(jìn)行置換運(yùn)算. 文獻(xiàn)[25] 提出了以自同構(gòu)映射為基礎(chǔ)來實(shí)現(xiàn)置換的方法, 其中自同構(gòu)映射是核心技術(shù), 下文將介紹自同構(gòu)映射在本方案中的應(yīng)用.

設(shè)密文c 對應(yīng)的明文為μ, 對應(yīng)的密鑰為f =f1f2···fN, 因此我們可知

其中e(x),k(x)∈R1×?q. 將自同構(gòu)xxi,i ∈作用于該等式可得

已知φm(x) 能夠整除φm(xi),i ∈, 從而我們可以將c(xi) 看作μ(xi) 關(guān)于密鑰f(xi) 的密文. 然而我們需要的密文應(yīng)當(dāng)是對應(yīng)于密鑰f(x) 的密文, 因此我們在進(jìn)行置換運(yùn)算時(shí), 需要借助于密鑰交換技術(shù)(key switching), 將密文c(xi) 轉(zhuǎn)化為一個(gè)新的密文c′= KeySwitch(c(xi)), 使得新密文能夠用f(x) 解密. 下面將說明本方案中為實(shí)現(xiàn)置換運(yùn)算所需要的密鑰交換過程.

設(shè)密文c(x) 對應(yīng)的聯(lián)合密鑰為f(x) = f1(x)f2(x)···fN(x), 密鑰交換過程KeySwitch(c(xi)) 分為以下2 步:

· 擁有密鑰fj的用戶首先計(jì)算cfj= MKHE.Enc(hj,fj(xi)), 然后每個(gè)用戶將各自的計(jì)算結(jié)果cfj發(fā)送到云端.

· 云端計(jì)算

得到的計(jì)算結(jié)果c′即是所需的密文.

其中c(0),f1f2···fN是對應(yīng)于密鑰f =f1f2···fN的0 的密文. 顯然, 當(dāng)密文噪聲不超過上界時(shí), c′能夠用f =f1f2···fN解密.

5 方案對比

本節(jié)中我們將對比本方案與其他經(jīng)典方案在性能上的差異.

首先簡要對比本方案與Dor?z 等人[27]在2016 年提出的方案(下稱DS16 方案) 之間的異同. 本方案與DS16 方案使用了類似的技術(shù)(即比特分解) 來處理噪聲的增長, 但是不同之處在于DS16 方案使用了BitDecomp、Flatten 等函數(shù)進(jìn)行比特分解; 本方案則利用工具向量g 及其相對應(yīng)的分解函數(shù)g-1(·)進(jìn)行分解, 此項(xiàng)差異造成了兩個(gè)方案的密文大小以及同態(tài)運(yùn)算的復(fù)雜度有所不同. 設(shè)n 表示分圓多項(xiàng)式的次數(shù), q 表示模數(shù), 那么DS16 方案中密文的尺寸為O(n log3q), 本方案中密文的尺寸為O(n log2q). 相較于DS16 方案, 本方案中的密文尺寸相對較小. 在同態(tài)運(yùn)算過程中, DS16 方案需進(jìn)行(維數(shù)為log q 的, 元素為多項(xiàng)式的) 矩陣加法和矩陣乘法, 本方案則進(jìn)行的是(維數(shù)為log q 的, 元素為多項(xiàng)式的) 向量加法和矩陣-向量乘法. 相比之下, 本方案的計(jì)算復(fù)雜度較低. 另外, DS16 方案討論的是單密鑰場景下的同態(tài)加密算法, 不需要DSPR 假設(shè); 而本方案是多密鑰場景下的基于NTRU 的同態(tài)加密方案, 無法避免DSPR假設(shè).

下面我們將與經(jīng)典的多密鑰同態(tài)加密方案進(jìn)行對比.

5.1 與LTV12 方案的比較

本方案與LTV12 方案都是基于NTRU 的MKFHE 方案, 既有共同點(diǎn)也有不同點(diǎn). 兩個(gè)方案在噪聲增長、可同態(tài)運(yùn)行的電路深度等方面有著類似的結(jié)論, 但是二者是利用不同的技術(shù)達(dá)成的. LTV12 方案利用relinearization 技術(shù)消除了聯(lián)合私鑰中的平方項(xiàng), 同時(shí)也實(shí)現(xiàn)了key switching 的功能; 又使用了modulus switching 技術(shù), 將NTRU 方案轉(zhuǎn)化為一個(gè)leveled MKFHE 方案. 這兩項(xiàng)技術(shù)的使用使得LTV12 方案必須在生成公私鑰的同時(shí)生成運(yùn)算密鑰, 并且在進(jìn)行每一次同態(tài)運(yùn)算(加法或乘法) 時(shí)都需要執(zhí)行relinearization 操作, 每一層同態(tài)運(yùn)算后都要進(jìn)行modulus switching, 才能使得方案成為一個(gè)leveled MKFHE 方案. 而本方案使用了工具向量和比特分解技術(shù), 使得實(shí)現(xiàn)同態(tài)運(yùn)算所需的操作變得非常簡單,不需要額外的技術(shù),并且直接將NTRU 方案轉(zhuǎn)化為一個(gè)leveled MKFHE 方案. 另外,實(shí)現(xiàn)本方案的同態(tài)運(yùn)算過程僅需要普通的多項(xiàng)式加法和乘法, 以及一個(gè)將多項(xiàng)式分解的g-1(·) 函數(shù). 相較于LTV12方案, 本方案更易于理解和代碼實(shí)現(xiàn).

表1 中列出了本方案與LTV12 方案的一些基本參數(shù)之間的對比, 其中n 表示分圓多項(xiàng)式的次數(shù), q表示模數(shù). 從表1 中可以看到, 我們的方案不需要運(yùn)算密鑰, 而LTV12 方案需要尺寸為O(n log3q) 的運(yùn)算密鑰. 雖然本方案在同態(tài)運(yùn)算過程中的密文的尺寸是大于LTV12 方案的(表1 中密文尺寸一行), 但是運(yùn)算后得到的最終密文(解密時(shí)所需的密文) 的尺寸與LTV12 方案相同(表1 中最終密文尺寸一行).

表1 與LTV12 方案的基本性質(zhì)的比較Table 1 Comparisons of basic properties with LTV12 scheme

下面我們將對比本方案與LTV12 方案在云計(jì)算場景下, 用戶端和云端分別所需執(zhí)行的操作. 將同態(tài)加密算法應(yīng)用于云計(jì)算場景時(shí), 用戶端需要執(zhí)行的主要操作是生成密鑰和同態(tài)計(jì)算所需的參數(shù)(即運(yùn)行KeyGen算法), 加密(Enc) 和解密(Dec); 云端進(jìn)行的操作則是對用戶上傳的密文進(jìn)行同態(tài)運(yùn)算. 我們對兩個(gè)方案在用戶端所需的操作進(jìn)行比較, 因?yàn)樵谠朴?jì)算場景中, 我們希望用戶端的開銷能夠盡可能地降低. 比較結(jié)果如表2 所示.

我們將表2 中所列出的密鑰生成和加密兩個(gè)過程中用戶端所做的操作綜合起來進(jìn)行對比: 若加密1 比特, 本方案中用戶端所需的全部操作是隨機(jī)生成2 個(gè)多項(xiàng)式, 進(jìn)行l(wèi)og q 次多項(xiàng)式乘法和2 log q 次多項(xiàng)式加法; LTV12 方案中用戶端所需的全部操作是隨機(jī)生成2(log2q+log q) 個(gè)多項(xiàng)式, 進(jìn)行6 log2q+1 次多項(xiàng)式乘法和8 log2q+2 次多項(xiàng)式加法. 由此可見, 當(dāng)加密少量比特(例如對稱加密算法的密鑰) 時(shí), 使用本方案在用戶端的計(jì)算開銷相對較低, 更符合云計(jì)算場景下用戶的計(jì)算能力有限的特點(diǎn).

表2 與LTV12 方案的基本操作的比較Table 2 Comparisons of basic operations with LTV12 scheme

5.2 與BP16、PS16 和CZW17 方案的比較

表3 中bootstrapping 一行表示, 每進(jìn)行一次(門電路) 運(yùn)算, 是否需要執(zhí)行bootstrapping. PS16 方案中, 每執(zhí)行一次與非門(NAND) 都要運(yùn)行一次bootstrapping, 而其他方案并不需要. 從表3 中可以看出CZW17 方案需要生成evaluation key, 因而用戶端的開銷相對較大. PS16 中的兩個(gè)方案雖然不需要evaluation key, 但是需要生成額外的密文或公共參數(shù), 以保證多密鑰同態(tài)運(yùn)算能夠正常進(jìn)行. BP16 方案是當(dāng)前理論上效果最佳的MKFHE 方案, 但是從表3 中可知, BP16 方案也需要生成evaluation key, 給用戶端帶來額外負(fù)擔(dān). 除此之外, 在BP16 方案中每執(zhí)行一次NAND 運(yùn)算, 都需要運(yùn)行一次bootstrapping, 不易于代碼實(shí)現(xiàn); 而上文也提到過本方案的同態(tài)運(yùn)算過程僅需要實(shí)現(xiàn)簡單的多項(xiàng)式間的運(yùn)算. 相較于BP16 方案, 本方案的同態(tài)運(yùn)算過程更易于理解和代碼實(shí)現(xiàn).

表3 與其他MKFHE 方案的比較Table 3 Comparisons with other MKFHE schemes

6 總結(jié)

本文提出了一種NTRU 型的多密鑰同態(tài)加密方案. 我們利用工具向量及相應(yīng)的分解函數(shù)將NTRU方案轉(zhuǎn)化為一個(gè)leveled MKFHE 方案, 并可以利用Gentry 的bootstrapping 定理將leveled FHE 方案轉(zhuǎn)化為完全的FHE 方案. 由于使用了工具向量及分解函數(shù), 我們的方案不需要使用relinearization 技術(shù),從而不需要生成evaluation key. 與此同時(shí), 本方案也不需要進(jìn)行密文擴(kuò)張以及生成額外的公共參數(shù). 相比于已有的MKFHE 方案, 我們的方案更加簡潔、易于實(shí)現(xiàn), 并且在云計(jì)算環(huán)境下用戶端的開銷相對較小. 另外, 本方案支持加密環(huán)中的元素而不僅是1 比特, 因而也支持多密鑰場景下的批處理同態(tài)運(yùn)算. 本方案的安全性基于RLWE 問題和DSPR 假設(shè), 而DSPR 假設(shè)并不是一個(gè)標(biāo)準(zhǔn)的密碼學(xué)假設(shè). 盡管到目前為止沒有高效的方法去破解小模數(shù)情形的DSPR 假設(shè), 我們?nèi)钥梢哉J(rèn)為DSPR 假設(shè)是安全的, 但是這個(gè)安全隱患需要引起關(guān)注. 當(dāng)前, 基于NTRU 的MKFHE 方案無法避免DSPR 假設(shè), 這是由解密時(shí)需要所有參與方的私鑰相乘所造成的固有缺陷. 因此如何構(gòu)造安全性只依賴于RLWE 問題的NTRU 型多密鑰同態(tài)加密方案仍有待進(jìn)一步研究.