標(biāo)準(zhǔn)模型下可撤銷(xiāo)的基于身份的代理重簽名方案

楊小東，李雨潼，王晉利，麻婷春，王彩芬

（1. 西北師范大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，甘肅 蘭州 730070；2. 密碼科學(xué)技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室，北京 100878）

基于身份的代理重簽名是一種具有轉(zhuǎn)換簽名功能的密碼體制，一個(gè)半可信的代理者能將 Alice的簽名轉(zhuǎn)換為Bob對(duì)同一個(gè)消息的簽名，但代理者無(wú)法獲得Alice或Bob的簽名密鑰的任何信息。在一種基于身份的代理重簽名方案中，用戶(hù)選擇如E-mail地址、手機(jī)號(hào)碼等身份標(biāo)識(shí)作為公鑰，而私鑰由可信的密鑰生成中心（PKG, private key generator）生成并通過(guò)安全的信道發(fā)送給用戶(hù)?；谏矸莸拇碇睾灻w制避免了復(fù)雜的公鑰證書(shū)，簡(jiǎn)化了密鑰管理，在云計(jì)算、大數(shù)據(jù)隱私保護(hù)等方面有廣泛的應(yīng)用[1-2]。

基于文獻(xiàn)[3]的加密方案，Shao等[4]構(gòu)造了第一種標(biāo)準(zhǔn)模型下安全的基于身份的代理重簽名方案；Feng等[5]利用抗碰撞的散列函數(shù)設(shè)計(jì)了一種基于身份的代理重簽名方案，但該方案不滿(mǎn)足多用性；Hu等[6]提出了一種緊規(guī)約的基于身份的代理重簽名方案，但該方案的安全性依賴(lài)于較強(qiáng)的困難問(wèn)題假設(shè)；Shao等[7]又設(shè)計(jì)了一種隨機(jī)預(yù)言模型下安全的單向基于身份的代理重簽名方案，但該方案的驗(yàn)證重簽名的計(jì)算開(kāi)銷(xiāo)與重簽名級(jí)數(shù)呈線(xiàn)性增長(zhǎng)關(guān)系；Huang等[8]提出了一種無(wú)雙線(xiàn)性對(duì)的基于身份的代理重簽名方案，并在隨機(jī)預(yù)言模型中證明了該方案的安全性可歸約到離散對(duì)數(shù)問(wèn)題。文獻(xiàn)[9-10]分別構(gòu)造了格上基于身份的代理重簽名方案，但這2種方案的參數(shù)尺寸、密鑰長(zhǎng)度和簽名長(zhǎng)度都比較大，并且安全性依賴(lài)于理想的隨機(jī)預(yù)言機(jī)。然而，在隨機(jī)模型中被證明安全的密碼方案，當(dāng)利用具體的散列函數(shù)實(shí)例化隨機(jī)預(yù)言機(jī)時(shí)，隨機(jī)預(yù)言模型并不能確保方案的實(shí)際安全性[11]。因此，研究標(biāo)準(zhǔn)模型下安全的基于身份的代理重簽名方案具有一定的現(xiàn)實(shí)意義。

在實(shí)際應(yīng)用中，任何實(shí)用的密碼系統(tǒng)都面臨用戶(hù)撤銷(xiāo)的問(wèn)題，比如用戶(hù)權(quán)限到期或用戶(hù)密鑰泄露，這就需要從密碼系統(tǒng)中撤銷(xiāo)用戶(hù)。為了實(shí)現(xiàn)基于身份的用戶(hù)撤銷(xiāo)機(jī)制，文獻(xiàn)[12]提出了PKG定期更新未撤銷(xiāo)用戶(hù)密鑰的撤銷(xiāo)方法，但 PKG與未撤銷(xiāo)用戶(hù)之間需要建立一個(gè)安全信道來(lái)傳輸更新密鑰。Boldyreva等[13]提出了PKG通過(guò)公開(kāi)信道實(shí)現(xiàn)用戶(hù)撤銷(xiāo)的方法，隨后一些基于Boldyreva所提方法的可撤銷(xiāo)加密方案相繼被提出[14-15]。為了解決簽名方案中的用戶(hù)撤銷(xiāo)問(wèn)題，Tsai等[16]提出了第一種可撤銷(xiāo)的基于身份簽名方案，但Liu等[17]發(fā)現(xiàn)該方案存在簽名密鑰泄露的安全風(fēng)險(xiǎn)。近年來(lái)，一些具有特殊性質(zhì)的可撤銷(xiāo)簽名方案[18-20]也相繼被提出，如可撤銷(xiāo)的屬性基簽名[21]、可撤銷(xiāo)的無(wú)證書(shū)簽名[22-23]、可撤銷(xiāo)的代理簽名[24]、可撤銷(xiāo)的前向安全簽名[25]等。

現(xiàn)有的基于身份的代理重簽名方案均未考慮用戶(hù)撤銷(xiāo)問(wèn)題，而用戶(hù)撤銷(xiāo)功能對(duì)一種實(shí)用的基于身份的代理重簽名方案是非常重要的。例如 Alice是某公司的總經(jīng)理，負(fù)責(zé)該公司所有文件的簽名。如果Alice因公出差，由該公司的副總經(jīng)理Bob生成公司文件的簽名，利用Alice和Bob之間的重簽名密鑰，將Bob的簽名轉(zhuǎn)換為Alice對(duì)同一文件的簽名。由于工作調(diào)動(dòng)或身體健康的原因，Bob離開(kāi)了公司。為了公司的利益，需要撤銷(xiāo)Bob的簽名權(quán)限。因此，基于身份代理重簽名體制在實(shí)現(xiàn)簽名轉(zhuǎn)換的同時(shí)，還必須支持高效的用戶(hù)撤銷(xiāo)機(jī)制。

鑒于此，本文提出了可撤銷(xiāo)的基于身份代理重簽名方案，并給出了相應(yīng)的形式化定義與安全模型。基于Shao等[4]提出的代理重簽名方案和二叉樹(shù)結(jié)構(gòu)，本文構(gòu)造了一種可撤銷(xiāo)的雙向基于身份的代理重簽名方案，在標(biāo)準(zhǔn)模型下證明了所構(gòu)造方案的安全性可規(guī)約到計(jì)算性Diffie-Hellman Diffie-Hellman（CDH, computational Diffie-Hellman）困難問(wèn)題。本文所提方案實(shí)現(xiàn)了用戶(hù)的撤銷(xiāo)與密鑰的更新，能抵抗簽名密鑰泄露攻擊，并且 PKG的工作量與用戶(hù)的數(shù)量呈對(duì)數(shù)增長(zhǎng)關(guān)系，具有良好的延展性。

2 準(zhǔn)備知識(shí)

2.1 符號(hào)說(shuō)明

本文所使用的符號(hào)及其說(shuō)明如表1所示。

2.2 雙線(xiàn)性映射

令p是一個(gè)大素?cái)?shù)，G和GT是2個(gè)階為p的乘法循環(huán)群，g是G的一個(gè)生成元。如果一個(gè)可計(jì)算的映射e:G×G→GT滿(mǎn)足以下條件，則稱(chēng)e是一個(gè)雙線(xiàn)性映射[4]。

1) 雙線(xiàn)性：對(duì)任意的a,b∈Zp，有

2.3 KUNode算法

選擇基于二叉樹(shù)的 KUNode算法[26]來(lái)提高未撤銷(xiāo)用戶(hù)的密鑰更新效率。令BT表示一棵具有N個(gè)葉子節(jié)點(diǎn)的二叉樹(shù)，root表示樹(shù)的根節(jié)點(diǎn)。對(duì)于每個(gè)非葉子節(jié)點(diǎn)θ，用θl和θr表示θ的左孩子節(jié)點(diǎn)和右孩子節(jié)點(diǎn)。每個(gè)用戶(hù)將分配至BT上的一個(gè)葉子節(jié)點(diǎn)η，用path(η)表示從葉子節(jié)點(diǎn)η到根節(jié)點(diǎn)root的路徑上的所有節(jié)點(diǎn)集合。RL表示一個(gè)由葉子節(jié)點(diǎn)ηi和時(shí)間周期ti組成的撤銷(xiāo)列表，Y表示BT中需要更新的最小節(jié)點(diǎn)集合。如果η∈RL，則path(η) ∩Y=?。KUNode算法的輸入是BT、RL和時(shí)間周期t，輸出是Y。KUNode算法的具體描述如算法1所示。

表1 符號(hào)列表及其說(shuō)明

算法1KUNode算法

輸入BT、RL和時(shí)間周期t

輸出需要更新的最小節(jié)點(diǎn)集合Y

1) 設(shè)置集合X=?,Y=?

2) ? (ηi,ti)∈ RL

3) 如果ti≤t，在X中添加 path(ηi)

4) ?θ∈X

5) 如果θl?X，在Y中添加θl

6) 如果θr?X，在Y中添加θr

7) 如果Y=?，在Y中添加root

8) 返回Y

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

定義1CDH假設(shè)。如果所有多項(xiàng)式時(shí)間算法無(wú)法解決G上CDH問(wèn)題，則稱(chēng)G上的CDH問(wèn)題是困難的[4]。

3 可撤銷(xiāo)的基于身份代理重簽名的安全性定義

3.1 形式化定義

一種撤銷(xiāo)的雙向基于身份的代理重簽名方案由下面9種算法構(gòu)成。

1) setup (1λ,N,T)→ (pp,msk,RL,st)是系統(tǒng)參數(shù)建立算法：輸入安全參數(shù)λ、最大用戶(hù)數(shù)N和用戶(hù)簽名密鑰有效期的最大時(shí)間周期T，輸出公開(kāi)參數(shù)pp、PKG的主密鑰msk、初始化為空集的用戶(hù)撤銷(xiāo)列表RL和狀態(tài)st。

2) extract (pp,msk,ID)→skID是秘密密鑰生成算法：輸入pp、msk和用戶(hù)身份ID，輸出秘密密鑰skID。

3) KeyUp (pp,msk,t,RL,st)→ ukt是密鑰更新算法：輸入pp、msk、更新的時(shí)間周期t、當(dāng)前的用戶(hù)撤銷(xiāo)列表RL和狀態(tài)st，如果t＞T，輸出一個(gè)錯(cuò)誤符號(hào)“⊥”；否則，輸出一個(gè)更新密鑰ukt。

4) SKGen (pp,skID,ukt)→ dkID,t是簽名密鑰生成算法：輸入pp、skID和ukt，如果用戶(hù)身份ID在時(shí)間周期t已被撤銷(xiāo)，輸出⊥；否則，輸出對(duì)應(yīng)于ID和t的簽名密鑰dkID,t。

6) sign (pp,dkID,t,t,M)→σ是簽名生成算法：輸入pp、dkID,t、當(dāng)前時(shí)間周期t(t≤T)和消息M，輸出關(guān)于M的簽名σ，其中dkID,t是用戶(hù)身份ID在時(shí)間周期t的簽名密鑰。

8) verify (pp,ID,t,M,σ)→{0,1}是簽名驗(yàn)證算法：輸入pp、身份ID、時(shí)間周期t(t≤T)、消息M和簽名σ，如果σ是合法的，輸出1；否則，輸出0。

9) revoke (ID,t,RL,st)→ RL′是用戶(hù)撤銷(xiāo)算法：輸入時(shí)間周期t(t≤T)內(nèi)，撤銷(xiāo)的用戶(hù)身份ID、用戶(hù)撤銷(xiāo)列表RL和狀態(tài)st，輸出更新后的用戶(hù)撤銷(xiāo)列表RL′。

3.2 安全模型

借鑒基于身份的代理重簽名方案的安全模型[4,7]和可撤銷(xiāo)的基于身份簽名方案的安全性定義[17-19]，本文通過(guò)攻擊者A和挑戰(zhàn)者C之間的安全游戲，給出可撤銷(xiāo)的雙向基于身份的代理重簽名方案的安全模型。

初始化C運(yùn)行setup(1λ,N,T)算法，將生成的系統(tǒng)參數(shù)pp發(fā)送給A，自己秘密保存主密鑰msk。

詢(xún)問(wèn)A自適應(yīng)地向C發(fā)起有限次的如下詢(xún)問(wèn)。

1) extract-query：對(duì)于A請(qǐng)求的關(guān)于身份ID的秘密密鑰詢(xún)問(wèn)，C運(yùn)行算法extract(pp,msk,ID)，將輸出的秘密密鑰skID發(fā)送給A。

2) KeyUp-query：對(duì)于A請(qǐng)求的關(guān)于時(shí)間周期t(t≤T)的更新密鑰詢(xún)問(wèn)，其中t不能小于以前所有詢(xún)問(wèn)過(guò)的時(shí)間周期，C運(yùn)行算法 KeyUp (pp,msk,t,RL,st)，將生成的更新密鑰ukt發(fā)送給A。

3) SKGen-query：收到A發(fā)送的關(guān)于(ID,t)的簽名密鑰詢(xún)問(wèn)后，C首先詢(xún)問(wèn)關(guān)于ID的 extractquery和關(guān)于t≤T的KeyUp-query，分別獲得相應(yīng)的秘密密鑰skID與更新密鑰ukt；然后運(yùn)行算法SKGen(pp,skID,ukt)生成簽名密鑰dkID,t，并將dkID,t發(fā)送給A。為了不失一般性，這里要求A未進(jìn)行關(guān)于t的 KeyUp-query詢(xún)問(wèn)前，不能發(fā)起關(guān)于t的SKGen-query詢(xún)問(wèn)。

4) ReKey-query：收到A發(fā)送的關(guān)于 2個(gè)身份(IDA,IDB)和時(shí)間周期t的重簽名密鑰詢(xún)問(wèn)后，C首先詢(xún)問(wèn)關(guān)于(IDA,t)和(IDB,t)的 SKGen-query，獲得對(duì)應(yīng)的簽名密鑰dkA,t與dkB,t；然后將算法 ReKey(pp,dkA,t,dkB,t)生成的重簽名密鑰rkA→B,t發(fā)送給A。

5) sign-query：收到A發(fā)送的關(guān)于身份ID、時(shí)間周期t(t≤T)與消息M的簽名詢(xún)問(wèn)后，C詢(xún)問(wèn)關(guān)于(ID,t)的SKGen-query獲得簽名密鑰dkID,t，并運(yùn)行算法sign (pp,dkID,t,t,M)，將生成的M的簽名σ返回給A。

6) revoke-query：如果A在時(shí)間周期t(t≤T)發(fā)起過(guò)關(guān)于身份ID的KeyUp-query，則A在時(shí)間周期t不能發(fā)起關(guān)于ID的revoke-query。收到A發(fā)送的(ID,t)后，其中t不能小于以前所有詢(xún)問(wèn)過(guò)的時(shí)間周期，C運(yùn)行算法revoke(ID,t,RL,st)，并將輸出的用戶(hù)撤銷(xiāo)列表RL′返回給A。

偽造攻擊者A最后輸出身份ID*、時(shí)間周期t*(t≤T)、消息M*和簽名σ*。如果以下5個(gè)條件均成立，則稱(chēng)A在以上游戲中獲勝。

1) verify (pp,ID*,t*,M*,σ*)=1。

2) (ID*,t*)未進(jìn)行過(guò)SKGen-query詢(xún)問(wèn)。

3) ID*未進(jìn)行過(guò) extract-query詢(xún)問(wèn)，并且t*≤T未進(jìn)行過(guò)KeyUp-query詢(xún)問(wèn)。

4) ID*未進(jìn)行過(guò)ReKey-query詢(xún)問(wèn)。

5) (ID*,t*,M*)未進(jìn)行過(guò)sign-query詢(xún)問(wèn)。

定義2若任何一個(gè)多項(xiàng)式時(shí)間攻擊者A在上述游戲中獲勝的概率是可忽略的，則稱(chēng)可撤銷(xiāo)的雙向基于身份的代理重簽名方案在適應(yīng)性選擇身份和消息攻擊下是存在不可偽造的。

定義 3如果攻擊者無(wú)法從當(dāng)前時(shí)間周期t泄露的簽名密鑰dkID,t中獲取秘密密鑰skID或威脅其他時(shí)間周期簽名密鑰的安全性，則稱(chēng)可撤銷(xiāo)的基于身份的代理重簽名方案滿(mǎn)足抗簽名密鑰泄露攻擊性。

4 可撤銷(xiāo)的雙向基于身份的代理重簽名方案

在Shao方案[4]基礎(chǔ)上，本文2.3節(jié)的KUNode算法構(gòu)造了一種可撤銷(xiāo)的雙向基于身份的代理重簽名方案。假設(shè)用戶(hù)身份的長(zhǎng)度和簽名消息的長(zhǎng)度分別為mbit和nbit，可通過(guò) 2個(gè)散列函數(shù)H1:{0,1}*→ {0,1}m和H2:{0,1}*→{0,1}n，將用戶(hù)身份和簽名消息的固定長(zhǎng)度延伸為可變長(zhǎng)度，即對(duì)于任意長(zhǎng)度的身份ID′和簽名消息M′，計(jì)算從而將身份ID′和消息M′分別映射為長(zhǎng)度為m和n的比特串。為了簡(jiǎn)化表述，假設(shè)方案中的用戶(hù)身份和消息都進(jìn)行了散列函數(shù)H1和H2的預(yù)處理，即用符號(hào)ID和M分別表示長(zhǎng)度為mbit的用戶(hù)身份和長(zhǎng)度為nbit的簽名消息。

4.1 方案描述

1) setup算法

輸入安全參數(shù)λ、最大用戶(hù)數(shù)N和最大時(shí)間周期T，PKG執(zhí)行如下操作。

① 選擇一個(gè)大素?cái)?shù)p，2個(gè)階為p的乘法循環(huán)群G和GT，一個(gè)G的生成元g和一個(gè)雙線(xiàn)性映射

② 在G中隨機(jī)選取

④ 選擇一棵具有N個(gè)葉子節(jié)點(diǎn)的二叉樹(shù)BT，設(shè)置用戶(hù)撤銷(xiāo)列表RL=?和狀態(tài)st=BT。

⑤ 秘密保存主密鑰msk=α，公開(kāi)參數(shù)pp=

為了表述方便，對(duì)于長(zhǎng)度為mbit的用戶(hù)身份和長(zhǎng)度為nbit的簽名消息和

2) extract算法

為了生成用戶(hù)身份ID的秘密密鑰，PKG執(zhí)行如下操作。

① 在BT上隨機(jī)選擇一個(gè)空的葉子節(jié)點(diǎn)η，并在η中保存ID。

② 對(duì)于每個(gè)節(jié)點(diǎn)θ∈path(η)，隨機(jī)選擇gθ∈G，并在θ中保存；選擇一個(gè)隨機(jī)數(shù)，計(jì)算

3) KeyUp算法

對(duì)于時(shí)間周期t、撤銷(xiāo)列表RL和狀態(tài)st，如果t＞T，輸出⊥；否則，PKG通過(guò)如下步驟生成更新密鑰ukt。

① 對(duì)于每個(gè)節(jié)點(diǎn)θ∈KUNode (BT, RL,t)，首先在θ中提取，然后隨機(jī)選取，計(jì)算 ukθ=

如果在時(shí)間周期t的撤銷(xiāo)列表 RL中包含了被撤銷(xiāo)的用戶(hù)身份ID，則PKG調(diào)用KUNode算法[26]生成需要更新的最小節(jié)點(diǎn)集合Y=KUNode (BT, RL,t)，但被撤銷(xiāo)的用戶(hù)無(wú)法獲得PKG生成的更新密鑰ukt。下面通過(guò)一個(gè)實(shí)例來(lái)說(shuō)明撤銷(xiāo)用戶(hù)的方法。

如圖1所示，假設(shè)4個(gè)用戶(hù)u1,u2,u3和u4被分配至 4 個(gè)葉子節(jié)點(diǎn)η3,η4,η5和η6。假設(shè)用戶(hù)u3被撤銷(xiāo)，則X=path(η5)={η5,η2, root}，Y={η1,η6}，path(η5)∩Y=?。除了u3外，從每個(gè)用戶(hù)對(duì)應(yīng)的葉子節(jié)點(diǎn)到根節(jié)點(diǎn)的路徑上至少包含Y中的一個(gè)節(jié)點(diǎn)。用戶(hù)u1和u2的路徑上包含Y中的節(jié)點(diǎn)η1，用戶(hù)u4的路徑上包含Y中的節(jié)點(diǎn)η6。在時(shí)間周期t，PKG只需更新Y={η1,η6}中每個(gè)節(jié)點(diǎn)的密鑰，便可完成未撤銷(xiāo)用戶(hù)u1,u2和u4的密鑰更新，從而實(shí)現(xiàn)對(duì)用戶(hù)u3的撤銷(xiāo)。

圖1 KUNode算法的一個(gè)實(shí)例

4) SKGen算法

如果用戶(hù)身份ID在時(shí)間周期t≤T已被撤銷(xiāo)，輸出⊥；否則，一定存在一個(gè)節(jié)點(diǎn)θ∈KUNode (BT,RL,t)∩path(η)；用戶(hù)隨機(jī)選取，利用自己的秘密密鑰和公開(kāi)的更新密鑰計(jì)算簽名密鑰為

5) ReKey算法

給定 2個(gè)用戶(hù)身份IDA和IDB的簽名密鑰和，采用類(lèi)似文獻(xiàn)[4]的安全協(xié)議，生成代理者的一個(gè)重簽名密鑰為

6) sign算法

對(duì)于當(dāng)前時(shí)間周期t≤T和一個(gè)消息M，身份為IDA的簽名者隨機(jī)選取，利用簽名密鑰計(jì)算，輸出一個(gè)關(guān)于M的簽名

7) resign算法

8) verify算法

給定身份ID、消息M、時(shí)間周期t≤T和簽名，驗(yàn)證者檢查以下等式是否成立。

如果等式成立，說(shuō)明σ是一個(gè)合法的簽名，輸出1；否則，輸出0。

9) revoke算法

給定 BT上存儲(chǔ)被撤銷(xiāo)用戶(hù)身份ID的葉子節(jié)點(diǎn)η，當(dāng)前時(shí)間周期t≤T、用戶(hù)撤銷(xiāo)列表RL和狀態(tài) st，PKG 在 RL 中添加 (η,t)，即 RL′=，并輸出更新后的用戶(hù)撤銷(xiāo)列表RL′。

4.2 正確性分析

假設(shè)身份IDB的簽名密鑰對(duì)于消息M的重簽名，其中

則Bσ的正確性驗(yàn)證如下

上述推導(dǎo)過(guò)程證明了本文方案的正確性。

通過(guò)IDA與IDB間的重簽名密鑰rkA→B,t，很容易計(jì)算出IDB與IDA間的重簽名密鑰，所以本文方案具有雙向性。

4.3 安全性分析

定理1 如果CDH假設(shè)成立，則本文方案滿(mǎn)足標(biāo)準(zhǔn)模型下自適應(yīng)性選擇身份和消息攻擊的存在不可偽造性。

證明 假設(shè)攻擊者A進(jìn)行了最多qsk次秘密密鑰詢(xún)問(wèn)、quk次更新密鑰詢(xún)問(wèn)、qdk次簽名密鑰詢(xún)問(wèn)、qrk次重簽名密鑰詢(xún)問(wèn)、qs次簽名詢(xún)問(wèn)和qr次撤銷(xiāo)詢(xún)問(wèn)后，以不可忽略的概率ε攻破了本文方案的存在不可偽造性，則存在一個(gè)挑戰(zhàn)者C將利用攻擊者A的偽造，以不可忽略的概率'ε解決G上的CDH問(wèn)題。對(duì)于一個(gè)CDH問(wèn)題實(shí)例的目標(biāo)是計(jì)算gab。

初始化C設(shè)置參數(shù)和，滿(mǎn)足lu(m+1)＜p和lm(n+1)＜p。隨機(jī)選取2個(gè)整數(shù)和km(0≤km≤n)，并隨機(jī)選擇。選擇一棵具有N個(gè)葉子節(jié)點(diǎn)的二叉樹(shù)BT，設(shè)置最大時(shí)間周期T、用戶(hù)撤銷(xiāo)列表RL=?和狀態(tài)st=BT，參數(shù)并發(fā)送系統(tǒng)參數(shù)給A。

詢(xún)問(wèn)C回答A發(fā)起的一系列如下詢(xún)問(wèn)。

1) extract-query：為了響應(yīng)A請(qǐng)求的關(guān)于身份ID的秘密密鑰詢(xún)問(wèn)，C維持一個(gè)初始化為空的列表tsk。如果F(ID)=0 modp，C退出模擬；否則，C執(zhí)行如下操作。

① 在BT上隨機(jī)選擇一個(gè)空的葉子節(jié)點(diǎn)η，并在η中保存ID。

② 對(duì)于每個(gè)節(jié)點(diǎn)θ∈path(η)，隨機(jī)選擇gθ∈G，并在θ中保存gθ。如果tsk中不存在(θ,rθ,ID)，隨機(jī)選取rθ∈Zp，將(θ,rθ,ID)添加到tsk中。然后提取rθ，計(jì)算

2) KeyUp-query：為了響應(yīng)A請(qǐng)求的關(guān)于時(shí)間周期t的更新密鑰詢(xún)問(wèn)，C維持一個(gè)初始化為空的列表Tuk，如果t＞T，輸出⊥；否則，C執(zhí)行如下操作。

① 對(duì)于每個(gè)節(jié)點(diǎn)θ∈KUNode (BT, RL,t)，首先在θ中提取gθ，然后在Tuk中提取sθ。如果Tuk中不存在，則選擇一個(gè)隨機(jī)數(shù)，將添加到Tuk中，并計(jì)算

3) SKGen-query：為了響應(yīng)A請(qǐng)求的關(guān)于(ID,t)的簽名密鑰詢(xún)問(wèn)，C維持一個(gè)初始化為空的列表Tdk。C首先詢(xún)問(wèn)關(guān)于ID的extract-query和關(guān)于t的KeyUp-query，分別獲得相應(yīng)的秘密密鑰skID與更新密鑰ukt；然后在Tdk中提取(rID,sID)。如果Tdk中不存在(rID,sID,ID,t)，則選擇2個(gè)隨機(jī)數(shù)rID、sID∈Zp，將(rID,sID,ID,t)添加到Tdk中；最后運(yùn)行算法SKGen(pp,skID,ukt)，將生成的簽名密鑰dkID,t返回給A。

4) ReKey-query：對(duì)于A請(qǐng)求的關(guān)于2個(gè)身份(IDA,IDB)和時(shí)間周期t的重簽名密鑰詢(xún)問(wèn)，C首先詢(xún)問(wèn)關(guān)于(IDA,t)和(IDB,t)的 SKGen-query，分別獲得對(duì)應(yīng)的簽名密鑰dkA,t與dkB,t；然后運(yùn)行算法ReKey(pp,dkA,t,dkB,t)，將生成的重簽名密鑰rkA→B,t發(fā)送給A。

5) sign-query：對(duì)于A請(qǐng)求的關(guān)于身份ID、時(shí)間周期t(t≤T)與消息M的簽名詢(xún)問(wèn)，如果F(ID)≠0 modp，C詢(xún)問(wèn)關(guān)于(ID,t)的 SKGen-query獲得簽名密鑰dkID,t，然后運(yùn)行算法sign(pp,dkID,t,t,M)，并將輸出的關(guān)于M的簽名σ返回給A。如果F(ID)=0 modp，則考慮以下2種情況。

① 如果K(M)=0 modp，則C退出模擬。

② 如果K(M)≠0 modp，則C在Tsk、Tuk、Tdk中提取rθ、sθ和(rID,sID)，并隨機(jī)選擇rm∈Zp，計(jì)算，然后將關(guān)于M的簽名發(fā)送給A。

6) revoke-query：對(duì)于A請(qǐng)求的關(guān)于(ID,t)的撤銷(xiāo)詢(xún)問(wèn)，C運(yùn)行算法revoke(ID,t,RL,st)，并將運(yùn)行結(jié)果返回給A。

偽造攻擊者A最后輸出一個(gè)對(duì)應(yīng)于身份*ID和時(shí)間周期t*≤T的關(guān)于消息M*的簽名。如果F(ID*)≠0 modp或退出模擬；否則，C計(jì)算CDH值gab過(guò)程如下

因此，C利用A的偽造(ID*,t*,M*,σ*)成功求解了CDH問(wèn)題實(shí)例。與文獻(xiàn)[3-4]的分析過(guò)程相似，C將以的概率成功解決G上的CDH問(wèn)題。

定理2本文方案滿(mǎn)足抗簽名密鑰泄露攻擊性。

證明在 4.1節(jié)的方案中，分別用gθ和來(lái)構(gòu)造秘密密鑰和更新密鑰，并且滿(mǎn)足。只有未撤銷(xiāo)的用戶(hù)才能正確恢復(fù)出，進(jìn)而生成合法的簽名密鑰。如果攻擊者獲得了未撤銷(xiāo)用戶(hù)ID的簽名密鑰dkID,t，則利用公開(kāi)信道傳輸?shù)母旅艽aukt計(jì)算

由于在本文方案的SKGen算法中，用戶(hù)隨機(jī)選取rID,sID∈Zp對(duì)秘密密鑰和更新密鑰進(jìn)行了隨機(jī)化處理，因此攻擊者即使獲得了用戶(hù)身份ID在時(shí)間周期t的更新密鑰dkID,t，但仍然無(wú)法直接從dkID,t中計(jì)算出對(duì)應(yīng)的秘密密鑰skID。因?yàn)橛脩?hù)的簽名密鑰dkID,t通過(guò)固定的秘密密鑰skID和定期變化的更新密鑰ukt生成，所以攻擊者在skID未知的情況下不能利用SKGen算法產(chǎn)生其他時(shí)間周期的合法簽名密鑰。

綜上所述，即使攻擊者獲得當(dāng)前時(shí)間段的簽名密鑰dkID,t，攻擊者無(wú)法通過(guò)dkID,t和公開(kāi)的更新密鑰ukt計(jì)算出秘密密鑰skID，也不會(huì)影響其他時(shí)間周期簽名密鑰的安全性。因此，本文方案能抵抗簽名密鑰泄露攻擊，即滿(mǎn)足抗簽名密鑰泄露攻擊性。

4.4 性能分析

文獻(xiàn)[4-6]分別提出了3個(gè)標(biāo)準(zhǔn)模型下安全的基于身份的代理重簽名方案（分別將其命名為 Shao方案[4]、Feng方案[5]和Hu方案[6]），將本文方案與這些方案進(jìn)行性能比較分析，如表2所示。令N表示用戶(hù)總數(shù)，R表示撤銷(xiāo)的用戶(hù)數(shù)，則由KUNode算法的計(jì)算復(fù)雜度可知[25]，本文方案中 PKG更新密鑰的開(kāi)銷(xiāo)為。假設(shè)所有方案選擇階為素?cái)?shù)p的群G和GT，僅考慮計(jì)算開(kāi)銷(xiāo)比較大的雙線(xiàn)性對(duì)和指數(shù)運(yùn)算，不再討論計(jì)算量較小的乘法運(yùn)算等操作。在表2中，符號(hào)|G|表示群G中一個(gè)元素的平均長(zhǎng)度，|p|表示有限域Zp中一個(gè)元素的平均長(zhǎng)度，Pa表示一次雙線(xiàn)對(duì)運(yùn)算，exp表示一次指數(shù)運(yùn)算。

從表2可知，與Shao方案[4]相比，本文方案的簽名長(zhǎng)度和重簽名長(zhǎng)度多了一個(gè)群G中的元素，并且簽名驗(yàn)證算法多了一次雙線(xiàn)性對(duì)運(yùn)算和一次指數(shù)運(yùn)算。與Feng方案[5]相比，本文方案與該方案有相同的重簽名長(zhǎng)度，但具有較高的簽名驗(yàn)證效率，并滿(mǎn)足多用性。與 Hu方案[6]相比，本文方案具有更短的簽名長(zhǎng)度和重簽名長(zhǎng)度，并且簽名算法的計(jì)算效率優(yōu)于該方案。然而，對(duì)比的3種方案均沒(méi)有考慮用戶(hù)撤銷(xiāo)問(wèn)題，本文方案實(shí)現(xiàn)了用戶(hù)撤銷(xiāo)功能，并且 PKG撤銷(xiāo)用戶(hù)的工作量隨用戶(hù)總數(shù)的增加呈對(duì)數(shù)增長(zhǎng)，具有良好的延展性。

將本文方案、Feng方案[5]和 Hu方案[6]進(jìn)行簽名算法的計(jì)算時(shí)間開(kāi)銷(xiāo)實(shí)驗(yàn)對(duì)比分析，具體結(jié)果如圖2所示。選取PBC庫(kù)的a.param初始化pairing，實(shí)驗(yàn)的硬件環(huán)境為：2.5 GHz英特爾酷睿i7-6500處理器，8 GB的內(nèi)存，512 GB的硬盤(pán)空間；軟件環(huán)境為：64位 Windows 10操作系統(tǒng)，密碼庫(kù)PBC-0.4.7-VC。

圖2 簽名生成的時(shí)間開(kāi)銷(xiāo)與消息長(zhǎng)度關(guān)系

表2 4種方案的計(jì)算開(kāi)銷(xiāo)與安全性能比較

由于本文方案是基于Shao方案[4]設(shè)計(jì)的，因此2種方案生成簽名的計(jì)算開(kāi)銷(xiāo)相同，均需要2次指數(shù)運(yùn)算。此外，F(xiàn)eng方案[5]需要3次指數(shù)運(yùn)算，Hu方案[6]需要6次指數(shù)運(yùn)算。對(duì)于長(zhǎng)度相同的簽名消息，圖 2表明本文方案生成簽名的時(shí)間開(kāi)銷(xiāo)低于Feng 方案[5]和 Hu 方案[6]。

本文方案利用 KUNode算法[26]來(lái)實(shí)現(xiàn)用戶(hù)的撤銷(xiāo)，而文獻(xiàn)[16]通過(guò)PKG直接更新未撤銷(xiāo)用戶(hù)的密鑰來(lái)實(shí)現(xiàn)用戶(hù)的撤銷(xiāo)。下面將2種方案進(jìn)行密鑰更新的性能比較，結(jié)果如圖3所示。假設(shè)用戶(hù)總數(shù)為32個(gè)，被撤銷(xiāo)的用戶(hù)數(shù)分別為1個(gè)、2個(gè)、4個(gè)、8個(gè)和16個(gè)。

圖3 密鑰更新的性能比較

本文方案和文獻(xiàn)[16]方案生成每個(gè)用戶(hù)的更新密鑰均需要執(zhí)行2次指數(shù)運(yùn)算，所需的時(shí)間開(kāi)銷(xiāo)約為15 ms。由圖3可知，當(dāng)被撤銷(xiāo)的用戶(hù)數(shù)小于用戶(hù)總數(shù)的一半時(shí)，本文方案需要更新密鑰的用戶(hù)個(gè)數(shù)小于文獻(xiàn)[16]方案。因此，本文方案具有更低的用戶(hù)撤銷(xiāo)開(kāi)銷(xiāo)。

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

本文基于 Shao方案[4]和 KUNode算法[26]，構(gòu)造了一種可撤銷(xiāo)的基于身份的代理重簽名方案，并在標(biāo)準(zhǔn)模型下證明了其安全性依賴(lài)于 CDH假設(shè)。本文方案支持用戶(hù)撤銷(xiāo)功能，滿(mǎn)足雙向性和多用性，可有效抵抗簽名密鑰泄露攻擊，具有良好的延展性。但本文方案無(wú)法抵抗量子計(jì)算攻擊，下一步的任務(wù)是設(shè)計(jì)格上可撤銷(xiāo)的基于身份的代理重簽名方案。