面向公有云的支持快速解密的CP-ABE 方案*

鄒莉萍 , 馮朝勝 , 秦志光 , 袁 丁 , 羅王平 , 李 敏,3

1(四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院,四川 成都 610101)2(電子科技大學(xué) 信息與軟件工程學(xué)院,四川 成都 610054)3(網(wǎng)絡(luò)與數(shù)據(jù)安全四川省重點(diǎn)實(shí)驗(yàn)室(電子科技大學(xué)),四川 成都 610054)

大數(shù)據(jù)的出現(xiàn),使得企業(yè)特別是中小型企業(yè)將數(shù)據(jù)外包給云服務(wù)商[1]變得緊迫,而數(shù)據(jù)外包首先要解決好數(shù)據(jù)機(jī)密性和隱私性[2]問題.加密是確保數(shù)據(jù)機(jī)密性和隱私性的有效途徑.如果只是進(jìn)行加密保存,傳統(tǒng)的加密方法即可勝任;如果還要實(shí)現(xiàn)密文共享,雖然傳統(tǒng)的加密方法也可以實(shí)現(xiàn),但只有采取效率低下的“一對(duì)一”加密方式和粗粒度的訪問控制[3]方式.為了實(shí)現(xiàn)密文共享的高效性和訪問控制的細(xì)粒度,基于屬性的加密方法被提出[4].基于屬性的加密方法可以分為兩種:密文策略基于屬性加密方法CP-ABE[5]和密鑰策略基于屬性加密方法KP-ABE(key-policy attribute-based encryption)[6].由于CP-ABE 的訪問控制方法和企業(yè)IT 系統(tǒng)在明文訪問控制上廣泛采用的基于角色的訪問控制方法RABC(role-based access control)相似,更加受到企業(yè)的關(guān)注.然而,現(xiàn)有的大部分CP-ABE 方案在解密時(shí)所用的時(shí)間隨著匹配訪問策略的屬性數(shù)量呈線性增長,用戶客戶端計(jì)算量急劇增長,對(duì)用戶終端設(shè)備要求較高,常用的用戶終端特別是平板、手機(jī)難以勝任.針對(duì)這一問題,利用Spark 集群中的Map 運(yùn)算和Reduce 運(yùn)算,提出一種基于Spark 的支持快速解密的CP-ABE 方案.本文具體貢獻(xiàn)包括:

(1) 提出一種基于Spark 集群的解密外包方案.在該方案中,云服務(wù)器對(duì)大量密文進(jìn)行存儲(chǔ),授權(quán)中心生成僅由用戶存儲(chǔ)的最終解密密鑰DK和用于云服務(wù)器解密的轉(zhuǎn)換密鑰TK,降低用戶客戶端對(duì)于存儲(chǔ)性能的需求.利用轉(zhuǎn)換密鑰TK對(duì)上傳到云服務(wù)器端密文使用Spark 集群中的Map 運(yùn)算與Reduce 運(yùn)算進(jìn)行半解密,將用戶客戶端解密代價(jià)降低到一次指數(shù)運(yùn)算,顯著減少云服務(wù)器計(jì)算時(shí)間;

(2) 設(shè)計(jì)了一種快速求解共享訪問樹根節(jié)點(diǎn)值的算法.該策略的核心是:將求解任務(wù)分成若干個(gè)可并行執(zhí)行的子任務(wù),然后將子任務(wù)交由Spark 集群中的Map 節(jié)點(diǎn)去完成,Reduce 節(jié)點(diǎn)通過匯聚Map 節(jié)點(diǎn)的輸出結(jié)果計(jì)算出目標(biāo)值.現(xiàn)有的包括Bethencourt 等人[5]的方案(以下簡稱BSW 方案)在內(nèi)的用樹來表示訪問策略CP-ABE 方案,幾乎所有的方案求解根節(jié)點(diǎn)所需的指數(shù)運(yùn)算次數(shù)都和共享訪問樹的節(jié)點(diǎn)數(shù)量成正比,而基于所設(shè)計(jì)的快速求解算法求解根節(jié)點(diǎn)值所需的指數(shù)運(yùn)算時(shí)間僅和葉子節(jié)點(diǎn)的數(shù)量成正比;

(3) 證明方案的有效性.安全性分析表明,在一般群模型和隨機(jī)預(yù)言模型下可抵御選擇明文攻擊.性能分析表明,該方案在計(jì)算上對(duì)用戶客戶端要求較低,手機(jī)、平板、電腦等移動(dòng)設(shè)備亦可勝任.

1 相關(guān)研究

2005 年,Sahai 和Waters[4]在歐洲密碼學(xué)年度會(huì)議上首先提出了一種基于屬性的加密算法(attribute-based encryption,簡稱ABE),并在學(xué)術(shù)界受到了廣泛的關(guān)注與研究.在該方案中,將每一個(gè)標(biāo)識(shí)視為一組描述屬性,并且將用戶私鑰和密文都與屬性相關(guān)聯(lián),只有當(dāng)用戶私鑰的屬性集合滿足密文屬性集合時(shí),才能解密出正確的明文數(shù)據(jù).之后,Bethencourt 和Goyal 分別提出了密文策略基于屬性加密CP-ABE[5]和密鑰策略基于屬性加密KPABE[6].在 CP-ABE 中,密文策略與訪問屬性相關(guān)聯(lián);在 KP-ABE 中,密鑰策略與訪問屬性相關(guān)聯(lián).2007 年,Ostrovsky 等人[7]提出了一種允許使用任意訪問結(jié)構(gòu)的ABE 方案,并且基于DBDH 假設(shè)(decisional bilinear diffie-Hellman assumption)進(jìn)行了安全性證明.同年,Ling 等人[8]提出一種支持訪問結(jié)構(gòu)包含正屬性和負(fù)屬性的CP-ABE 方案,在DBDH 假設(shè)下,證明了該論文提出的基本方案滿足CPA 安全,然后使用Canetti-Halevi-Katz 技術(shù)進(jìn)行一次性簽名,使得改進(jìn)方案滿足CCA 安全.但是該方案只適用于僅限于門限與(“AND”)的共享訪問策略.2008 年,Goyal 等人[9]首次提出了一種基于數(shù)論理論假設(shè)且支持高級(jí)訪問結(jié)構(gòu)的CP-ABE 方案,并且在DBDH假設(shè)下給出安全性證明.2009 年,Li 等人[10]提出了一種具有用戶責(zé)任的ABE 方案,在該方案中,給每個(gè)用戶私鑰中嵌入額外的用戶特定信息,以防止用戶間非法密鑰共享問題,進(jìn)一步解決用戶訪問隱私問題.2011 年,Waters[11]提出一種更加安全的易于實(shí)現(xiàn)的高效CP-ABE 方案,在該方案中,提出了3 種不同的結(jié)構(gòu),這些結(jié)構(gòu)允許在系統(tǒng)效率和不同的安全假設(shè)間進(jìn)行不同的權(quán)衡,使其比基本的CP-ABE 方案擁有更好的實(shí)用效率.但是其解密時(shí)間還是隨著密文大小增長,隨著訪問結(jié)構(gòu)復(fù)雜度增加而增加.同年,Green 等人[12]在Water 等人[11]的方案上提出了一種實(shí)現(xiàn)了RCCA 安全并且同時(shí)適用于CP-ABE 和KP-ABE 的解密外包方案.該方案將大量解密計(jì)算外包給云服務(wù)器,減少了用戶客戶端解密計(jì)算量,但是沒有給出云服務(wù)器端進(jìn)行解密的具體操作.2012 年,Li 等人[13]基于Zhou 等人[14]提出的外包加密CP-ABE 方案,提出了一種基于MapReduce 的外包加密方案.但是在該方案中,沒有提出相應(yīng)的使用MapReduce 的快速解密方案,且Hadoop 中的MapReduce 存在高延遲性的特性,在實(shí)際應(yīng)用中較難實(shí)現(xiàn).2013 年,Lai 等人[15]基于Green 等人[12]的方案,提出了一種可驗(yàn)證的外包解密方案,并且該方案的安全性不依賴于隨機(jī)預(yù)言模型.在該方案中,除了對(duì)明文數(shù)據(jù)進(jìn)行加密,還需要對(duì)GT域中的一個(gè)隨機(jī)元素進(jìn)行加密處理.由于加密工作量的增加,導(dǎo)致解密時(shí)計(jì)算代價(jià)增加一倍.2015 年,Qin 等人[16]基于Green 等人[12]的方案,提出了一個(gè)高效的可驗(yàn)證的解密外包方案,與Lai 等人[15]方案相比,在該方案中引入了哈希映射來驗(yàn)證第三方解密的正確性.同年,Lin 等人[17]也提出了一種可驗(yàn)證的外包解密方案,并且證明其在標(biāo)準(zhǔn)模型下是安全的.與Lai 等人[15]方案相比,密文長度減少,解密計(jì)算代價(jià)減少接近一半.2016 年,Mao 等人[18]提出一種CPA 安全的可驗(yàn)證的外包解密方案.與其他可驗(yàn)證的CPA 安全相比,該方案不再單獨(dú)加密一個(gè)額外的隨機(jī)消息,而是采用同時(shí)對(duì)一個(gè)消息和一個(gè)隨機(jī)值進(jìn)行加密,然后通過該隨機(jī)值來將消息提交給云服務(wù)器,使得其擁有比一般CPA 安全外包方案更短的密文長度.同年,Zhang 等人[19]提出一種具有可驗(yàn)證性外包功能的自適應(yīng)安全的多授權(quán)CP-ABE方案.該方案不僅實(shí)現(xiàn)了解密外包驗(yàn)證,并且降低了公鑰大小.但是在該方案中,每個(gè)屬性不是由唯一的控制權(quán)限控制,所以僅能被視為適當(dāng)?shù)亩嗍跈?quán)ABE 方案,且其僅支持單調(diào)訪問結(jié)構(gòu).2017 年,Liu 等人[20]提出一種將離線與在線技術(shù)相結(jié)合的密文策略ABE 方案,并且支持可驗(yàn)證的外包解密.該方案將密鑰生成和大部分加密計(jì)算都進(jìn)行離線計(jì)算,減少在線計(jì)算時(shí)間,并且將大部分解密工作量都外包給第三方服務(wù)器,但是仍然沒有對(duì)云服務(wù)器端解密方式進(jìn)行快速處理.

由以上分析可知:現(xiàn)有的ABE 方案,無論是在用戶端還是云服務(wù)器端,都存在計(jì)算量過大、計(jì)算時(shí)間過長的問題.

2 系統(tǒng)模型與算法定義

2.1 系統(tǒng)模型

支持快速解密的CP-ABE 系統(tǒng)模型如圖1 所示,包括授權(quán)中心、云服務(wù)器、數(shù)據(jù)所有者和數(shù)據(jù)消費(fèi)者.

Fig.1 Ciphertext-policy attribute-based encryption system model with fast decryption圖1 支持快速解密的密文共享系統(tǒng)模型

(1) 授權(quán)中心:通常在企業(yè)可信域內(nèi),負(fù)責(zé)生成系統(tǒng)公鑰PK、系統(tǒng)主密鑰MK、用戶最終解密密鑰DK和云服務(wù)器轉(zhuǎn)換密鑰TK;

(2) 云服務(wù)器:云服務(wù)器是模型中半可信的第三方,用于存儲(chǔ)大量密文數(shù)據(jù),并且從授權(quán)中心獲取轉(zhuǎn)換密鑰TK對(duì)密文進(jìn)行半解密;

(3) 數(shù)據(jù)所有者:數(shù)據(jù)所有者是模型中數(shù)據(jù)的原始擁有者,將數(shù)據(jù)進(jìn)行加密并上傳至云服務(wù)器進(jìn)行存儲(chǔ);

(4) 數(shù)據(jù)消費(fèi)者:數(shù)據(jù)消費(fèi)者是模型中數(shù)據(jù)的使用者,使用由授權(quán)中心獲取到的最終解密密鑰DK,將從云服務(wù)器獲取到的半解密密文進(jìn)行解密,以獲得共享數(shù)據(jù).

2.2 算法定義

定義1.一種基于Spark 集群的解密外包方案由以下5 個(gè)算法構(gòu)成.

·Setup(λ,U)→(PK,MK):由授權(quán)中心執(zhí)行,輸入安全參數(shù)λ、屬性空間U,輸出系統(tǒng)公鑰PK和系統(tǒng)主密鑰MK;

·Encrypt(PK,M,T)→(CT):由用戶客戶端執(zhí)行,輸入訪問策略T、明文M和系統(tǒng)公鑰PK,輸出密文CT;

·KeyGen(MK,S)→(DK,TK):由授權(quán)中心執(zhí)行,輸入用戶屬性集合S、系統(tǒng)主密鑰MK,輸出用戶最終解密密鑰DK和轉(zhuǎn)換密鑰TK;

·Transform(CT,TK)→(CT′):由云服務(wù)器執(zhí)行,輸入密文CT和轉(zhuǎn)換密鑰TK,輸出半解密密文CT′;

·Decrypt(DK,CT′)→(M):由用戶客戶端執(zhí)行,輸入用戶最終解密密鑰DK和半解密密文CT′,輸出解密密文M.

3 支持快速解密的CP-ABE 方案

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

3.1.1 雙線性映射

雙線性映射(bilinear map)[21,22]因其在密鑰生成上具有高效、精確和安全的特點(diǎn),使其成為ABE 的數(shù)學(xué)基礎(chǔ)之一.其具體定義如下.

設(shè)G1,G2和GT都是階為素?cái)?shù)p的乘法循環(huán)群,記G1的生成元為g1,G2的生成元為g2.形如e:G1×G2→GT的映射就是雙線性映射.雙線性映射具有以下特性.

(1) 雙線性.對(duì)于?a,b∈Zp,?u∈G1,?v∈G2有e(ua,vb)=e(ub,va)=e(u,v)ab,當(dāng)G1=G2時(shí),該映射被稱為對(duì)稱雙線性映射;

(2) 可計(jì)算性.對(duì)于任意取值,雙線性映射的計(jì)算都是高效的;

(3) 非退化性.e(g,g)≠1,即不會(huì)將所有的數(shù)對(duì)都映射為GT中的同一元素.

3.1.2 拉格朗日插值系數(shù)

拉格朗日插值法[23]是以法國數(shù)學(xué)家約瑟夫·拉格朗日命名的一種多項(xiàng)式插值方法.假設(shè)平面上有(x0,y0),(x1,y1),…,(xn-1,yn-1)共n個(gè)點(diǎn),令函數(shù)f(x)經(jīng)過這n個(gè)點(diǎn),設(shè)Dn={0,1,…,n-1},存在n個(gè)多項(xiàng)式pj(x),j∈Dn.則對(duì)于任意k∈Dn,都有pk(x),Bk={i|i≠k,i∈Dn},使得:

pk(x)就是拉格朗日系數(shù).拉格朗日插值公式的一般表達(dá)形式如下:

在本文方案中,令i∈,S表示一個(gè)節(jié)點(diǎn)集合,Δi,S(x)表示拉格朗日系數(shù),則由公式(1)可得:

3.1.3 共享訪問樹

為實(shí)現(xiàn)秘密共享,訪問策略可以用共享訪問樹表達(dá).設(shè)共享訪問樹為T,且其根節(jié)點(diǎn)為R.共享訪問樹T的每一個(gè)非葉子節(jié)點(diǎn)都代表一個(gè)“AND”門或“OR”門.為實(shí)現(xiàn)基于屬性的訪問控制,共享訪問數(shù)T的每一個(gè)葉子節(jié)點(diǎn)都和一個(gè)屬性相對(duì)應(yīng).

令共享訪問樹T的每個(gè)節(jié)點(diǎn)x的閾值為kx(當(dāng)x為葉子節(jié)點(diǎn)時(shí),設(shè)kx=1),為x隨機(jī)選擇一元kx-1 次多項(xiàng)式qx.秘密共享從T的根節(jié)點(diǎn)R開始,采用自上而下的方式進(jìn)行.選擇隨機(jī)數(shù)s∈(p為大素?cái)?shù)),令根節(jié)點(diǎn)的秘密共享數(shù)qR(0)=s,加密共享數(shù)為e(g,g)αs(α∈);令其他節(jié)點(diǎn)的秘密共享數(shù)為qx(0)=qparent(x)(index(x))(parent(x)表示節(jié)點(diǎn)x的父節(jié)點(diǎn);index(x)表示節(jié)點(diǎn)x在兄弟節(jié)點(diǎn)中的序號(hào),按共享訪問樹結(jié)構(gòu)從左往右依次進(jìn)行編號(hào)),加密共享數(shù)為e(g,g)αqx(0).

如果屬性集S滿足Tx(以x為根的樹),記作Tx(S)=1.計(jì)算Tx(S)按照遞歸方式進(jìn)行.如果x不是葉子節(jié)點(diǎn),則為x的每個(gè)孩子節(jié)點(diǎn)x′計(jì)算Tx′(S);如果x代表“AND”門,只有所有孩子的返回值都為1 時(shí),才有Tx(S)=1;如果x代表“OR”門,只要有一個(gè)孩子的返回值為1,就有Tx(S)=1.如果x是葉子節(jié)點(diǎn)且其關(guān)聯(lián)的屬性屬于S,則Tx(S)=1.

3.2 最優(yōu)子樹與加密共享數(shù)

3.2.1 共享訪問樹的最優(yōu)子樹

如果某個(gè)用戶屬性集滿足共享訪問樹T,就可以用用戶密鑰和葉子節(jié)點(diǎn)的共享數(shù)計(jì)算出根節(jié)點(diǎn)R對(duì)應(yīng)的共享數(shù)e(g,g)αs,其中,s為秘密共享數(shù).顯然,滿足共享訪問樹并不一定要求屬性集中的屬性和每個(gè)葉子節(jié)點(diǎn)關(guān)聯(lián)的屬性都匹配,可能只需匹配部分葉子節(jié)點(diǎn)就能滿足訪問樹.

定義2.如果屬性集S只和T的葉子節(jié)點(diǎn)集LT的某個(gè)子集SLT匹配就能實(shí)現(xiàn)對(duì)T的滿足,即T(S)=1,那么由從T的根節(jié)點(diǎn)到葉子節(jié)點(diǎn)集SLT形成的T的子樹,就被稱作共享訪問樹T的解密子樹.

定義3.共享訪問樹T的解密子樹中葉子節(jié)點(diǎn)最少的子樹,被稱作共享訪問樹T的最優(yōu)解密子樹.

定義4.將共享訪問樹T的最優(yōu)解密子樹中所有的“OR”節(jié)點(diǎn)刪除后所形成的樹,稱作共享訪問樹T的最優(yōu)簡化解密子樹.

3.2.2 加密共享數(shù)

觀察如圖2 所示共享訪問樹,該樹的所有非葉子節(jié)點(diǎn)都代表“AND”門,si和F=Esi分別表示節(jié)點(diǎn)i的秘密共享數(shù)和加密共享數(shù),lij表示i的第j個(gè)孩子的拉格朗日系數(shù),其中,E=e(g,g)α.

Fig.2 Sharing access tree圖2 共享訪問樹

根據(jù)共享訪問樹秘密共享方法和拉格朗日插值法,計(jì)算根節(jié)點(diǎn)加密共享數(shù)的過程如下:

根據(jù)以上觀察,得到定理1.

定理1.共享訪問樹的最優(yōu)簡化子樹根節(jié)點(diǎn)對(duì)應(yīng)的加密共享數(shù)等于以每個(gè)葉子節(jié)點(diǎn)對(duì)應(yīng)的加密共享數(shù)為底、以從葉子節(jié)點(diǎn)到根節(jié)點(diǎn)路徑上所有節(jié)點(diǎn)對(duì)應(yīng)的拉格朗日系數(shù)的積為指數(shù)的冪的乘積.

證明:用數(shù)學(xué)歸納法容易證明,限于篇幅考慮,省略證明過程.□

3.3 方案構(gòu)造

方案包括系統(tǒng)初始化、數(shù)據(jù)加密、密鑰生成、數(shù)據(jù)轉(zhuǎn)換和數(shù)據(jù)解密這5 個(gè)模塊.

(1) 系統(tǒng)初始化:Setup(λ,U)→(PK,MK)

系統(tǒng)初始化算法由授權(quán)中心執(zhí)行,該算法以系統(tǒng)空間U和安全參數(shù)λ作為輸入,選擇一個(gè)階為大素?cái)?shù)p的雙線性群G0,記G0的生成元為g,定義雙線性映射e:G0×G0→GT.設(shè)定哈希函數(shù)H1:GT→{0,1}l,選擇兩個(gè)隨機(jī)數(shù)α,β∈,輸出系統(tǒng)公鑰PK信息如下:

將其上傳至云服務(wù)器,并向云服務(wù)器及所有用戶公開.

授權(quán)中心保存系統(tǒng)主密鑰:MK=(β,gα).

(2) 數(shù)據(jù)加密:Encrypt(PK,M,T)→(CT)

數(shù)據(jù)加密算法由用戶客戶端執(zhí)行,該算法以系統(tǒng)公鑰PK、明文數(shù)據(jù)M、密文共享訪問樹T作為輸入,輸出明文數(shù)據(jù)M與共享訪問樹T相關(guān)聯(lián)的密文數(shù)據(jù)CT.

隨機(jī)選擇秘密共享數(shù)s∈,令qR(0)=s(R表示共享訪問樹T的根節(jié)點(diǎn)).按照第3.1.3 節(jié)介紹的方法進(jìn)行秘密共享.令Y是共享訪問樹T中的所有葉子節(jié)點(diǎn)的集合,輸出如下密文:

(3) 密鑰生成:KeyGen(MK,S)→(DK,TK)

密鑰生成算法由授權(quán)中心執(zhí)行,該算法以系統(tǒng)主密鑰MK和屬性集合S作為輸入,選擇一個(gè)隨機(jī)數(shù)對(duì)于任意屬性j∈S,選擇隨機(jī)數(shù).在授權(quán)中心輸出用戶私鑰SK如下:

最后,通過安全信道將最終解密密鑰DK=n發(fā)送給用戶客戶端.

(4) 數(shù)據(jù)轉(zhuǎn)換:Transform(CT,TK)→(CT′)

數(shù)據(jù)轉(zhuǎn)換算法由云服務(wù)器執(zhí)行,該算法以密文消息CT和轉(zhuǎn)換密鑰TK作為輸入,根據(jù)定理1,使用Spark 集群快速計(jì)算半解密密文CT′的模型如圖3 所示.

首先檢測用戶屬性是否滿足共享訪問樹:若不滿足,則直接輸出⊥;否則,針對(duì)最優(yōu)簡化解密子樹中的節(jié)點(diǎn)x(包括葉子節(jié)點(diǎn))啟動(dòng)Spark 中的Map 運(yùn)算,對(duì)最優(yōu)解密子樹中的葉子節(jié)點(diǎn)y啟動(dòng)Spark 中的Reduce 運(yùn)算.整個(gè)算法包括Transform(Map),Transform(Reduce)和Transform(Multiple)這3 個(gè)重要模塊.

①Transform(Map)

對(duì)每個(gè)葉子節(jié)點(diǎn)y,使用轉(zhuǎn)換密鑰TK,通過如下計(jì)算獲得該節(jié)點(diǎn)的部分秘密值CTy′:

令NodeLeafy為葉子節(jié)點(diǎn)標(biāo)識(shí)符,將每個(gè)葉子節(jié)點(diǎn)的標(biāo)識(shí)符和部分秘密值鍵值對(duì)分別發(fā)送到不同的Reduce.

對(duì)于從葉子節(jié)點(diǎn)y到根節(jié)點(diǎn)路徑上的每個(gè)非葉子節(jié)點(diǎn)x,計(jì)算該節(jié)點(diǎn)在該路徑上的孩子節(jié)點(diǎn)sx對(duì)應(yīng)的拉格朗日系數(shù)值Δindex(sx),S(0).對(duì)于x的每個(gè)子孫葉子節(jié)點(diǎn)y,將(NodeLeafy,Δindex(sx),S(0))鍵值對(duì)發(fā)送給y所對(duì)應(yīng)的Reduce.

②Transform(Reduce)

對(duì)每一個(gè)Reduce 運(yùn)算,首先判斷傳入的值是葉子節(jié)點(diǎn)的值還是非葉子節(jié)點(diǎn)的值:如果是兩個(gè)非葉子節(jié)點(diǎn)的值,則將兩個(gè)節(jié)點(diǎn)的拉格朗日系數(shù)值相乘;如果是一個(gè)葉子節(jié)點(diǎn)的值、一個(gè)非葉子節(jié)點(diǎn)的值且該輪Reduce 運(yùn)算所需要的所有非葉子節(jié)點(diǎn)的值還未全部傳入,則將非葉子節(jié)點(diǎn)的拉格朗日系數(shù)值保存起來,直到所有節(jié)點(diǎn)的值傳入完畢.在Reduce 節(jié)點(diǎn)接收到所有值后,根據(jù)定理1 計(jì)算葉子節(jié)點(diǎn)y對(duì)應(yīng)的冪值:

③Transform(Multiply)

令共享訪問樹T的最優(yōu)簡化解密子樹ST的葉子節(jié)點(diǎn)的總數(shù)為num(ST),將每一個(gè)Reduce 的結(jié)果收集起來進(jìn)行連乘運(yùn)算,得到根節(jié)點(diǎn)的秘密共享數(shù):

然后進(jìn)行如下計(jì)算,得到半解密密文CT′.

Fig.3 Spark-based semi-decryption model圖3 基于Spark 平臺(tái)進(jìn)行半解密模型圖

(5) 數(shù)據(jù)解密:Decrypt(DK,CT′)→(M)

數(shù)據(jù)解密算法由用戶客戶端執(zhí)行,以用戶最終解密密鑰DK和云服務(wù)器傳回的半解密密文CT′作為輸入,輸出明文M.

首先,使用最終解密密鑰DK對(duì)從云服務(wù)器傳回的半解密密文CT′進(jìn)行開方處理,得到密文解密參數(shù)A=e(g,g)αs,再通過如下計(jì)算得到明文M′:

如果H1(M′)等于,則表明M′等于M,輸出明文M;否則,輸出⊥.

4 安全性與性能分析

4.1 安全模型

實(shí)現(xiàn)CPA 安全的CP-ABE 安全模型如下.

· 初始化:挑戰(zhàn)者運(yùn)行Setup算法,產(chǎn)生系統(tǒng)公鑰PK,并且將公鑰PK公開給敵手;

· 第1 階段:敵手A查詢屬性集S1,...,Sq1分別對(duì)應(yīng)的私鑰;

· 挑戰(zhàn):敵手提交要挑戰(zhàn)的訪問結(jié)構(gòu)A*和兩個(gè)等長的明文消息M0和M1.選擇挑戰(zhàn)的訪問結(jié)構(gòu)時(shí),應(yīng)保證第1 階段查詢過的任意屬性集都不滿足該訪問結(jié)構(gòu).挑戰(zhàn)者選擇一個(gè)隨機(jī)數(shù)b,并且基于訪問結(jié)構(gòu)A*加密數(shù)據(jù)Mb形成密文CT*,然后將密文CT*提供給敵手;

· 第2 階段:選擇一組都不滿足訪問結(jié)構(gòu)的屬性Sq1+1,...,Sq,重復(fù)第1 階段的操作;

· 猜測:敵手A輸出與隨機(jī)數(shù)b對(duì)應(yīng)的猜測值b′.

敵手能夠贏得上述挑戰(zhàn)游戲的優(yōu)勢為Pr[b′=b]-1/2.在上述游戲中,如果敵手在多項(xiàng)式時(shí)間內(nèi)贏得游戲的優(yōu)勢是可忽略不計(jì)的,就可以認(rèn)為對(duì)應(yīng)的CP-ABE 方案是安全的.

4.2 安全性分析

定理2.本文所提出的方案,在一般群模型和隨機(jī)預(yù)言模型下可抵御選擇明文攻擊.

證明:假設(shè)敵手(算法)A在一般群模型和隨機(jī)預(yù)言模型能以不可忽略優(yōu)勢攻破本文所提出的方案,那么可以基于A構(gòu)建敵手(算法)B,使得其可以在同樣模型下攻破BSW 方案,這與在一般群模型和隨機(jī)預(yù)言模型下BSW方案可以抵御選擇明文攻擊矛盾,故本文所提出的方案在一般群模型和隨機(jī)預(yù)言模型下可抵御選擇明文攻擊.下面說明敵手B的構(gòu)建過程.

· 初始化階段:敵手B獲取BSW 方案的公鑰PK=(G0,g,h=gβ,e(g,g)α),并將其發(fā)送給A;

· 第1 階段:敵手B建立空表T,敵手A可重復(fù)發(fā)出查詢請(qǐng)求.A發(fā)出一次查詢后,B將要查詢屬性集S發(fā)送給BSW 方案挑戰(zhàn)者(模擬器),由BSW 方案挑戰(zhàn)者利用密鑰生成算法生成與S對(duì)應(yīng)的私鑰SK′并返回給B.B選擇一個(gè)隨機(jī)數(shù)n∈Z*p,由SK′計(jì)算出轉(zhuǎn)換密鑰TK,計(jì)算SK=(n,TK).將SK返回給A.將(S,SK,TK)存入到表T中;

· 挑戰(zhàn)階段:當(dāng)A確定第一個(gè)階段結(jié)束后,向B提交要挑戰(zhàn)的訪問結(jié)構(gòu)樹T和兩個(gè)明文消息M0,M1∈G1.提交T時(shí),要確保已經(jīng)查詢的屬性集中沒有一個(gè)滿足T.B將T和兩個(gè)消息發(fā)送給BSW 方案挑戰(zhàn)者以獲得密文CT;

· 第2 階段:B繼續(xù)接受A的查詢,但查詢分為如下兩種情況.

?S不滿足T.重復(fù)第1 階段的查詢過程;

?S滿足T.該情況下,無法查詢S對(duì)應(yīng)私鑰,故只能按如下方法生成偽轉(zhuǎn)換密鑰:B隨機(jī)選擇t∈G0,運(yùn)行KeyGen((d,t,PK),S)生成密鑰SK′,令TK=SK′,SK=(d,TK).將TK返回給A,將(S,SK,TK)存入到表T中;

· 猜測:如果A輸出的猜測為b′,那么B輸出的猜測也為b′.因此,如果A能以不可忽略優(yōu)勢攻破本文所提出的方案,那么B也能以不可忽略優(yōu)勢攻破BSW 方案.

5 性能分析

5.1 理論分析

在進(jìn)行數(shù)據(jù)處理時(shí),雙線性運(yùn)算B和指數(shù)運(yùn)算E所需要的時(shí)間占CP-ABE 方案絕大部分時(shí)間,故以這兩個(gè)指標(biāo)作為衡量計(jì)算性能的指標(biāo).令|TL|為T的葉子節(jié)點(diǎn)個(gè)數(shù)(樹結(jié)構(gòu))或矩陣的行數(shù)(LSSS 結(jié)構(gòu)),則針對(duì)本文方案,在解密時(shí),用戶客戶端僅需對(duì)從云服務(wù)器端獲取到的半解密密文CT′進(jìn)行一次指數(shù)運(yùn)算,即用戶客戶端解密代價(jià)僅為1E.云服務(wù)器端需要對(duì)每一個(gè)葉子節(jié)點(diǎn)進(jìn)行一次雙線性運(yùn)算和一次指數(shù)運(yùn)算,最后在求解半解密密文時(shí)再進(jìn)行一次雙線性運(yùn)算,所以在云端的解密代價(jià)為(|TL|+1)B+|TL|E,且其運(yùn)行在Spark 集群上,將云服務(wù)器的解密代價(jià)分給集群中各個(gè)節(jié)點(diǎn),從而進(jìn)一步減少了云服務(wù)器解密時(shí)間.故本文方案解密總代價(jià)為(|TL|+1)B+(|TL|+1)E.

本文方案與BSW 方案、文獻(xiàn)[12]中的方案、文獻(xiàn)[18]中的方案在用戶端解密計(jì)算開銷、服務(wù)器端解密計(jì)算開銷以及解密計(jì)算總開銷對(duì)比見表1～表3.

Table 1 Comparison of decryption time in user client表1 用戶客戶端解密計(jì)算開銷對(duì)比

5.2 實(shí)驗(yàn)分析

實(shí)驗(yàn)采用Eclipse 開發(fā)工具,利用雙線性對(duì)加密庫(JPBC)(http://crypto.stanford.edu/pbc/)和CP-ABE 開發(fā)工具包(http://acsc.csl.sri.com/cpabe/),基于本文提出的方案,在Spark 集群環(huán)境下進(jìn)行.雙線性運(yùn)算和指數(shù)運(yùn)算皆采用JPBC 中原有的操作,從素?cái)?shù)階群y2=x3+x中選取群G和GT,群G和GT中的元素長度為512 位.實(shí)驗(yàn)使用的虛擬PC 機(jī)用戶客戶端配置為:1 個(gè)Intel(R) Xeon(R) CPU(E5-2620 2.0GHZ),內(nèi)存1GB,系統(tǒng)CentOS6.5 64 位;實(shí)驗(yàn)使用的虛擬移動(dòng)設(shè)備用戶客戶端配置為:1 個(gè)Google APIs Intel Atom(x86_64),內(nèi)存2GB,系統(tǒng)Android7.0;實(shí)驗(yàn)使用的虛擬云服務(wù)器端配置為:4 個(gè)Intel(R) Xeon(R) CPU(E5-2620 2.0GHZ),內(nèi)存8GB,系統(tǒng)CentOS6.5 64 位;實(shí)驗(yàn)使用的虛擬云服務(wù)器端Spark 集群配置為:11 臺(tái)虛擬機(jī),其中1 臺(tái)為master 節(jié)點(diǎn),另外10 臺(tái)均為node 節(jié)點(diǎn).每臺(tái)配置均為:2 個(gè)Intel(R) Xeon(R) CPU(E5-2620 2.0GHZ),內(nèi)存8GB,系統(tǒng)CentOS6.5 64 位.

實(shí)驗(yàn)時(shí),分別使用PC 機(jī)和手機(jī)作為客戶端進(jìn)行對(duì)比實(shí)驗(yàn).為保證數(shù)據(jù)的可靠性,每組對(duì)比實(shí)驗(yàn)中每個(gè)方案每輪進(jìn)行50 次運(yùn)算并取其平均值.針對(duì)PC 機(jī)用戶客戶端解密時(shí)間和總解密時(shí)間,將本文方案分別與BSW 方案、文獻(xiàn)[12]中的方案、文獻(xiàn)[18]中的方案進(jìn)行對(duì)比;針對(duì)移動(dòng)設(shè)備用戶客戶端解密時(shí)間和總解密時(shí)間,將本文方案分別與文獻(xiàn)[12]中的方案、文獻(xiàn)[18]中的方案進(jìn)行對(duì)比;針對(duì)云服務(wù)器端解密時(shí)間,將本文方案分別和基于BSW 方案的Proxy 方案(即將解密工作外包給云服務(wù)器但未進(jìn)行并行化處理)、文獻(xiàn)[12]中的方案、文獻(xiàn)[18]中的方案進(jìn)行對(duì)比.為方便進(jìn)行實(shí)驗(yàn)比較,密文共享訪問結(jié)構(gòu)之間的邏輯關(guān)系均為邏輯與(即“AND”關(guān)系).每組對(duì)比實(shí)驗(yàn)進(jìn)行25 輪測試,每輪增加4 個(gè)共享訪問策略屬性,為保證實(shí)驗(yàn)變量的唯一性,每一輪所使用的數(shù)據(jù)及共享訪問策略相同.

當(dāng)用戶客戶端分別為PC 機(jī)和移動(dòng)設(shè)備時(shí),本文方案與BSW 方案、文獻(xiàn)[12]中的方案、文獻(xiàn)[18]中的方案在用戶客戶端解密時(shí)間對(duì)比分別如圖4、圖5 所示.當(dāng)用戶客戶端為PC 機(jī)時(shí),本文方案、文獻(xiàn)[12]中的方案、文獻(xiàn)[12]中的方案在用戶客戶端解密時(shí)間在3ms～5ms 之間,而BSW 方案的解密時(shí)間隨著訪問策略屬性數(shù)量的增加呈急劇上升趨勢;當(dāng)用戶客戶端為移動(dòng)設(shè)備時(shí),本文方案、文獻(xiàn)[12]中的方案和文獻(xiàn)[18]中的方案這3 種方案在用戶客戶端解密時(shí)間均在4ms～8ms 之間.

Fig.4 Comparison of decryption time in user client (PC)圖4 用戶端解密時(shí)間對(duì)比圖(PC)

Fig.5 Comparison of decryption time in user client (Android)圖5 用戶端解密時(shí)間對(duì)比圖(安卓)

本文方案與Proxy 方案、文獻(xiàn)[12]中的方案、文獻(xiàn)[18]中的方案在云服務(wù)器端解密時(shí)間對(duì)比如圖6 所示,幾種方案在云服務(wù)器端的解密時(shí)間都隨著訪問策略屬性的增加而逐漸增長,但是當(dāng)共享訪問策略屬性數(shù)量增加時(shí),本文方案具有明顯優(yōu)勢.

Fig.6 Comparison of decryption time in cloud server圖6 云服務(wù)器端解密時(shí)間對(duì)比圖

當(dāng)用戶客戶端為PC 機(jī)時(shí),本文方案與BSW 方案、文獻(xiàn)[12]中的方案、文獻(xiàn)[18]中的方案總解密時(shí)間對(duì)比如圖7 所示;當(dāng)用戶客戶端為移動(dòng)設(shè)備時(shí),本文方案與文獻(xiàn)[12]中的方案、文獻(xiàn)[18]中的方案總解密時(shí)間對(duì)比如圖8 所示.無論是使用PC 機(jī)還是移動(dòng)設(shè)備,幾種方案的解密時(shí)間都隨著訪問策略屬性的增加呈現(xiàn)上升趨勢,但是在兩種環(huán)境下,本文方案在共享訪問策略數(shù)量增加的情況下都具有明顯優(yōu)勢,且當(dāng)訪問策略屬性的數(shù)量達(dá)到100 個(gè)時(shí),本文方案總解密時(shí)間在1s 左右,滿足用戶響應(yīng)時(shí)間要求.

Fig.7 Comparison of total decryption time (PC)圖7 總解密時(shí)間對(duì)比圖(PC)

Fig.8 Comparison of total decryption time (Android)圖8 總解密時(shí)間對(duì)比圖(安卓)

6 結(jié)束語

現(xiàn)有的CP-ABE 方案在解密時(shí)普遍存在計(jì)算量過大、計(jì)算時(shí)間過長等問題,難以在用戶終端特別是運(yùn)算能力較弱的移動(dòng)終端上實(shí)施.為了減少用戶客戶端的負(fù)擔(dān),一些將解密外包給云服務(wù)器的CP-ABE 方案被提出.這些方案雖然明顯降低了用戶終端解密時(shí)的計(jì)算量,但計(jì)算時(shí)間過長問題并沒有得到有效解決.針對(duì)該問題,將Spark 集群技術(shù)和并行計(jì)算技術(shù)引入到CP-ABE 方案的設(shè)計(jì)之中,提出了一種面向公有云的支持快速解密的CP-ABE 方案.在該方案中,將計(jì)算量較大的求解共享訪問樹根節(jié)點(diǎn)對(duì)應(yīng)的加密共享數(shù)的任務(wù)分解為若干個(gè)可并行執(zhí)行的Map 任務(wù)和Reduce 任務(wù).Map 任務(wù)負(fù)責(zé)拉格朗日系數(shù)的計(jì)算或葉子節(jié)點(diǎn)加密共享數(shù)的計(jì)算,Reduce節(jié)點(diǎn)負(fù)責(zé)計(jì)算出葉子節(jié)點(diǎn)對(duì)應(yīng)的冪值.最后,計(jì)算出的冪值的乘積即為共享訪問樹根節(jié)點(diǎn)對(duì)應(yīng)的加密共享數(shù).性能分析表明,與BSW 方案、文獻(xiàn)[12]中的方案、文獻(xiàn)[18]中的方案相比,所提出的方案在解密速度上有顯著提高;而安全性分析表明,所提出方案在一般群模型和隨機(jī)預(yù)言模型下能對(duì)抗選擇明文攻擊.