基于謂詞的Paillier型密文解密外包方案

張 薇， 白 平， 李鎮(zhèn)林， 李 聰

(1.武警工程大學(xué) 密碼工程學(xué)院 陜西 西安 710086； 2.武警工程大學(xué) 信息安全保密重點(diǎn)實(shí)驗(yàn)室 陜西 西安 710086)

0 引言

隨著云計算技術(shù)(cloud computing)[1]的快速發(fā)展和逐步完善，越來越多的用戶傾向于將復(fù)雜的計算資源、存儲資源外包給“云端”，從而極大地減輕了用戶的負(fù)擔(dān).然而 “云端”并不是完全可信的，人們在享受“云端”所帶來便利的同時，對于數(shù)據(jù)的訪問控制也進(jìn)行了各種嘗試，從不同角度對數(shù)據(jù)訪問控制權(quán)限進(jìn)行研究[2-4].然而，將同態(tài)加密與謂詞相聯(lián)系的研究卻很少.試想如果用戶將明文數(shù)據(jù)直接交由“云端”處理，無疑會增加數(shù)據(jù)的安全隱患.為了防止“云端”的惡意篡改和非法用戶訪問敏感數(shù)據(jù)，用戶不僅需要對敏感數(shù)據(jù)進(jìn)行加密，更重要的是要設(shè)置必要的訪問控制策略.在傳統(tǒng)的云計算加解密模型中，無法實(shí)現(xiàn)對計算結(jié)果的訪問控制.在公鑰密碼體制中，用戶的身份是由數(shù)字證書來確認(rèn)的，但證書的使用無疑會增加系統(tǒng)的開銷，這將無法體現(xiàn)出云的優(yōu)勢.文獻(xiàn)[5]提出了謂詞加密(predicate encryption，PE)，因其能夠?qū)崿F(xiàn)對密文更加精細(xì)、靈活的訪問控制而備受關(guān)注.

方案以類同態(tài)Paillier方案[11]為基礎(chǔ)，結(jié)合經(jīng)典文獻(xiàn)[12]提出的KP-ABE(key-policy ABE)型密文解密外包設(shè)計思想，構(gòu)造了一個基于謂詞的Paillier型密文解密外包方案.相比文獻(xiàn)[12]，該方案在解密時間上有所增長，但是對密文的訪問控制卻優(yōu)于文獻(xiàn)[12]，增強(qiáng)了用戶數(shù)據(jù)的安全性，從而在一定程度上減小了數(shù)據(jù)泄露的概率，方案還可以抵抗任何惡意云服務(wù)器的攻擊.在方案構(gòu)造中，部分密文的解密被外包到云上進(jìn)行，減小了用戶的計算量，更為重要的是對密文的訪問控制策略被隱藏在密文當(dāng)中，所以要想完成對密文的正常解密，要求用戶屬性必須滿足密文策略，實(shí)現(xiàn)了用戶對外包計算結(jié)果的有效控制.此外，方案對密文可以進(jìn)行任意次加法同態(tài)操作和一次乘法同態(tài)操作.同態(tài)加密可以允許用戶在不知道明文的情況下對密文進(jìn)行操作，從而很大程度上方便了用戶.隨著同態(tài)加密受到越來越多的關(guān)注，涌現(xiàn)出了許多同態(tài)加密的研究成果[13-14].

1 預(yù)備知識

1.1 雙線性映射

G，GT是兩個階為p的循環(huán)群，g為生成元，則雙線性映射[15]e:G×G→GT滿足下列性質(zhì)：

1) 雙線性.對任意r,s∈G和a,b∈Zp，都有e(ra,sb)=e(r,s)ab.

2) 非退化性.存在r,s∈G，使得e(r,s)≠1.

3) 可計算性.存在有效的多項式算法對任意r,s∈GT，都可以計算出e(r,s).

1.2 訪問結(jié)構(gòu)

定義P={P1,P2,…,Pn}是秘密共享的參與者集合.訪問結(jié)構(gòu)AS是2p上的一個非空子集，即AS?2p{?}.訪問結(jié)構(gòu)單調(diào)性定義如下：?A,B，如果A∈AS且A?B，則B∈AS.同時，對于能重構(gòu)出共享秘密的子集稱為授權(quán)集合；反之，則稱為非授權(quán)集合.

1.3 LSSS矩陣訪問結(jié)構(gòu)

定義在秘密共享參與者集合P上的線性秘密共享機(jī)制[15](linear secret sharing scheme，LSSS)是指：

1) 所有參與者的共享組成一個Zp上的向量.

2) 存在一個l×n的矩陣M，它是一個關(guān)于的共享生成矩陣.M的第i行標(biāo)記成ρ(i)，其中i=1,2,…,l，ρ是從{1,2,…,l}到P的映射函數(shù).隨機(jī)選擇列向量其中s是共享秘密，那么M·v就是利用得到的關(guān)于s的l個共享組成的向量，并且(M·v)i對應(yīng)于ρ(i).

1.4 Paillier方案

Paillier公鑰密碼[11]是由Paillier在1999年提出的一種基于高次剩余類問題的加密體制，該體制具有同態(tài)的優(yōu)良性質(zhì)，其良好的同態(tài)性質(zhì)可以用于構(gòu)造很多實(shí)用且高效的密碼算法.方案的具體描述如下：

解密算法.解密者收到密文c后，使用私鑰sk可計算出明文m=L(cnmodn2)·φmodn.具體解密過程為

Paillier方案同態(tài)性質(zhì)分析.

1) 加法同態(tài)：

2) 乘法同態(tài)：

1.5 安全模型

方案的安全模型引用文獻(xiàn)[6].

初始化運(yùn)用算法Γ生成公鑰參數(shù)，將其傳送給敵手B.

步驟1敵手B對多組謂詞向量v對應(yīng)的密鑰skv進(jìn)行詢問.

博弈敵手B輸出長度相同的明文消息m0和m1及其相應(yīng)的屬性x0和x1.假如步驟1中的謂詞向量v不滿足條件fv(x0)=1,fv(x1)=1，則挑戰(zhàn)者C用屬性xb隨機(jī)加密明文mb，其中b∈{0,1}.然后將對應(yīng)的加密密文c*發(fā)送給敵手B.

步驟2敵手B按照步驟1的方式不斷詢問直到謂詞向量v滿足條件fv(x0)=1,fv(x1)=1.

猜想敵手B輸出b′，如果b′=b，則攻擊成功.

定義1當(dāng)敵手B在上述交互過程中的優(yōu)勢是可以忽略的，方案是IND-AH-CPA安全的.

Payload-hiding安全只能保護(hù)明文信息不被竊取，對于其他相關(guān)信息是做不到隱私保護(hù)的.這在一些保密要求高的應(yīng)用場合(如屬性信息也要求保密)是不適用的.該方案可以達(dá)到attribute-hiding安全：可以將明文信息和屬性信息同時混淆在加密密文中而不被泄露.相比而言，attribute-hiding在安全性和適用范圍上要比payload-hiding有更廣泛前景.

1.6 安全假設(shè)

方案的安全性假設(shè)借鑒了文獻(xiàn)[16]中基于雙線性映射子群判定問題的擴(kuò)展.

輸入生成元g和安全參數(shù)1λ，輸出元組(N=p1p2p3,G,GT,e)，其中p1,p2,p3是互不相同的素數(shù).G和GT均是階為N的循環(huán)群，定義Gp1,Gp2,Gp3是G的子群.隨機(jī)選擇生成元q∈Gp1.為了便于說明，引入一個參數(shù)h∈Gp1，由于參數(shù)h對于挑戰(zhàn)者來說是獨(dú)立的，故參數(shù)h的引入并不會增加敵手的優(yōu)勢.

假設(shè)1根據(jù)生成元g定義：

(N=p1p2p3,G,GT,e)←g，

q,h←Gp1,X3←Gp3,

D=(G,q,h,X3),

T0←Gp1,T1←Gp1p2.

定義算法Λ能夠區(qū)分某一元素屬于Gp1或者Gp1p2的優(yōu)勢為

Adv1g,Λ(λ)=|Pr[Λ(D,T0)=0]-Pr[Λ(D,T1)=0]|.

定義2對于多項式時間算法Λ，當(dāng)Adv1g,Λ(λ)可忽略時，則滿足假設(shè)1.

假設(shè)2根據(jù)生成元g定義：

(N=p1p2p3,G,GT,e)←G,

q,h，X1←Gp1,X2,Y2←Gp2,X3，Y3←Gp3,

D=(G,q,h,X3,X1X2,Y2Y3),

T0=Gp1p3,T1←Gp1p2p3.

定義算法Λ能夠區(qū)分某一元素屬于Gp1p3或者Gp1p2p3的優(yōu)勢為

Adv2g,Λ(λ)=|Pr[Λ(D,T0)=0]-Pr[Λ(D,T1)=0]|.

定義3對于多項式時間算法Λ，當(dāng)Adv2g,Λ(λ)可忽略時，則滿足假設(shè)2.

假設(shè)3根據(jù)生成元g定義：

(N=p1p2p3,G,GT,e)←g,k∈ZN,

q,h←Gp1,X2,Y2,Z2←Gp2,X3←Gp3,

D=(G,X3,Z2,q,qkX2,hY2),

T0=e(q,h)k,T1←GT.

定義算法Λ能夠區(qū)分某一元素是T0還是屬于GT的優(yōu)勢為

Adv3g,Λ(λ)=|Pr[Λ(D,T0)=0]-Pr[Λ(D,T1)=0]|.

定義4對于多項式時間算法Λ，當(dāng)Adv3g,Λ(λ)可忽略時，則滿足假設(shè)3.

2 基于謂詞的Paillier型密文解密外包系統(tǒng)模型

在闡述方案構(gòu)造之前，首先簡要介紹有關(guān)基于謂詞的密文解密外包主要部分的工作流程模式.該方案主要涉及“云端”和用戶兩個主體.它們之間的交互過程可以分為兩步進(jìn)行.第一步，用戶給 “云端”發(fā)送一個轉(zhuǎn)換密鑰TK，主要作用是將外包給 “云端”的密文進(jìn)行必要的轉(zhuǎn)換以方便用戶的解密操作.第二步，“云端”利用用戶發(fā)送的轉(zhuǎn)換密鑰TK，將存儲在自己服務(wù)器上的密文進(jìn)行相應(yīng)的轉(zhuǎn)換，以滿足用戶需求，而后將其回傳給用戶.

1) “云端”:具有較強(qiáng)的計算和存儲能力，可以為用戶提供更為方便快捷的服務(wù)，但是云服務(wù)器是屬于完全不可信或者半可信的.所以必須對敏感數(shù)據(jù)進(jìn)行加密，并且設(shè)定必要的訪問控制權(quán)限.

2) 用戶:具有較弱的計算和存儲能力，傾向于把一些復(fù)雜的數(shù)據(jù)資源交給“云端”來處理，但希望這些數(shù)據(jù)不能被云服務(wù)器竊取或者篡改.

3 基于謂詞的Paillier型密文解密外包方案

本小節(jié)主要介紹該方案的具體實(shí)現(xiàn)過程，通過將Paillier方案與密文解密外包思想相結(jié)合，構(gòu)造了基于謂詞的Paillier型密文解密外包方案，可以實(shí)現(xiàn)對云計算結(jié)果的訪問控制.方案主要由以下5個算法構(gòu)成.

PK={g,g1=ga,e(g,g)α,{Ti=gti}i=1,…,n,F}，

主密鑰MK=(gα,PK).

(1)

最終是密文形式

C=(c,c1).

(2)

PK,K=K′1/ε=g-xi/sεgat/r,L=L′1/ε=g(t′/ε)=gt,

私鑰為SK=(ε,TK,skv).

轉(zhuǎn)換算法(TK,CT).輸入轉(zhuǎn)換密鑰TK=(PK,K,L,{Kx}x∈S)和密文CT=(C,C′,C1,…,Cl)，如果屬性S不滿足訪問結(jié)構(gòu)(M,ρ)，則輸出⊥；反之定義I={i:ρ(i)∈S}，且I?{1,2,…,l},存在常數(shù)集{ωi∈Zp}i∈I,對于{λi}中所有的值，∑i∈Iωiλi=s.運(yùn)用轉(zhuǎn)換算法計算.

(3)

算法最后輸出部分密文CT′=(C,Q).

解密算法(SK,CT).輸入私鑰SK=(ε,TK,skv)和密文CT，假如密文CT不是部分密文，則需要先運(yùn)行轉(zhuǎn)換算法(TK,CT)，將其轉(zhuǎn)換為部分密文.轉(zhuǎn)換算法(TK,CT)輸出為⊥時，則解密算法也輸出⊥.反之，利用(ε,Q)計算出Qε=e(g,g)rxi，再利用解密密鑰skv，結(jié)合Euler函數(shù)計算

L(cηmodn2)·φ·H(e(c1,di))=L((1+n)m/H(e(g,g)-rxi)·Rn)ηmodn2·η-1·

(m/H(e(g,g)-rxi))·H(e(g,g)-rxi·e(g,h)sr∑xivi).

(4)

只有當(dāng)接收方的謂詞向量滿足x·v=0 modN，才可恢復(fù)出明文消息.根據(jù)哈希函數(shù)的抗碰撞性質(zhì)，如果非法解密者不能滿足x·v=0 modN，則無法計算獲得明文.

4 方案分析

4.1 安全性分析

本方案在子群判定問題困難假設(shè)下達(dá)到了語義安全.同時，需要注意的是，密文屬性的泄露不會影響密文的安全.因?yàn)榧词构粽吣玫矫芪牡膶傩韵蛄縳，即攻擊者能夠算出e(g,g)-rxi的值，但是攻擊者得不到謂詞向量v的值，無法滿足fv(x)=1，從而不能正確解密得到明文m.另一方面，攻擊者即使同時拿到了屬性向量x和謂詞向量v，滿足fv(x)=1.但攻擊者如果得不到隨機(jī)參數(shù)ε，攻擊者也不能正常解密而得到明文m.綜上所述，只有當(dāng)攻擊者得到謂詞密鑰才能解密嵌套了屬性向量x的密文，同時得到隨機(jī)參數(shù)ε從而獲得訪問控制權(quán)限，才能真正攻擊成功.

為了證明該方案的安全性，采用文獻(xiàn)[16]的方法.證明先前定義的兩種結(jié)構(gòu).

正常密鑰能夠解密正常密文和半功能密文，同時正常密文可以由正常密鑰和半功能密鑰解密.當(dāng)使用半功能密鑰解密半功能密文時，結(jié)果的等式中多出e(g2,g2)cd∑yi·zi.只有滿足∑yi·zi=0時，半功能密鑰才能夠解密半功能密文.

基于以上分析，可以通過證明以下Game[15]的不可區(qū)分性而達(dá)到證明該方案的安全性.

Game0中密文為半功能密文，密鑰均為正常密鑰.

Gamereal實(shí)際加密環(huán)境過程中使用的均為正常密文和正常密鑰.

Gamek中前k次對半功能密鑰查詢，大于k次的均是對正常密鑰查詢.

Gamefinal中密文為半功能密文，而密鑰為半功能密鑰.

證明敵手B將(G,q,h,X3,T)作為算法初始化輸入，隨機(jī)選擇a∈ZN,ti∈ZN,i=1,…,n.公共參數(shù)和算法初始化公開參數(shù)相同.敵手B模擬Gamereal，Game0與敵手A進(jìn)行交互.

使用謂詞向量v,敵手B能夠通過主密鑰MK生成相應(yīng)的正常解密密鑰.

敵手A選擇等長的明文(m0,m1)及相應(yīng)的屬性(x0,x1)，敵手B將假設(shè)1嵌入到挑戰(zhàn)密文中，而后使用擲硬幣的方式進(jìn)行加密，生成密文形式為

證明敵手B將(q,h,X3,T,Y2Y3,X1X2)作為算法的輸入，隨機(jī)選擇a∈ZN,ti∈ZN,i=1,…,n.公共參數(shù)和引理1中公開參數(shù)相同.敵手B模擬Gamek-1，Gamek與敵手A進(jìn)行交互.

使用謂詞向量v,當(dāng)敵手B在查詢次數(shù)大于k的情況下，能夠利用MK生成正常解密密鑰，而在查詢次數(shù)小于k的情況下，則生成半功能密鑰.隨機(jī)選擇s,d∈ZN，生成的半功能解密密鑰表示為

敵手A選擇等長的明文(m0,m1)及相應(yīng)的屬性(x0,x1)，敵手B通過使用擲硬幣的方式進(jìn)行隨機(jī)加密，密文形式為

證明敵手B將(q,X3,Z2,grX2,hY2,T)作為輸入，隨機(jī)選擇a∈ZN,ti∈ZN,i=1,…,n.公共參數(shù)為PK={g,hY2,g1=ga,{Ti=gti}i=1,…,n}.參數(shù)N的分解不被A所獲知，故A無法正確區(qū)分hY2和h.敵手B模擬Gameq，Gamefinal與敵手A進(jìn)行交互.

如果T=gm/H(e(g,h)r)-m，則上述密文c*為半功能密文；如果T∈GT，則上述密文c*為隨機(jī)明文的加密的半功能密文，因此能夠模擬Gamefinal,故B能夠利用A的輸出以優(yōu)勢ε解決假設(shè)3.

定理1如果上述的3個假設(shè)均為困難問題，則該方案為IND-AH-CPA安全.

證明如果上述的假設(shè)為困難問題，則由以上的分析可知Gamefinal與實(shí)際加密環(huán)境是不可區(qū)分的.在Gamefinal中挑戰(zhàn)密文是不會泄漏關(guān)于B的任何信息.故敵手A攻擊該該方案成功的概率幾乎可以忽略不計，方案可達(dá)到IND-AH-CPA安全.

4.2 性能分析

本方案相比于文獻(xiàn)[12]中Green的方案，改進(jìn)之處是能夠支持對外包密文的同態(tài)操作，更重要的是方案的安全性并不完全取決于屬性參數(shù)，屬性參數(shù)的泄露并不會對密文造成致命的影響.這意味著即使敵手獲得了相關(guān)屬性參數(shù)而沒有掌握用戶事先隨機(jī)設(shè)定的參數(shù)時，敵手仍然是無法攻擊成功的，從而在很大程度上增強(qiáng)了用戶數(shù)據(jù)的安全性.

Green等人在文獻(xiàn)[12]中提出了基于屬性的密文解密外包思想，并構(gòu)造了一個密文策略外包方案.為了更好地展示方案的優(yōu)缺點(diǎn)，我們將在完全密文長度、完全密文解密時間、部分密文長度和部分解密時間分別與文獻(xiàn)[12]和文獻(xiàn)[17]進(jìn)行比較.表1中l(wèi)表示線性秘密共享機(jī)制LSSS中l(wèi)×n矩陣中的行數(shù)，k表示密文序列長度.P、EG分別表示在G中計算線性最大時間和求模冪運(yùn)算的最大時間，ET表示在GT中計算模的最大時間，在計算時間中忽略了起非主導(dǎo)作用操作所消耗的時間.通過分析表1可以得出如下結(jié)論：本方案在全密文長度和外包解密時間上比Green方案略長.然而，方案在訪問控制上卻可以優(yōu)于Green方案，安全性不僅僅取決于單一的屬性變量，提高了用戶數(shù)據(jù)的安全性，從而達(dá)IND-AH-CPA安全.具體的比較結(jié)果如表1所示.

表1 效率分析比較

4.3 同態(tài)性質(zhì)分析

1) 加法同態(tài)

g(m1+m2)/H(e(g,g)-rxi)(R1R2)n=E(m1+m2,PK).

如果解密者想要求出式中e(g,g)-rxi的值，則屬性必須滿足密文策略，而后通過解密算法求出m1+m2,

E(m1,PK)gm2=gm1e(g,g)-rxiRn1gm2modn2=E(m1+m2,PK).

2) 乘法同態(tài)

與加法同態(tài)類似，只有滿足密文策略的解密者才能正確解密.

5 結(jié)束語

本文通過將謂詞向量引入到類同態(tài)Parllier方案中，構(gòu)造了一個適用于云計算環(huán)境的外包方案.方案通過將謂詞向量隱藏在密文中的舉措，有效地解決了用戶對云計算結(jié)果的訪問控制問題，而且外包過程中將復(fù)雜的計算任務(wù)交由云服務(wù)器來完成，很大程度上減輕了用戶的開銷，提高了外包密文的解密效率.需要更進(jìn)一步的工作是探索密文解密外包與全同態(tài)加密方案的有機(jī)結(jié)合，構(gòu)造一個云環(huán)境下訪問控制性能更好的全同態(tài)密文解密外包方案.