基于身份的可穿刺簽名方案

楊冬梅，陳越，魏江宏，胡學(xué)先

（信息工程大學(xué)數(shù)據(jù)與目標(biāo)工程學(xué)院，河南 鄭州 450001）

1 引言

在基于公鑰基礎(chǔ)設(shè)施的密碼體制中，權(quán)威機(jī)構(gòu)通過(guò)數(shù)字簽名為用戶(hù)頒發(fā)公鑰證書(shū)，保證了用戶(hù)公鑰的真實(shí)性和可信性。與此同時(shí)，用戶(hù)證書(shū)的頒發(fā)、存儲(chǔ)和撤銷(xiāo)以及認(rèn)證核查等工作也帶來(lái)了繁重的管理開(kāi)銷(xiāo)。為此，Shamir[1]在1984 年首次提出了基于身份的簽名（IBS,identity-based signature）方案，即以用戶(hù)的個(gè)人信息（如身份證號(hào)、手機(jī)號(hào)、電子郵箱地址等）作為其公鑰，而用戶(hù)私鑰由一個(gè)密鑰生成中心利用系統(tǒng)主密鑰來(lái)生成，簽名的驗(yàn)證也只需要簽名用戶(hù)的公鑰對(duì)所對(duì)應(yīng)的身份信息，從而避免了對(duì)公鑰基礎(chǔ)設(shè)施的依賴(lài)。

隨后，圍繞IBS 方案安全性增強(qiáng)、效率提升和功能擴(kuò)展等方面，密碼學(xué)者提出了很多新的IBS 方案，如Cha[2]給出了完整的IBS 方案和該方案在隨機(jī)預(yù)言模型下的安全性證明，Paterson 等[3]在標(biāo)準(zhǔn)模型下構(gòu)造了第一個(gè)高效的IBS 方案，楊小東等[4]提出了強(qiáng)不可偽造的基于身份服務(wù)器輔助驗(yàn)證簽名方案，劉翔宇等[5]提出了第一個(gè)緊致安全的IBS 方案，田苗苗等[6]提出了格上基于身份的增量簽名方案以及侯紅霞等[7]提出了素?cái)?shù)階群上基于非對(duì)稱(chēng)對(duì)的身份基環(huán)簽名。在這些傳統(tǒng)的IBS 方案中，假設(shè)用戶(hù)私鑰都是絕對(duì)安全的。但在現(xiàn)實(shí)應(yīng)用環(huán)境中，隨著網(wǎng)絡(luò)攻擊手段的多樣化，用戶(hù)私鑰泄露事件趨于高發(fā)。另一方面，一旦用戶(hù)私鑰被攻擊者竊取，攻擊者就可以產(chǎn)生任何消息的合法簽名，導(dǎo)致用戶(hù)之前生成的所有簽名都將失效。

為降低數(shù)字簽名方案中由私鑰泄露所帶來(lái)的損失，Anderson[8]在1997 年首次引入了前向安全數(shù)字簽名方案的概念，即要求在用戶(hù)私鑰泄露后，之前所生成的簽名是不能被偽造的，但他并沒(méi)有給出具體構(gòu)造。Bellare 等[9]在1999 年的美密會(huì)上首次對(duì)這種密碼學(xué)原語(yǔ)進(jìn)行了形式化定義，并基于RSA（Rivest Shamir Adleman）群上的整數(shù)分解問(wèn)題給出了一個(gè)具體構(gòu)造。隨后，學(xué)者對(duì)前向安全的數(shù)字簽名方案進(jìn)行了大量而又深入的研究，提出了很多在安全性和效率方面具有各自?xún)?yōu)勢(shì)的相關(guān)方案，如Itkis 等[10]提出了具有高效簽名和驗(yàn)證效率的前向安全簽名方案，Kozlov 等[11]給出了密鑰能快速更新的前向安全簽名方案，Libert 等[12]構(gòu)造了不可信更新環(huán)境中前向安全的簽名方案，Abdalla 等[13]對(duì)文獻(xiàn)[9]方案的私鑰規(guī)模進(jìn)行了優(yōu)化等。以上這些前向安全的數(shù)字簽名方案均是基于公鑰證書(shū)的。為避免對(duì)公鑰基礎(chǔ)設(shè)施的依賴(lài)，Yu 等[14]在IBS 中引入了前向安全性，形式化地定義了前向安全的基于身份簽名方案，并給出了一個(gè)具體構(gòu)造。

然而，如Green 等[15]所指出，上述傳統(tǒng)的通過(guò)周期性更新密鑰實(shí)現(xiàn)前向安全性的方法不夠靈活，導(dǎo)致其在實(shí)際部署中不可用。具體而言，傳統(tǒng)的前向安全I(xiàn)BS 方案[14]以固定的時(shí)間周期為單位（如每小時(shí)、每天等）更新用戶(hù)私鑰，這導(dǎo)致當(dāng)前時(shí)間周期的私鑰泄露之后，攻擊者仍能偽造當(dāng)前時(shí)間周期內(nèi)的簽名。此外，傳統(tǒng)的前向安全I(xiàn)BS 方案采用二叉樹(shù)結(jié)構(gòu)管理用戶(hù)密鑰和時(shí)間周期，使這些方案的密鑰更新效率較慢。

為克服已有前向安全I(xiàn)BS 方案在密鑰更新靈活性和效率方面存在的不足，本文提出了基于身份的可穿刺簽名（IBPS,identity-based puncturable signature）方案。這種新的簽名方案實(shí)現(xiàn)了細(xì)粒度的前向安全性，即每當(dāng)用戶(hù)完成對(duì)某個(gè)消息的簽名之后，立即對(duì)私鑰進(jìn)行更新，使更新后的私鑰不能再用來(lái)對(duì)同樣的消息進(jìn)行簽名，保證了私鑰泄露之前所生成簽名的安全性。本文主要貢獻(xiàn)總結(jié)如下。

1) 對(duì)傳統(tǒng)的IBS機(jī)制進(jìn)行了擴(kuò)展，給出了IBPS機(jī)制的形式化定義，并通過(guò)安全模型刻畫(huà)了這種簽名方案的存在不可偽造性。

2) 將基于布隆過(guò)濾器的可穿刺公鑰密碼方案的構(gòu)造思想應(yīng)用到IBS，基于Paterson 等[3]的IBS方案構(gòu)造了一個(gè)具體的IBPS 方案，其密鑰更新過(guò)程只需進(jìn)行一次布隆過(guò)濾器中的元素刪除操作。

3) 基于計(jì)算性Diffie-Hellman（CDH,computational Diffie-Hellman）假設(shè)，在隨機(jī)預(yù)言模型下證明了所構(gòu)造IBPS 方案滿(mǎn)足存在不可偽造性，并通過(guò)仿真實(shí)驗(yàn)展示了方案的實(shí)際性能。

2 相關(guān)工作

Yu 等[14]基于Waters[16]提出的基于身份加密方案，利用二叉樹(shù)結(jié)構(gòu)首次構(gòu)造了前向安全的IBS 方案。在這種構(gòu)造中，系統(tǒng)的生命周期被離散化為N個(gè)子周期，通過(guò)單向地周期性更新私鑰和刪除前一周期的私鑰，用戶(hù)可以在每個(gè)時(shí)間周期內(nèi)使用不同的私鑰，從而實(shí)現(xiàn)了前向安全性。沿用類(lèi)似的方法，魏江宏等[17]提出了前向安全的密文策略基于屬性加密方案；Wei 等[18]在前向安全I(xiàn)BS 的基礎(chǔ)上通過(guò)用戶(hù)撤銷(xiāo)引入了后向安全性；Oh 等[19]進(jìn)一步考慮了系統(tǒng)主密鑰泄露的問(wèn)題，提出了能同時(shí)抵抗用戶(hù)私鑰泄露和系統(tǒng)主密鑰泄露的IBS 方案；楊小東等[20]在標(biāo)準(zhǔn)模型下提出了可撤銷(xiāo)的基于身份的代理重簽名方案。

事實(shí)上，上述方案的構(gòu)造方法在一定程度上源于前向安全的公鑰加密方案[21]，因此也就繼承了其局限性。為實(shí)現(xiàn)更實(shí)用的細(xì)粒度前向安全性，Green等[15]提出了可穿刺公鑰加密方案的概念，并基于支持非單調(diào)訪(fǎng)問(wèn)結(jié)構(gòu)的基于屬性加密方案構(gòu)造了具體的可穿刺公鑰加密方案。隨后，Wei 等[22]構(gòu)造了密文長(zhǎng)度固定的可穿刺的基于身份加密方案。為提高可穿刺加密方案中私鑰穿刺的效率，Derler 等[23]進(jìn)一步提出了布隆過(guò)濾器加密方案，并基于不同密碼學(xué)原語(yǔ)給出了多種構(gòu)造方案。

類(lèi)似于可穿刺的公鑰加密方案，可穿刺簽名方案同樣能提供簽名的細(xì)粒度前向安全性，由Bellare等[24]首次提出。但是，他們給出的通用構(gòu)造依賴(lài)于不可區(qū)分混淆和單向函數(shù)，具有較高的計(jì)算開(kāi)銷(xiāo)，在實(shí)際中不可用。Halevi 等[25]雖然也提出了一個(gè)可穿刺簽名方案，但是需要在私鑰穿刺操作后更新公鑰，帶來(lái)了較大的公鑰管理負(fù)擔(dān)。Li 等[26]基于布隆過(guò)濾器加密方案構(gòu)造了具有較高穿刺效率的可穿刺簽名方案，并將其應(yīng)用到了區(qū)塊鏈中的權(quán)益證明協(xié)議。

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

3.1 布隆過(guò)濾器

布隆過(guò)濾器[27]是一種經(jīng)典的隨機(jī)數(shù)據(jù)結(jié)構(gòu)，通過(guò)一個(gè)簡(jiǎn)短的二進(jìn)制序列T來(lái)表示一個(gè)集合S，并能高效地判定一個(gè)元素s是否屬于該集合。具體而言，在集合S 上進(jìn)行查詢(xún)時(shí)，若s∈S，則以概率1 返回1，表示s確實(shí)在集合S 中；若s?S，則以概率1-δ返回0，表示s不在集合S 中，其中δ為假陽(yáng)性概率，即當(dāng)s?S 時(shí)，仍以δ的概率返回1。

定義1布隆過(guò)濾器[27]。令U 為元素取值空間，其上的布隆過(guò)濾器 B=(BFGen,BFUpdate,BFCheck) 由3 個(gè)子算法組成，具體定義如下。

BFGen (?,k)，生成算法。以2個(gè)正整數(shù) ?,k∈N為輸入，首先選擇k個(gè)一般的Hash 函數(shù)H1,…,Hk，其中Hj:U→[ ?]，并令（長(zhǎng)度為? 且各個(gè)位置均為0 的字符串），最后輸出(H,T)。

BFUpdate (H,T,u)，更新算法。以Hash 函數(shù)族過(guò)濾器當(dāng)前狀態(tài)T∈{0,1}?和一個(gè)元素u∈U 為輸入，首先令T′←T，然后對(duì)任意的整數(shù)j∈ [k]，令T′[H j(u)]=1，其中T′[i]表示T′的第i位，最后返回更新后的過(guò)濾器狀態(tài)T′。

BFCheck (H,T,u)，檢驗(yàn)算法。同樣以Hash函數(shù)族過(guò)濾器的當(dāng)前狀態(tài)T∈{0,1}?和一個(gè)元素u∈U 為輸入，然后計(jì)算并輸出一個(gè)比特

如上定義的布隆過(guò)濾器具有完善的完備性、假陽(yáng)性概率有界、集合表示緊致等特性。

3.2 雙線(xiàn)性映射與CDH 假設(shè)

定義2雙線(xiàn)性映射。令G 和GT是2 個(gè)階為p的乘法循環(huán)群，其中p是一個(gè)長(zhǎng)度為λ（安全參數(shù)）的素?cái)?shù)，令g為G 的隨機(jī)生成元，則雙線(xiàn)性映射e:G × G →GT滿(mǎn)足下述條件的映射。

1) 雙線(xiàn)性：對(duì)任意的群元素x,y∈G 和任意的整數(shù)a,b∈Zp，e(x a,yb)=e(x,y)ab均成立。

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

3) 可計(jì)算性：對(duì)任意的群元素x,y∈G，存在一個(gè)多項(xiàng)式時(shí)間算法能有效計(jì)算出e(x,y)。

為方便描述，用一個(gè)五元組 (G,GT,g,p,e)來(lái)表示如上定義的雙線(xiàn)性映射。進(jìn)一步，定義在群G 上的CDH 問(wèn)題是指，給定群元素g a,gb∈G，要求計(jì)算gab，其中是隨機(jī)選取的整數(shù)。

定義3CDH 假設(shè)。對(duì)于任意一個(gè)概率多項(xiàng)式時(shí)間的攻擊者A，給定g a,gb∈G，若其輸出gab的概率是λ的可忽略函數(shù)，則稱(chēng)CDH 假設(shè)在群G 上成立。

4 可穿刺的IBS 方案定義

4.1 形式化定義

IBPS 方案可看作一般的IBS 方案在安全性方面的增強(qiáng)，也可看作可穿刺簽名方案針對(duì)無(wú)公鑰基礎(chǔ)設(shè)施情形下的擴(kuò)展。粗略而言，可穿刺的簽名方案比一般簽名方案多了一個(gè)私鑰穿刺算法，即當(dāng)用戶(hù)的私鑰在每簽名完一個(gè)消息后，需要利用該消息在用戶(hù)私鑰上進(jìn)行穿刺操作，以防用戶(hù)私鑰被再次用來(lái)產(chǎn)生該消息的簽名。

通過(guò)結(jié)合一般的IBS 方案[3]和可穿刺加密/簽名方案[23,26]的形式化定義，下面給出IBPS 方案的形式化定義，共由5 個(gè)多項(xiàng)式時(shí)間的算法組成。

Setup()λ，系統(tǒng)建立算法。輸入系統(tǒng)安全參數(shù)λ，輸出系統(tǒng)公開(kāi)參數(shù)pp 和系統(tǒng)主密鑰msk。

Extract(pp,msk,ID)，私鑰提取算法。輸入系統(tǒng)公開(kāi)參數(shù)pp、系統(tǒng)主密鑰msk 和用戶(hù)身份ID，輸出相應(yīng)的初始私鑰skID。

Punc(pp,skID,m)，私鑰穿刺算法。輸入系統(tǒng)公開(kāi)參數(shù)pp、用戶(hù)的當(dāng)前私鑰skID和一個(gè)用該私鑰簽名過(guò)的消息m，輸出一個(gè)更新過(guò)的私鑰sk′ID，此時(shí)也稱(chēng)sk′ID是被消息m穿刺過(guò)的私鑰。

Sign(pp,skID,m)，簽名算法。輸入系統(tǒng)公開(kāi)參數(shù)pp、用戶(hù)當(dāng)前私鑰skID和待簽名消息m，輸出對(duì)消息m的簽名σ。

Verify(pp,σ,m,ID)，驗(yàn)證算法。輸入系統(tǒng)公開(kāi)參數(shù)pp、簽名σ、簽名消息m和用戶(hù)身份ID，當(dāng)σ是一個(gè)關(guān)于ID 和m的有效簽名時(shí)輸出1，否則輸出0。

一個(gè)IBPS 方案是正確的是指，對(duì)任意按正確方式生成的公開(kāi)參數(shù)和主密鑰(pp,msk)←Setup(λ)、任意用戶(hù)初始私鑰skID←Extract (pp,msk,ID)以及任意簽名消息集M={m1,…,mq}和簽名消息m∈M，有

總成立。對(duì)反復(fù)穿刺q次后的用戶(hù)私鑰Punc(pp,skID,mi)(i∈ [q])，只要簽名消息m?M，則

總成立。

4.2 安全性定義

為定義IBPS 方案的存在不可偽造性，在安全模型中給攻擊者提供了私鑰提取詢(xún)問(wèn)、簽名詢(xún)問(wèn)和私鑰穿刺詢(xún)問(wèn)。此外，為刻畫(huà)前向安全性，還允許攻擊者詢(xún)問(wèn)挑戰(zhàn)者身份所對(duì)應(yīng)的私鑰，但所返回的私鑰必須是被挑戰(zhàn)消息穿刺過(guò)的。具體而言，IBPS方案的存在不可偽造性通過(guò)一個(gè)挑戰(zhàn)者C 和一個(gè)敵手A 之間的安全游戲來(lái)定義，主要包含以下3 個(gè)階段。

系統(tǒng)建立階段。給定安全參數(shù)λ，挑戰(zhàn)者C 運(yùn)行系統(tǒng)建立算法Setup(λ)→(pp,msk)，然后將系統(tǒng)公開(kāi)參數(shù)pp 發(fā)送給敵手A，而自己持有系統(tǒng)主密鑰msk。同時(shí)，挑戰(zhàn)者C 初始化4 個(gè)空集

詢(xún)問(wèn)階段。在該階段，敵手A 可以自適應(yīng)地進(jìn)行以下3 種詢(xún)問(wèn)。

1) 私鑰提取詢(xún)問(wèn)。敵手A 向挑戰(zhàn)者C 提交一個(gè)用戶(hù)身份ID，要求挑戰(zhàn)者C 返回相應(yīng)的私鑰skID。接收到該詢(xún)問(wèn)后，挑戰(zhàn)者C 直接運(yùn)行私鑰提取算法Extract(pp,ms k,ID)→skID，同時(shí)更新集合Qsk←Qsk∪{ID}，然后將skID發(fā)送給敵手A。

2) 簽名詢(xún)問(wèn)。敵手A 向挑戰(zhàn)者C 提交一個(gè)用戶(hù)身份ID 和消息m，要求挑戰(zhàn)者C 返回相應(yīng)的簽名σ。挑戰(zhàn)者C 首先調(diào)用私鑰生成算法Extract(pp,msk,ID) →skID，然后運(yùn)行簽名算法Sign(pp,skID,m)→σ，同時(shí)更新集合Qsig←Qsig∪{(ID,m)}和Qσ←Qσ∪{σ}，最后將簽名 發(fā)送給敵手A。

3) 穿刺詢(xún)問(wèn)。敵手A 向挑戰(zhàn)者C 提交一個(gè)用戶(hù)身份ID 和消息m，要求挑戰(zhàn)者C 返回相應(yīng)被m穿刺過(guò)的用戶(hù)私鑰為此，挑戰(zhàn)者首先通過(guò)調(diào)用私鑰生成算法產(chǎn)生用戶(hù)的初始私鑰，即Extract(pp,ms k,ID)→skID，然后調(diào)用私鑰穿刺算法Punc(pp,skID,m)→同時(shí)更 新集合Qpunc←Qpunc∪{(ID,m)}，最后將穿刺過(guò)后的私鑰sk′ID發(fā)送給敵手A。

偽造階段。敵手A 結(jié)束詢(xún)問(wèn)階段之后，輸出一個(gè)關(guān)于(m*,ID*)的簽名σ*。

若以下條件同時(shí)滿(mǎn)足，則稱(chēng)敵手A 贏得了上述安全性游戲。

定義4IBPS 的存在不可偽造性。對(duì)任意一個(gè)針對(duì)IBPS方案的概率多項(xiàng)式時(shí)間敵手A，若其贏得上述安全游戲的概率是λ的一個(gè)可忽略函數(shù)，則稱(chēng)該IBPS 方案滿(mǎn)足存在不可偽造性。

本文考慮一種較弱的存在不可偽造性，即選擇性存在不可偽造性，要求敵手A 在開(kāi)始安全性游戲之前就將挑戰(zhàn)消息m*提交給挑戰(zhàn)者C。

5 方案具體構(gòu)造

基于Paterson 等[3]的IBS 方案，本節(jié)給出一個(gè)具體的IBPS 方案構(gòu)造，其核心在于如何實(shí)現(xiàn)用戶(hù)密鑰的穿刺操作。為此，本文借鑒Derler 等[23]提出的密鑰穿刺機(jī)制，利用布隆過(guò)濾器來(lái)管理用戶(hù)私鑰和簽名消息。具體而言，在生成用戶(hù)私鑰時(shí)，先初始化一個(gè)布隆過(guò)濾器(H,T)←BFGen(?,k)，然后對(duì)于T的每一個(gè)位置i∈[ ? ]，生成一個(gè)相應(yīng)的私鑰構(gòu)件ski；在對(duì)消息m進(jìn)行簽名時(shí)，首先利用H將其映射到T的k個(gè)位置，從中選取一個(gè)滿(mǎn)足T[i′] ≠ 1的位置i′，然后利用相應(yīng)的用戶(hù)私鑰構(gòu)件進(jìn)行簽名；在完成對(duì)m的簽名之后，將m添加到布隆過(guò)濾器中并更新其狀態(tài)BFUpdate(H,T,m)→T′，同時(shí)，在所有滿(mǎn)足T′[i]=1的位置，將相應(yīng)的用戶(hù)私鑰構(gòu)件設(shè)置為ski←⊥?？梢钥闯?，通過(guò)上述密鑰穿刺過(guò)程，用戶(hù)私鑰不能對(duì)已簽名過(guò)的消息進(jìn)行再次簽名。具體構(gòu)造的IBPS 方案由以下5 個(gè)算法組成。

Setup(λ)。給定系統(tǒng)安全參數(shù)λ之后，系統(tǒng)建立算法首先生成雙線(xiàn)性群 (G,GT,g,p,e)；然后，分別定義用戶(hù)身份標(biāo)識(shí)空間ID={0,1}γ和簽名消息空間M={0,1}η，選擇 2 個(gè) Hash 函數(shù)H:{0,1}*→{0,1}γ和H′:{0,1}*→{0,1}η，以及另外一個(gè) Hash 函數(shù)H～ :N →G ；選擇隨機(jī)群元素g2,u0,vo∈G，以及2 個(gè)隨機(jī)向量u=(u1,… ,uγ)∈Gγ和v=(v1,…,vη)∈Gη；最后，選擇一個(gè)隨機(jī)整數(shù)α∈Zp，計(jì)算g1=gα，并令系統(tǒng)主密鑰為系統(tǒng)公開(kāi)參數(shù)為pp={(G,GT,g,p,e),

Extract(pp,msk,ID)。給定系統(tǒng)公開(kāi)參數(shù)pp、系統(tǒng)主密鑰msk 和用戶(hù)身份ID∈{0,1}*，私鑰提取算法首先將ID 映射到系統(tǒng)定義的身份標(biāo)識(shí)空間，即令θ=H(ID)=(θ1,…,θγ) ∈{0,1}γ；然后，初始化一個(gè)布隆過(guò)濾器(H,T)←BFGen(?,k)，其中T=0?；選擇隨機(jī)整數(shù)r1,r2∈Zp，對(duì)任意整數(shù)i∈[? ]，按如下方式計(jì)算私鑰構(gòu)件ski。

最后，按照如下結(jié)構(gòu)輸出用戶(hù)私鑰。

Punc(pp,skID,m)。給定系統(tǒng)公開(kāi)參數(shù)pp、用戶(hù)的當(dāng)前私鑰和一個(gè)消息m∈{0,1}*，令ω=H′(m)=(ω1,…,ωη)∈{0,1}η；然后，將消息m添加到布隆過(guò)濾器的集合中，并對(duì)其狀態(tài)進(jìn)行更新，即令T′←BFUpdate(H,T,m)；對(duì)任意i∈［ ? ］，按照如下方式對(duì)相應(yīng)的私鑰構(gòu)件進(jìn)行更新。

Sign(pp,skID,m) 。給定公開(kāi)參數(shù)pp、用戶(hù)當(dāng)前私鑰和待簽名消息m，若BFCheck(H,T,m)→1，則輸出錯(cuò)誤符號(hào)⊥，否則，存在一個(gè)指標(biāo)i*∈{i1,… ,ik}使其中i j=H j(m)(j∈ [k])；令ω=H′(m)=(ω1,…,ωη)，選取隨機(jī)指數(shù)rm∈Zp，計(jì)算

最后，返回簽名σ={i*,σ o,σ1,σ2,σ3}。

Verify(pp,σ,m,ID)。給定公開(kāi)參數(shù)pp、簽名σ={i*,σ o,σ1,σ2,σ3}、消息m和用戶(hù)身份ID，首先令θ=H(ID)=(θ1,…,θγ)和ω=H′(m)=(ω1,…,ωη)；然后，驗(yàn)證下述等式是否成立。

若等式成立，則說(shuō)明σ是一個(gè)關(guān)于ID 和m的有效簽名，輸出1；否則輸出0。

方案正確性依據(jù)私鑰生成算法可知，私鑰構(gòu)件sk*i的值為將其代入式(5)可得

6 安全性證明及性能分析

6.1 安全性證明

定理1IBPS 方案安全性。對(duì)于依據(jù)安全參數(shù)λ生成的雙線(xiàn)性群 (G,GT,g,p,e)，若CDH 假設(shè)在群G 上成立，則所構(gòu)造的IBPS 方案在隨機(jī)預(yù)言模型下滿(mǎn)足選擇性的存在不可偽造性。具體地，有

其中，qpunc是私鑰穿刺詢(xún)問(wèn)次數(shù)，qsk是私鑰提取詢(xún)問(wèn)次數(shù)，qsig是簽名詢(xún)問(wèn)次數(shù)。

證明為證明定理1，主要采用Waters[16]提出的證明技巧，同時(shí)以隨機(jī)預(yù)言機(jī)的方式模擬Hash函數(shù)對(duì)其進(jìn)行擴(kuò)展。下面，給出挑戰(zhàn)者C 模擬安全性游戲各個(gè)階段的細(xì)節(jié)。

系統(tǒng)建立階段在初始階段，挑戰(zhàn)者C 收到一個(gè)雙線(xiàn)性群 (G,GT,g,p,e)，以及群G 上CDH 問(wèn)題的實(shí)例(g a,gb)，其中a和b是選自中的隨機(jī)整數(shù)，C 的目標(biāo)是計(jì)算出gab。此外，敵手A 需在安全性游戲開(kāi)始之前提交挑戰(zhàn)消息m*。

在上述定義的基礎(chǔ)上，按如下方式設(shè)置所構(gòu)造IBPS 方案的系統(tǒng)公開(kāi)參數(shù)

最后，C 初始化4 個(gè)空集Qsk←?、Qsig←?、Qσ←?和Qpunc←?，并將按照上述方式生成的系統(tǒng)公開(kāi)參數(shù)發(fā)送給攻擊者A，同時(shí)還向其提供Hash 函數(shù)的查詢(xún)服務(wù)。

詢(xún)問(wèn)階段在該階段，A 可以自適應(yīng)地進(jìn)行私鑰提取查詢(xún)、簽名查詢(xún)和私鑰穿刺查詢(xún)，這3 種詢(xún)問(wèn)同時(shí)還涉及Hash 函數(shù)H,H′,的詢(xún)問(wèn)。對(duì)于H和H′，挑戰(zhàn)者將它們模擬成一般的抗碰撞Hash函數(shù)。對(duì)于Hash 函數(shù)，挑戰(zhàn)者C 按照如下方式進(jìn)行模擬：對(duì)任意i∈[ ? ]，選擇一個(gè)隨機(jī)整數(shù)ti∈Zp，若有i∈{H j(m*):j∈[k]}，則直接令否則令下面給出C 響應(yīng)3 種查詢(xún)的方式。

1) 私鑰提取詢(xún)問(wèn)。給定一個(gè)用戶(hù)身份ID，C 先令H(ID)=(θ1,…,θγ)，此時(shí)H被模擬成一個(gè)一般的抗碰撞Hash 函數(shù)。進(jìn)一步，若有F(ID)=0 modp，則C 終止模擬，否則C 選擇隨機(jī)整數(shù)令然后，C 計(jì)算ID 所對(duì)應(yīng)的私鑰構(gòu)件ski

從式(8)中可以看出，盡管C 不知道系統(tǒng)主密鑰，但上述私鑰構(gòu)件對(duì)其都是可計(jì)算的，并且與按照真實(shí)的私鑰提取算法所產(chǎn)生的私鑰是同分布的。最后，C 將ID 的私鑰發(fā)送給敵手A，同時(shí)更新集合

2) 簽名詢(xún)問(wèn)。給定用戶(hù)身份ID 和待簽名消息m，挑戰(zhàn)者C 首先將它們映射到相應(yīng)的二進(jìn)制字符串，即此時(shí)若有則C 通過(guò)調(diào)用私鑰提取詢(xún)問(wèn)先生成相應(yīng)的用戶(hù)私鑰skID，然后直接利用IBPS方案的簽名算法即可生成關(guān)于ID 和m的正確簽名，并返回給敵手A。另一方面，若F(ID)=0 modp且K(m)=0 modp，則C 終止安全性游戲，否則C 選擇隨機(jī)整數(shù)并令，然后按照下述方式生成簽名

可以看出，上述簽名構(gòu)件對(duì)C 都是可計(jì)算的，且與IBPS 方案中的簽名算法所產(chǎn)生的簽名同分布。最后，C 將關(guān)于ID 和m的簽名σ={i*,σ o,σ1,σ2,σ3}返回給敵手A，同時(shí)更新集合Qsig←Qsig∪{(ID,m)}和Qσ←Qσ∪{σ}。

3) 私鑰穿刺詢(xún)問(wèn)。在響應(yīng)該詢(xún)問(wèn)之前，挑戰(zhàn)者C 先猜測(cè)敵手A 的第j次該詢(xún)問(wèn)是關(guān)于挑戰(zhàn)身份ID*的查詢(xún)，若猜測(cè)失敗，則終止安全性游戲。對(duì)于關(guān)于其他用戶(hù)身份的私鑰穿刺詢(xún)問(wèn)，C 先調(diào)用私鑰提取詢(xún)問(wèn)得到相應(yīng)的用戶(hù)私鑰，然后利用IBPS方案的私鑰穿刺算法即可得到穿刺后的私鑰，并將其返回給敵手A。特別地，對(duì)于A 的第j次詢(xún)問(wèn)，由安全模型中對(duì)敵手的約束可知，此時(shí)A 提供的就是挑戰(zhàn)身份ID*和挑戰(zhàn)消息m*。為生成穿刺后的用戶(hù)私鑰，C 選擇隨機(jī)整數(shù)對(duì)任意i∈[ ? ]，若，則令ski←⊥，否則按照下述方式計(jì)算ski

偽造階段敵手A 結(jié)束詢(xún)問(wèn)階段之后，輸出一個(gè)關(guān)于(m*,ID*)的簽名同時(shí)滿(mǎn)足下述條件。

此時(shí)，若F(ID*) ≠0 modp或K(m*) ≠0 modp，則挑戰(zhàn)者C 直接終止安全性游戲。最終，若挑戰(zhàn)者C沒(méi)有終止安全性?xún)?yōu)勢(shì)，則可按照下述方式計(jì)算出gab。

從而解決了給定的CDH 問(wèn)題實(shí)例。

概率分析挑戰(zhàn)者C 能計(jì)算出abg的前提是不終止安全性游戲，而由Waters[16]的“artificial abort”分析技術(shù)可得，C 不終止安全性游戲的概率為

6.2 性能分析

表1 給出了本文所提IBPS 方案與其他相關(guān)簽名方案在計(jì)算開(kāi)銷(xiāo)和存儲(chǔ)開(kāi)銷(xiāo)方面的比較。在比較過(guò)程中，用e 表示一次模指數(shù)運(yùn)算，p 表示一次雙線(xiàn)性對(duì)運(yùn)算，γ表示用戶(hù)身份的長(zhǎng)度，η表示簽名消息的長(zhǎng)度，? 表示布隆過(guò)濾器的數(shù)組長(zhǎng)度，N表示時(shí)間周期總數(shù)，G 表示一個(gè)群元素。在比較過(guò)程中忽略運(yùn)算時(shí)間非常小的Hash 運(yùn)算。

表1 相關(guān)簽名方案的計(jì)算/存儲(chǔ)開(kāi)銷(xiāo)比較

從表1 中可以看出，相比于Paterson 等[3]的IBS 方案，本文所提IBPS 方案在私鑰提取算法上具有較大的計(jì)算開(kāi)銷(xiāo)，這主要是由于為了實(shí)現(xiàn)細(xì)粒度的前向安全性，額外地為布隆過(guò)濾器所對(duì)應(yīng)的二進(jìn)制序列的每一個(gè)位置上都生成了一個(gè)私鑰構(gòu)件。另一方面，相比于Yu 等[14]的前向安全I(xiàn)BS方案，本文所提IBPS 方案的密鑰穿刺/更新開(kāi)銷(xiāo)主要是Hash 運(yùn)算和刪除運(yùn)算，幾乎可以忽略，而Yu 等[14]的前向安全I(xiàn)BS 方案的密鑰更新開(kāi)銷(xiāo)與總的時(shí)間周期數(shù)目成對(duì)數(shù)關(guān)系。此外，在存儲(chǔ)開(kāi)銷(xiāo)方面，本文所提IBPS 方案的公開(kāi)參數(shù)規(guī)模與Paterson 等[3]的IBS 方案相當(dāng)，而Yu 等[14]的前向安全I(xiàn)BS 方案具有更大的公開(kāi)參數(shù)規(guī)模。在簽名長(zhǎng)度方面，本文所提方案與Yu 等[14]的前向安全I(xiàn)BS 方案相同，均略高于Paterson 等[3]的IBS 方案。特別地，Yu 等[14]的前向安全I(xiàn)BS 方案的私鑰規(guī)模與總的時(shí)間周期總數(shù)的對(duì)數(shù)成平方關(guān)系，具有較高的存儲(chǔ)開(kāi)銷(xiāo)。

表2 給出了相關(guān)簽名方案在安全性質(zhì)方面的比較。從表2 可以看出，只有本文所提方案具有細(xì)粒度的前向安全性，但其安全性卻是在隨機(jī)預(yù)言模型下證明的，而非標(biāo)準(zhǔn)模型。此外，在安全性假設(shè)方面，Yu 等[14]方案的安全性基于一個(gè)更強(qiáng)的q-型Diffie-Hellman 指數(shù)困難性問(wèn)題假設(shè)。

表2 相關(guān)簽名方案的安全性質(zhì)比較

6.3 仿真實(shí)驗(yàn)

為驗(yàn)證所構(gòu)造IBPS 方案的實(shí)際性能，將其在Charm[28]框架下進(jìn)行了實(shí)現(xiàn)，并測(cè)試了各個(gè)算法的實(shí)際運(yùn)行時(shí)間。所有的測(cè)試實(shí)驗(yàn)均是在具有16 GB內(nèi)存和i7-1160G7@1.20GHz CPU 的PC 上進(jìn)行的。

在仿真實(shí)驗(yàn)中，布隆過(guò)濾器中的集合規(guī)模設(shè)置為n=220，即允許用戶(hù)在一年中每天向其中添加 212個(gè)元素，同時(shí)布隆過(guò)濾器的假陽(yáng)性概率設(shè)置為δ=10-3，表示布隆過(guò)濾器的字符串長(zhǎng)度為?=1.7 ×107，Hash 函數(shù)個(gè)數(shù)為k=10。在一般的前向安全I(xiàn)BS 方案中，設(shè)定總的時(shí)間周期數(shù)為N=219，即允許用戶(hù)在一年的時(shí)間里每隔一分鐘更新一次私鑰。所采用的 Hash 函數(shù)均為SHA-256，橢圓曲線(xiàn)為Charm 提供的SS512 曲線(xiàn)和SS1024 曲線(xiàn)。

圖1 給出了相關(guān)基于身份簽名方案中各個(gè)算法運(yùn)行時(shí)間對(duì)比。從圖1 可以看出，本文所提IBPS方案的私鑰抽取算法的運(yùn)行時(shí)間要遠(yuǎn)高于其他2 個(gè)方案，但該算法一般都是離線(xiàn)運(yùn)行且執(zhí)行一次，故在實(shí)際中不影響系統(tǒng)性能。另一方面，本文所提IBPS方案的私鑰更新效率非常高。具體地，在SS512 曲線(xiàn)下，私鑰穿刺算法的運(yùn)行時(shí)間僅有2.32 s，而Yu等[14]方案中算法的運(yùn)行時(shí)間則接近350 s，比本文所提IBPS 方案高了近150 倍。

圖1 相關(guān)基于身份簽名方案中各個(gè)算法運(yùn)行時(shí)間對(duì)比

圖2 給出了相關(guān)IBS 方案的存儲(chǔ)開(kāi)銷(xiāo)。從圖2可以看出，由于產(chǎn)生了私鑰構(gòu)件的多個(gè)備份，本文所提IBPS 方案具有較大的私鑰規(guī)模。

圖2 相關(guān)IBS 方案的存儲(chǔ)開(kāi)銷(xiāo)

6.4 方案應(yīng)用

本文所提IBPS 方案可以在任何部署過(guò)IBS 的場(chǎng)景中使用，以增強(qiáng)用戶(hù)私鑰的前向安全性。下面以IBPS 在監(jiān)控系統(tǒng)的應(yīng)用為例，如圖3 所示。目前的物聯(lián)網(wǎng)技術(shù)和無(wú)線(xiàn)通信技術(shù)支持部署大規(guī)模的監(jiān)控系統(tǒng)，物聯(lián)網(wǎng)設(shè)備、智能手機(jī)、無(wú)線(xiàn)攝像頭、無(wú)線(xiàn)相機(jī)等向云服務(wù)器提供視頻和圖像，即向監(jiān)控系統(tǒng)提供監(jiān)控?cái)?shù)據(jù)。一個(gè)安全可靠的監(jiān)控系統(tǒng)，應(yīng)該做到設(shè)備提供的視頻和圖像確保是真實(shí)的，不是被修改或偽造的；設(shè)備需要諸如公鑰證書(shū)等憑證來(lái)提供視頻和圖像的真實(shí)性；任何攻擊或私鑰泄露不會(huì)破壞所有以前的監(jiān)控?cái)?shù)據(jù)，即應(yīng)當(dāng)保證監(jiān)控?cái)?shù)據(jù)的前向安全。

圖3 IBPS 在監(jiān)控系統(tǒng)的應(yīng)用

本文所提IBPS 方案為解決上述實(shí)際問(wèn)題提供了可靠對(duì)策。圖3 中的每個(gè)設(shè)備將其身份標(biāo)識(shí)注冊(cè)到云服務(wù)器，密鑰服務(wù)器負(fù)責(zé)為每個(gè)設(shè)備分發(fā)與其身份標(biāo)識(shí)對(duì)應(yīng)的私鑰，同時(shí)，把自己的公鑰發(fā)送給云服務(wù)器。當(dāng)設(shè)備發(fā)送數(shù)據(jù)時(shí)，先對(duì)數(shù)據(jù)簽名，然后把簽名和數(shù)據(jù)一起發(fā)送，而云服務(wù)器只接受其簽名有效的數(shù)據(jù)。這樣，一方面保證了數(shù)據(jù)來(lái)源的真實(shí)性，另一方面云服務(wù)器利用密鑰服務(wù)器的公鑰驗(yàn)證接收的數(shù)據(jù)，而設(shè)備不需要攜帶證書(shū)。每發(fā)送完一次數(shù)據(jù)，該設(shè)備都進(jìn)行密鑰穿刺操作，完成私鑰的更新。這保證了任何設(shè)備在私鑰泄露的情況下，該設(shè)備所有以前的簽名仍然有效。

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

本文針對(duì)已有的前向安全的基于身份簽名方案的靈活性不強(qiáng)、私鑰更新效率較低的問(wèn)題，通過(guò)引入可穿刺公鑰加密思想，提出了基于身份的可穿刺簽名方案?；赑aterson 等[3]的基于身份簽名方案，利用布隆過(guò)濾器構(gòu)造了一個(gè)具體的基于身份的可穿刺簽名方案，以較高的存儲(chǔ)開(kāi)銷(xiāo)為代價(jià)，實(shí)現(xiàn)了簽名的細(xì)粒度前向安全性和用戶(hù)私鑰的高效更新。安全性證明表明，本文所提IBPS 方案在隨機(jī)預(yù)言模型下滿(mǎn)足存在不可偽造性。理論分析和實(shí)驗(yàn)結(jié)果表明，本文所提IBPS 方案在安全性和效率方面具有優(yōu)勢(shì)，更適合在實(shí)際應(yīng)用中部署。