強(qiáng)不可偽造的基于身份服務(wù)器輔助驗(yàn)證簽名方案

楊小東，楊苗苗，高國(guó)娟，李亞楠，魯小勇，王彩芬

?

強(qiáng)不可偽造的基于身份服務(wù)器輔助驗(yàn)證簽名方案

楊小東，楊苗苗，高國(guó)娟，李亞楠，魯小勇，王彩芬

（西北師范大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，甘肅蘭州 730070）

標(biāo)準(zhǔn)模型下的基于身份簽名方案大多數(shù)是存在性不可偽造的，無法阻止攻擊者對(duì)已經(jīng)簽名過的消息重新偽造一個(gè)合法的簽名，并且驗(yàn)證簽名需要執(zhí)行耗時(shí)的雙線性對(duì)運(yùn)算。為了克服已有基于身份簽名方案的安全性依賴強(qiáng)和計(jì)算代價(jià)大等缺陷，提出了一個(gè)強(qiáng)不可偽造的基于身份服務(wù)器輔助驗(yàn)證簽名方案，并在標(biāo)準(zhǔn)模型下證明了新方案在合謀攻擊、自適應(yīng)選擇身份和消息攻擊下是安全的。分析結(jié)果表明，新方案有效減少了雙線性對(duì)的計(jì)算量，大大降低了簽名驗(yàn)證算法的計(jì)算復(fù)雜度，在效率上優(yōu)于已有的基于身份簽名方案。

基于身份服務(wù)器輔助驗(yàn)證簽名；強(qiáng)不可偽造性；合謀攻擊；標(biāo)準(zhǔn)模型

1 引言

基于身份密碼體制是一種將用戶身份標(biāo)識(shí)作為公鑰的密碼體制，用于解決公鑰基礎(chǔ)設(shè)施PKI/CA中數(shù)字證書的存儲(chǔ)和管理開銷等問題[1]。在基于身份的密碼體制中，用戶的E-mail地址等唯一身份標(biāo)識(shí)作為用戶的公鑰，密鑰生成中心PKG借助主密鑰生成相應(yīng)的用戶私鑰。由于不再需要使用傳統(tǒng)的公鑰證書，因而大大減輕了密鑰的管理與分發(fā)開銷。2001年，Boneh和Franklin[2]利用雙線性對(duì)工具首次構(gòu)造出高效的基于身份加密方案；隨后國(guó)內(nèi)外學(xué)者對(duì)基于身份密碼體制進(jìn)行了大量的研究，并取得一系列原創(chuàng)性研究成果[3~6]。

然而，大部分基于身份簽名方案的簽名驗(yàn)證算法都要進(jìn)行耗時(shí)的雙線性對(duì)計(jì)算，不能有效地應(yīng)用于各類低端計(jì)算設(shè)備。手機(jī)、無線傳感器、智能手表等低端計(jì)算設(shè)備便于攜帶，但能源供應(yīng)有限、計(jì)算和存儲(chǔ)能力較弱。因此，應(yīng)用于低端計(jì)算設(shè)備的簽名方案必須優(yōu)先考慮計(jì)算量。然而，雙線性對(duì)是目前比較耗時(shí)的密碼操作[7]，迫切需要研究新的基于身份簽名方案，減少簽名驗(yàn)證算法中的雙線性對(duì)計(jì)算量。

基于身份的服務(wù)器輔助驗(yàn)證簽名將基于身份簽名體制和服務(wù)器輔助驗(yàn)證簽名體制相結(jié)合，驗(yàn)證簽名合法性的大部分計(jì)算量交給服務(wù)器執(zhí)行，驗(yàn)證者只需進(jìn)行少量的計(jì)算，從而有效減輕了驗(yàn)證者的計(jì)算負(fù)擔(dān)，提高簽名驗(yàn)證的性能，非常適用于低端計(jì)算設(shè)備?；谏矸莘?wù)器輔助驗(yàn)證簽名的研究才剛剛起步，公開的相關(guān)文獻(xiàn)較少。2013年，Zhang等[8]設(shè)計(jì)了一個(gè)基于身份的服務(wù)器輔助驗(yàn)證簽名方案，但其安全依賴于現(xiàn)實(shí)世界無法實(shí)現(xiàn)的隨機(jī)預(yù)言機(jī)假設(shè)。一個(gè)在隨機(jī)預(yù)言模型下可證明安全的密碼系統(tǒng)，在現(xiàn)實(shí)中無法確保它的安全性[9]。標(biāo)準(zhǔn)模型下安全的基于身份簽名方案能消除理想隨機(jī)預(yù)言機(jī)的安全假設(shè)，但已有的這類方案[10,11]僅能抵抗攻擊者的存在性不可偽造。由于強(qiáng)不可偽造性能同時(shí)確保攻擊者不能對(duì)未簽名消息和已簽名消息進(jìn)行偽造簽名，被用來設(shè)計(jì)群簽名方案、簽密方案及電子現(xiàn)金系統(tǒng)等[12,13]，所以研究強(qiáng)不可偽造的基于身份服務(wù)器輔助驗(yàn)證簽名方案具有一定的現(xiàn)實(shí)意義。

2014年，Kwon[14]構(gòu)造了一個(gè)滿足強(qiáng)不可偽造安全屬性的基于身份簽名方案，在標(biāo)準(zhǔn)模型中具有系統(tǒng)公開參數(shù)少、簽名短等特點(diǎn)，但簽名驗(yàn)證算法需要3個(gè)雙線性對(duì)運(yùn)算。為了克服已有基于身份簽名方案的安全性依賴強(qiáng)和計(jì)算代價(jià)大等缺陷，本文基于Kwon方案[14]設(shè)計(jì)了一個(gè)強(qiáng)不可偽造的服務(wù)器輔助驗(yàn)證簽名方案，并證明新方案在合謀攻擊和強(qiáng)不可偽造攻擊下是安全的。新方案的簽名驗(yàn)證算法避免了復(fù)雜的雙線性對(duì)運(yùn)算，與現(xiàn)有的同類方案相比，具有更低的計(jì)算復(fù)雜度，可應(yīng)用于簽名驗(yàn)證時(shí)間受限或計(jì)算能力有限的設(shè)備。目前還沒有關(guān)于標(biāo)準(zhǔn)模型下強(qiáng)不可偽造的基于身份服務(wù)器輔助驗(yàn)證簽名研究的公開文獻(xiàn)。

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

2.1 雙線性映射

2.2 CDH假設(shè)

定義1 計(jì)算性Diffie-Hellman（CDH, computational Diffie-Hellman）問題。設(shè)是一個(gè)大素?cái)?shù)，是階為的循環(huán)群，是的任意一個(gè)生成元，已知，對(duì)于未知的，計(jì)算。

定義2 CDH假設(shè)。若沒有一個(gè)多項(xiàng)式時(shí)間算法能以不可忽略的概率求解上的CDH問題，那么稱群上的CDH問題是困難的[6]。

3 強(qiáng)不可偽造的基于身份服務(wù)器輔助驗(yàn)證簽名的形式化安全定義

一個(gè)強(qiáng)不可偽造的基于身份服務(wù)器輔助驗(yàn)證簽名方案包括下面6個(gè)算法。

6) SAV-Verify (,){0, 1}是服務(wù)器輔助驗(yàn)證協(xié)議。給定字符串、用戶身份和消息簽名對(duì)，驗(yàn)證者在服務(wù)器的協(xié)助下驗(yàn)證的正確性，若當(dāng)是對(duì)應(yīng)于的的合法簽名，輸出1；否則，輸出0。

服務(wù)器可以是具有強(qiáng)大計(jì)算能力的云服務(wù)提供商，驗(yàn)證者是計(jì)算能力較弱的云計(jì)算終端（如智能手機(jī)等），利用SAV-Verify交互協(xié)議在服務(wù)器的幫助下完成簽名的合法性驗(yàn)證。

一個(gè)強(qiáng)不可偽造的基于身份服務(wù)器輔助驗(yàn)證簽名方案至少應(yīng)滿足基于身份簽名的強(qiáng)不可偽造性和服務(wù)器輔助驗(yàn)證協(xié)議SAV-Verify的完備性。強(qiáng)不可偽造性能確保攻擊者無法生成一個(gè)未簽名消息或已簽名消息的有效簽名，完備性保證服務(wù)器不能讓驗(yàn)證者確信一個(gè)非法簽名是合法的。為了改進(jìn)文獻(xiàn)[8]給出的基于身份服務(wù)器輔助驗(yàn)證簽名的安全模型，假設(shè)服務(wù)器不僅與合法的簽名者合謀，也可以與非法的簽名者合謀。由于服務(wù)器能獲得任何消息的簽名，因此無法給出一個(gè)統(tǒng)一的安全定義來刻畫基于身份服務(wù)器輔助驗(yàn)證簽名的強(qiáng)不可偽造性和服務(wù)器輔助驗(yàn)證協(xié)議的完備性。文獻(xiàn)[12,14]已給出了基于身份簽名方案的強(qiáng)不可偽造性安全定義，下面借助攻擊者A和挑戰(zhàn)者C之間的安全游戲，給出在合謀攻擊和自適應(yīng)性選擇消息攻擊下服務(wù)器輔助驗(yàn)證協(xié)議的完備性安全定義。在這個(gè)游戲中，攻擊者A擁有主密鑰和簽名密鑰。

建立：挑戰(zhàn)者C首先運(yùn)行系統(tǒng)參數(shù)生成算法Setup、密鑰提取算法Extract和服務(wù)器輔助驗(yàn)證參數(shù)生成算法SAV-Setup，生成系統(tǒng)參數(shù)、字符串、主密鑰和身份/私鑰對(duì)(,)，然后將發(fā)送給A。

定義4 若攻擊者A在以上游戲中獲勝的概率是可忽略的，則稱SAV-Verify協(xié)議滿足完備性。

利用簽名方案的存在不可偽造性和服務(wù)器輔助驗(yàn)證協(xié)議的完備性，文獻(xiàn)[15]給出了服務(wù)器輔助驗(yàn)證簽名的安全性定義，文獻(xiàn)[8]給出了基于身份服務(wù)器輔助驗(yàn)證簽名的安全性定義。采用類似的方法，下面給出強(qiáng)不可偽造的基于身份服務(wù)器輔助驗(yàn)證簽名的安全性定義。

定義5 若基于身份簽名方案滿足強(qiáng)不可偽造性，服務(wù)器輔助驗(yàn)證協(xié)議滿足完備性，則稱相應(yīng)的基于身份服務(wù)器輔助驗(yàn)證簽名方案是安全的。

4 強(qiáng)不可偽造的基于身份服務(wù)器輔助驗(yàn)證簽名方案設(shè)計(jì)

本節(jié)在Kwon方案[14]的基礎(chǔ)上，設(shè)計(jì)一個(gè)強(qiáng)不可偽造的基于身份服務(wù)器輔助驗(yàn)證簽名方案，與Kwon方案的主要區(qū)別是降低了簽名驗(yàn)證者的計(jì)算量，將簽名驗(yàn)證的大部分計(jì)算任務(wù)通過服務(wù)器輔助驗(yàn)證協(xié)議轉(zhuǎn)移給一個(gè)不可信的服務(wù)器執(zhí)行。因此，驗(yàn)證者在服務(wù)器的協(xié)助下完成簽名的驗(yàn)證，具有更低的計(jì)算復(fù)雜度，可應(yīng)用于簽名驗(yàn)證時(shí)間受限或計(jì)算能力有限的設(shè)備。新方案包含的6個(gè)算法具體如下。

1) Setup算法

密鑰生成中心PKG選擇2個(gè)素?cái)?shù)階的循環(huán)群和，選取一個(gè)的生成元，選擇一個(gè)雙線性映射和一個(gè)抗碰撞的散列函數(shù)；然后隨機(jī)選取個(gè)元素，并隨機(jī)選取，計(jì)算和；最后PKG將作為自己的秘密主密鑰，公開相應(yīng)的系統(tǒng)參數(shù)=。

2) Extract算法

3) Sign算法

4) Verify算法

③驗(yàn)證式(2)是否成立。

5) SAV-Setup算法

6) SAV-Verify協(xié)議

5 安全性證明與有效性分析

5.1 合理性分析

1) 密鑰提取算法的合理性

2) 服務(wù)器輔助驗(yàn)證協(xié)議的正確性驗(yàn)證

于是有

5.2 安全性分析

本文提出的新方案基于Kwon方案[14]，而文獻(xiàn)[14]基于CDH困難問題假設(shè)，已在標(biāo)準(zhǔn)模型下證明了Kwon方案滿足強(qiáng)不可偽造性。由定義5可知，僅需證明服務(wù)器輔助驗(yàn)證協(xié)議滿足完備性，就可以證明本文方案是安全的。

定理1 本文方案的服務(wù)器輔助驗(yàn)證協(xié)議能抵抗合謀攻擊，并在自適應(yīng)性選擇消息擊下滿足完備性。

證明 在執(zhí)行服務(wù)器輔助驗(yàn)證協(xié)議SAV-Verify中，攻擊者A代表服務(wù)器，挑戰(zhàn)者C代表驗(yàn)證者。A發(fā)送給C一個(gè)非法的消息簽名對(duì)，A的目標(biāo)是讓C確信是消息的合法簽名。

3) 輸出。經(jīng)過有限次的詢問后，攻擊者A將偽造的消息簽名對(duì)發(fā)送給挑戰(zhàn)者C，這里是對(duì)應(yīng)于用戶身份的所有合法簽名的集合，。挑戰(zhàn)者利用計(jì)算，將發(fā)送給攻擊者A。A首先檢查的坐標(biāo)的最右邊比特值，然后計(jì)算，，和，并將返回給挑戰(zhàn)者C。

在本文方案的服務(wù)器輔助驗(yàn)證協(xié)議SAV-Verify中，驗(yàn)證者將的冪運(yùn)算值發(fā)送給攻擊者，由于參數(shù)對(duì)服務(wù)器是保密的，因而可有效抵抗針對(duì)服務(wù)器輔助驗(yàn)證簽名方案的各類合謀攻擊[16,17]。

定理2 在標(biāo)準(zhǔn)模型下，Kwon方案在自適應(yīng)性選擇身份和消息攻擊下滿足強(qiáng)不可偽造性[14]。

定理3 在標(biāo)準(zhǔn)模型下，本文提出的基于身份服務(wù)器輔助驗(yàn)證簽名方案在合謀攻擊、自適應(yīng)選擇身份和消息攻擊下是安全的。

通過定義5、定理1和定理2，很容易得到定理3。

5.3 性能比較

為了表述方便，用PS方案表示Paterson和Schuldt[10]提出的基于身份簽名方案，TTS方案表示Tsai等[12]提出的基于身份簽名方案，ZS-SAVIDS-1方案和ZS- SAVIDS-2方案分別表示Zhang等[8]提出的第1個(gè)和第2個(gè)基于身份服務(wù)器輔助驗(yàn)證簽名方案。假定所有方案選擇相同長(zhǎng)度的素?cái)?shù)，以及相同階的群和。由于計(jì)算量比較大的密碼學(xué)操作是雙線性對(duì)與冪運(yùn)算，因此不再詳細(xì)討論其余運(yùn)算操作。用表示上的冪運(yùn)算，用表示上的冪運(yùn)算，用表示雙線對(duì)運(yùn)算的數(shù)量，所有方案的比較結(jié)果如表1所示。

由表1可知，在本文方案中驗(yàn)證者只需進(jìn)行2次冪運(yùn)算；但在Kwon方案中，驗(yàn)證者的計(jì)算開銷是3次雙線性對(duì)和1次冪運(yùn)算，因此根據(jù)定義3可得知本文方案是計(jì)算節(jié)約的。

與其他5個(gè)方案相比，本文方案的簽名驗(yàn)證者的計(jì)算開銷最小，大大提高了簽名的驗(yàn)證速度，具有較高的計(jì)算效率，在低端計(jì)算設(shè)備中具有更好的適應(yīng)性。雖然Zhang等[8]提出的2個(gè)方案具有較短的簽名長(zhǎng)度，但這2個(gè)方案的安全性依賴于理想隨機(jī)預(yù)言機(jī)，而本文方案的安全性僅依賴于CDH困難問題，并滿足強(qiáng)不可偽造性，具有更高的安全性。本文方案與Kwon方案[14]的系統(tǒng)公開參數(shù)長(zhǎng)度相同，但小于PS方案[10]和TTS方案[12]的系統(tǒng)參數(shù)長(zhǎng)度，具有較高的通信代價(jià)。

表1 計(jì)算開銷與安全性能比較

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

基于Kwon方案和CDH假設(shè)，提出了一個(gè)強(qiáng)不可偽造的基于身份服務(wù)器輔助驗(yàn)證簽名方案，其安全性不依賴于理想的隨機(jī)預(yù)言機(jī)。驗(yàn)證者在本文方案中不需要執(zhí)行耗時(shí)的雙線性對(duì)運(yùn)算，大大降低了驗(yàn)證者的計(jì)算開銷。本文方案的系統(tǒng)參數(shù)小，通信代價(jià)低，非常適用于各類低端計(jì)算設(shè)備。下一步的工作是設(shè)計(jì)具有更短公開參數(shù)的基于身份服務(wù)器輔助驗(yàn)證簽名方案。

[1] SHAMIR A. Identity-based cryptosystems and signature schemes[C]// CRYPTO 1984, LNCS 0196. Springer Berlin Heidelberg, c1984: 47-53.

[2] BONEH D, FRANKLIN M. Identity-based encryption from the Weil pairing[C]//CRYPTO 2001, LNCS 2139. Springer Berlin Heidelberg, c2001: 213-229.

[3] KAR J. Provably secure on-line/off-line identity-based signature scheme for wireless sensor network[J]. IJ Network Security, 2014, 16(1): 29-39.

[4] TIAN M, HUANG L. Efficient identity-based signature from lattices[M]. ICT Systems Security and Privacy Protection, Springer Berlin Heidelberg, 2014: 321-329.

[5] TSENG Y M, TSAI T T, HUANG S S. Leakage-free ID-based signature[J]. The Computer Journal, 2015, 58(4): 750-757.

[6] ATTRAPADUNG N, EMURA K, HANAOKA G, et al. A revocable group signature scheme from identity-based revocation techniques: achieving constant-size revocation list[C]//Applied Cryptography and Network Security.c2014: 419-437.

[7] HAO S G, LI Z, GHULAM M. A union authentication protocol of cross-domain based on bilinear pairing[J]. Journal of Software, 2013, 8(5): 1094-1100.

[8] ZHANG J, SUN Z. An ID-based server-aided verification short signature scheme avoid key escrow[J]. Journal of Information Science and Engineering, 2013, 29(3): 459-473.

[9] CANETTI R, GOLDREICH O, HALEVI S. The random oracle methodology, revisited[J]. Journal of the ACM, 2004, 51(4): 557-594.

[10] PATERSON K G, SCHULDT J C N. Efficient identity-based signatures secure in the standard model[C]//ACISP, LNCS 4058. Springer Berlin Heidelberg, c2006: 207-222.

[11] WU Q, ZHANG L Y. New strongly unforgeable identity-based signature scheme in the standard model[J]. Journal of Beijing University of Posts and Telecommunications, 2011, 34(3): 71-74.

[12] TSAI T T, TSENG Y M, HUANG S S. Efficient strongly unforgeable ID-based signature without random oracles[J]. Informatica, 2014, 25(3): 505-521.

[13] HUNG Y H, TSAI T T, TSENG Y M, et al. Strongly secure revocable ID-based signature without random oracles[J]. Information Technology and Control, 2014, 43(3): 264-276.

[14] KWON S. An identity-based strongly unforgeable signature without random oracles from bilinear pairings [J]. Information Sciences, 2014, 276(1): 1-9.

[15] WU W, MU Y, SUSILO W, et al. Provably secure server-aided verification signatures[J]. Computers & Mathematics with Applications, 2011, 61(7): 1705-1723.

[16] WANG Z, WANG L, YANG Y, et al. Comment on Wu, et al.'s server-aided verification signature schemes[J]. IJ Network Security, 2010, 10(2): 158-160.

[17] WU H, XU C X, DENG J, et al. On the security of server-aided verification signature schemes[J]. Journal of Computational Information System, 2013, 9(4): 1449-1454.

ID-based server-aided verification signature scheme with strong unforgeability

YANG Xiao-dong, YANG Miao-miao, GAO Guo-juan, LI Ya-nan, LU Xiao-yong, WANG Cai-fen

(College of Computer Science and Engineering, Northwest Normal University, Lanzhou 730070, China)

Most identity-based signature schemes in the standard model are existentially unforgeable, which cannot prevent adversaries from forging valid signatures on messages that have previously been signed. However, signature verification algorithms of ID-based signature schemes in the standard model require expensive bilinear pairing operations. In order to overcome the shortcomings of the existing ID-based signature schemes such as strong security assumption and high computation cost，a strongly unforgeable ID-based server-aided verification signature scheme was presented. This scheme was proven to be secure under collusion attacks, adaptive chosen identity and message attacks in the standard model. Analysis results show that the proposed scheme effectively reduces computation cost of pairing operation, and it greatly reduces computational complexity of signature verification algorithm. The proposed scheme is more efficient than the existing ID-based signature schemes.

ID-based server-aided verification signature, strong unforgeability, collusion attack, standard model

TP309

A

10.11959/j.issn.1000-436x.2016115

2015-07-21；

2015-09-10

國(guó)家自然科學(xué)基金資助項(xiàng)目（No.61262057）；甘肅省科技計(jì)劃基金資助項(xiàng)目（No.145RJDA325）；國(guó)家檔案局科技基金資助項(xiàng)目（No.2014-X-33）；甘肅省高等學(xué)?？蒲谢鹳Y助項(xiàng)目（No.2014-A011）；蘭州市科技計(jì)劃基金資助項(xiàng)目（No.2013-4-22）；西北師范大學(xué)青年教師科研能力提升計(jì)劃基金資助項(xiàng)目（No.NWNU-LKQN-13-23, No.NWNU-LKON-14-7）

The National Natural Science Foundation of China (No.61262057), The Natural Science Foundation of Gansu Province (No.145RJDA325), The Science and Technology Project of State Archives Administration of China (No.2014-X-33), Research Fund of Higher Education of Gansu Province (No.2014-A011), Science and Technology Project of Lanzhou City of China (No.2013-4-22), The Foundation for Excellent Young Teachers by Northwest Normal University (No.NWNU-LKQN-13-23, No.NWNU-LKON-14-7)

楊小東（1981-），男，甘肅甘谷人，西北師范大學(xué)副教授，主要研究方向?yàn)槊艽a學(xué)及云計(jì)算安全。

楊苗苗（1991-），女，甘肅金昌人，西北師范大學(xué)碩士生，主要研究方向?yàn)榇髷?shù)據(jù)安全。

高國(guó)娟（1991-），女，甘肅永登人，西北師范大學(xué)碩士生，主要研究方向?yàn)樾畔踩?/p>

李亞楠（1990-），男，山東沂州人，西北師范大學(xué)碩士生，主要主要研究方向?yàn)榫W(wǎng)絡(luò)安全。

魯小勇（1982-），男，甘肅張掖人，西北師范大學(xué)博士生、工程師，主要研究方向?yàn)樾畔⑾到y(tǒng)安全。

王彩芬（1963-），女，河北安國(guó)人，西北師范大學(xué)教授、博士生導(dǎo)師，主要研究方向?yàn)槊艽a學(xué)、網(wǎng)絡(luò)安全和信息安全。