強不可偽造的基于身份服務器輔助驗證簽名方案

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

?

強不可偽造的基于身份服務器輔助驗證簽名方案

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

（西北師范大學計算機科學與工程學院，甘肅蘭州 730070）

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

基于身份服務器輔助驗證簽名；強不可偽造性；合謀攻擊；標準模型

1 引言

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

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

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

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

2 預備知識

2.1 雙線性映射

2.2 CDH假設

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

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

3 強不可偽造的基于身份服務器輔助驗證簽名的形式化安全定義

一個強不可偽造的基于身份服務器輔助驗證簽名方案包括下面6個算法。

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

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

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

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

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

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

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

4 強不可偽造的基于身份服務器輔助驗證簽名方案設計

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

1) Setup算法

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

2) Extract算法

3) Sign算法

4) Verify算法

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

5) SAV-Setup算法

6) SAV-Verify協(xié)議

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

5.1 合理性分析

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

2) 服務器輔助驗證協(xié)議的正確性驗證

于是有

5.2 安全性分析

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

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

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

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

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

定理2 在標準模型下，Kwon方案在自適應性選擇身份和消息攻擊下滿足強不可偽造性[14]。

定理3 在標準模型下，本文提出的基于身份服務器輔助驗證簽名方案在合謀攻擊、自適應選擇身份和消息攻擊下是安全的。

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

5.3 性能比較

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

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

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

表1 計算開銷與安全性能比較

6 結束語

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

[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

國家自然科學基金資助項目（No.61262057）；甘肅省科技計劃基金資助項目（No.145RJDA325）；國家檔案局科技基金資助項目（No.2014-X-33）；甘肅省高等學校科研基金資助項目（No.2014-A011）；蘭州市科技計劃基金資助項目（No.2013-4-22）；西北師范大學青年教師科研能力提升計劃基金資助項目（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-），男，甘肅甘谷人，西北師范大學副教授，主要研究方向為密碼學及云計算安全。

楊苗苗（1991-），女，甘肅金昌人，西北師范大學碩士生，主要研究方向為大數(shù)據(jù)安全。

高國娟（1991-），女，甘肅永登人，西北師范大學碩士生，主要研究方向為信息安全。

李亞楠（1990-），男，山東沂州人，西北師范大學碩士生，主要主要研究方向為網(wǎng)絡安全。

魯小勇（1982-），男，甘肅張掖人，西北師范大學博士生、工程師，主要研究方向為信息系統(tǒng)安全。

王彩芬（1963-），女，河北安國人，西北師范大學教授、博士生導師，主要研究方向為密碼學、網(wǎng)絡安全和信息安全。