高效可撤銷(xiāo)的身份基在線離線加密方案

王占君，馬海英，王金華，李 燕

1.南通大學(xué) 理學(xué)院，江蘇 南通 226019

2.南通大學(xué) 信息科學(xué)技術(shù)學(xué)院，江蘇 南通 226019

1 引言

1984 年，Shamir 首次提出了身份基加密（Identity-Based Encryption，IBE）[1]的概念。在IBE 中，用戶可以使用一個(gè)字符串（例如，家庭住址、身份證號(hào)、email地址等）表示自己的身份信息，密鑰生成中心（Key Generation Center，KGC）利用該身份信息和系統(tǒng)主密鑰為其生成用戶私鑰，加密者利用接收者身份信息和系統(tǒng)公鑰加密消息。IBE 刪除了傳統(tǒng)公鑰加密機(jī)制中證書(shū)驗(yàn)證過(guò)程，提高了加密效率。隨后，學(xué)者們提出了許多實(shí)用的IBE 方案[2-4]，然而，在實(shí)際應(yīng)用，用戶私鑰可能會(huì)泄漏、丟失或者到期，因此，IBE需要提供一種有效的成員私鑰撤銷(xiāo)機(jī)制。

針對(duì)IBE的成員撤銷(xiāo)問(wèn)題，現(xiàn)有的解決方案利用完全子樹(shù)和子集不同方法可以實(shí)現(xiàn)成員撤銷(xiāo)[5]。由于利用完全子樹(shù)撤銷(xiāo)方法，用戶僅需存儲(chǔ)較短的私鑰，Boldyreva等人[6]基于該方法提出了成員撤銷(xiāo)的IBE方案。該IBE方案利用用戶身份和時(shí)間進(jìn)行加密，KGC 根據(jù)最新成員撤銷(xiāo)列表，周期性地發(fā)布未撤銷(xiāo)用戶的更新鑰，使得未撤銷(xiāo)用戶利用相應(yīng)的更新鑰可以重構(gòu)自己的解密鑰。由于更新鑰的工作量過(guò)大，導(dǎo)致KGC 可能構(gòu)成系統(tǒng)的瓶頸。該方案[6]僅滿足選擇身份模型下的安全性。為了提高系統(tǒng)的安全性，文獻(xiàn)[7]提出適應(yīng)性安全的可撤銷(xiāo)IBE 方案，文獻(xiàn)[8-10]在此基礎(chǔ)上進(jìn)一步增強(qiáng)系統(tǒng)安全，提出了抗密鑰暴露攻擊的可撤銷(xiāo)IBE 方案。然而，加密過(guò)程需要執(zhí)行一些橢圓曲線上的冪乘運(yùn)算，很難適用于輕量級(jí)設(shè)備。

為了提高 IBE 中的加密效率，2008 年，Guo 等人提出了身份基在線離線加密方案[11]，將加密過(guò)程分解為離線和在線兩個(gè)階段，離線階段首先對(duì)大部分加密運(yùn)算進(jìn)行預(yù)處理生成離線密文，在線階段利用離線密文執(zhí)行少量簡(jiǎn)單運(yùn)算生成密文，提高了實(shí)際加密的效率。隨后，研究人員提出了一系列高效的身份基在線離線加密方案[12-16]和屬性基在線離線加密方案[17-18]。然而，現(xiàn)有的身份基在線離線加密方案都不能實(shí)現(xiàn)用戶撤銷(xiāo)的功能。

本文提出了一種高效的可撤銷(xiāo)成員的身份基在線離線加密。利用完全子樹(shù)方法實(shí)現(xiàn)用戶的撤銷(xiāo)，首先，生成一顆完全二叉樹(shù)，每個(gè)節(jié)點(diǎn)指定一個(gè)一次多項(xiàng)式f(x)=ax+1，利用該多項(xiàng)式將1 分解成兩個(gè)份額f(1)和f(T)，其中，T為時(shí)間且大于1，利用份額f(1)來(lái)生成用戶的身份私鑰，利用f(T)來(lái)生成用戶的更新鑰。密鑰生成中心周期性的發(fā)布更新鑰，任意非撤銷(xiāo)用戶可以重構(gòu)自己的解密鑰。由于所有撤銷(xiāo)用戶都擁有相同的份額f(1)，其聯(lián)合起來(lái)也不能重構(gòu)解密鑰，從而該方案可以抵抗聯(lián)合攻擊。為了減輕輕量級(jí)設(shè)備加密的負(fù)擔(dān)，利用在線離線技術(shù)，將加密過(guò)程分解為離線階段和在線階段。在得知消息和接受者身份前，離線階段執(zhí)行大部分的加密工作。一旦得知消息和接受者身份之后，輕量級(jí)設(shè)備利用離線密文經(jīng)過(guò)少量簡(jiǎn)單運(yùn)算即可快速生成密文。特別地，離線階段可在空閑時(shí)間利用高性能計(jì)算機(jī)執(zhí)行。與相關(guān)知名方案相比，本文方案不僅提高了KGC 生成更新鑰的效率，而且極大地減輕了輕量級(jí)設(shè)備的加密負(fù)擔(dān)。

2 雙線性對(duì)和DBDHI假設(shè)

雙線性對(duì)：設(shè)G和GT都是素?cái)?shù)p階的循環(huán)群，g是群G的生成元，e:G×G→GT是一個(gè)映射，且滿足：（1）雙線性，對(duì)?u,v∈G,β,δ∈Z，則e(uδ,vβ)=e(u,v)δβ；（2）非退化性，e(g,g)≠1；（3）可計(jì)算性：對(duì) ?u,v∈G，可在多項(xiàng)式時(shí)間內(nèi)計(jì)算e(u,v)，則稱(chēng)e為一個(gè)雙線性對(duì)。

2(l+1)-DBDHI 假設(shè)：設(shè)g是群G的生成元，x∈，給定一個(gè)2(l+2)元組，則任意多項(xiàng)式時(shí)間算法A判定T=e(g,g)1/x或T是GT中的隨機(jī)元素的優(yōu)勢(shì)都是可以忽略的。

3 RIBOOE定義和安全模型

一個(gè)可撤銷(xiāo)成員的身份基在線離線加密（RIBO0E）方案由初始化（Setup）、私鑰生成（Genkey）、更新鑰生成（Updatekey）、解密鑰生成（Derivekey）、離線加密(Encoff)、在線加密 (Encon)、解密（Dec）、撤銷(xiāo)（Revoke）算法構(gòu)成。

Setup（λ，Nmax）→PP,MK,RL,ST。KGC 運(yùn)行初始化算法，輸入安全參數(shù)λ和用戶最大個(gè)數(shù)Nmax，輸出系統(tǒng)主密鑰MK，公共參數(shù)PP，撤銷(xiāo)列表RL，狀態(tài)ST。

Genkey(ID,MK,ST,PP)→SKID，ST′。KGC運(yùn)行私鑰生成算法，輸入身份ID、管理員密鑰MK，狀態(tài)ST和公共參數(shù)PP，輸出ID的私鑰SKID和更新的狀態(tài)ST′。

Updatekey(T,PP,MK,RL,ST)→UKT,R。KGC運(yùn)行更新鑰生成算法，輸入時(shí)間T、公共叁數(shù)PP、系統(tǒng)主密鑰MK、撤銷(xiāo)列表RL狀和態(tài)ST，輸出T時(shí)刻的更新鑰UKT,R其中R為T(mén)時(shí)刻的撤銷(xiāo)身份集合。

Derivekey (SKID,UKT,R,PP)→DKID,T/⊥。用戶運(yùn)行解密鑰生成算法，輸入私鑰SKID，更新鑰UKT,R和公共參數(shù)PP，輸出解密密鑰DKID,T或失敗符號(hào)⊥。

Encoff(PP)→CToff。用戶可以利用高性能設(shè)備在空閑時(shí)間運(yùn)行離線加密算法，輸入公共參數(shù)PP，輸出離線密文CToff。

Encon(PP,ID,T,M,CToff)→CTID,T。用戶利用輕量級(jí)設(shè)備運(yùn)行在線加密算法，輸入公共參數(shù)PP、身份ID、時(shí)間T、消息M和離線密文CToff，輸出密文CTID,T。

Dec (CTID,T,DKID',T',PP)→M/⊥。接收者運(yùn)行解密算法，輸入密文CTID,T、解密鑰DKID',T'和公共參數(shù)PP，當(dāng)ID=ID′且T=T′時(shí)，輸出消息M，否則輸出失敗符號(hào)⊥。

Revoke(ID,T,RL,ST)→RL′。KGC 運(yùn)行撤銷(xiāo)算法，輸入身份ID、時(shí)間T、撤銷(xiāo)列表RL和狀態(tài)ST，輸出更新后的撤銷(xiāo)列表RL′。

RIBOOE的安全性由攻擊者A和挑戰(zhàn)者C之間的游戲來(lái)定義如下。

開(kāi)始：A提交挑戰(zhàn)身份ID*、挑戰(zhàn)時(shí)間T*、T*時(shí)刻的撤銷(xiāo)列表RL*給挑戰(zhàn)者C。

初始化：挑戰(zhàn)者C運(yùn)行Setup算法，生成系統(tǒng)主密鑰MK、撤銷(xiāo)列表RL、狀態(tài)ST、公共參數(shù)PP，并將PP發(fā)送給敵手A。

階段1 敵手A可以適應(yīng)性地詢問(wèn)如下3個(gè)預(yù)言機(jī)。

（1）私鑰生成預(yù)言機(jī)OSK（·），敵手A 提交身份ID給C，C 運(yùn)行Genkey(ID,MK,ST,PP)算法，返回SKID給A。

（2）更新鑰生成預(yù)言機(jī)OUK（·），敵手A 提交時(shí)間T給C，C運(yùn)行Updatekey(T,PP,MK,RL,ST)算法，返回UKT,R給A。

（3）撤銷(xiāo)預(yù)言機(jī)ORev（·，·），敵手A提交身份ID和時(shí)間T給C，C 運(yùn)行Revoke(ID,T,RL,ST)算法，并返回新的撤銷(xiāo)列表RL′給A。如果敵手A 詢問(wèn)過(guò)，則C必須在T*時(shí)刻之前撤銷(xiāo)掉用戶ID*。

挑戰(zhàn)：敵手A提交兩個(gè)長(zhǎng)度相等的消息M0，M1給C，C隨機(jī)選擇μ∈{0,1}，運(yùn)行Encon(PP,ID,T,M,CToff)并將，返回給A。

階段2 與Phase1相同。

猜測(cè)：A輸出μ的猜測(cè)值μ′，如果μ′=μ，則稱(chēng)A贏得該安全性游戲。

敵手A的優(yōu)勢(shì)AdvRIBOOE=|Pr[μ=μ′]-1/2|。如果任意多項(xiàng)式時(shí)間敵手A 贏得上述游戲的優(yōu)勢(shì)都是可以忽略的，則稱(chēng)RIBOOE 在選擇撤銷(xiāo)身份列表（Selective-Revocation-List）模型下是安全的。

4 RIBOOE方案

本文方案利用完全子樹(shù)方法撤銷(xiāo)用戶。首先生成一棵完全二叉樹(shù)，每個(gè)節(jié)點(diǎn)指定一個(gè)一次多項(xiàng)式f(x)，使得f(0)=1。每個(gè)用戶被指定到一個(gè)葉子節(jié)點(diǎn)，獲得從其葉子節(jié)點(diǎn)到根節(jié)點(diǎn)路徑上每個(gè)節(jié)點(diǎn)處的身份私鑰。利用X=e(g,g)s加密消息。給定T時(shí)刻的撤銷(xiāo)用戶集合R，KGC生成非撤銷(xiāo)用戶的覆蓋集合，為覆蓋集合中的每個(gè)節(jié)點(diǎn)生成更新鑰，使得未撤銷(xiāo)用戶利用更新鑰可以計(jì)算Xf(T)，利用身份私鑰計(jì)算Xf(1)，由于f(x)為一次函數(shù)，利用Xf(T)和Xf(1)可以算出Xf(0)，可以成功解密密文。特別地，撤銷(xiāo)用戶僅能計(jì)算Xf(1)，即使任意多個(gè)撤銷(xiāo)用戶聯(lián)合起來(lái)也得不到f(x)上的其他點(diǎn)，不能重構(gòu)函數(shù)f(x)，所以，無(wú)法獲知f(0)的值，導(dǎo)致撤銷(xiāo)用戶解密失敗。因此，本文方案滿足抗聯(lián)合攻擊性。

Setup(λ,Nmax)：該算法輸入安全參數(shù)λ和用戶最大個(gè)數(shù)Nmax，生成素?cái)?shù)p階的雙線性群e:G×G→GT，令g為G的生成元。隨機(jī)選擇，計(jì)算，，生成存放(ID,u)的用戶列表UL，存放(u,fu(x))的函數(shù)列表FL。設(shè)M為消息空間，|M|=nM，選擇Hash 函數(shù)，然后，生成一棵完全二叉樹(shù)BT，使其至少有Nmax個(gè)葉子節(jié)點(diǎn)。對(duì)該樹(shù)的任意葉子節(jié)點(diǎn)u，隨機(jī)選擇一個(gè)一次函數(shù)fu(x)，使得fu(0)=1，并存放(u,fu(x))到FL。最后，輸出系統(tǒng)主密鑰MK=(y1,y2,FL)、撤銷(xiāo)用戶列表RL、狀態(tài)ST=(BT,UL) 和公共參數(shù)PP=(g,Y1,Y2,e(g,g),H1,H2)。

Genkey(ID,MK,ST,PP)：該算法輸入身份ID、系統(tǒng)主密鑰MK，狀態(tài)ST和公共參數(shù)PP。首先，選擇一個(gè)未使用的葉子節(jié)點(diǎn)u，將ID指定給葉子節(jié)點(diǎn)u，并保存該元組(ID,u)到UL中。然后，對(duì)于任意節(jié)點(diǎn)z∈Path(u)，檢索函數(shù)列表FL={(u,fu(x))|?u∈BT}，計(jì)算：

最后，輸出更新的狀態(tài)ST和用戶私鑰SKID={Path(u),。

Updatekey(T,PP,MK,RL,ST)：該算法輸入時(shí)間T、公共叁數(shù)PP、系統(tǒng)主密鑰MK、撤銷(xiāo)列表RL和狀態(tài)ST。首先利用RL定義T時(shí)間的撤銷(xiāo)用戶集合R，即如果存在 (ID′,T′)∈RL且T′≤T，則ID′∈R，根據(jù)用戶列表UL定義撤銷(xiāo)集合索引RI，得到撤銷(xiāo)用戶的覆蓋集合CVRI。然后，對(duì)任意z∈CVRI，計(jì)算：

最后，輸出更新的狀態(tài)和更新鑰UKT,R={CVRI,{Ez}z∈CVRI}。

DeriveKey(SKID,UKT,R,PP)：該算法輸入SKID={Path(u),{Dz}z∈Path(u)} ，UKT,R={CVRI,{Ez}z∈CVRI} ，如果ID?R，由完全子樹(shù)方法得z∈Path(u)∩CVRI，得到解密鑰：

否則輸出⊥。

Encoff(PP) ：該算法輸入公共參數(shù)PP，隨機(jī)選擇s,δ,β∈Zp，計(jì)算R=e(g,g)s，R0=H2(R)，R1=(Y1gδ)ss，R2=(Y2gδ)s，輸出離線密文CToff=(R0,R1,R2,s,δ,β)。

Encon(PP,ID,T,M,CToff)：該算法輸入公共參數(shù)PP、身份ID、時(shí)間T、消息M和離線密文CToff，計(jì)算C=R0⊕M,C1=s(H1(ID)-δ)，C2=s(T-β)，輸出密文CTID,T=(C,C1,C2,R1,R2)

Dec(CTID,T,DKID',T',PP)該算法輸入密文CTID,T，解密鑰DKID',T'和公共參數(shù)PP，當(dāng)ID=ID′且T=T′時(shí)，則計(jì)算：

輸出明文M=H2(e(g,g)s)。

Revoke(ID,T,RL,ST)：該算法輸入身份ID、時(shí)間T、撤銷(xiāo)列表RL、狀態(tài)ST=(T,UL)，如果(ID,*)∈UL，輸出⊥；否則將(ID,T)加入到RL中，輸出更新后的撤銷(xiāo)列表RL′。

5 安全性證明

定理如果2(l+1)-DBDHI假設(shè)成立，則本文RIBOOE方案在選擇撤銷(xiāo)身份列表模型下是安全的。

證明假定存在一個(gè)敵手A 能攻破RIBOOE 方案，則可以構(gòu)造一個(gè)算法B攻破2(l+1)-DBDHI假設(shè)。

開(kāi)始：A 提交挑戰(zhàn)身份ID*、挑戰(zhàn)時(shí)間T*和T*時(shí)刻的挑戰(zhàn)撤銷(xiāo)列表RL*。

（1）?z∈FixedSubset(ID*)，隨機(jī)選擇y∈Zp，隱式的保存(x=H1(ID*),αy)到FL；

（2）?z?FixedSubset(ID*)，隨機(jī)選擇y∈Zp，隱式的保存(x=H1(T*),αy)到FL，注意一次函數(shù)fu(x)被兩個(gè)點(diǎn)（0，1）和(x,αy)所確定。

B設(shè)置撤銷(xiāo)列表RL和狀態(tài)ST=(BT,UL)，隨機(jī)選擇π1，π2∈{1,2,…,l}，Iπ1，w1,w2,…,wπ1-1,wπ1+1,…,wl∈Zp，當(dāng)i≠π1時(shí)定義，對(duì)系統(tǒng)運(yùn)行時(shí)間T1,…,…,Tl，計(jì)算 2(l-1) 次多項(xiàng)式：

構(gòu)造生成元：

當(dāng)i{1,…,l}{π1}時(shí)，B計(jì)算：

當(dāng)i∈{1,…,l}{π2}時(shí)，B計(jì)算：

階段1 A 適應(yīng)性的進(jìn)行哈希函數(shù)隨機(jī)預(yù)言機(jī)、私鑰、更新鑰詢問(wèn)。

針對(duì)哈希函數(shù)H1的詢問(wèn)，假設(shè)第v次詢問(wèn)的身份為IDv，B設(shè)置H1(IDv)=Iv。

針對(duì)身份IDi的私鑰詢問(wèn)，當(dāng)IDi≠I(mǎi)D*時(shí)，首先構(gòu)造點(diǎn)（0，1）的臨時(shí)鑰部件：

若(IDi,*)∈UL，從UL中下載(IDi,u)，否則隨機(jī)選擇u使得u≠u(mài)*∧(*,u)?UL，并保存(IDi,u)到UL，然后得到Pathu。對(duì)節(jié)點(diǎn)z∈Pathu，檢索函數(shù)列表(u,fu(x))，若z∈FixedSubset(ID*)，此時(shí)(x=H1(ID*,αy)：

若z?FixedSubset(ID*)，此時(shí) (x=T*,αy)：

當(dāng)IDi=ID*時(shí)，此時(shí)必有ID*∈R*，從UL中下載(ID*,u*)，得到。對(duì)，此時(shí)(x=H1(ID*),αy)：

如果敵手A 進(jìn)行時(shí)間Ti的更新鑰詢問(wèn)，當(dāng)Ti≠T*時(shí)，構(gòu)造點(diǎn)（0，1）的臨時(shí)鑰部件：

定義Ti時(shí)刻的撤銷(xiāo)用戶集合R，并得到覆蓋集合CVRI，對(duì)節(jié)點(diǎn)z∈CVRI，檢索函數(shù)列表 (u,fu(x))。若z∈FixedSubset(ID*)，此時(shí) (x=H1(ID*),αy)：

若z?FixedSubset(ID*)，此時(shí) (x=T*,αy)：

當(dāng)Ti=T*時(shí)，定義T*時(shí)刻的撤銷(xiāo)用戶集合R*，并得到覆蓋集合CVRI*。當(dāng)ID*∈R*，F(xiàn)ixedSubset(ID*)={Path(u*)}，CVRI*∩FixedSubset(ID*)=? ，當(dāng)ID*?R*，F(xiàn)ixedSubset(ID*)=? ，CVRI*?FixedSubset(ID*)=? ，總之CVRI*?FixedSubset(ID*)=?。對(duì)節(jié)點(diǎn)z∈CVRI*，檢索函數(shù)列表(u,fu(x))。由z?FixedSubset(ID*)，注意此時(shí) (x=T*,αy)，計(jì)算：

構(gòu)造更新鑰為UKT,R=(CVRI,{Ez}z∈CVRI)。

挑戰(zhàn)：A 提交兩個(gè)消息M0、M1，B 隨機(jī)選擇μ∈{0,1}，d,m∈Zp，構(gòu)造挑戰(zhàn)密文為：B隱式的設(shè)置s=1/α，δ=H1(ID*)+α(d+1),β=T*+α(m+1)：

當(dāng)Z=e(P,P)1/α?xí)r ，C=Mμe(P,P)s，C1,C2,R1,R2為Mμ的密文，當(dāng)Z∈GT時(shí)，C,C1,C2,R1,R2為隨機(jī)消息的密文。

猜測(cè)：A 輸出猜測(cè)值μ′∈{0,1}。當(dāng)μ′=μ時(shí)，B 輸出1，否則B輸出0。

6 性能比較和實(shí)驗(yàn)分析

如表1 將本文RIBOOE 方案和兩個(gè)相關(guān)方案在效率和功能方面進(jìn)行了比較，其中，假設(shè)素?cái)?shù)p階的雙線性群e:G×G→GT中，E表示群G中的冪乘運(yùn)算，mc表示Zp中的模乘運(yùn)算，r表示撤銷(xiāo)用戶的個(gè)數(shù)，Nmax表示用戶最大個(gè)數(shù)。特別地，群G中冪乘的計(jì)算量遠(yuǎn)遠(yuǎn)大于Zp中模乘運(yùn)算的計(jì)算量。

表1 本文方案與3個(gè)知名方案的性能比較

由表 1 可知，本文方案與 BGK 方案[6]和 JK[8]都能實(shí)現(xiàn)用戶撤銷(xiāo)，但BGK 的加密過(guò)程需要執(zhí)行橢圓曲線上的12 個(gè)冪乘運(yùn)算，輕量級(jí)設(shè)備難以在短時(shí)間內(nèi)完成加密任務(wù)，且需要消耗大量電能。本文方案將加密分解成離線和在線兩個(gè)階段，加密者可以利用高性能計(jì)算機(jī)在可信環(huán)境下執(zhí)行離線加密，輕量級(jí)設(shè)備僅需執(zhí)行整數(shù)環(huán)上的兩個(gè)模乘運(yùn)算即可生成密文，整數(shù)環(huán)上的模乘運(yùn)算量遠(yuǎn)遠(yuǎn)小于橢圓曲線上的冪乘運(yùn)算量。因此，與BGK方案和JK 方案相比，輕量級(jí)設(shè)備運(yùn)行本文方案的加密算法效率得到了極大地提高。此外，本文方案的KGC私鑰更新工作量是BGK的1/7，是JK[8]的1/3。

WMW[15]提出了一種高效的可外包解密的身份基在線離線加密方案，該方案支持輕量級(jí)設(shè)備快速加密數(shù)據(jù)，但不能實(shí)現(xiàn)用戶撤銷(xiāo)的功能。與WMW[15]方案相比，本文方案支持用戶撤銷(xiāo)功能，盡管在線加密工作量比WMW[15]方案多執(zhí)行一個(gè)整數(shù)環(huán)上的模乘運(yùn)算，由于整數(shù)環(huán)上的模乘運(yùn)算量極小，輕量級(jí)設(shè)備完全能夠承擔(dān)。性能比較表明，本文方案不僅大大提高了輕量級(jí)設(shè)備的加密效率，而且極大地減少了KGC 私鑰更新的工作量，適合于輕量級(jí)設(shè)備保護(hù)用戶隱私信息。

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

本文提出高效可撤銷(xiāo)的身份基在線離線加密方案，該方案利用完全子樹(shù)方法實(shí)現(xiàn)用戶撤銷(xiāo)功能，利用在線離線技術(shù)提高輕量級(jí)設(shè)備加密效率?；贒BDHI 假設(shè)，證明本文方案是安全的。本文方案的優(yōu)勢(shì)主要表現(xiàn)在三個(gè)方面：（1）輕量級(jí)設(shè)備的加密效率很高；（2）KGC的私鑰更新工作量大大減少；（3）實(shí)現(xiàn)成員撤銷(xiāo)功能。因此，本文方案非常適合于移動(dòng)環(huán)境中輕量級(jí)設(shè)備保護(hù)用戶隱私信息。