可證安全的基于證書廣播加密方案

李繼國(guó),張亦辰,衛(wèi)曉霞

(河海大學(xué)計(jì)算機(jī)與信息學(xué)院,江蘇南京 210098)

?

可證安全的基于證書廣播加密方案

李繼國(guó),張亦辰,衛(wèi)曉霞

(河海大學(xué)計(jì)算機(jī)與信息學(xué)院,江蘇南京 210098)

廣播加密可使發(fā)送者選取任意用戶集合進(jìn)行廣播加密,只有授權(quán)用戶才能夠解密密文.但是其安全性依賴廣播中心產(chǎn)生和頒布群成員的解密密鑰.針對(duì)這一問(wèn)題,本文提出基于證書廣播加密的概念,給出了基于證書廣播加密的形式化定義和安全模型.結(jié)合基于證書公鑰加密算法的思想,構(gòu)造了一個(gè)高效的基于證書廣播加密方案,并證明了方案的安全性.在方案中,用戶私鑰由用戶自己選取,證書由認(rèn)證中心產(chǎn)生,解密密鑰由用戶私鑰和證書兩部分組成,克服了密鑰托管的問(wèn)題.在方案中,廣播加密算法中的雙線性對(duì)運(yùn)算可以進(jìn)行預(yù)計(jì)算,僅在解密時(shí)做一次雙線性對(duì)運(yùn)算,提高了計(jì)算效率.

廣播加密;基于證書加密;雙線性對(duì)

1　引言

對(duì)于有N個(gè)用戶的系統(tǒng),假設(shè)需要通過(guò)公開(kāi)的信道發(fā)送某個(gè)消息給其中S個(gè)用戶,要求只有這S個(gè)用戶能夠解密密文,其余用戶不能由密文恢復(fù)出消息.直觀的方法是用這S個(gè)用戶的公鑰分別進(jìn)行加密,將對(duì)應(yīng)的密文通過(guò)公開(kāi)信道傳送,由于這S個(gè)用戶擁有對(duì)應(yīng)的私鑰,可以保證只有指定用戶才能進(jìn)行解密.但這種方法的計(jì)算代價(jià)很大,消息發(fā)送者需要將同一段消息加密S次并傳輸,而廣播加密就可以很好地解決這類問(wèn)題.廣播加密方案是實(shí)現(xiàn)一點(diǎn)對(duì)多點(diǎn)通信的一種方式,在一個(gè)廣播加密系統(tǒng)中,廣播者可以對(duì)某個(gè)集合內(nèi)的用戶發(fā)起廣播,加密后的消息在公開(kāi)信道上進(jìn)行傳送,任何監(jiān)聽(tīng)廣播的用戶均能獲得廣播密文,只有被授權(quán)的合法接收者才可以進(jìn)行解密,恢復(fù)出廣播消息,而其它監(jiān)聽(tīng)廣播信道的不法用戶均無(wú)法恢復(fù)廣播的明文.在收費(fèi)電視、數(shù)字版權(quán)保護(hù)、安全電子郵件等特殊領(lǐng)域,其效率遠(yuǎn)遠(yuǎn)高于傳統(tǒng)的點(diǎn)對(duì)點(diǎn)通信方式,有廣泛的實(shí)際應(yīng)用背景.

廣播加密是一種在不安全信道上給一組用戶傳輸加密信息的密碼體制,它可使發(fā)送者選取任意用戶集合進(jìn)行廣播加密,只有授權(quán)用戶才能夠解密密文.2001年,Naor等人[1]用完備子樹和子集差分的方法巧妙地構(gòu)造了一個(gè)高效的廣播加密方案,該方案分割集合的效率很高,并使用數(shù)學(xué)知識(shí)證明了兩種分割方法的正確性,適用于數(shù)量較大的合法用戶和數(shù)量較少的非法用戶集合.Boneh等人[2,3]提出了可抗完全聯(lián)合攻擊的廣播加密方案,方案的優(yōu)點(diǎn)是縮短了密文和密鑰的長(zhǎng)度,其缺點(diǎn)是公鑰長(zhǎng)度與接收用戶數(shù)目成正比.為了克服文獻(xiàn)[2,3]中的缺點(diǎn),Liu等人[4]提出了一個(gè)公鑰定長(zhǎng)的廣播加密方案,并縮減了私鑰的長(zhǎng)度,并證明方案在隨機(jī)預(yù)言模型下可抵抗完全聯(lián)合攻擊.2007年,Delerablée[5]結(jié)合基于身份的公鑰密碼體制提出了基于身份的廣播加密方案,方案中密文和私鑰長(zhǎng)度都是固定的,但是公鑰長(zhǎng)度與接收用戶集合數(shù)目成線性關(guān)系.Gentry和Waters[6]提出一個(gè)半靜態(tài)安全的新概念,并給出從半靜態(tài)安全系統(tǒng)到自適應(yīng)安全系統(tǒng)的通用“雙密鑰”轉(zhuǎn)換.進(jìn)一步,構(gòu)造了具有固定密文長(zhǎng)度的廣播加密系統(tǒng).最近,Boneh等[7]使用多線性映射技術(shù)較好地解決了公鑰廣播加密中密文和密鑰過(guò)長(zhǎng)的問(wèn)題,并給出三個(gè)構(gòu)造.提出的方法能夠完全抵抗任意數(shù)量合謀者的攻擊.上述方案中接收者的解密密鑰都是由廣播中心計(jì)算生成,通過(guò)安全通道發(fā)送給各個(gè)用戶,存在密鑰托管問(wèn)題,并且需要建立安全信道.Tan等人[8]提出了一個(gè)傳統(tǒng)公鑰密碼體制下的安全公鑰廣播加密方案,用戶的私鑰由用戶自己選擇,避免了密鑰托管問(wèn)題,但是用戶私鑰由6個(gè)群元素組成,公鑰由4個(gè)群元素組成,用戶的密鑰存儲(chǔ)代價(jià)較大,并且存在證書管理問(wèn)題.Phan等[9]去除了群管理者,提出了分布式動(dòng)態(tài)廣播加密的概念,利用“黑盒”思想,給出一個(gè)具體的構(gòu)造,該構(gòu)造可以看作子集覆蓋框架的拓展.伍前紅等[10]結(jié)合了廣播加密和群密鑰協(xié)商提出了捐助廣播加密(ContributoryBroadcastEncryption)密碼原語(yǔ).在這種新密碼原語(yǔ)下,提出了具有短密文的捐助廣播加密方案.為了解決叛徒跟蹤和撤銷問(wèn)題,Hofheinz和Striecks[11]基于文獻(xiàn)[12],提出了具有跟蹤和撤銷的廣播加密方案.Boneh和Zhandry[13]使用不可區(qū)分混淆技術(shù),構(gòu)造了多方密鑰交換,高效廣播加密和叛徒跟蹤方案.

Gentry[14]在2003年首次提出基于證書的公鑰密碼體制(Certificate-BasedCryptography,簡(jiǎn)稱CBC),該體制中用戶私鑰由用戶自己選取,加密方案中的解密密鑰由用戶私鑰和CA頒發(fā)的證書構(gòu)成.由于解密密鑰由兩部分組成,且證書在公開(kāi)信道中發(fā)送,避免了密鑰托管和建立安全信道的問(wèn)題,也簡(jiǎn)化了證書的管理,所以基于證書的公鑰密碼體制為構(gòu)建安全高效的公鑰基礎(chǔ)設(shè)施PKI(PublicKeyInfrastructure,簡(jiǎn)稱PKI)提供了有效的方法.2006年,Morillo等人[15]基于Waters[16]IBE(Identity-BasedEncryption,簡(jiǎn)稱IBE)方案提出了第一個(gè)標(biāo)準(zhǔn)模型下滿足自適應(yīng)選擇密文安全的CBE(Certificate-BasedEncryption,簡(jiǎn)稱CBE)方案.Dodis等人[17]利用選擇密文安全的IBE方案和PKE(PublicKeyEncryption,簡(jiǎn)稱PKE)方案以及一次簽名構(gòu)造出選擇密文安全的CBE方案.為了減少通信代價(jià),Galindo等人[18]對(duì)文獻(xiàn)[17]中的CBE方案進(jìn)一步改進(jìn),縮短了密文的長(zhǎng)度,使其安全規(guī)約更加簡(jiǎn)潔,并在標(biāo)準(zhǔn)模型下證明了方案是自適應(yīng)選擇密文安全的.Lu等人[19]提出高效的基于證書加密方案,該方案通過(guò)預(yù)計(jì)算減少了雙線性對(duì)的運(yùn)算次數(shù),僅在解密時(shí)做一次雙線性對(duì)運(yùn)算,與其它方案相比提高了計(jì)算效率.

本文集成基于證書公鑰密碼體制[14,20,21]的思想,首次提出基于證書廣播加密的概念,給出方案的形式化定義和安全模型,構(gòu)造了一個(gè)具體的基于證書廣播加密方案,并證明方案在自適應(yīng)選擇密文攻擊下是安全的.提出的廣播加密方案中用戶的私鑰為兩個(gè)群元素,用戶的公鑰也由兩個(gè)群元素組成,用戶的密鑰存儲(chǔ)代價(jià)較低.在方案中,廣播加密算法中的雙線性對(duì)運(yùn)算可以進(jìn)行預(yù)計(jì)算,僅在解密時(shí)做一次雙線性對(duì)運(yùn)算,計(jì)算效率較高.并且廣播系統(tǒng)中的用戶可以隨時(shí)加入或退出廣播系統(tǒng),而不需要對(duì)其它用戶的密鑰進(jìn)行更新.此外,本文提出的方案可以抵抗完全聯(lián)合攻擊.

2　困難問(wèn)題假設(shè)

定義1雙線性映射G1和G2是兩個(gè)q階加法循環(huán)群,GT是q階乘法循環(huán)群,q為大素?cái)?shù).P1和P2分別是群G1、G2的兩個(gè)生成元,雙線性映射e:G1×G2→GT具備以下三個(gè)性質(zhì)[17,18]:

(1)雙線性:對(duì)任意的P∈G1,Q∈G2,a,b∈Zq,有e(aP,bQ)=e(P,Q)ab.

(2)非退化性:e(P1,P2)≠1(GT中單位元).

(3)可計(jì)算性:e是可有效計(jì)算的.

若G1和G2相同,該雙線性映射被稱為對(duì)稱雙線性映射,G1和G2不同則稱為非對(duì)稱雙線性映射.本文使用的雙線性映射為對(duì)稱雙線性映射.

定理1如果p=2q+1,且p和q為兩個(gè)大的奇素?cái)?shù),對(duì)于整數(shù)a,若0

k-mBDHI困難問(wèn)題假設(shè)如果不存在概率多項(xiàng)式時(shí)間算法A能以不可忽略的優(yōu)勢(shì)解決G1上的k-mBDHI問(wèn)題,則稱群G1上的k-mBDHI問(wèn)題是難解的.

DDH困難問(wèn)題假設(shè)若不存在概率多項(xiàng)式時(shí)間算法能以不可忽略的優(yōu)勢(shì)判斷T是否等于gab,則稱DDH問(wèn)題在有限域中是難解的.

3　基于證書廣播加密方案的形式化定義及安全模型

結(jié)合基于證書加密方案的形式化定義和廣播加密的一般構(gòu)造,下面分別給出基于證書廣播加密方案的形式化定義及安全模型.

3.1基于證書廣播加密的形式化定義

設(shè)SN為所有廣播用戶的集合,其中N={1,2,…,n}.一個(gè)基于證書的廣播加密方案由一個(gè)廣播密鑰封裝機(jī)制和一個(gè)對(duì)稱加密方案組成,包括下面五個(gè)算法:

系統(tǒng)參數(shù)設(shè)置算法Setup該算法由CA運(yùn)行.CA選擇系統(tǒng)的安全參數(shù)ζ,運(yùn)行此算法產(chǎn)生主公鑰和主密鑰(mpk,msk)以及其它系統(tǒng)參數(shù),公開(kāi)系統(tǒng)參數(shù)params(包括系統(tǒng)主公鑰mpk),CA保存系統(tǒng)主密鑰msk.

用戶密鑰生成算法Extract該算法由用戶IDi(i∈N)運(yùn)行.用戶IDi利用系統(tǒng)參數(shù)params生成自己的公/私鑰對(duì)(PKi,SKi),私鑰SKi自己保存,公鑰PKi公開(kāi).

證書產(chǎn)生算法Certify該算法由CA中心運(yùn)行.CA以用戶IDi的身份信息、公鑰PKi、系統(tǒng)參數(shù)params和主私鑰msk為輸入,產(chǎn)生用戶證書CertIDi,τ,并通過(guò)公開(kāi)信道發(fā)送給用戶IDi.

加密算法Enc該算法由廣播者運(yùn)行.廣播者選擇廣播集合S={ID1,ID2,…,IDw},滿足w≤n.對(duì)于需要廣播的消息m,算法以廣播集合S、廣播公鑰PKS和系統(tǒng)公開(kāi)參數(shù)params為輸入,先計(jì)算(Hdr,k)=Enc(S,PKS),其中報(bào)頭Hdr是對(duì)對(duì)稱密鑰k的封裝,k∈K,K為對(duì)稱加密方案(E,D)的密鑰空間,再用對(duì)稱加密算法E以k為密鑰對(duì)m進(jìn)行加密,生成對(duì)應(yīng)的密文C0=Ek(m),將C=(S,Hdr,C0)通過(guò)廣播信道進(jìn)行廣播.

解密算法Dec該算法由用戶IDi(IDi∈S)運(yùn)行.在收到廣播密文C后,用戶IDi首先利用私鑰SKi、證書CertIDi,τ以及報(bào)頭信息Hdr恢復(fù)出對(duì)稱加密算法的密鑰k=Dec(Hdr,SKi,CertIDi,τ),最后以k和對(duì)稱加密方案的解密算法D恢復(fù)出對(duì)應(yīng)的消息m=Dk(C0)或者直接輸出無(wú)效標(biāo)志⊥.

一個(gè)安全的基于證書廣播加密方案必需滿足以下性質(zhì):

(1)正確性按照方案的步驟正常運(yùn)行生成的廣播密文可以被合法用戶正確解密.

(2)保密性在不知道合法用戶的私鑰和證書的情況下,任何監(jiān)聽(tīng)廣播的用戶都無(wú)法正確解密.

(3)抗聯(lián)合攻擊若廣播集合外的所有用戶聯(lián)合起來(lái)也無(wú)法破解廣播密文,則稱該方案可抵抗完全聯(lián)合攻擊.

(4)用戶的動(dòng)態(tài)加入和退出可以方便的實(shí)現(xiàn)用戶加入和退出廣播集合,并且對(duì)于新加入的用戶而言,只能正常解密加入后的廣播消息,而不能解密之前的廣播消息,對(duì)于已撤銷的用戶而言,不能對(duì)撤銷之后的廣播消息進(jìn)行解密.

3.2基于證書廣播加密的安全模型

2005年,Boneh等人[2]定義了廣播加密的靜態(tài)安全模型.2007年,Delerablée[5]結(jié)合基于身份公鑰加密的性質(zhì),給出了基于身份廣播加密方案的安全模型.本文結(jié)合上述兩個(gè)安全模型以及Gentry[14]提出的基于證書加密方案的安全模型,引入公鑰替換攻擊思想[23～26],首次刻畫了基于證書廣播加密方案的安全模型.在本文所定義的安全模型下,基于證書廣播加密方案的安全性是指在自適應(yīng)選擇密文攻擊下,對(duì)于靜態(tài)敵手而言是密文不可區(qū)分的,且能抵抗完全聯(lián)合攻擊.

基于證書廣播加密方案中包含兩類攻擊者AI和AII.AI模擬了未認(rèn)證的用戶這一類敵手,它可以獲得任意用戶的私鑰,不可以獲得目標(biāo)廣播集合內(nèi)任何用戶的證書,但可以詢問(wèn)目標(biāo)廣播集合外任意用戶的證書,可以進(jìn)行除目標(biāo)密文外的解密詢問(wèn),AI還可以進(jìn)行公鑰替換攻擊,可以獲得替換后公鑰所對(duì)應(yīng)的證書,但若敵手AI對(duì)目標(biāo)廣播集合內(nèi)的用戶進(jìn)行了公鑰替換攻擊,則AI不能詢問(wèn)替換后公鑰所對(duì)應(yīng)的證書.AII模擬了一個(gè)惡意的CA,它擁有系統(tǒng)主密鑰,可以生成任意用戶的證書,不可以詢問(wèn)目標(biāo)廣播集合內(nèi)用戶的私鑰,但可以獲得目標(biāo)廣播集合外任意用戶的私鑰,AII也可以進(jìn)行公鑰替換,但不可以替換目標(biāo)廣播集合內(nèi)用戶的公鑰,可以進(jìn)行除目標(biāo)廣播密文外的解密詢問(wèn).

廣播加密方案一般是由一個(gè)密鑰封裝算法和一個(gè)對(duì)稱加密算法組成,對(duì)稱加密算法都是選取自適應(yīng)選擇密文攻擊下安全的算法,在定義方案的安全模型時(shí)只對(duì)密鑰封裝算法部分進(jìn)行定義.由于我們的安全模型是針對(duì)靜態(tài)敵手,所以敵手在系統(tǒng)參數(shù)生成前需要確定目標(biāo)廣播集合.結(jié)合上述兩類敵手及其各自不同的攻擊能力,下面分別給出兩類敵手與挑戰(zhàn)者之間的游戲:

游戲1

初始化階段AI選擇目標(biāo)廣播集合S*,S*?SN.

系統(tǒng)參數(shù)設(shè)置挑戰(zhàn)者C運(yùn)行算法Setup,生成系統(tǒng)的主公/私鑰對(duì)(mpk,msk)以及其它系統(tǒng)參數(shù),C保存主私鑰msk,把系統(tǒng)參數(shù)params(包括主公鑰mpk)發(fā)送給AI.

第一階段詢問(wèn)(Phase 1)在該階段,AI可向挑戰(zhàn)者C自適應(yīng)地進(jìn)行下列詢問(wèn):

公鑰詢問(wèn)AI提交任意用戶IDi的身份信息,C返回IDi所對(duì)應(yīng)的公鑰信息.

私鑰提取詢問(wèn)AI提交用戶IDi的身份信息,C返回IDi所對(duì)應(yīng)的私鑰.

公鑰替換AI提交(IDi,PKi′,SKi′),C將IDi的公鑰替換為PKi′.

證書詢問(wèn)AI提交(IDi,PKi),若IDi∈S*,C拒絕回復(fù)詢問(wèn);否則C運(yùn)行證書生成算法,返回(IDi,PKi)對(duì)應(yīng)的證書.

解密詢問(wèn)AI提交(IDi,Si,Hdri),其中IDi∈Si.C運(yùn)行解密算法返回對(duì)應(yīng)的ki或無(wú)效標(biāo)志⊥.

挑戰(zhàn)階段AI判斷Phase1詢問(wèn)結(jié)束后,C運(yùn)行廣播加密算法,計(jì)算(Hdr*,k*)=Enc(S*,PKS*),k*∈K,然后C隨機(jī)選擇λ∈{0,1},k∈K,令kλ=k*,k1-λ=k,將(Hdr*,k1-λ,kλ)返回給AI.

第二階段詢問(wèn)(Phase2):AI可繼續(xù)類似Phase1中的步驟進(jìn)行詢問(wèn),但解密詢問(wèn)時(shí)不可對(duì)Hdr*進(jìn)行詢問(wèn).

猜測(cè)Phase2詢問(wèn)結(jié)束后AI輸出λ′,若λ′=λ,則稱AI贏得該游戲.

我們定義AI贏得游戲1的優(yōu)勢(shì)為:

游戲2

初始化階段AII選擇目標(biāo)廣播集合S*,S*?SN.

系統(tǒng)參數(shù)設(shè)置挑戰(zhàn)者C運(yùn)行算法Setup,生成系統(tǒng)的主公/私鑰對(duì)(mpk,msk)以及其它系統(tǒng)參數(shù),將主私鑰msk和系統(tǒng)參數(shù)params(包括系統(tǒng)主公鑰mpk)都發(fā)送給敵手AII.

第一階段詢問(wèn)(Phase 1)在該階段,AII可以自適應(yīng)地向挑戰(zhàn)者C進(jìn)行下列詢問(wèn):

公鑰詢問(wèn)AII提交任意用戶IDi的身份信息,C返回IDi對(duì)應(yīng)的公鑰信息.

私鑰提取詢問(wèn)AII提交用戶IDi的身份信息,若IDi∈S*,C拒絕回復(fù)詢問(wèn);否則返回用戶IDi所對(duì)應(yīng)的私鑰.

公鑰替換AII提交(IDi,PKi′,SKi′),若IDi∈S*,C拒絕替換;否則C將IDi的公鑰替換為PKi′.

解密詢問(wèn)AII提交(IDi,Si,Hdri),其中IDi∈Si,C運(yùn)行解密算法返回對(duì)應(yīng)的ki或無(wú)效標(biāo)志⊥.

挑戰(zhàn)階段AII判斷Phase1詢問(wèn)結(jié)束后,C運(yùn)行廣播加密算法,生成(Hdr*,k*)=Enc(S*,PKS*),k*∈K,隨機(jī)選擇λ∈{0,1},k∈K,令kλ=k*,k1-λ=k,將(Hdr*,k1-λ,kλ)返回給AII.

第二階段詢問(wèn)(Phase 2)AII可類似Phase1中的步驟繼續(xù)進(jìn)行詢問(wèn),但解密詢問(wèn)時(shí)不可對(duì)目標(biāo)Hdr*進(jìn)行詢問(wèn).

猜測(cè)Phase2詢問(wèn)結(jié)束后AII輸出λ′,若λ′=λ,則稱AII贏得該游戲.

我們定義AII贏得游戲2的優(yōu)勢(shì)為:

注:敵手在進(jìn)行詢問(wèn)時(shí),允許敵手詢問(wèn)目標(biāo)廣播集合以外的所有用戶信息,因此本文給出的安全模型是可以抵抗完全聯(lián)合攻擊的.

4　基于證書廣播加密方案

在這部分中,首次提出了一個(gè)基于證書廣播加密方案,并對(duì)它進(jìn)行正確性分析.該方案由以下五個(gè)算法組成:

加密算法Enc該算法由廣播者運(yùn)行.廣播加密算法由一個(gè)密鑰封裝算法和一個(gè)安全的對(duì)稱加密算法共同來(lái)實(shí)現(xiàn):

步驟1廣播者選擇需要廣播的集合S?SN.

步驟2對(duì)于IDi∈S,廣播者依次計(jì)算hi=H1(τ‖IDi‖PKi),QIDi∈S=hiP+Q.

步驟4廣播者通過(guò)公開(kāi)的廣播信道廣播消息C=(Hdr,S,C0).

解密算法Dec該算法由用戶IDi(IDi∈S)運(yùn)行.在收到廣播密文C后,用戶IDi以其私鑰SKi、證書CertIDi,τ為輸入,按照下面的步驟計(jì)算,最后輸出C對(duì)應(yīng)的消息m或者無(wú)效標(biāo)志⊥:

步驟4驗(yàn)證H3(σ′,k′)是否等于H3(σ,k),若相等,則以對(duì)稱加密方案中的解密算法D返回m=Dk′(C0),否則返回⊥.

對(duì)于廣播的消息該方案只需要進(jìn)行一次加密,系統(tǒng)可以對(duì)g1=e(P,P)進(jìn)行預(yù)計(jì)算,加密算法中就不需要進(jìn)行雙線性對(duì)運(yùn)算,僅在解密算法中做一次雙線性對(duì)運(yùn)算,提高了計(jì)算效率.

正確性分析

本文的方案里,廣播集合里的合法用戶可將接收到的正確的廣播密文恢復(fù)出對(duì)應(yīng)的廣播消息.

(1)用戶IDi∈S收到廣播密文后計(jì)算:

5　安全性證明

下面根據(jù)3.2節(jié)提出的安全模型給出本方案的安全性證明.由于不同的敵手具備不同的能力,本文刻畫了兩個(gè)游戲來(lái)模擬不同敵手與挑戰(zhàn)者之間的交互,從而證明方案的安全性.本文提出的方案是由一個(gè)密鑰封裝算法和一個(gè)安全的對(duì)稱加密算法構(gòu)成,假定選取的對(duì)稱加密算法為自適應(yīng)選擇密文安全的算法,在進(jìn)行安全性證明時(shí),只對(duì)密鑰封裝算法部分進(jìn)行分析,分析敵手是否能由頭文件Hdr以不可忽略的優(yōu)勢(shì)區(qū)分出對(duì)稱加密算法的對(duì)稱密鑰k.由于是靜態(tài)敵手,所以在系統(tǒng)參數(shù)產(chǎn)生之前兩類敵手都需要先選定目標(biāo)廣播集合.

定理2如果存在概率多項(xiàng)式時(shí)間靜態(tài)敵手AI,經(jīng)過(guò)最多qPK次公鑰詢問(wèn)、qSK次私鑰詢問(wèn)、qr次公鑰替換詢問(wèn)、qH1次H1詢問(wèn)、qH2次H2詢問(wèn)、qC次證書詢問(wèn)、qd次解密詢問(wèn)后,在最多t時(shí)間內(nèi)以不小于ε的概率贏得游戲1,那么就存在一個(gè)算法可以在t′時(shí)間內(nèi)以不小于ε′的概率解決k-mBDHI問(wèn)題,其中k≥(qH1-w),ε′=(1-w/qt)qdε/qH2,w為廣播集合內(nèi)的用戶個(gè)數(shù),qt=(qPK+qSK+qr+qC+qd).

初始化階段AI選擇目標(biāo)廣播集合S*?SN,|S*|=w.

系統(tǒng)參數(shù)設(shè)置算法(Setup)B運(yùn)行算法Setup.B令系統(tǒng)主公鑰Q=sP,其中sP為k-mBDHI困難問(wèn)題的輸入,主私鑰為s未知.將系統(tǒng)參數(shù)params={ζ,G1,G2,e,q,P,Q,g1,g2,p,SN,pi,K,H1,H2,H3}發(fā)送給AI.

第一階段詢問(wèn)(Phase 1)B保存列表LAI:{IDi,PKi,SKi,hi,CertIDi,τ,δ},列表初始化為{⊥,⊥,⊥,⊥,⊥,0},列表LH2:{(gi,σi),ki},初始化為{(⊥,⊥),⊥}.在該階段,AI可以向B自適應(yīng)地進(jìn)行下列詢問(wèn):

公鑰詢問(wèn)AI提交任意用戶IDi的身份信息,B檢查L(zhǎng)AI:

(2)若IDi不為⊥,B直接返回IDi的公鑰PKi.

私鑰提取詢問(wèn)AI提交用戶IDi的身份信息,B檢查L(zhǎng)AI.

(2)若IDi不為⊥,B直接返回IDi的私鑰SKi.

公鑰替換AI提交(IDi,PKi′,SKi′),B直接更新列表LAI為:{IDi,PKi′,SKi′,⊥,⊥,1}.

H1詢問(wèn)AI提交用戶的身份信息IDi和公鑰信息PKi,B檢查L(zhǎng)AI:

(1)若IDi?S*,B隨機(jī)選擇hi,滿足hi∈(h1,h2,…,hk)且未曾出現(xiàn)過(guò),更新列表LAI為:{IDi,PKi,SKi,hi,⊥,δ},δ表示保持原狀.B返回hi.

H2詢問(wèn)AI提交(gi,σi),B檢查L(zhǎng)H2:

(1)若存在{(gi,σi),ki}元組,則B返回ki.

(2)若不存在{(gi,σi),ki}元組,B隨機(jī)選擇ki∈K且未曾出現(xiàn)過(guò),將{(gi,σi),ki}添加到LH2中,返回ki.

證書詢問(wèn)AI提交用戶IDi的身份信息,若IDi∈S*,B輸出⊥并退出(對(duì)目標(biāo)集合中用戶公鑰詢問(wèn)證書,拒絕詢問(wèn)),否則若IDi?S*則檢查L(zhǎng)AI,CertIDi,τ不為⊥時(shí),直接返回CertIDi,τ,否則:

解密詢問(wèn)AI對(duì)(IDi,Si,Hdri)進(jìn)行詢問(wèn),其中IDi∈Si.若IDi∈S*,則B失敗并退出;否則B按步驟計(jì)算生成(SKi,CertIDi,τ),運(yùn)行解密算法:

=e(P,P)ri

挑戰(zhàn)階段AI判斷Phase1詢問(wèn)結(jié)束后,B運(yùn)行廣播加密算法:

第二階段詢問(wèn)(Phase 2)AI可繼續(xù)進(jìn)行Phase1中的各種詢問(wèn),但解密詢問(wèn)時(shí)不可對(duì)(IDi,S*,Hdr*)進(jìn)行詢問(wèn),其中IDi∈S*.

猜測(cè)Phase2詢問(wèn)結(jié)束后AI猜測(cè)λ′∈{0,1}.B在LH2中隨機(jī)選擇{(gi,σi),ki},B輸出(gi)1/li作為k-mBDHI的解.

分析

下面分析B解決k-mBDHI困難問(wèn)題的概率:

B要解決k-mBDHI困難問(wèn)題就必須保證在與AI進(jìn)行交互時(shí)沒(méi)有失敗退出.由游戲模擬過(guò)程可知,當(dāng)AI對(duì)目標(biāo)集合內(nèi)用戶進(jìn)行解密詢問(wèn)時(shí),B挑戰(zhàn)失敗.記事件E1表示AI未對(duì)目標(biāo)集合內(nèi)用戶進(jìn)行解密詢問(wèn),其概率Pr[E1]=(1-w/qt)qd.

事件E2表示LH2中存在{(g*,σ*),k*},即AI對(duì)(g*,σ*)進(jìn)行過(guò)H2詢問(wèn),則Pr[λ′=λ]=Pr[λ′=λ|E2]Pr[E2]+Pr[λ′=λ|E2]Pr[E2]≥ε,若AI未對(duì)(g*,σ*)進(jìn)行H2詢問(wèn),而是隨機(jī)猜測(cè),則Pr[λ′=λ|E2]=1/2,即[E2] ≥[,可知Pr[E2]≥2Pr[λ′=λ]-1=ε.

事件E3表示B選擇了滿足需要的{(g*,σ*),k*}元組,其概率Pr[E3]≥1/qH2.

B要成功破解k-mDBDHI問(wèn)題必須保證事件E1,E2,E3同時(shí)發(fā)生,Pr[B Success]≥(1-w/qt)qd·ε·1/qH2=(1-w/qt)qdε/qH2,即若存在概率多項(xiàng)式時(shí)間的敵手AI能在t時(shí)間內(nèi)以不可忽略的優(yōu)勢(shì)ε贏得游戲1,則必然存在一個(gè)概率多項(xiàng)式時(shí)間的算法能夠以不小于ε′的概率解決k-mBDHI問(wèn)題,其中ε′=(1-w/qt)qdε/qH2.而由于k-mBDHI困難問(wèn)題是難解的,所以不存在概率多項(xiàng)式時(shí)間的敵手AI能在t時(shí)間內(nèi)以不可忽略的優(yōu)勢(shì)贏得游戲1,即該方案能夠抵抗第一類敵手攻擊.

定理3如果存在概率多項(xiàng)式時(shí)間靜態(tài)敵手AII,經(jīng)過(guò)最多qPK次公鑰詢問(wèn)、qSK次私鑰詢問(wèn)、qr次公鑰替換詢問(wèn)、qd次解密詢問(wèn)后,在最多t時(shí)間內(nèi)以不小于ε的概率贏得游戲2,那么就存在一個(gè)算法可以在t′時(shí)間內(nèi)以不小于ε′的概率解決DDH問(wèn)題,其中ε′=(1-w/qt)qd(1+ε)/2,w為廣播集合內(nèi)的用戶個(gè)數(shù),qt=(qPK+qSK+qr+qd).

證明(g,ga,gb,T)為一個(gè)DDH問(wèn)題的輸入,構(gòu)造算法B,在游戲中B模擬挑戰(zhàn)者與敵手AII進(jìn)行交互,最后判斷T是否等于gab.

初始化階段AII選擇目標(biāo)廣播集合S*?SN,|S*|=w.

第一階段詢問(wèn)(Phase 1)B保存列表LAII:{IDi,PKi,SKi,δ},初始化為{⊥,⊥,⊥,0},AII可以自適應(yīng)地向挑戰(zhàn)者B進(jìn)行下列詢問(wèn):

公鑰詢問(wèn)AII提交任意用戶IDi的身份信息,B檢查L(zhǎng)AII:

(2)若IDi已存在,B直接返回IDi的公鑰PKi.

私鑰提取詢問(wèn)AII提交用戶IDi的身份信息,若IDi∈S*,B拒絕并輸出⊥退出,若IDi?S*,B檢查L(zhǎng)AII:

(2)若IDi已存在,B直接返回IDi的私鑰SKi.

公鑰替換AII提交(IDi,PKi′,SKi′),若IDi∈S*,B拒絕替換并輸出⊥退出,否則B直接更新列表LAI為:{IDi,PKi′,SKi′,1}.

解密詢問(wèn)AII對(duì)(IDi,Si,Hdri)進(jìn)行解密詢問(wèn),其中IDi∈Si.若IDi∈S*,則B失敗并退出;否則,B同時(shí)擁有系統(tǒng)主密鑰和用戶私鑰,直接運(yùn)行解密算法:

=σi.

(2)根據(jù)riQIDi再計(jì)算

e(riQIDi,CertIDi,τ)1/xi2

=e(P,P)ri

挑戰(zhàn)階段AII決定Phase 1詢問(wèn)結(jié)束后,B運(yùn)行廣播加密算法:

(1)對(duì)于IDi∈S*,B計(jì)算QIDi∈S*=hiP+Q.

第二階段詢問(wèn)(Phase 2)AII可類似Phase1中的步驟繼續(xù)進(jìn)行詢問(wèn),但解密詢問(wèn)時(shí)不可以對(duì)(IDi,S*,Hdr*)進(jìn)行詢問(wèn),其中IDi∈S*.

猜測(cè)Phase2詢問(wèn)結(jié)束后猜測(cè)λ′∈{0,1},若λ′=λ,則B輸出T=gab,否則輸出T≠gab.

分析

下面分析B成功破解DDH問(wèn)題的概率:

B要解決DDH困難問(wèn)題就必須保證在與AII進(jìn)行交互時(shí)沒(méi)有失敗退出.由游戲模擬過(guò)程可知,當(dāng)AII對(duì)目標(biāo)集合內(nèi)用戶進(jìn)行解密詢問(wèn)時(shí),B挑戰(zhàn)失敗.記事件E1表示AII未對(duì)目標(biāo)集合內(nèi)用戶進(jìn)行解密詢問(wèn),其概率Pr[E1]=(1-w/qt)qd.

E2表示在AII未退出游戲、輸出猜測(cè)后B解決DDH困難問(wèn)題的概率,則Pr[E2]=Pr[λ′=λ|T=gab]·Pr[T=gab]+Pr[λ′≠λ|T≠gab]·Pr[T≠gab].T=gab時(shí)AII能夠區(qū)分λ′的概率不小于(1/2+ε),即Pr[λ′=λ|T=gab]≥(1/2+ε),T≠gab時(shí)AII不能從各種詢問(wèn)中獲得有用信息,只能隨機(jī)猜測(cè)λ′,即Pr[λ′=λ|T≠gab]=Pr[λ′≠λ|T≠gab]=1/2,因此B在AII輸出猜測(cè)后解決DDH困難問(wèn)題的概率Pr[E2]≥(1/2+ε)·1/2+1/2·1/2=(ε+1)/2.

B要成功破解DDH困難問(wèn)題必須保證事件E1,E2同時(shí)發(fā)生,即Pr[B Success]=Pr[E1]·Pr[E2]≥(1-w/qt)qd(1+ε)/2.

若存在概率多項(xiàng)式時(shí)間的敵手AII能在t時(shí)間內(nèi)以不可忽略的優(yōu)勢(shì)ε贏得游戲2,則必然存在一個(gè)概率多項(xiàng)式時(shí)間的算法能夠以不小于ε′的概率解決DDH問(wèn)題,其中ε′=(1-w/qt)qd(1+ε)/2.而由于DDH問(wèn)題是難解的,所以不存在概率多項(xiàng)式時(shí)間的敵手AII能在t時(shí)間內(nèi)以不可忽略的優(yōu)勢(shì)贏得游戲2,即該方案是能抵抗第二類敵手攻擊的.

6　結(jié)論

本文構(gòu)造了一個(gè)高效的基于證書廣播加密方案,并證明了方案在自適應(yīng)選擇密文攻擊下是安全的.在基于證書廣播加密方案中,用戶的密鑰由用戶自己選擇,而不是由廣播中心分發(fā),避免了密鑰托管的問(wèn)題,同時(shí),由于證書通過(guò)公開(kāi)信道發(fā)送,也就不需要建立安全信道.對(duì)于需要廣播的消息,廣播發(fā)送者只需要進(jìn)行一次加密.系統(tǒng)可以對(duì)雙線性對(duì)進(jìn)行預(yù)計(jì)算,因此在加密過(guò)程中就不需要進(jìn)行雙線性對(duì)的運(yùn)算,在解密時(shí)只要做一次雙線性對(duì)運(yùn)算,提高了計(jì)算效率.并且該方案可以實(shí)現(xiàn)用戶的動(dòng)態(tài)加入和撤銷,不需要更新其它用戶的密鑰信息,新添加的用戶只需將公鑰信息添加到公鑰列表,而撤銷的用戶只需刪除其公鑰信息.但本文給出的具體構(gòu)造中密文長(zhǎng)度與廣播集合中用戶數(shù)量呈線性增長(zhǎng),下一步將重點(diǎn)研究密文定長(zhǎng)廣播加密方案.

[1]Naor D,Naor M,Lotspiech J.Revocation and tracing schemes for stateless receiver[A].Advances in Cryptography-CRYPTO 2001[C].LNCS 2139,Berlin:Springer-Verlag,2001.41-62.

[2]Boneh D,Gentry C,Waters B.Collusion resistant broadcast encryption with short ciphertexts and private keys[A].Advances in Cryptology-CRYPTO 2005[C].LNCS 3621,Berlin:Springer-Verlag,2005.258-275.

[3]Boneh D,Waters B.A fully collusion resistant broadcast,traces,and revokes system[A].Proceedings of the 13th ACM Conference on Computer and Communications Security[C].ACM New York,NY,USA:2006.211-220.

[4]Liu Y R,Tzeng W G.Public key broadcast encryption with low number of keys and constant decryption time[A].PKC 2008[C].LNCS 4939,Berlin:Springer-Verlag,2008.380-396.

[5]Delerablée C.Identity-based broadcast encryption with constant size ciphertexts and private keys[A].Advances in Cryptology-ASIACRYPT 2007[C].LNCS 4833,Berlin:Springer-Verlag,2007.200-215.

[6]Gentry C,Waters B.Adaptive security in broadcast encryption systems (with short ciphertexts)[A].Advances in Cryptology-EUROCRYPT 2009[C].LNCS 5479,Berlin:Springer-Verlag,2009.171-188.

[7]Boneh D,Waters B.Zhandry M.Low overhead broadcast encryption from multilinear maps[A].Advances in Cryptology-CRYPTO 2014[C].LNCS 8616,Berlin:Springer-Verlag,2014.206-223.

[8]Tan Z W,Liu Z J,Xiao H G.A fully public key tracing and revocation scheme provably secure against adaptive adversary[J].Journal of Software,2005,16(7):1333-1343.

[9]Phan D H,Pointcheval D,Strefler M.Decentralized dynamic broadcast encryption[A].Security and Cryptography for Networks[C].LNCS 7485,Berlin:Springer-Verlag,2012.166-183.

[10]Wu Q H,Qin B,Zhang L,Ferrer J D,Farràs O.Bridging broadcast encryption and group key agreement[A].Advances in Cryptology-ASIACRYPT 2011[C].LNCS 7073,Berlin:Springer-Verlag,2011.143-160.

[11]Hofheinz D,Striecks C.A generic view on trace-and-revoke broadcast encryption schemes[A].Topics in Cryptology-CT-RSA 2014[C].LNCS 8366,Berlin:Springer-Verlag,2014.48-63.

[12]Wee H.Threshold and revocation cryptosystems via extractable hash proofs[A].Advances in Cryptology-EUROCRYPT 2011[C].LNCS 6632,Berlin:Springer-Verlag,2011.589-609.

[13]Boneh D,Zhandry M.Multiparty key exchange,efficient traitor tracing,and more from indistinguishability obfuscation[A].Advances in Cryptology-CRYPTO 2014[C].LNCS 8616,Berlin:Springer-Verlag,2014.480-499.

[14]Gentry C.Certificate-based encryption and the certificate revocation problem[A].Advances in Cryptology-EUROCRYPT 2003[C].LNCS 2656,Berlin:Springer-Verlag,2003.272-293.

[15]Morillo P,Ràfols C.Certificate-based encryption without random oracles[DB/OL].Cryptology ePrint Archive,Report 2006/12,2006.

[16]Waters B.Efficient identity-based encryption without random oracles[A].Advances in Cryptology-EUROCRYPT 2005[C].LNCS 3494,Berlin:Springer-Verlag,2005.114-127.

[17]Dodis Y,Katz J.Chosen-ciphertext security of multiple encryptions[A].TCC 2005[C].LNCS 3378,Berlin:Springer-Verlag,2005.188-209.

[18]Galindo D,Morillo P,Ràfols C.Improved certificate-based encryption in the standard model[J].Journal of Systems and Software,2008,81(7):1218-1226.

[19]陸陽(yáng),李繼國(guó),肖軍模.一個(gè)高效的基于證書的加密方案[J].計(jì)算機(jī)科學(xué),2009,36(9):28-31.

Lu Y,Li J G,Xiao J M.Efficient certificate-based encryption scheme[J].Computer Science,2009,36(9):28-31.(in Chinese )

[20]Li J G,Huang X Y,Hong M X,Zhang Y C.Certificate-based signcryption with enhanced security features[J].Computers and Mathematics with Applications.2012,64(6):1587-1601.

[21]Li J G,Wang Z W,Zhang Y C.Provably secure certificate-based signature scheme without pairings[J].Information Sciences,2013,233(6):313-320.

[22]Selvi S,Vivek S,Shukla D.Efficient and provable secure certificateless multi-receiver signcryption[A].ProvSec 2008[C].LNCS 5324,Berlin:Springer-Verlag,2008.52-67.

[23]Al-Riyami S S,Paterson K G.Certificateless public key cryptography[A].Advances in Cryptology-ASIACRYPT 2003[C].LNCS 2894,Berlin:Springer-Verlag,2003.452-473.

[24]Li J G,Huang X Y,Mu Y,Susilo W,Wu Q H.Certificate-based signature:security model and efficient construction[A].Advances in Cryptology-EuroPKI’07[C].LNCS 4582,Berlin:Springer-Verlag,2007.110-125.

[25]Li J G,Huang X Y,Mu Y,Susilo W,Wu Q H.Constructions of certificate-based signature secure against key replacement attacks[J].Journal of Computer Security,2010,18(3):421-449.

[26]Li J G,Huang X Y,Zhang Y C,Xu L Z.An efficient short certificate-based signature scheme[J].Journal of Systems and Software,2012,85(2):314-322.

李繼國(guó)(通信作者)男,1970年生于黑龍江富裕,博士,教授,博士生導(dǎo)師,主要研究領(lǐng)域?yàn)樾畔踩?、密碼學(xué)理論與技術(shù)、云計(jì)算安全等.

E-mail:ljg1688@163.com

張亦辰女,1971年生于黑龍江齊齊哈爾,學(xué)士,博士研究生,講師,主要研究領(lǐng)域?yàn)槊艽a學(xué)理論與技術(shù).

A Provably Secure Certificate-Based Broadcast Encryption Scheme

LI Ji-guo,ZHANG Yi-chen,WEI Xiao-xia

(CollegeofComputerandInformationEngineering,HohaiUniversity,Nanjing,Jiangsu210098,China)

Broadcast encryption allows a sender to securely broadcast to any subset of the group members.However,its security heavily depends on broadcast centre to generate and distribute decryption secret keys for group members.In order to solve the above problem,we propose the notion of certificate-based broadcast encryption,describe the formal definition and security model of the certificate-based broadcast encryption.Furthermore,we also provide an efficient certificate-based broadcast encryption scheme.In our scheme,the decryption key includes user’s private key and a certificate,where the private key is chosen by user himself,and the certificate is generated by certification authority.Therefore,our scheme overcomes the key escrow problem.In addition,our scheme is efficient,because it needs only one paring in decryption algorithm and paring operation in encryption algorithm can be pre-computed.

broadcast encryption;certificate-based encryption;bilinear paring

2014-07-29;

2014-11-28責(zé)任編輯:馬蘭英

國(guó)家自然科學(xué)基金(No.61272542);中央高校基本科研項(xiàng)目(No.2013B07014)

TP309

A

0372-2112 (2016)05-1101-10

電子學(xué)報(bào)URL:http://www.ejournal.org.cn10.3969/j.issn.0372-2112.2016.05.013