張 凱 魏立斐 李祥學(xué) 陳 潔 錢(qián)海峰

1(華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系 上海 200241)2(綜合業(yè)務(wù)網(wǎng)理論及關(guān)鍵技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室(西安電子科技大學(xué)) 西安 710071)3(上海海洋大學(xué)信息學(xué)院 上海 201306)4(衛(wèi)士通摩石實(shí)驗(yàn)室 北京 100070) (zhangkaiecnu@163.com)

?

具備強(qiáng)表達(dá)能力的選擇密文安全高效屬性基加密方案

張 凱1,2魏立斐3李祥學(xué)1,4陳 潔1,2錢(qián)海峰1

1(華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系 上海 200241)2(綜合業(yè)務(wù)網(wǎng)理論及關(guān)鍵技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室(西安電子科技大學(xué)) 西安 710071)3(上海海洋大學(xué)信息學(xué)院 上海 201306)4(衛(wèi)士通摩石實(shí)驗(yàn)室 北京 100070) (zhangkaiecnu@163.com)

屬性基加密(attribute-based encryption, ABE)是一種新型公鑰加密體制，它實(shí)現(xiàn)了對(duì)加密數(shù)據(jù)的細(xì)粒度訪(fǎng)問(wèn)控制.在密鑰策略屬性基加密方案(key-policy attribute-based encryption, KP-ABE)中，密文與屬性集合相關(guān)聯(lián)，密鑰則與訪(fǎng)問(wèn)控制結(jié)構(gòu)相關(guān)聯(lián).因此在大多數(shù)KP-ABE方案中，解密開(kāi)銷(xiāo)與解密算法所涉及的屬性數(shù)目成正比.結(jié)合Hohenberger和Waters提出的快速解密屬性基加密方案的思想，構(gòu)造了一個(gè)同時(shí)支持非單調(diào)訪(fǎng)問(wèn)結(jié)構(gòu)、大屬性空間的選擇屬性集合和選擇明文安全快速解密密鑰策略屬性基加密方案，并在隨機(jī)預(yù)言機(jī)模型下證明是選擇性屬性集合和選擇明文安全的；并在此基礎(chǔ)上，利用Lai等人提出的合數(shù)階上具有強(qiáng)表達(dá)能力的快速解密KP-ABE方案的思想，再結(jié)合用于給出構(gòu)造選擇密文安全的KP-ABE方案的變色龍Hash技術(shù)，構(gòu)造了一個(gè)同樣支持非單調(diào)的訪(fǎng)問(wèn)控制結(jié)構(gòu)且表達(dá)能力豐富的選擇密文安全快速解密KP-ABE方案.比較相關(guān)方案，所提出的2個(gè)方案都具備相當(dāng)?shù)慕饷苄?

屬性基加密；選擇密文安全；非單調(diào)訪(fǎng)問(wèn)結(jié)構(gòu)；快速解密；大屬性空間

隨著云計(jì)算服務(wù)、大數(shù)據(jù)技術(shù)的普及，傳統(tǒng)的公鑰加密方案及身份基加密(identity-based encryp-tion, IBE)[1,2]不足以適應(yīng)“一對(duì)多”的網(wǎng)絡(luò)服務(wù)需求[3].作為一種新型的公鑰加密體制，屬性基加密(attribute-based encryption, ABE)[4,5,6]被認(rèn)為是IBE體制的擴(kuò)展概念，它能夠保證數(shù)據(jù)發(fā)送方與數(shù)據(jù)接收方按照設(shè)定的訪(fǎng)問(wèn)策略共享數(shù)據(jù)，使用戶(hù)能夠更加安全、高效地享受新型網(wǎng)絡(luò)服務(wù)[7].通常，ABE分為2種類(lèi)型：密鑰策略屬性基加密(key-policy attribute-based encryption, KP-ABE)和密文策略屬性基加密(ciphertext-policy attribute-based encryption, CP-ABE).在KP-ABE方案中，密文是與一組屬性集合相關(guān)聯(lián)，密鑰則是與基于屬性構(gòu)成的訪(fǎng)問(wèn)結(jié)構(gòu)相關(guān)聯(lián)；而在CP-ABE方案中，密鑰是與一組屬性集合相關(guān)聯(lián)，密文則是與基于屬性構(gòu)成訪(fǎng)問(wèn)結(jié)構(gòu)相關(guān)聯(lián).

由于ABE具備細(xì)粒度的訪(fǎng)問(wèn)控制能力，這也給ABE方案帶來(lái)較大的計(jì)算開(kāi)銷(xiāo).在典型ABE中，解密開(kāi)銷(xiāo)常常與在解密過(guò)程中所需要用到的屬性數(shù)目成正比，至少需要|Δ|個(gè)雙線(xiàn)性對(duì)運(yùn)算，其中|Δ|為解密過(guò)程中所需的屬性數(shù)目.這大大限制ABE在資源受限環(huán)境(如弱密碼設(shè)備)中的應(yīng)用.基于此問(wèn)題，Hohenberger和Waters提出了第1個(gè)快速解密ABE方案[8]，該方案是基于GPSW中的KP-ABE方案[4]，將原有密鑰更加細(xì)化、增加更多的“幫助層”元素.在密鑰生成算法時(shí)間和密鑰長(zhǎng)度略增的前提下，解密過(guò)程所需的雙線(xiàn)性運(yùn)算個(gè)數(shù)降為常數(shù)量級(jí)的2次運(yùn)算，并給出2種變種方案.

在此之后，Lai等人[9]采用聚合技術(shù)實(shí)現(xiàn)了固定短密文長(zhǎng)度性質(zhì)，給出一個(gè)合數(shù)階上的快速解密且表達(dá)能力豐富的KP-ABE方案，并利用雙系統(tǒng)證明技術(shù)證明該方案在適應(yīng)性安全模型下是安全的.不過(guò)該聚合技術(shù)只能應(yīng)用到小屬性空間KP-ABE方案的構(gòu)造上.然而，對(duì)于小屬性空間的ABE方案，通常要求系統(tǒng)建立算法需要事先確定屬性的數(shù)目，這使得屬性空間的大小往往與安全參數(shù)λ是多項(xiàng)式倍的關(guān)系.而在大屬性空間[10]的方案，屬性空間的大小往往不需要在系統(tǒng)建立算法中事先確定好，它與安全參數(shù)λ是指數(shù)倍的關(guān)系，具備更大的靈活度.

對(duì)于公鑰加密方案，可抵抗選擇密文攻擊(chosen ciphertext attack, CCA)是比可抵抗選擇明文攻擊(chosen plaintext attack, CPA)更被廣泛接受的一種語(yǔ)義安全性.具體到構(gòu)造CCA安全的KP-ABE，最初是通過(guò)對(duì)Canetti-Halevi-Katz轉(zhuǎn)換方法[11]稍加調(diào)整得到.之后，Yamada等人給出一種從CPA安全到CCA安全ABE方案的通用轉(zhuǎn)換方法[12]，但要求ABE方案滿(mǎn)足可代理性質(zhì)或者可驗(yàn)證性質(zhì).不過(guò)，這些方案都需要使用一次簽名.之后，有不使用一次簽名而直接給出CCA安全的ABE構(gòu)造[13-14]，不過(guò)這些方案僅能支持門(mén)限訪(fǎng)問(wèn)結(jié)構(gòu)策略.最近，Liu等人[15]通過(guò)觀(guān)察Boyen-Mei-Waters方法[16]，創(chuàng)新性地將在線(xiàn)離線(xiàn)簽名的變色龍Hash技術(shù)[17]應(yīng)用到加密方案中，最終給出一個(gè)選擇密文安全KP-ABE方案的直接構(gòu)造，但該方案要求ABE方案需支持大屬性空間特性.

在ABE體制中，基于屬性的訪(fǎng)問(wèn)結(jié)構(gòu)有單調(diào)訪(fǎng)問(wèn)結(jié)構(gòu)和非單調(diào)訪(fǎng)問(wèn)結(jié)構(gòu)2種[18].具體來(lái)說(shuō)，單調(diào)訪(fǎng)問(wèn)結(jié)構(gòu)僅支持“與”、“或”、“門(mén)限”操作，而非單調(diào)訪(fǎng)問(wèn)結(jié)構(gòu)可以額外支持“非”操作.因此，非單調(diào)的訪(fǎng)問(wèn)結(jié)構(gòu)允許用戶(hù)的私鑰可以基于任意訪(fǎng)問(wèn)結(jié)構(gòu)生成，加大了方案的表達(dá)能力，增加了ABE方案的具體實(shí)際應(yīng)用場(chǎng)景的范圍.

本文在已有工作的基礎(chǔ)上，給出2個(gè)具體的支持快速解密性質(zhì)的KP-ABE構(gòu)造：

1) 觀(guān)察文獻(xiàn)[8]中的方案，利用實(shí)現(xiàn)非單調(diào)訪(fǎng)問(wèn)結(jié)構(gòu)的技術(shù)[18-19]，借助隨機(jī)預(yù)言機(jī)[20]使得方案支持大屬性空間.最終提出一個(gè)支持非單調(diào)訪(fǎng)問(wèn)結(jié)構(gòu)、支持大屬性空間的快速解密素?cái)?shù)階KP-ABE構(gòu)造，并證明是滿(mǎn)足選擇屬性集合和選擇明文安全性定義.

2) 基于方案1，借鑒實(shí)現(xiàn)支持任意單調(diào)訪(fǎng)問(wèn)結(jié)構(gòu)技術(shù)[11]，將原有方案表達(dá)能力進(jìn)一步加強(qiáng).觀(guān)察Liu等人[15]用于直接構(gòu)造CCA安全KP-ABE方案的變色龍Hash技術(shù)[17].最終提出一個(gè)具備豐富表單能力、支持非單調(diào)訪(fǎng)問(wèn)結(jié)構(gòu)、支持大屬性空間的高效選擇密文安全快速解密素?cái)?shù)階KP-ABE方案構(gòu)造.

1 預(yù)備知識(shí)

1.1 訪(fǎng)問(wèn)結(jié)構(gòu)

定義1. 令{P1,P2,…,Pn}是一個(gè)參與方集合.一個(gè)單調(diào)的訪(fǎng)問(wèn)結(jié)構(gòu)是指一個(gè)非空的集合?2{P1,P2,…,Pn}{?}：對(duì)于任意B,C，若B∈且B?C，則C∈.在的集合被稱(chēng)為授權(quán)集合，不在的集合被稱(chēng)為非授權(quán)集合.

1.2 線(xiàn)性秘密分享方案

令S∈是一個(gè)任意授權(quán)集合，I?{1,2,…,}定義為I?{i|ρ(i)∈S}.若{λi}是根據(jù)∏關(guān)于任意秘密s的有效分享碎片，則存在一組常數(shù)集合{μi}i∈I，滿(mǎn)足μiλi=s.令Wi表示W(wǎng)中的第i行，有).其中{μi}i∈I可以通過(guò)高斯消除法計(jì)算得到.

1.3 密鑰策略屬性基加密

一個(gè)KP-ABE方案由4個(gè)算法構(gòu)成：

1) 系統(tǒng)建立Setup(1λ).系統(tǒng)建立算法以安全參數(shù)λ作為輸入；輸出公開(kāi)參數(shù)MPK以及主密鑰MSK.

2) 加密Encrypt(MPK,M,S).加密算法以公開(kāi)參數(shù)MPK、消息M和屬性集合S作為輸入；輸出密文CT.

3) 密鑰生成KeyGen(MPK,MSK,).密鑰生成算法以MPK、MSK、訪(fǎng)問(wèn)結(jié)構(gòu)作為輸入；輸出一個(gè)基于訪(fǎng)問(wèn)結(jié)構(gòu)的密鑰SK.

4) 解密Dec(MPK,CT,SK).解密算法輸入公開(kāi)參數(shù)MPK、密文CT以及密鑰SK.當(dāng)屬性集合滿(mǎn)足訪(fǎng)問(wèn)結(jié)構(gòu)，即S∈時(shí)，算法返回消息M.

安全模型：KP-ABE的安全模型是由一個(gè)挑戰(zhàn)者和一個(gè)攻擊者A完成的游戲進(jìn)行定義：

1) 系統(tǒng)建立階段.挑戰(zhàn)者運(yùn)行Setup算法，并將公開(kāi)參數(shù)MPK發(fā)送給攻擊者.

2) 詢(xún)問(wèn)階段1.該階段攻擊者將會(huì)自適應(yīng)地向挑戰(zhàn)者發(fā)出2種詢(xún)問(wèn)：

② 密文問(wèn)詢(xún).攻擊者問(wèn)詢(xún)關(guān)于集合S的密文CT.挑戰(zhàn)者構(gòu)造使得S能夠滿(mǎn)足的訪(fǎng)問(wèn)結(jié)構(gòu)，運(yùn)行密鑰生成算法KeyGen(MPK,MSK,)得到密鑰SK；再運(yùn)行解密算法Dec(MPK,CT,SK)解密密文CT，并將得到的結(jié)果返回給攻擊者.

3) 挑戰(zhàn)階段.攻擊者遞交2個(gè)等長(zhǎng)的消息M0,M1.除此之外，還會(huì)遞交一個(gè)屬性集合S*，但該集合不能滿(mǎn)足詢(xún)問(wèn)階段的任一訪(fǎng)問(wèn)結(jié)構(gòu).挑戰(zhàn)者隨機(jī)擲一枚硬幣b，然后基于屬性集合S*加密Mb得到挑戰(zhàn)密文CT*，并將CT*傳遞給攻擊者.

4) 詢(xún)問(wèn)階段2.與階段1相同.

5) 猜測(cè)階段.攻擊者會(huì)輸出關(guān)于b的猜測(cè)值b′.實(shí)驗(yàn)輸出結(jié)果1當(dāng)且僅當(dāng)b=b′.

定義3. 對(duì)于所有的概率多項(xiàng)式時(shí)間攻擊者A，如果存在一個(gè)可忽略函數(shù)使得

成立，對(duì)于屬性空間U的密鑰策略屬性基加密方案KP-ABE是選擇密文安全的.

選擇性屬性集合安全(selective security).如果在系統(tǒng)建立階段之前增加一個(gè)初始化階段，在該階段中攻擊者必須將要挑戰(zhàn)的屬性集合S*發(fā)送給挑戰(zhàn)者，那么認(rèn)為該KP-ABE方案是選擇性屬性集合安全.

選擇明文安全(chosen plaintext security).如果在詢(xún)問(wèn)階段中將密文問(wèn)詢(xún)階段去除掉，那么認(rèn)為該KP-ABE方案是選擇明文安全的.

1.4 雙線(xiàn)性映射

1) 雙線(xiàn)性性.對(duì)于所有的u,v∈和a,b∈p，有e(ua,vb)=e(u,v)ab.

2) 非退化性.e(g,g)≠1.

定義4. 判定性BDHE.令a,s∈p是隨機(jī)選取的元素，g是一個(gè)階為p∈Θ(2λ)群的生成元.判定性q-BDHE是指給定向量：

y=(,p,g,gs,ga,…,g(aq),g(aq+2),…,g(a2q)),

對(duì)于所有的概率多項(xiàng)式時(shí)間攻擊者A，以一個(gè)關(guān)于λ的可忽略?xún)?yōu)勢(shì)區(qū)分e(g,g)aq+1s∈T和一個(gè)隨機(jī)元素R∈T.攻擊者A的優(yōu)勢(shì)定義如下：

|Pr[A(y,e(g,g)aq+1s)=0]-Pr[A(y,R)=0]|,

2 CPA安全的快速解密KP-ABE方案

基于文獻(xiàn)[8]提出的快速解密KP-ABE方案，文獻(xiàn)[19]給出一個(gè)支持屬性變成函數(shù)加密[21]方案的KP-ABE方案，并實(shí)現(xiàn)了固定短密文長(zhǎng)度.通過(guò)觀(guān)察這2個(gè)KP-ABE方案[8,19]，借助隨機(jī)預(yù)言機(jī)結(jié)合非單調(diào)訪(fǎng)問(wèn)結(jié)構(gòu)技術(shù)，本節(jié)給出一個(gè)在選擇性屬性集合安全和選擇明文安全模型下、支持非單調(diào)訪(fǎng)問(wèn)結(jié)構(gòu)、大屬性空間及快速解密等良好性質(zhì)的KP-ABE方案(注意到在支持快速解密特性同時(shí)，試圖在大屬性空間下實(shí)現(xiàn)固定密文長(zhǎng)度這一工作仍是目前的一個(gè)公開(kāi)問(wèn)題).同時(shí)，該方案對(duì)下一節(jié)構(gòu)造實(shí)際高效的選擇密文安全的KP-ABE(同時(shí)保持支持非單調(diào)訪(fǎng)問(wèn)結(jié)構(gòu)、大屬性空間、快速解密等良好特性)做好準(zhǔn)備工作.

最終，本節(jié)提出了一個(gè)支持非單調(diào)訪(fǎng)問(wèn)結(jié)構(gòu)、大屬性空間的快速解密KP-ABE方案.

2.1 KP-ABE方案描述

本節(jié)提出的KP-ABE方案由4個(gè)算法組成：

1) 系統(tǒng)建立Setup(1λ).系統(tǒng)建立算法選擇一個(gè)素?cái)?shù)階為p∈Θ(2λ)的雙線(xiàn)性群，隨機(jī)選取一個(gè)生成元g∈.然后，選取隨機(jī)元素h0,u∈和α∈p.令Hash函數(shù)H:{0,1}*→，令H作為一個(gè)預(yù)言機(jī).給定任意比特串zi∈U，其中i∈|k|，定義hi=H(zi).最后，設(shè)置方案公開(kāi)參數(shù)MPK=(,p,g,h0,H,e(g,g)α)以及主私鑰MSK=(PK,α).

2) 加密Encrypt(MPK,M,S=(x1,x2,…,xk)?{0,1}*).加密算法以公開(kāi)參數(shù)MPK、消息M∈T和給定屬性集合S=(x1,x2,…,xk)?U作為輸入.算法隨機(jī)選取s∈p，對(duì)于任意的屬性xi∈{0,1}*，其中i∈|k|，令hi=H(xi).輸出密文CT=(S,rch,C,C0,C1,C2,C3)，其中C=M.

3) 密鑰生成KeyGen(MPK,MSK,).密鑰生成算法以MSK、一個(gè)非單調(diào)的訪(fǎng)問(wèn)結(jié)構(gòu)作為輸入.給定一個(gè)對(duì)于屬性集合S的非單調(diào)訪(fǎng)問(wèn)結(jié)構(gòu)，存在一個(gè)對(duì)于屬性集合的單調(diào)訪(fǎng)問(wèn)結(jié)構(gòu)滿(mǎn)足關(guān)系=NM().令=(W,ρ)，其中W是一個(gè)×m的矩陣，映射ρ:[]→n.利用Share算法計(jì)算秘密碎片{λi}i∈[].對(duì)于分享矩陣W的每一行Wi，隨機(jī)選取ri∈p，然后:

① 當(dāng)ρ(i)是一個(gè)正常屬性時(shí)，計(jì)算:

② 當(dāng)ρ(i)是一個(gè)拒絕屬性時(shí)，計(jì)算:

輸出密鑰：

然后，對(duì)于每一行i，有：

① 當(dāng)ρ(i)是一個(gè)正常屬性時(shí)，解密可以先對(duì)密鑰做預(yù)計(jì)算.計(jì)算：

再計(jì)算得到：

② 當(dāng)ρ(i)是一個(gè)拒絕屬性時(shí)，解密可以先對(duì)密鑰做預(yù)計(jì)算.計(jì)算：

再計(jì)算得到：

最后，解密算法可以計(jì)算得到:

3 安全性分析

結(jié)合文獻(xiàn)[8,19]的證明技巧，特別是文獻(xiàn)[19]的證明思路，本文采用定理1給出方案的安全性證明.

證明. 令e:×→T是一個(gè)雙線(xiàn)性映射，|U|是屬性集合中屬性數(shù)目，這里|U|是關(guān)于安全參數(shù)1λ的多項(xiàng)式.假設(shè)存在一個(gè)PPT的攻擊者，在實(shí)驗(yàn)中以不可忽略的概率輸出結(jié)果1，那么就可以構(gòu)造一個(gè)PPT的模擬器B打破群的|U|-BDHE問(wèn)題，具體過(guò)程如下：

1) 初始化階段.攻擊者A提交用于生成挑戰(zhàn)密文的屬性集合S*.

2) 系統(tǒng)建立階段.模擬器B收到來(lái)自|U|-BDHE關(guān)于系統(tǒng)參數(shù)的挑戰(zhàn)輸入：

(,p,g,gs,ga,…,ga|U|,ga|U|+2,…,ga2|U|,T),

其中，T=e(g,g)a|U|+1s或是T中的隨機(jī)元素R.然后，隨機(jī)選取α′∈p，設(shè)置e(g,g)α=e(g,g)α′·e(ga,ga|U|)，并私下設(shè)置α=α′+a|U|+1.最終，模擬器B將設(shè)置好的公開(kāi)參數(shù)MPK發(fā)送給攻擊者A.

3) 詢(xún)問(wèn)階段1.模擬器B模擬預(yù)言機(jī)H:{0,1}*→如下：①在實(shí)驗(yàn)開(kāi)始時(shí)初始化一個(gè)表TRO.②一旦收到關(guān)于屬性xi的問(wèn)詢(xún)，模擬器B會(huì)首先檢測(cè)該屬性xi是否存在于表TRO中，若存在則直接返回結(jié)果；若不存在，則首先創(chuàng)建一個(gè)新表項(xiàng)(xi,i,hi)，并隨機(jī)選取zi←p，計(jì)算hi=gzigai.這里，可以認(rèn)為返回的結(jié)果hi是與中的隨機(jī)元素獨(dú)立同分布的.③再隨機(jī)選取z0←p，并計(jì)算得到h0=gai.該階段攻擊者將會(huì)自適應(yīng)地向挑戰(zhàn)者發(fā)出密鑰詢(xún)問(wèn).攻擊者問(wèn)詢(xún)關(guān)于非單調(diào)訪(fǎng)問(wèn)結(jié)構(gòu)的密鑰，挑戰(zhàn)者會(huì)運(yùn)行KeyGen算法將計(jì)算出的密鑰返回給攻擊者，分為2個(gè)步驟完成：

Ⅱ. 如果ρ(i)?N(S*)，而且ρ(i)是一個(gè)正常屬性時(shí)，則有ρ(i)?S*.首先計(jì)算ci=v Wi，那么λi=αci=ci(α′+a|U|+1).利用消除技術(shù)去除密鑰元素，令ri=-cia|U|+1-ρ(i)，因此模擬器B有能力計(jì)算：

② 至此，模擬器B生成了有效密鑰，但這些密鑰并滿(mǎn)足良好分布，需要再對(duì)這些密鑰進(jìn)行隨機(jī)化操作，這里采用文獻(xiàn)[9]中提到的技術(shù).首先隨機(jī)選取y2,y3,…,yn∈p，設(shè)置向量v#=(0,y2,y3,…,yn)，計(jì)算關(guān)于0的秘密分享碎片，得到i,j}j∈Uρ(i).之后，將第1步驟生成的有效密鑰隨機(jī)化:

*Di=Di(#Di),

{*Di,j=Di,j(#Di,j)}j∈Uρ(i),

最終，將滿(mǎn)足均勻隨機(jī)分布的密鑰傳遞給攻擊者.

4) 挑戰(zhàn)階段.攻擊者A提交2個(gè)等長(zhǎng)的消息M0,M1,模擬器B會(huì)隨機(jī)選取一個(gè)比特位b←{0,1}，然后基于挑戰(zhàn)屬性集合S*生成挑戰(zhàn)密文:

C*=MT,

如果T=e(g,g)a|U|+1s，上面的密文是對(duì)Mb的有效加密，否則是對(duì)T中隨機(jī)元素的加密.

5) 詢(xún)問(wèn)階段2.與詢(xún)問(wèn)階段1相同.

6) 猜測(cè)階段.最終，攻擊者輸出一個(gè)關(guān)于的猜測(cè)值b′.如果b=b′，輸出0(猜測(cè)T=e(g,g)a|U|+1s)；否則輸出1(猜測(cè)T是一個(gè)隨機(jī)值).

那么，B對(duì)A的回應(yīng)是與KP-ABE的安全游戲同分布的.因此，當(dāng)實(shí)驗(yàn)中A的輸出為1,這則意味著B(niǎo)成功解決了判定性的|U|-BDHE問(wèn)題.

證畢.

4 CCA安全的快速解密KP-ABE方案

Liu等人[15]利用變色龍Hash技術(shù)得到選擇密文安全的KP-ABE的直接構(gòu)造，使得在實(shí)現(xiàn)CCA安全性時(shí)帶來(lái)很小的開(kāi)銷(xiāo).本節(jié)試圖利用該技術(shù)實(shí)現(xiàn)表達(dá)能力豐富的快速解密KP-ABE方案.但發(fā)現(xiàn)該技術(shù)只適用于大屬性空間，因此借助隨機(jī)預(yù)言機(jī)，將Lai等人提出的僅支持單調(diào)訪(fǎng)問(wèn)結(jié)構(gòu)的小屬性空間快速解密KP-ABE方案[9]拓展支持非單調(diào)訪(fǎng)問(wèn)結(jié)構(gòu)大屬性空間快速解密KP-ABE方案.基于第2節(jié)CPA安全性方案，最終提出CCA安全的KP-ABE方案.

Lai的方案能夠支持任意單調(diào)訪(fǎng)問(wèn)結(jié)構(gòu)，可以認(rèn)為訪(fǎng)問(wèn)結(jié)構(gòu)表達(dá)能力豐富.技術(shù)上是將屬性空間分為2個(gè)部分：屬性名和屬性值.假設(shè)與密文綁定的屬性集合數(shù)目恰好為n，而這n個(gè)屬性又恰好來(lái)自于n個(gè)不同的屬性名類(lèi).根據(jù)文獻(xiàn)[9]有性質(zhì)：對(duì)于每一個(gè)屬性i分類(lèi)的唯一屬性zi，該屬性集合可以被表示為(z1,z2,…,zn).對(duì)應(yīng)一個(gè)訪(fǎng)問(wèn)結(jié)構(gòu)(W,ρ,I)，其中W是一個(gè)×n的矩陣，映射ρ:[]→n,T=(tρ(1),tρ(2),…,tρ())∈，其中tρ(i)是訪(fǎng)問(wèn)結(jié)構(gòu)下特定的屬性名ρ(i).因此，一個(gè)屬性集合S=(z1,z2,…,zn)滿(mǎn)足訪(fǎng)問(wèn)結(jié)構(gòu)(W,ρ,I)，當(dāng)且僅當(dāng)存在一個(gè)集合I?{1,2,…,}和一組常數(shù){μi}i∈，對(duì)于所有i∈I滿(mǎn)足關(guān)系：

在實(shí)現(xiàn)選擇密文安全性時(shí)，借鑒變色龍Hash技術(shù)實(shí)現(xiàn).本節(jié)尋找到一個(gè)基于decisional Diffie-Hellman的挑戰(zhàn)密文結(jié)構(gòu)g,gs′,uV,(uV)s′同樣將對(duì)屬性空間p分為2部分：1)用作正常屬性空間U=；2)用作虛擬屬性空間.這樣就使得虛擬屬性空間僅用作密文的有效性檢測(cè)，并不能用來(lái)對(duì)正常屬性空間的密文作檢測(cè).

最終，本節(jié)提出了一個(gè)具備豐富表達(dá)能力、支持非單調(diào)訪(fǎng)問(wèn)結(jié)構(gòu)、大屬性空間、選擇密文安全快速解密KP-ABE方案.

4.1 方案描述

本節(jié)提出的KP-ABE方案由4個(gè)算法組成：

1) 系統(tǒng)建立Setup(1λ).系統(tǒng)建立算法選擇一個(gè)素?cái)?shù)階為p∈Θ(2λ)的雙線(xiàn)性群，隨機(jī)選取一個(gè)生成元g∈.然后，選取隨機(jī)h0,u∈和α∈p.這里，定義.因此，U∩V=?,U∪V=p.令Hash函數(shù)H:U→，將令H作為一個(gè)預(yù)言機(jī).給定任意zi∈U，其中i∈|k|，定義hi=H(zi).繼而，定義一個(gè)變色龍Hash函數(shù)Hash:{0,1}*→V.最后，設(shè)定方案公開(kāi)參數(shù)MPK=(Hash,,p,g,h0,H,u,ω,e(g,g)α)以及主私鑰MSK=(PK,α).

2) 加密Encrypt(MPK,M,S=(z1,z2,…,zk)?U).加密算法以MPK、消息M∈T和給定屬性集合S=(z1,z2,…,zk)?U作為輸入.算法隨機(jī)選取s,s′∈p，對(duì)任意的屬性zi∈U，其中i∈|S|(定義|S|的值恰好是n)，令hi=H(zi).計(jì)算,隨機(jī)選取rch←R并設(shè)置V=Hash(pkch,pkch‖C‖C0‖C1‖…‖Cn+1‖Cn+2,rch)∈V，再計(jì)算得到C4=(uV)s′ωs.輸出密文CT=(S,rch,C,C0,{Ci}i∈[n]Cn+1,Cn+2,Cn+3)，其中:

C=Me(g,g)αs,

Cn+1=gs,

Cn+2=gs′,

Cn+3=(uV)s′ωs.

3) 密鑰生成KeyGen(MPK,MSK,).密鑰生成算法以MSK、一個(gè)非單調(diào)的訪(fǎng)問(wèn)結(jié)構(gòu)作為輸入.給定一個(gè)對(duì)于屬性集合S的非單調(diào)訪(fǎng)問(wèn)結(jié)構(gòu)，存在一個(gè)對(duì)于屬性集合的單調(diào)訪(fǎng)問(wèn)結(jié)構(gòu)滿(mǎn)足關(guān)系=NM().令=(W,ρ)，其中W是一個(gè)×m的矩陣，映射ρ:[].令=(W,ρ,T)，其中W是一個(gè)×n的矩陣，映射ρ:[]→n，且T=(tρ(1),tρ(2),…,tρ())∈.該算法利用Share算法計(jì)算秘密碎片{λi}i∈[].對(duì)于分享矩陣W的每一行Wi，隨機(jī)選取ri∈p，然后:

① 當(dāng)ρ(i)是一個(gè)正常屬性時(shí)，計(jì)算:

② 當(dāng)ρ(i)是一個(gè)拒絕屬性時(shí)，計(jì)算:

輸出密鑰:

e(g,Cn+3)=e(Cn+2,uV)e(Cn+1,ω).

這里的密文有效性是可以公開(kāi)檢測(cè)的，因?yàn)樗枰玫降墓_(kāi)參數(shù)MPK和密文都是公開(kāi)的.

② 解密部分步驟.令(W,ρ,T)是對(duì)于的一個(gè)LSSS結(jié)構(gòu)，可以找到一組I?{1,2,…,}和一組常數(shù){μi}i∈，對(duì)于所有i∈I滿(mǎn)足：

對(duì)在集合里面的密文元素做聚合操作，定義:

對(duì)于每一行i，有：

Ⅰ. 當(dāng)ρ(i)是一個(gè)正常屬性時(shí)，解密可以先對(duì)密鑰做預(yù)計(jì)算.計(jì)算:

再計(jì)算得到:

Ⅱ. 當(dāng)ρ(i)是一個(gè)拒絕屬性時(shí)，解密可以先對(duì)密鑰做預(yù)計(jì)算.計(jì)算:

再計(jì)算得到:

最后，解密算法可以計(jì)算得到:

4.2 安全性分析

在選擇密文安全性的證明中，基本證明思路與第3節(jié)一致.但是，攻擊者在階段1和階段2中除了自適應(yīng)性地向攻擊者問(wèn)詢(xún)關(guān)于訪(fǎng)問(wèn)結(jié)構(gòu)的密鑰外，同樣可以發(fā)出密文問(wèn)詢(xún).在這一部分的模擬中，與文獻(xiàn)[12]中思路基本一致.

1) 當(dāng)S?S*，得到問(wèn)詢(xún)密鑰無(wú)法解密基于挑戰(zhàn)屬性集合生成的挑戰(zhàn)密文；

2) 當(dāng)S?S*和V≠V*，該部分滿(mǎn)足正常屬性空間構(gòu)成的訪(fǎng)問(wèn)結(jié)構(gòu)密鑰，并不能解密關(guān)于基于虛擬屬性空間生成的CCA的挑戰(zhàn)密文結(jié)構(gòu)；

3) 當(dāng)S?S*和V=V*，模擬器無(wú)法模擬去回答，導(dǎo)致攻擊者以1|V|=2(p-1)的概率使得游戲終止.

因此，最終在隨機(jī)預(yù)言機(jī)模型下，可以證明在該方案基于|U|-BDHE和安全的變色龍Hash函數(shù)，本文的方案是選擇性屬性集合安全和選擇密文安全的.

5 方案對(duì)比

本節(jié)將本文提出的2個(gè)快速解密KP-ABE方案與文獻(xiàn)[8-9]進(jìn)行對(duì)比，如表1所示:

Table 1 Comparison with other KP-ABE schemes with Fast Decryption

本文第3節(jié)、第4節(jié)提出的方案均支持大屬性空間、非單調(diào)訪(fǎng)問(wèn)結(jié)構(gòu).除此之外，第4節(jié)提出的快速解密KP-ABE方案額外支持了類(lèi)似“屬性復(fù)用”的功能以及選擇密文安全性.在安全性假設(shè)方面，文獻(xiàn)[11]的方案是依賴(lài)于合數(shù)階群下的子群假設(shè)，而文獻(xiàn)[9]和本文的方案則是依賴(lài)于素?cái)?shù)階群下的假設(shè).對(duì)比其他相關(guān)工作，本文方案實(shí)現(xiàn)了一些良好性質(zhì)，但卻需要借助隨機(jī)預(yù)言機(jī)實(shí)現(xiàn).

表1在加密、解密時(shí)間的分析上，僅考慮“統(tǒng)治級(jí)”運(yùn)算.其中，加密開(kāi)銷(xiāo)僅考慮群中冪運(yùn)算(Exp)個(gè)數(shù)，解密開(kāi)銷(xiāo)僅考慮雙線(xiàn)性對(duì)運(yùn)算(Pairing)個(gè)數(shù)，可以看出4個(gè)方案解密開(kāi)銷(xiāo)相當(dāng).但是，本文的2個(gè)方案為了實(shí)現(xiàn)非單調(diào)訪(fǎng)問(wèn)結(jié)構(gòu)，它們的密鑰長(zhǎng)度和解密開(kāi)銷(xiāo)中的冪次運(yùn)算大約為文獻(xiàn)[8-9]的2倍.特別地，為了在訪(fǎng)問(wèn)結(jié)構(gòu)額外實(shí)現(xiàn)類(lèi)似“屬性復(fù)用”的功能，第4節(jié)的方案需要更多的加密開(kāi)銷(xiāo).除此之外，由于本文的2個(gè)方案支持大屬性空間，無(wú)法采用密文聚合技術(shù)，因此密文長(zhǎng)度比文獻(xiàn)[8]要分別多1個(gè)和3個(gè)群元素，而基于合數(shù)階群假設(shè)的文獻(xiàn)[9]則實(shí)現(xiàn)了固定密文長(zhǎng)度.對(duì)比其他相關(guān)工作，本文雖然借助了隨機(jī)預(yù)言機(jī)實(shí)現(xiàn)了一些良好性質(zhì)，但卻犧牲了一些空間和時(shí)間效率.

6 結(jié)束語(yǔ)

本文借助隨機(jī)預(yù)言機(jī)安全給出2個(gè)支持非單調(diào)訪(fǎng)問(wèn)結(jié)構(gòu)(表達(dá)能力豐富)、大屬性空間的快速解密KP-ABE構(gòu)造，其中1個(gè)實(shí)現(xiàn)選擇明文安全性，1個(gè)實(shí)現(xiàn)選擇密文安全性.本文的未來(lái)工作是在標(biāo)準(zhǔn)模型下得到適應(yīng)性選擇密文安全高效快速解密KP-ABE方案，并在大屬性空間下實(shí)現(xiàn)短固定密文長(zhǎng)度并支持非單調(diào)的訪(fǎng)問(wèn)控制結(jié)構(gòu).

[1]Dan B, Franklin M. Identity-based encryption from the weil pairing[J]. Siam Journal on Computing, 2003, 32(3): 213-229

[2]Shamir A. Identity-based cryptosystems and signature schemes[G] //LNCS196: Proc of Advances in Cryptography (CRYPTO 1984). Berlin: Springer, 1985, 21(2): 47-53

[3]Cao Z. New Directions of Modern Cryptography[M]. Boca Raton, Florida: CRC Press, 2012

[4]Goyal V, Pandey O, Sahai A, et al. Attribute-based encryption for fine-grained access control of encrypted data[G] //Proc of the 13th ACM Conf on Computer and Communications Security (CCS). New York: ACM, 2006: 89-98

[5]Sahai A, Waters B. Fuzzy identity-based encryption[G] //LNCS 3494: Proc of the 24th Annual Int Conf on the Theory and Applications of Cryptographic Techniques (EUROCRYPT). Berlin: Springer, 2005: 457-473

[6]Su Jinshu, Cao Dan, Wang Xiaofeng, et al. Attribute based encryption schemes[J]. Journal of Software, 2011, 22(6): 1299-1315(蘇金樹(shù), 曹丹, 王小峰, 等. 屬性基加密機(jī)制[J]. 軟件學(xué)報(bào), 2011, 22(6): 1299-1315)

[7]Fu Yingxun, Luo Shengmei, Shu Jiwu. Survey of secure cloud storage system and key technologies[J]. Journal of Computer Research and Development, 2013, 50(1): 136-145(傅穎勛, 羅圣美, 舒繼武. 安全云存儲(chǔ)系統(tǒng)與關(guān)鍵技術(shù)綜述[J]. 計(jì)算機(jī)研究與發(fā)展, 2013, 50(1): 136-145)

[8]Hohenberger S, Waters B. Attribute-based encryption with fast decryption[G] //LNCS 7778: Proc of the 16th Int Conf on Practice and Theory in Public-Key Cryptography (PKC). Berlin: Springer, 2013: 162-179

[9]Lai J, Deng R H, Li Y, et al. Fully secure key-policy attribute-based encryption with constant-size ciphertexts and fast decryption[G] //Proc of the 9th ACM Symp on Information, Computer and Communications Security. New York: ACM, 2014: 239-248

[10]Yannis R, Waters B. Practical constructions and new proof methods for large universe attribute-based encryption[C] //Proc of the 2013 ACM SIGSAC Conf on Computer & Communications Security. New York: ACM, 2013: 463-474

[11]Ran C, Halevi S, Katz J. Chosen-ciphertext security from identity-based encryption[J]. SIAM Journal on Computing, 2007, 36(5): 1301-1328

[12]Yamada S, Attrapadung N, Hanaoka G, et al. Generic constructions for chosen-ciphertext secure attribute based encryption[G] //LNCS 6571: Proc of the 14th Int Conf on Practice and Theory in Public Key Cryptography (PKC). Berlin: Springer, 2011: 71-89

[13]Chen C, Zhang Z, Feng D. Efficient ciphertext policy attribute-based encryption with constant-size ciphertext and constant computation-cost[G] //LNCS 7778: Proc of the 5th Int Conf on Provable Security. Berlin: Springer, 2011: 84-101

[14]Ge A, Zhang R, Chen C, et al. Threshold ciphertext policy attribute-based encryption with constant size ciphertexts[G] //LNCS 7372: Information Security and Privacy. Berlin: Springer, 2012: 336-349

[15]Liu W, Liu J, Wu Q, et al. Practical direct chosen ciphertext secure key-policy attribute-based encryption with public ciphertext test[G] //LNCS 8713: Proc of the 19th European Symp on Research in Computer Security (ESORICS). Berlin: Springer, 2014: 91-108

[16]Xavier B, Mei Qixiang, Waters B. Direct chosen ciphertext security from identity-based techniques[G] //Proc of the 12th ACM Conf on Computer and Communications Security. New York: ACM, 2005: 320-329

[17]Krawczyk H M, Rabin T D. Chameleon hashing and signatures[EB/OL]. International Association for Cryptologic Research (1998-03-17) [2016-08-15]. http://eprint.iacr.org/1998/010

[18]Rafail O, Sahai A, Waters B. Attribute-based encryption with non-monotonic access structures[G] //Proc of the 14th ACM Conf on Computer and Communications Security (CCS). New York: ACM, 2007: 195-203

[19]Huo W, Pei J, Zhang K, et al. KP-ABE with attribute extension: Towards functional encryption schemes integration[G] //Proc of the 6th Int Symp on Parallel Architectures, Algorithms and Programming. Piscataway, NJ: IEEE, 2014: 230-237

[20]Bellare M. Random oracles are practical: A paradigm for designing efficient protocols[C] //Proc of the 1st ACM Conf on Computer & Communication Security. New York: ACM, 1970: 62-73

[21]Dan B, Sahai A, Waters B. Functional encryption: Definitions and challenges[G] //LNCS 6597: Proc of the 8th Theory of Cryptography Conf. Berlin: Springer, 2010: 253-273

Zhang Kai, born in 1990. PhD candidate. His main research interests include public key cryptography and information security.

Wei Lifei, born in 1982. PhD. His main research interests include cryptography and cyber security (Lfwei@shou.edu.cn).

Li Xiangxue, born in 1974. Professor and PhD supervisor. His main research interests include cryptography and information security (xxli@cs.ecnu.edu.cn).

Chen Jie, born in 1985. Professor and PhD supervisor. His main research interests include public key cryptography and information security (jchen@cs.ecnu.edu.cn).

Qian Haifeng, born in 1977. Professor and PhD supervisor. His main research interests include cryptography and network security.

An Efficient and Expressive Attribute-Based Encryption Scheme with Chose Ciphertext Security

Zhang Kai1,2, Wei Lifei3, Li Xiangxue1,4, Chen Jie1,2, and Qian Haifeng1

1(DepartmentofComputerScience&Technology,EastChinaNormalUniversity,Shanghai200241)2(TheStateKeyLaboratoryofIntegratedServicesNetworks(XidianUniversity),Xi’an710071)3(CollegeofInformationTechnology,ShanghaiOceanUniversity,Shanghai201306)4(WestoneCryptologicResearchCenter,Beijing100070)

Attribute-based encryption (ABE) is a promising version of public key encryption, since it enables fine-grained access control on the encrypted data. In a key-policy ABE (KP-ABE) scheme, every ciphertext is related to attributes set and each secret key is associated with an access structure. Therefore, the decryption overhead is usually proportional to the number of attributes used in decryption process in most existing KP-ABE schemes. Inspired by Hohenberger and Waters’ KP-ABE scheme with fast decryption, we propose a large universe KP-ABE with fast decryption supporting non-monotonic access structure, which is proven selective chosen attribute set secure and chosen plaintext secure in the random oracle model. Moreover, observing Lai et.al expressive KP-ABE with fast decryption and applying with Chameleon Hash technique used to give a direct chosen ciphertext secure KP-ABE construction, we also give a direct chosen plaintext secure KP-ABE construction in the random oracle model, which still achieves the following features: non-monotonic access structure, large-universe and fast decryption. Compared with the related work, both two expressive large universe KP-ABE schemes enjoy comparable time efficiency in decryption process.

attribute-based encryption (ABE); chosen ciphertext security; non-monotonic access structure; fast decryption; large-universe

2016-06-15；

2016-08-17

國(guó)家自然科學(xué)基金項(xiàng)目(61571191,61572192,61472142,61402282);上海市科學(xué)技術(shù)委員會(huì)科技項(xiàng)目(13JC1403502);上海市青年科技英才揚(yáng)帆計(jì)劃項(xiàng)目(14YF1404200,14YF1410400);綜合業(yè)務(wù)網(wǎng)理論及關(guān)鍵技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室開(kāi)放基金項(xiàng)目(ISN17-11);華東師范大學(xué)研究生科研創(chuàng)新實(shí)踐資助項(xiàng)目

錢(qián)海峰(hfqian@cs.ecnu.edu.cn)

TP309

This work was supported by the National Natural Science Foundation of China (61571191, 61572192, 61472142, 61402282), the Project of Science and Technology Commission of Shanghai Municipality(13JC1403502), the Shanghai Yang-Fan Plan (14YF1404200, 14YF1410400), the Open Foundation of the State Key Laboratory of Integrated Services Networks (ISN17-11), and the East China Normal University Fund for Graduate Student's Scientific Research, Innovation and Practice.