車小亮,周昊楠,周潭平,,李寧波,楊曉元,
(1.武警工程大學密碼工程學院,西安 710086;2.網(wǎng)絡與信息安全武警部隊重點實驗室,西安 710086)
(*通信作者電子郵箱smo_mrche@yeah.net)
多密鑰全同態(tài)加密(Multi-Key Fully Homomorphic Encryption,MKFHE)方案支持對不同用戶的密文進行任意的同態(tài)運算,且運算之后的結(jié)果必須由參與計算的所有用戶聯(lián)合解密,可以較好地解決多用戶密文進行同態(tài)計算的問題[1-2]。基于NTRU(Number Theory Research Unit)的多密鑰全同態(tài)加密方案是基于多項式的加解密運算,密文和密鑰量小,加解密結(jié)構簡單,是公認的基于格的運算速度較快的加密方案之一,具有較強的實用性。
NTRU 型MKFHE 最初是由López-Alt 等[3]提出的,被稱為LTV12(López-alt-Tromer-Vaikuntanathan)方案,其安全性基于2 的冪次多項式環(huán)上的LWE(Learning With Errors)問題[4]和DSPR(Decisional Small Polynomial Ratio)假設問題[3]。DSPR假設是非標準性假設,Stehlé 等[5]已經(jīng)證明了在特定條件下DSPR 假設可以規(guī)約到RLWE(Ring Learning With Errors)困難問題。但2 的冪次分圓多項式環(huán)無法抵御子域攻擊[6-7],且可選環(huán)較少,致使NTRU 型同態(tài)加密方案的安全基礎受到了威脅。2017 年,Yu 等[8]提出基于素數(shù)次分圓多項式環(huán)上的NTRU 方案,該類環(huán)可有效應對子域攻擊威脅,但參數(shù)選取較大;同年,Yu等[9]又相繼提出了基于素數(shù)冪次分圓多項式環(huán)的NTRU 方案,該類環(huán)能有效抵御子域攻擊的同時,使得密文密鑰等參數(shù)尺寸與2 的冪次分圓多項式環(huán)上參數(shù)尺寸選取在同一量級,且可選環(huán)較多。本文研究NTRU 型多密鑰加密方案的解密結(jié)構的安全基礎即是基于素數(shù)冪次分圓多項式環(huán)上的困難問題。
另外,LTV12方案在進行解密運算時運算復雜度高,產(chǎn)生的噪聲大,計算效率具有很大提升空間。主要是因為NTRU型多密鑰加密方案的原始解密結(jié)構在進行一次同態(tài)運算時,需要頻繁使用密鑰交換技術[10],會使產(chǎn)生的噪聲呈指數(shù)級增長。所以在實現(xiàn)全同態(tài)運算時,必須使用模交換技術[10]以控制噪聲的增長。Dor?z 等[11]通過優(yōu)化參數(shù)提高了LTV12 方案的效率,但其同態(tài)解密結(jié)構沒有改變;Bos 等[12]改進了NTRU方案的解密結(jié)構,使產(chǎn)生的噪聲降低;陳智罡[13]和李子臣等[14]通過擴展密文向量改進了NTRU 方案的解密結(jié)構,消除了密鑰交換過程,這些改進均是針對NTRU 型單密鑰同態(tài)加密方案。對于NTRU 型多密鑰同態(tài)加密方案,受參與用戶數(shù)量影響,使得參數(shù)選取更加復雜,產(chǎn)生的噪聲更大。為了提高NTRU型多密鑰同態(tài)加密方案性能,本文研究了NTRU多密鑰同態(tài)加密方案的解密結(jié)構,提出了兩種優(yōu)化改進的解密結(jié)構形式,并對三種解密結(jié)構的性能參數(shù)進行了對比分析。
本文用λ表示安全參數(shù),negl(λ)表示一個可忽略的函數(shù)。a表示向量,A表示矩陣,ai表示向量a中的第i個元素。v?表示向量v,w∈Rm的內(nèi)積。對于向量的長度,一般用范數(shù)(Euclidean norm)度量。例如l1范數(shù),定義為||v||1= |v1|+ |v2|+ …+ |vm|;無窮范數(shù)l∞定義為||v||∞= max{|v1|,|v2|,…,|vm|}。
高斯分布[15]對于任意的σ>0,定義Rn上的高斯函數(shù)為:?x∈Rn,ρσ(x)= exp(-π||x||2/σ2);ψσ表示R上的高斯分布:ψσ=ρσ(x)/σ,x∈R;Rn上的球形高斯分布(spherical Gaussian distribution)表示為ψnσ,即對于(v1,v2,…,vn)∈Rn中的任意vi分別服從高斯分布ψσ。
正則嵌入下的離散高斯分布[9]設P(x)∈Z[x]是首一的n階不可約多項式,。P(x)在復數(shù)域下的根為w1,w2,…,wn。正則變換矩陣為:(其中0 ≤i≤n- 1,1 ≤j≤n)。設t=tn-1xn-1+tn-2xn-2+…+t0∈R,系數(shù)嵌入表示為(tn-1,tn-2,…,t0),正則嵌入變換表示為σ(t)=(tn-1,tn-2,…,t0)V。正則嵌入下的離散高斯分布t←DZn,σ:σ(t) ←ψnσ,t=σ-1(t)=σ(t)?V-1,DZn,σ(x)=ρσ(x)/ρσ(Zn)。
素數(shù)冪次分圓多項式環(huán)[9]對于n=dν-1,d為素數(shù),則Φn(X)=Φd(Xdν-1),則環(huán)R=Z[X]/Φn(X)和Rq=R/qR即為素數(shù)冪次分圓多項式環(huán)。因此在環(huán)Rq=R/qR上的加法和乘法運算是按系數(shù)逐個進行的,且系數(shù)取值區(qū)間為[-q/2,q/2)(q不等于2)。令χ是環(huán)R上的錯誤分布,設χ的界是B,則χ中多項式的系數(shù)均在[-B,B]區(qū)間,即a←χ,則。
下面給出素數(shù)次分圓多項式環(huán)上噪聲增長特性,并討論最壞情況下噪聲增長的規(guī)律。
引理1[9]令n=dν-1,d為素數(shù),其中Φn(X)=Φd(Xdν-1),環(huán)R=Z[X]/Φn(X),對于任意a,b∈R,最壞情況下,則有||ab||∞≤2φ(n)||a||∞||b||∞,這里φ(n)是關于參數(shù)n的變量。
由引理1容易得到如下推論。
推論1令χ是環(huán)R上的界為B的離散高斯分布,對于a,b∈χ,考慮最壞情況,則||ab||∞≤2φ(n)B2,特殊地,當b的界是1時,||ab||∞≤2φ(n)B。
推論2令n=dν-1,d為素數(shù),環(huán)R=Z[X]/Φn(X),其中Φn(X)=Φd(Xdν-1)。χ是環(huán)R上的錯誤分布,設χ的界是B,λ是安全參數(shù),模q是素數(shù)。令s1,s2,…,sk←χ,則:
定義1RLWEΦ,q,d,χ問題(基于素數(shù)冪次分圓多項式環(huán)的LWE 問題):令n=dν-1,d為素數(shù),Φn(X)=Φd(Xdν-1)。定義多項式環(huán)R=Z[X]/Φn(X)和Rq=R/qR,以及環(huán)R上的Bbound 截斷(正則嵌入下的)離散高斯分布χ。RLWEΦ,q,d,χ假設是指區(qū)分以下兩個分布是困難的:1)元組(ai,u)在上隨機均勻分布的;2)隨機均勻選取ai,,e←χ,輸出的元組。
定義2DSPRΦ,q,d,χ假設(基于素數(shù)冪次分圓多項式環(huán)的DSPR 假設):令n=dν-1,d為素數(shù),Φn(X)=Φd(Xdν-1)。定義多項式環(huán)R=Z[X]/Φn(X)和Rq=R/qR,以及環(huán)R上的Bbound截斷(正則嵌入下的)離散高斯分布χ。DSPRΦ,q,d,χ問題是指難以區(qū)分以下兩個分布:1)多項式h= 2g/f,其中f=2f'+ 1 且在Rq上可逆,f',g←χ;2)在Rq=R/qR上隨機均勻采樣得到的多項式u。
位展開技術[16]同態(tài)加密方案中經(jīng)常用到BitDecomp(*)函數(shù)和Powersof2(*)函數(shù)進行比特位展開。令,這兩個函數(shù)簡述為:
BitD(x∈Rq):Rq→。 對于多項式x∈Rq,輸 出x?(x0,x1,…,xl-1)∈;
Pof2(y∈Rq):Rq?。 對于多項式y(tǒng)∈Rq,輸 出y?(y,2y,…,2l-1y)。
對于多項式x,y∈Rq,容易驗證:。
密鑰轉(zhuǎn)換技術(key-switching)[10]就是將密鑰f轉(zhuǎn)換成密鑰fevk,將對應的密文由c∈Rq(對應解密密鑰為f)轉(zhuǎn)換成為想要的密文形式cevk∈Rq(對應解密密鑰為fevk)。對本文來說,令。則:
1)Key SwitchGen(f∈R,fevk∈Rq):給定h∈Rq,sτ,eτ←χl。輸出計算密鑰:
2)Key Switch(c,γτ,q):計算,輸出:cevk=。
基于素數(shù)冪次分圓多項式環(huán)上的LWE 問題和DSPR 假設,可有效抵御子域攻擊。本文對NTRU 型多密鑰同態(tài)加密方案的解密結(jié)構研究與分析基于素數(shù)冪次分圓多項式環(huán)上。本章首先給出了基于素數(shù)冪次分圓多項式環(huán)上的NTRU 多密鑰同態(tài)加密方案模型,研究分析其原始的解密結(jié)構特性,而后改進設計了兩種解密結(jié)構,最后對其性能及參數(shù)進行對比分析。
令n=dν-1,d為素數(shù),Φn(X)=Φd(Xdν-1),多項式環(huán)R=Z(x)/Φn(X)和Rq=R/qR。設在R上的錯誤分布χ的界為B=B(λ),則錯誤分布空間的界亦為B。令K1,K2為兩個N個用戶的公鑰集合,不失一般性,設K1∩K2=,K1∪K2={pk1,pk2, …,pkr}, 這 里j∈[0,N],r∈[N,2N]?;谒財?shù)冪次分圓多項式環(huán)上的NTRU型多密鑰同態(tài)加密方案描述如下。
根據(jù)LTV12 方案[3]的分析可知,加法同態(tài)運算產(chǎn)生的噪聲遠小于乘法同態(tài)運算,所以只要乘法同態(tài)運算滿足全同態(tài)運算,則方案是全同態(tài)方案。此原始方案的同態(tài)乘法解密結(jié)構的性能直接影響設計方案的效率問題。下面詳細分析該方案中的解密結(jié)構性能及參數(shù),并討論影響方案效率的因素。
2.2.1 設定條件
對于t∈[1,j],聯(lián)合解密私鑰為Ft=Ft-1(ft)-1,其中F0=。
2.2.2 解密結(jié)構
利用聯(lián)合解密私鑰解密時,要先進行密鑰交換將密文乘積線性化,經(jīng)過一次密鑰交換后可得:
由式(1)可知,經(jīng)過j次密鑰交換循環(huán),可得
利用聯(lián)合解密私鑰Fj進行解密,可得:
式(2)即為LTV12的原始解密結(jié)構形式,完成正確解密的條件是式(2)中Error是2的倍數(shù),且。由式(2)可以看出,密鑰交換的作用是線性化密文乘積,形式上是建立了與的等式關系,本質(zhì)上還是利用NTRU 型同態(tài)加密方案最初的解密結(jié)構形式。 設,則可得:
2.2.3 噪聲分析
設聯(lián)合解密產(chǎn)生的噪聲參數(shù)為δ,一個新鮮密文解密產(chǎn)生的噪聲參數(shù)為δ0。對于,設||ciFKi||∞≤δ。假設最壞情況下得到聯(lián)合密文ci,即ci是集合Ki中N個用戶的新鮮密文的乘積。設一個新鮮密文解密產(chǎn)生的噪聲為,根據(jù)引理1 和推論1,容易得到δ0=(2B+ 1)+ 3φ(n)(2B+ 1)2,所以根據(jù)推論2可得δ≤2N-1φ(n)N-1(δ0)N,為了方便計算,令EN≤2N-1φ(n)N-1(2B+1)N。
由式(2)可以得到原始解密結(jié)構產(chǎn)生的解密噪聲為:
所以由式(4)進一步可知,產(chǎn)生的噪聲為:
取式(5)中的系數(shù)最大項,則此結(jié)構產(chǎn)生的噪聲量級為Θ(32NE4N)。
2.2.4 性能及參數(shù)分析
式(3)稱為NTRU 型同態(tài)方案的解密結(jié)構。受限于這種解密結(jié)構,同態(tài)乘法解密時需要用密鑰交換技術來將密文乘積的重復部分線性化,最終約減為如式(2)的樣式。其實是用計算密鑰替換了重復的聯(lián)合解密私鑰部分,這樣會導致噪聲增長較快。由式(4)可知由密鑰交換而產(chǎn)生的噪聲增大了。
①安全性:該結(jié)構是基于素數(shù)冪次分圓多項式環(huán)上設計的,可有效抵抗子域攻擊,其安全性基于RLWEΦ,q,d,χ問題和DSPRΦ,q,d,χ假設。
②參數(shù)選取:該結(jié)構的密文是2 個次數(shù)小于dν-1的多項式,其尺寸最大為2φ(n)logq;加密使用的公鑰是2N個次數(shù)小于dν-1的多項式,所以公鑰尺寸為2Nφ(n)logq;解密時用到r個次數(shù)小于dν-1的且系數(shù)小于(2B+ 1)多項式私鑰,故其私鑰尺寸大小為rφ(n)log(2B+ 1);每進行一次同態(tài)運算,要進行j次密鑰交換,所以使用的計算密鑰的尺寸為。由文獻[11]知,素數(shù)冪次分圓多項式環(huán)與2的冪次分圓多項式環(huán)上的參數(shù)選取在同一量級,所以該解密結(jié)構參數(shù)尺寸與原始解密結(jié)構中參數(shù)尺寸的選取在同一量級。
③同態(tài)解密運算時間:為了方便運算效率的評比,文章模擬了實驗消耗時間。忽略多項式不同系數(shù)([-q/2,q/2)內(nèi)的實數(shù))乘法耗時的差異性,定義兩多項式完成一次乘法運算用時為Tmult,BitDecomp(*)函數(shù)進行一次多項式分解用時為TBD,完成個多項式求和運算用時為TA。以完成一次同態(tài)乘法解密為例,在不做任何模q和模2 處理的情況下,原始解密結(jié)構完成解密運算用時為:
即Tmult前的系數(shù)為多項式運算次數(shù),TBD前的系數(shù)為進行BitDecomp(*)分解次數(shù),TA前的系數(shù)為多項式求和次數(shù)。
根據(jù)2.2節(jié)分析可知,影響NTRU型多密鑰同態(tài)加密方案效率主要有兩個方面:一是受原始同態(tài)乘法解密結(jié)構的限制和參與運算的用戶數(shù)量影響,使得方案產(chǎn)生的噪聲較大;二是受密鑰交換次數(shù)j的影響,使得運算復雜性增大,運算時間較大。目前還沒有很好的辦法消除多密鑰同態(tài)方案中用戶N對產(chǎn)生噪聲的影響,但可以通過改進NTRU 型多密鑰同態(tài)加密方案中原始的解密結(jié)構,降低噪聲,減少或消除密鑰交換次數(shù),以提高方案效率。
2.3.1 “Regev-Style”解密結(jié)構
文獻[12]中對NTRU 型單密鑰同態(tài)加密方案的解密結(jié)構進行了改進,即采用“Regev-Style”加解密模式[17-18],降低多項式的系數(shù),減小噪聲的產(chǎn)生。本節(jié)將此方法進行改進,并應用到多密鑰同態(tài)加密方案中。
1)設定條件。
對于明文m∈{0,1},加密可得,對于聯(lián)合密文c,解密形式為:(2/q)FKc=m+Error,即得m=;計算密鑰為:;對于給定的兩個多項式聯(lián)合密文c1和c2對應的加密公鑰集合分別為K1,K2。令。
2)解密結(jié)構。
同態(tài)解密時,同樣需要循環(huán)進行密鑰交換,即同式(2),可得:
如式(7)所示,“Regev-Style”解密結(jié)構改變了初始解密結(jié)構的形式,運算,即可以恢復明文。
3)噪聲分析。
設此情況聯(lián)合解密產(chǎn)生的噪聲參數(shù)為β,一個新鮮密文解密產(chǎn)生的噪聲參數(shù)為β0。對聯(lián)合密文c1和c2,令||(2/q)ciFKi||∞≤β,則最壞情況下,可得新鮮密文解密產(chǎn)生的噪聲為β0≤(2B+ 1)+(4φ(n)/q)(2B+ 1)2,同原始解密結(jié)構,可得一個聯(lián)合密文解密后產(chǎn)生的噪聲為:
所以根據(jù)式(6)可得“Regev-Style”解密結(jié)構產(chǎn)生的噪聲為:
由式(8)進一步可得,產(chǎn)生的噪聲為:
由式(9)知,參數(shù)q?B,q?φ(n),當受用戶數(shù)量N影響較大時,可得(1+(4φ(n)/q)(2B+ 1))2N≤22N,則“Regev-Style”解密結(jié)構產(chǎn)生的噪聲的量級為Θ(22NE2N)。
4)性能及參數(shù)分析。
“Regev-Style”解密結(jié)構在解密時要降低多項式系數(shù),噪聲較原始解密結(jié)構呈指數(shù)級降低。缺點是:仍沒有消除密鑰交換過程,且每進行一次解密運算,均要進行多項式系數(shù)的降低處理,使得運算復雜度增大。但由于每次的多項式降系數(shù)處理,大幅度降低了噪聲,用于設計全同態(tài)方案時,可以減少密鑰交換和模交換的使用次數(shù),以提高效率。
①安全性?!癛egev-Style”解密結(jié)構亦是基于素數(shù)冪次分圓多項式環(huán)上設計的,其可有效抵御子域攻擊。另外,“Regev-Style”解密結(jié)構應用于NTRU 型單密鑰同態(tài)加密方案中時,由于多項式系數(shù)較小,選取的參數(shù)滿足SS11[6]中對于DSPR 假設規(guī)約到RLWE 的條件,因此其安全性只基于RLWE問題。而應用于素數(shù)冪次多項式環(huán)上的多密鑰同態(tài)加密方案中,受用戶數(shù)量N的影響,使得DSPR 假設到RLWE 問題的規(guī)約條件不適用于多密鑰同態(tài)加密方案中。但在RLWEΦ,q,d,χ問題和DSPRΦ,q,d,χ假設成立條件下,“Regev-Style”解密結(jié)構是安全的,且能抵御更多的子域攻擊。
②參數(shù)選取?!癛egev-Style”解密結(jié)構加密時先增大明文的系數(shù),即增大了多項式密文中的常系數(shù),密文仍是2 個次數(shù)小于dν-1的多項式,其尺寸最大為2φ(n)logq,同樣使用到的公鑰、解密私鑰和計算密鑰尺寸與原始方案相同。
③同態(tài)解密運算時間?!癛egev-Style”解密結(jié)構在完成一次密文與密鑰相乘后,均要進行多項式系數(shù)的降低處理,設對多項式降系數(shù)處理用時為Δt。其他運算消耗的時間設定與原始解密結(jié)構相同,則“Regev-Style”解密結(jié)構完成一次同態(tài)解密用時為:
相對于原始解密結(jié)構,由于每次解密均要做多項式降系數(shù)處理,所以運算時間增加了(2+r)Δt。
2.3.2 “Ciphertext-Expansion”解密結(jié)構
文獻[13-14]通過擴展密文向量完成對解密結(jié)構的改進,本節(jié)對其設定條件進行改進,并應用到NTRU 型多密鑰同態(tài)加密方案中,可消除NTRU 型多密鑰同態(tài)加密方案中的密鑰交換過程。
1)設定條件。
2)解密結(jié)構。
對于給定的兩個聯(lián)合多項式密文向量c1和c2對應的公鑰集合分別為K1,K2,令K=K1?K2。
同態(tài)解密時,先進行密文變換,可得:
取式(10)的第一項進行(mod 2) 運算,可得m1m2=。當時,完成正確解密。
3)噪聲分析。
設此情況聯(lián)合解密產(chǎn)生的噪聲參數(shù)為η,一個新鮮密文解密產(chǎn)生的噪聲參數(shù)為η0。對聯(lián)合多項式密文向量ci,有。易得新鮮多項式密文向量解密時產(chǎn)生的噪聲中η0≤3φ(n)(2B+1)2,同理原始解密結(jié)構,最壞情況下,可得一個聯(lián)合多項式密文向量解密后產(chǎn)生的噪聲為:
由式(10)可得,“Ciphertext-Expansion”解密結(jié)構產(chǎn)生的噪聲為:
4)性能及參數(shù)分析。
“Ciphertext-Expansion”解密結(jié)構通過密文擴展,使加解密在多項式向量下完成運算。該方法消除了密鑰交換過程,使得產(chǎn)生的噪聲較小,缺點是密文空間增大了。
①安全性?!癈iphertext-Expansion”解密結(jié)構是用Powersof2(*)將密文變換為向量形式,計算過程使用BitDecomp(*)函數(shù)進行多項式向量的轉(zhuǎn)換。根據(jù)文獻[3,16]可知,函數(shù)BitDecomp(*)和Powersof2(*)對安全性沒有影響。所以“Ciphertext-Expansion”解密結(jié)構的安全性與原始解密結(jié)構和“Regev-Style”解密結(jié)構相同,安全性是基于RLWEΦ,q,d,χ問題和DSPRΦ,q,d,χ假設,可抵御更多的子域攻擊。
③同態(tài)解密運算時間。假設運算消耗的時間設定與原始解密結(jié)構相同。由于“Ciphertext-Expansion”解密結(jié)構輸入的是兩個維的多項式密文向量,解密時只取密文向量的第一項進行求和運算。所以完成一次同態(tài)解密運算用時為:
與原始解密結(jié)構運算時間進行差運算:
參數(shù)Tmult、TBD和TA的大小關系受參數(shù)q和n的影響,通過選取合適參數(shù)的j,q和n,可使ΔT>0。
綜合分析上述三種解密結(jié)構,以完成一次同態(tài)乘法運算為例,給出原始解密結(jié)構、“Regev-Style”解密結(jié)構和“Ciphertext-Expansion”解密結(jié)構性能及所有參數(shù)尺寸對比,具體如表1、2。
表1 3種解密結(jié)構的性能對比Tab.1 Performance comparison of three decryption structures
如表2 所示,與原始解密結(jié)構相比,“Regev-Style”解密結(jié)構產(chǎn)生的噪聲呈指數(shù)級降低,但由于每次解密運算要進行多項式降系數(shù)處理,使得運算時間增大。同樣與原始解密結(jié)構相比,“Ciphertext-Expansion”解密結(jié)構產(chǎn)生的噪聲呈指數(shù)級降低,且當兩個公鑰集合K1、K2的交集個數(shù)j越大,噪聲值就越?。涣硗?,“Ciphertext-Expansion”解密結(jié)構無需進行密鑰交換,雖然密文尺寸增加了,但設計全同態(tài)方案時,可以通過選取合適的參數(shù),使ΔT>0,減少運算時間,提高效率。
表2 3種解密結(jié)構的參數(shù)對比Tab.2 Parameters comparison of three decryption structures
NTRU 型多密鑰同態(tài)加密方案的解密結(jié)構影響方案的效率,本文對原始的多密鑰同態(tài)解密結(jié)構進行了分析,優(yōu)化改進了兩種多密鑰解密結(jié)構,并對其參數(shù)性能進行了分析,為設計NTRU 型MKFHE 方案提供了解密結(jié)構基礎。通過分析,“Regev-Style”解密結(jié)構產(chǎn)生的噪聲較小,雖然運算復雜度增大了,但應用于多密鑰全同態(tài)加密方案中,通過控制多項式系數(shù),可以減少密鑰交換和模交換的使用次數(shù)?!癈iphertext-Expansion”解密結(jié)構無需使用密鑰交換技術,產(chǎn)生的噪聲較小,適用于設計參與計算的用戶重復較多的全同態(tài)加密方案,并可通過控制參數(shù)選取以提高方案運算效率。