何明星，李鵬程，李 虓

高效的可證明安全的無證書數(shù)字簽名方案

何明星，李鵬程，李 虓

(西華大學(xué)計算機與軟件工程學(xué)院 成都 610039)

無證書公鑰密碼體制結(jié)合了基于身份和傳統(tǒng)PKI公鑰密碼體制的優(yōu)勢，克服了基于身份公鑰密碼體制的密鑰托管問題及PKI系統(tǒng)的證書管理問題，具有很高的效率。該文提出一個在隨機預(yù)言機模型下可證明安全的無證書數(shù)字簽名方案。該方案只需分別在系統(tǒng)初始化階段、驗證階段預(yù)進(jìn)行一次雙線性對運算，而在簽名階段不需要進(jìn)行計算。計算結(jié)果證明該方案比以往的無證書數(shù)字簽名方案具有更高的計算效率和通信效率，且具有隨機預(yù)言機模型下的可證明安全性。

雙線性對; 無證書數(shù)字簽名; 可證明安全; 數(shù)字簽名

文獻(xiàn)[1]首次提出了基于身份的數(shù)字簽名方案。文獻(xiàn)[2]第一次提出雙線性對的概念，并利用雙線性對構(gòu)造了一個基于身份的數(shù)字簽名方案。文獻(xiàn)[3]首次構(gòu)造了一個無證書數(shù)字簽名方案，該方案也是基于雙線性對的，但并沒有對該方案進(jìn)行嚴(yán)格的安全性證明和安全性分析。文獻(xiàn)[4]論證了文獻(xiàn)[3]的不安全性，容易受到公鑰替換攻擊，敵手可以假冒用戶對任意消息進(jìn)行偽造簽名。文獻(xiàn)[5-6]中的方案也不能抵抗公鑰替換攻擊。此外，經(jīng)過分析發(fā)現(xiàn)文獻(xiàn)[6]中用戶還可以恢復(fù)出SEM擁有的對應(yīng)于該用戶私鑰的另一部分私鑰，使得該簽名方案無仲裁性質(zhì)。文獻(xiàn)[7]構(gòu)造了一個高效的無證書數(shù)字簽名方案，它基于離散對數(shù)困難性假設(shè)，該方案在簽名中不需要“雙線性對”運算，在驗證階段僅需2次“雙線性對”運算。但文獻(xiàn)[8]發(fā)現(xiàn)文獻(xiàn)[7]的方案也不能抵抗公鑰替換攻擊。文獻(xiàn)[9-11]也從不同側(cè)面對安全性和有效性進(jìn)行了更加深入和廣泛的討論。本文在這些成果基礎(chǔ)上提出一個新的在隨機預(yù)言機模型下可證明安全的無證書數(shù)字簽名方案，且比以往的無證書數(shù)字簽名方案具有更高的計算效率和通信效率。

1 無證書數(shù)字簽名模型

1.1 無證書數(shù)字簽名

一個無證書數(shù)字簽名系統(tǒng)由密鑰生成中心(key generate center, KGC)、簽名者(signaturer)、驗證者(verifier)3個合法參與者構(gòu)成。包含7個多項式時間算法：

1) 系統(tǒng)初始化算法：輸入系統(tǒng)安全參數(shù)1k后，返回KGC的主私鑰(master secret key,MSK)以及系統(tǒng)全局參數(shù)。

2) 部分私鑰提取算法：輸入用戶身份字符串ID∈{0,1}*({0,1}*表示所有的比特串集合)、系統(tǒng)主私鑰MSK及系統(tǒng)公開參數(shù)，由KGC返回用戶部分私鑰D。

3) 設(shè)置秘密值算法：用戶隨機選擇一個秘密值x，用于生成用戶的公鑰及私鑰。

4) 用戶公鑰生成算法：用戶輸入秘密值x及系統(tǒng)公開參數(shù)后，生成自己的公鑰PK。

5) 用戶私鑰生成算法：用戶輸入秘密值x及由KGC生成的部分私鑰D，返回完整的私鑰SK。

6) 簽名算法：該算法是概率多項式時間算法。簽名發(fā)送者在執(zhí)行算法過程中，輸入待簽名消息m∈MCLS、簽名發(fā)送者身份IDS、完整私鑰SKS和公鑰PKS、簽名驗證方身份IDR、全局參數(shù)及一些隨機數(shù)r∈RCLS。算法執(zhí)行完畢后，若簽名正確則輸出消息m∈MCLS對應(yīng)的簽名σ∈ΣCLS；否則輸出錯誤標(biāo)識“⊥”。

7) 簽名驗證算法：輸入簽名σ∈ΣCLS、簽名發(fā)送者用戶身份IDS、公鑰PKS、簽名驗證方身份IDR及系統(tǒng)全局參數(shù)。算法由簽名驗證者執(zhí)行完畢后，若驗證簽名正確則輸出“接受簽名”；否則輸出錯誤標(biāo)識“⊥”。

1.2 無證書數(shù)字簽名體制的敵手

無證書數(shù)字簽名體制的敵手[3]分為兩類：1) 敵手IA定義為外部的惡意敵手，是主動敵手，不知道系統(tǒng)的主私鑰MSK，但擁有替換用戶公鑰的能力；2) 敵手IIA是一個誠實但好奇(honest-but- curious)的KGC，是一個被動敵手，擁有系統(tǒng)的主私鑰MSK，但不能替換用戶的公鑰。

在隨機預(yù)言機模型下，一個無證書數(shù)字簽名方案的可證明安全性，可通過一個挑戰(zhàn)者C與敵手IA或者IIA進(jìn)行交互來確定。

1.2.1 游戲1(針對敵手IA)

1) 系統(tǒng)初始化：挑戰(zhàn)者C輸入系統(tǒng)安全參數(shù)l，運行初始化算法，獲取系統(tǒng)主私鑰MSK及全局參數(shù)，然后將系統(tǒng)全局參數(shù)發(fā)送給敵手IA，并對系統(tǒng)主私鑰MSK保密。

2) 攻擊階段：敵手IA可以進(jìn)行多項式次的交互詢問。

① 請求公鑰詢問PK(IDi)：當(dāng)敵手AI向挑戰(zhàn)者提交一個合法的身份IDi并請求詢問該IDi的公鑰后，挑戰(zhàn)者返回提交IDi相對應(yīng)的公鑰PK(IDi)。

② 替換公鑰詢問PKR(IDi,PK′IDi)：當(dāng)敵手AI向挑戰(zhàn)者提交一個合法的身份IDi以及一個偽造的合符系統(tǒng)格式的公鑰PK′IDi后，挑戰(zhàn)者應(yīng)該利用提交的偽造公鑰PK′IDi替換掉敵手提交IDi的當(dāng)前公鑰PKIDi。

③ 秘密值詢問SV(IDi)：當(dāng)敵手AI向挑戰(zhàn)者提交一個合法的身份IDi并請求詢問該IDi的秘密值xi后，如果該IDi的公鑰未被替換，那么挑戰(zhàn)者向敵手返回該IDi對應(yīng)的秘密值xIDi；否則模擬失敗。

④ 部分私鑰提取詢問PPK(IDi)：當(dāng)敵手AI向挑戰(zhàn)者提交一個合法的身份IDi并請求詢問該IDi的部分私鑰后，挑戰(zhàn)者返回提交IDi相對應(yīng)的部分私鑰DIDi。

⑤ 私鑰提取詢問SK(IDi)：當(dāng)敵手AI向挑戰(zhàn)者提交一個合法的身份IDi并請求詢問該IDi的私鑰后，挑戰(zhàn)者返回提交IDi相對應(yīng)的私鑰SKIDi，如果該IDi對應(yīng)的公鑰被替換，則模擬失敗。

⑥ 簽名詢問Sig(Mi,IDi,PKi)：敵手AI可以對任何用戶IDi對消息Mi的簽名進(jìn)行詢問，挑戰(zhàn)者收到一個挑戰(zhàn)(Mi,IDi,PKi)后，挑戰(zhàn)者C對消息Mi生成一個簽名σi作于對敵手AI的回答。這里要求對消息Mi生成簽名σi對于用戶IDi和其對應(yīng)的公鑰PKIDi是有效的。

3) 偽造階段：最后，若敵手AI輸出一個元組(M*,σ*,ID*,PK)，當(dāng)且僅當(dāng)滿足以下3個條件，

ID*敵手AI獲得該游戲的勝利。

① 對于用戶ID*和其對應(yīng)的公鑰PKID*，元組中簽名σi是有效的。

② 敵手AI沒有對用戶ID*進(jìn)行過部分私鑰提取詢問。

1.2.2 游戲2

與游戲1不同之處：AII僅有請求公鑰詢問PK(IDi)、秘密值詢問SV(IDi)、私鑰提取詢問SK(IDi)、簽名詢問Sig(Mi,IDi,PKi)的能力。AII不像AI具有公鑰替換的能力PKR(IDi,PK′ID)：當(dāng)AI向挑戰(zhàn)者提交一個合法的身份IDi及一個偽造的符合系統(tǒng)格式的公鑰PK′ID后，挑戰(zhàn)者應(yīng)利用提交的偽造公鑰PK′ ID替換AI提交IDi的當(dāng)前公鑰PKIDi。

2 高效的無證書數(shù)字簽名方案

2.1 無證書數(shù)字簽名方案描述

系統(tǒng)初始化算法分為以下5個步驟：

1) KGC首先生成素數(shù)q階的加法循環(huán)群G1及乘法循環(huán)群G2，任意選擇一個生成元P∈G1。

3) KGC計算得到系統(tǒng)主公鑰P0=sP∈G1。

4) KGC預(yù)計算雙線性對e( P, P)=g∈G2，e是一個雙線性映射。

5) 最后，KGC選擇兩個密碼學(xué)安全的Hash函數(shù)H1:{0,1}*→(×表示集合間的笛卡爾積)。

部分私鑰提取算法分為兩個步驟：

用戶公鑰生成算法執(zhí)行分為兩個步驟：

1) 計算得到身份哈希值：

2) 用戶iU計算得到公鑰：

2) Alice計算U=H2(M||R|| T)∈。

3) Alice計算得到消息簽名V=x( U?1D?

最后，Alice通過公開信道將簽名σ=＜R, T, V＞發(fā)送給Bob。

簽名驗證算法執(zhí)行步驟：Bob在接收到Alice發(fā)送的簽名σ=＜R, T, V＞后驗證簽名。

1) Bob首先計算U′=H2(M||R|| T)∈。

2) Bob驗證等式：

若成立，則接受簽名；否則拒絕簽名。

2.2 無證書數(shù)字簽名方案的正確性分析

在一般的數(shù)字簽名中，簽名的原始消息對于簽名發(fā)送方以及簽名驗證方均是公開的，所以如果對消息的簽名在傳輸過程中沒有被敵手篡改，那么簽名驗證方在收到簽名后，首先計算出正確的U′=(M||R|| T)∈，有U=U′∈，簽名則能通過式(3)的驗證，即：

3 無證書數(shù)字簽名方案的安全性證明

定理 1 無證書數(shù)字簽名方案在k-CCA困難性假設(shè)及隨機預(yù)言機(Random Oracle)模型下，對敵手AI可抵抗存在性偽造攻擊。

證明：挑戰(zhàn)者算法C首先與敵手ΑI交互生成k-CCA困難問題的實例。

初始化階段：設(shè)置PPub=sP, g=e( P, P)。值得注意的是系統(tǒng)主私鑰是保密的。隨后C隨機選擇一個指數(shù)l∈{1,2,…,k }，這里k≤qH1。

1) H1詢問

ΑI可以不重復(fù)地對每一個身份IDi(i∈{1, 2,…,k})進(jìn)行詢問：

① 若i≠l，C向ΑI返回QID=ti，并將元組(i,ID,QID=ti)添加進(jìn)一個初始化為空的表L1；

② 若i=l，則C向ΑI返回身份值QID=t0，并將元組(i,ID,QID=t0)添加進(jìn)H1哈希詢問所維護(hù)的表L1。

2) H2詢問

對于ΑI提起的每一個詢問(Mi, R, T)：

① C首先檢查表L2，若表中存在一個元組(Mi, R, T, h2)，那么C向ΑI返回相對應(yīng)的Hash值；

② 否則，C任意選擇一個Hash值h2∈Zq*返回給ΑI，并將相應(yīng)的元組(Mi, R, T, h2)添加進(jìn)表L2；

③ 提取部分私鑰詢問，ΑI就一個身份IDi向C提起提取部分私鑰詢問請求；

④ 若i=l，C終止該預(yù)言機的模擬；

⑤ 若i≠l，C首先查表LK={i,ID,xID,DID, PKID}，如果表中存在該IDi對應(yīng)的元組，則向ΑI返回對應(yīng)的；否則，挑戰(zhàn)者C先以ID作i一次H1哈希詢問，并將元組(i,ID,)更新到表L1，然后向ΑI返回對應(yīng)ID的部分私鑰DID=(s+，并將元組{i,ID,⊥,,⊥}更新到表，這里“⊥”表示為空。

3) 秘密值詢問

當(dāng)AI向C以IDi并提起詢問后：

① C首先查表LK，如果該表中存在一個元組{i,ID,xID,DID,PKID}該IDi的公鑰未被替換，那么C向AI返回該ID對應(yīng)的秘密值xID，否則輸出模擬失敗。

② 否則，C先以IDi作一次H1哈希詢問，并將元組(i,ID,QID=ti)更新到表L1，然后再作一次部分私鑰詢問并隨機選擇一個xID∈Zq*，最后向ΑI返回秘密值xID并將元組{i,ID,xID,DID,PKID}更新到表LK，元組中插入的公鑰PKID為C成秘密值后利用公鑰生成算法獲得的。

4) 請求公鑰詢問

對于ΑI的每一個詢問IDi：

① C首先查表LK，如果該表中存在一個元組{i,ID,xID,DID,PKID}，則返回該ID所對應(yīng)的公鑰PKID；

② 否則，C先以IDi作一次H1哈希詢問，并將元組(i,ID,QID=ti)更新到表L1，然后執(zhí)行一次秘密值詢問，執(zhí)行公鑰生成算法為其生成一個新的公鑰對返回給ΑI，并將新的元組{i,ID,xID,DID,PKID}添加進(jìn)該詢問維護(hù)的表LK。

5) 替換公鑰詢問

ΑI向挑戰(zhàn)者提交一個合法的元組(ID,PK′ID)：

① C首先根據(jù)ID搜索表LK，如果表中存在對應(yīng)ID的元組，則將其內(nèi)容更新為{i,ID,⊥,DID,PK′ID}；

② 否則，C先以IDi作一次H1哈希詢問，并將元組(i,ID,QID=ti)更新到表L1，然后再作一次部分私鑰提取，并將新元組{i,ID,⊥,DID,PK′ID}插入進(jìn)表LK。C并不知道敵手偽造用戶公鑰所用到的秘密值xI′D。

6) 提取私鑰詢問

ΑI就一個身份IDi向C起提取私鑰詢問后：

① 若i=l，挑戰(zhàn)者終止該預(yù)言機的模擬；

② 若i≠l，分兩種情況：

第一，挑戰(zhàn)者查表LK，若表中存在該ID對應(yīng)的元組，但是該用戶的公鑰已經(jīng)被替換，挑戰(zhàn)者模擬失敗；否則返回該用戶對應(yīng)的私鑰SKID=(xID,DID)；

第二，若表LK中不存在該ID對應(yīng)的元組，查表L1，找到該ID對應(yīng)的身份哈希值QID，如果該ID對應(yīng)元組不存在，則以該ID作一次H1詢問，并將元組(i,ID,QID=ti)更新到表L1，然后執(zhí)行一次秘密值提取詢問，將新元組{i,ID,xID,DID,⊥}插入表LK并向ΑI返回提交ID私鑰SKID=(xID,DID)。

7） 簽名詢問

在預(yù)言機詢問中，ΑI提交的詢問內(nèi)容為一個元組(Mi,IDi,PKIDi)，無論該ID公鑰是否被替換，C均能生成一個合法的簽名(通過驗證等式)：

① 任意選擇兩個隨機數(shù)r, t∈Zq*，計算得到R=gr, T=gt；

② 計算U=H2(Mi||R|| T )；

③ 計算V=rU?1D?PK，并將生成的簽名

IDA(V, R, T)返回給ΑI。

8) 偽造階段

最后，ΑI輸出一個成功的偽造元組(M*,σ*= (V*,R*, T*),ID*,PKID*)，元組里的簽名σ*是能通過驗證等式的，ID*≠IDl，若挑戰(zhàn)者終止模擬；否則，利用文獻(xiàn)[12]中的的攻擊方法，C進(jìn)行重放攻擊，生成另一個偽造元組(M*,σ*=(V*,R*, T*), ID*,PKID*)，這里要求Α及簽名σ*需滿足：

最后C則通過兩次偽造簽名的恒等性e( V*+P))獲得k-CCA困難性問題的解

定理 2 無證書數(shù)字簽名方案在kCCA?困難性假設(shè)以及隨機預(yù)言機模型下，對敵手IIA可以抵抗存在性偽造攻擊。思路與方法同定理1。

4 無證書數(shù)字簽名方案的效率分析

表1列舉了本文方案與其他無證書數(shù)字簽名方案在簽名以及驗證階段中計算效率和簽名規(guī)模上的比較?？梢钥闯觯疚姆桨概c其他的無證書數(shù)字簽名方案相比，不但費時的雙線性對運算比其他的無證書數(shù)字簽名方案少，而且指數(shù)運算和計算快速的倍點運算也與其他無證書數(shù)字簽名方案相當(dāng)，可見本文方案具有更高的運算效率；另外，本文方案的簽名規(guī)模也和其他方案大致平衡；最后，在協(xié)議的執(zhí)行過程中，本文方案不需要復(fù)雜的運行費時的映射到點(map-to-point)的Hash函數(shù)。因此，本文方案是一個高效的無證書數(shù)字簽名方案。

表1 4個無證書數(shù)字簽名方案的效率對比

5 結(jié) 論

本文提出了一個在隨機預(yù)言機模型下可證明安全的無證書數(shù)字簽名方案。方案僅需在系統(tǒng)初始化階段預(yù)計算一次雙線性對，在驗證階段計算一次雙線性對，而在簽名階段不需要進(jìn)行雙線性對運算，因此本方案比以往一些無證書數(shù)字簽名方案具有更高的計算效率和通信效率。

[1] SHAMIR A. Identity-based cryptosystems and signature schemes[C]//Advances in Cryptology-CRYPTO’84. Berlin: Springer-Verlag, 1984.

[2] SAKAI R, OHGISHI K, KASAHARA M. Cryptosystems based on pairing[C]//Proceedings of Symposium on Cryptography and Information Security. Okinawa, Japan: [s.n.], 2000.

[3] AL-RIYAMI S, PATERSON K G. Certificateless public key cryptography[C]//Advances in Cryptology-ASIACRYPT’03. Berlin: Springer-Verlag, 2003.

[4] HUANG Xin-yi, WILLY SUSILO, YI MU, et al. On the security of a certificateless signature scheme from Asiacrypt 2003[C]//4th International Conference on Cryptology and Network Security. Berlin: Springer-Verlag, 2005.

[5] LI X, CHEN K, SUN L. Certificateless signature and proxy signature schemes from bilinear pairings[J]. Lietuvos Matematikos Rinkinys, 2005, 45(1): 76-83.

[6] JU H, KIM D, LEE D, et al. Efficient revocation of security capability in certificateless public key cryptography [C]//Knowledge-Based Intelligent Information and Engineering Systems. Berlin: Springer-Verlag, 2005.

[7] YAP W, HENG S, GOI B. An efficient certificateless signature scheme[C]//Emerging Directions in Embedded and Ubiquitous Computing, EUC Workshops 2006. Berlin: Springer-Verlag, 2006.

[8] ZHANG Zhen-feng, FENG Deng-guo. Key replacement attack on a certificateless signature scheme[EB/OL]. http:// eprint.iacr.org/2006/453.

[9] ZHANG Z, XU J, FENG D. Certificateless public-key signature: Security model and efficient construction[C]// Advances in ACNS 2006. Berlin: Springer-Verlag, 2006.

[10] HE D, CHEN J, ZHANG R. An efficient and provably-secure certificateless signature scheme without bilinear pairings[J]. International Journal of Communication Systems, 2012, 25(11): 1432-1442.

[11] HE De-biao, CHEN Yi-tao, CHEN Jian-hua. An efficient certificateless proxy signature scheme without pairing[J]. Mathematical and Computer Modelling, 2013(57): 2510-2518.

編 輯 葉 芳

Efficient and Provably Secure Certificateless Signature from Bilinear Pairings

HE Ming-xing, LI Peng-cheng, and LI Xiao

(School of Computer and Software Engineering, Xihua University Chengdu 610039)

Certificateless cryptography aims at combining the advantages of identity based and traditional certificate-based public key cryptography, so as to avoid the key escrow problem inherent in the identity based system and certificate management in public key infrastructure. In this paper, we propose a new efficient certificateless signature scheme and prove its security in the random oracle model. Furthermore, via pre-computing a bilinear pairing in the setup phase, our scheme only needs to compute one pairing in the verify stage. It is more efficient in computation complexity and communication complexity than that of many previous schemes.

bilinear pairing; certificateless signature; provable security; signature

TP309

A

10.3969/j.issn.1001-0548.2015.05.016

2013 ? 07 ? 21；

2014 ? 03 ?01

科技部支撐計劃(2011BAH26B00)；四川省國際合作項目(2009HH0009)；四川省高校創(chuàng)新團(tuán)隊項目(13TD0005)作者簡介：何明星(1964 ? )，男，博士，教授，主要從事密碼學(xué)與信息安全方面的研究.