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

張 薇， 白 平， 李鎮林， 李 聰

(1.武警工程大學 密碼工程學院 陜西 西安 710086； 2.武警工程大學 信息安全保密重點實驗室 陜西 西安 710086)

0 引言

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

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

1 預備知識

1.1 雙線性映射

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

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 訪問結構

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

1.3 LSSS矩陣訪問結構

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

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

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

1.4 Paillier方案

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

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

Paillier方案同態性質分析.

1) 加法同態：

2) 乘法同態：

1.5 安全模型

方案的安全模型引用文獻[6].

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

步驟1敵手B對多組謂詞向量v對應的密鑰skv進行詢問.

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

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

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

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

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

1.6 安全假設

方案的安全性假設借鑒了文獻[16]中基于雙線性映射子群判定問題的擴展.

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

假設1根據生成元g定義：

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

q,h←Gp1,X3←Gp3,

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

T0←Gp1,T1←Gp1p2.

定義算法Λ能夠區分某一元素屬于Gp1或者Gp1p2的優勢為

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

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

假設2根據生成元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.

定義算法Λ能夠區分某一元素屬于Gp1p3或者Gp1p2p3的優勢為

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

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

假設3根據生成元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.

定義算法Λ能夠區分某一元素是T0還是屬于GT的優勢為

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

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

2 基于謂詞的Paillier型密文解密外包系統模型

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

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

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

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

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

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).

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

(3)

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

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

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)

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

4 方案分析

4.1 安全性分析

本方案在子群判定問題困難假設下達到了語義安全.同時，需要注意的是，密文屬性的泄露不會影響密文的安全.因為即使攻擊者拿到密文的屬性向量x，即攻擊者能夠算出e(g,g)-rxi的值，但是攻擊者得不到謂詞向量v的值，無法滿足fv(x)=1，從而不能正確解密得到明文m.另一方面，攻擊者即使同時拿到了屬性向量x和謂詞向量v，滿足fv(x)=1.但攻擊者如果得不到隨機參數ε，攻擊者也不能正常解密而得到明文m.綜上所述，只有當攻擊者得到謂詞密鑰才能解密嵌套了屬性向量x的密文，同時得到隨機參數ε從而獲得訪問控制權限，才能真正攻擊成功.

為了證明該方案的安全性，采用文獻[16]的方法.證明先前定義的兩種結構.

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

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

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

Gamereal實際加密環境過程中使用的均為正常密文和正常密鑰.

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

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

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

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

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

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

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

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

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

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

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

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

4.2 性能分析

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

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

表1 效率分析比較

4.3 同態性質分析

1) 加法同態

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) 乘法同態

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

5 結束語

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