高效可證安全的基于證書數字簽名方案

黃茹芬，農強，黃振杰

閩南師范大學計算機科學與工程系，福建漳州 363000

高效可證安全的基于證書數字簽名方案

黃茹芬，農強，黃振杰

閩南師范大學計算機科學與工程系，福建漳州 363000

1 引言

為了簡化傳統公鑰密碼系統的證書管理過程，解決基于身份公鑰密碼系統[1]固有的密鑰托管問題，Gentry[2]在2003年的歐密會上首次提出了基于證書公鑰密碼系統的概念。隨后的2004年，Kang等人[3]將基于證書公鑰密碼系統擴展到基于證書的數字簽名，提出了基于證書數字簽名（CBS）的概念及其安全性定義，并構造了兩個基于證書的數字簽名方案。2007年，Li等[4]給出了基于證書公鑰密碼系統中攻擊敵手的形式化定義，并使用聚合簽名的思想提出了效率更高的CBS方案。2008年，Liu等[5]進一步構造了在標準模型下可證明安全的CBS方案。2009年，Wu等在

文獻[6]中進一步完善了基于證書數字簽名的安全定義。近年來，相繼有研究者們提出了一些基于證書的簽名方案，包括利用雙線性對構造的簽名[7-10]、盲簽名[11]、短簽名[12-13]、指定驗證者簽名[14-15]，以及不含雙線性對的簽名[16-17]等方案。基于證書的數字簽名結合了傳統公鑰數字簽名和基于身份數字簽名的優點，克服了這兩類簽名系統所存在的問題。在一個CBS中，簽名者首先根據自己選定的私鑰來生產公鑰，隨后證書授權中心（Certificate Authority，CA）在證書生成過程中綁定了簽名者公鑰，CA的證書在簽名階段作為簽名私鑰的一部分，從而實現了對簽名者公鑰的隱含驗證。因此，CBS系統既簡化了傳統公鑰數字簽名系統中證書的管理、存儲和發布，解決了基于身份公鑰簽名系統中的密鑰托管問題，還克服了無證書公鑰密碼系統中存在的信任級別只能達到2級[18]，不能達到Girault 3級和存在拒絕解密（Denial of Decryption，DoD）攻擊[19]等缺點。目前，對基于證書加密和簽名的研究雖然已取得了一些成果，但為數還相對較少。

本文構造了一個有效的基于證書數字簽名方案，并在隨機預言機模型下，基于q強Diffie-Hellman問題和擴展的逆計算Diffie-Hellman問題的困難性，證明了所構造簽名方案的安全性。新方案的簽名算法簡單、不需要任何雙線性對運算，驗證算法也僅僅需要一個雙線性對運算，因此，所提方案在計算代價上相當有效。

2 預備知識

2.1 雙線性映射

設G1是一個加法群，其階為素數p，P是G1的任意一個生成元，G2是一個乘法群，其階數與G1相同。一個雙線性對是一個映射e:G1×G1→G2，滿足雙線性性、非退化性和可計算性。

（1）雙線性：對于任意的a,b∈，下列等式成立：e(aP,bQ)=e(P,Q)ab。

（2）非退化性：存在P,Q∈G1，滿足e(P,Q)≠1。

（3）可計算性：對于任意的P,Q∈G1，存在有效的多項式時間算法，可以計算出e(P,Q)。

2.2 困難假設

假設1q-SDHA（q-強Diffie-Hellman困難假設）：如果不存在一個概率多項式算法，可以在時間t內，以至少ε的概率解群G上的q-SDHP，則稱(t,ε)-q-SDHP困難假設在該群G上成立。

假設2 E-inv-CDHA（擴展的逆計算Diffie-Hellman困難假設）：如果不存在一個概率多項式的算法，可以在時間t內，以至少ε的概率解群G上的E-inv-CDHP，則稱(t,ε) E-inv-CDHP困難假設在該群G上成立。

3 基于證書簽名的相關定義

3.1 形式化定義

定義3（基于證書的數字簽名CBS）一個基于證書的數字簽名方案一般由以下五個算法組成。

（1）系統初始化：輸入安全參數，輸出系統公開參數和系統主私鑰。

（2）密鑰生成：輸入系統公開參數和用戶身份，輸出用戶的私鑰和公鑰。

（3）證書生成：輸入系統公開參數、系統主私鑰、用戶身份及其公鑰，CA輸出用戶的公鑰證書。

（4）簽名生成：輸入待簽消息m、系統公開參數、用戶身份、用戶私鑰及其公鑰證書，輸出對應于消息m的簽名σ。

（5）簽名驗證：輸入消息/簽名對(m,σ)、系統公開參數、用戶身份及其公鑰，輸出接受或拒絕簽名。

3.2 安全性定義

基于證書的數字簽名方案必須滿足正確性和存在不可偽造性。正確性是指由簽名算法所產生的簽名必須能夠通過簽名驗證算法。存在不可偽造性是指所產生的簽名在適應性選擇消息、選擇身份以及替換公鑰攻擊下是不可偽造的。在基于證書的數字簽名中，需要考慮兩種類型敵手的攻擊：類型I敵手AI和類型II敵手AII。

類型I敵手AI：AI模擬用戶攻擊，即敵手試圖以用戶身份偽造合法用戶的簽名。因此，敵手AI知道用戶的私鑰，但不知道對應公鑰的證書，可以任意替換用戶的公鑰。

類型II敵手AII：AII模擬CA攻擊，即不誠實的證書授權中心試圖偽造用戶產生簽名。因此，敵手AII知道系統主私鑰，可以產生用戶的公鑰證書，但不知道用戶的私鑰，也不能替換目標用戶的公鑰。

基于證書簽名方案的存在不可偽造性是通過敵手A∈{AI,AII}和挑戰者C之間的游戲來定義的。

（1）游戲Game1：類型I敵手AI和挑戰者C之間進行的游戲。

系統建立：輸入系統安全參數，C執行系統初始化算法，獲得系統公開參數和主私鑰，并發送系統公開參數給敵手AI。

預言機服務：敵手AI可以在多項式時間內向C發布密鑰詢問、Hash函數詢問、證書詢問、私鑰詢問、替換公鑰詢問和簽名詢問。

偽造輸出：如果敵手AI在上述游戲Game1中輸出的對應于身份ID*和公鑰P，在消息m*上的偽造簽名σ*能夠通過簽名驗證算法，則敵手AI贏得上述游戲Game1。

注意，在上述Game1中，不能發布對(ID*,P)的證書詢問；也不能發布對(ID*,P,m*)的簽名詢問。

（2）游戲Game2：類型II敵手AII和挑戰者C之間進行的游戲。

系統建立：輸入系統安全參數，C執行系統初始化算法，獲得系統公開參數和主私鑰，發送給敵手AII。

預言機服務：敵手AII可以在多項式時間內向C發布密鑰詢問、Hash函數詢問和簽名詢問。

偽造輸出：如果敵手AII在上述游戲Game2中輸出的對應于身份ID*和公鑰P，在消息m*上的偽造簽名σ*能夠通過驗證算法，則敵手AII贏得上述游戲Game2。

注意，在上述Game2中，不能發布對(ID*,P,m*)的簽名詢問，其中，PKID*是對應于ID*的密鑰詢問的輸出，而且PKID*所對應的私鑰沒有被詢問過。

最后，如果不存在多項式時間算法C，借助于敵手AI和AII，能夠以一個不可忽略的優勢贏得敵手A∈{AI,AII}和挑戰者C之間的游戲Game∈{Game1,Game2}，則稱一個基于證書的簽名方案滿足存在不可偽造性。

定義4（不可偽造性）一個基于證書簽名方案是存在不可偽造的，如果不存在多項式時間算法C，借助于敵手AI和AII，能夠以一個不可忽略的優勢贏得敵手A∈{AI,AII}和挑戰者C之間的游戲Game∈{Game1,Game2}。

定義5（安全性）一個基于證書簽名方案是安全的，如果它是正確的并且在適應性選擇消息、選擇身份以及替換公鑰攻擊下具有存在不可偽造性。

4 提出的方案

基于雙線性對，參照文獻[20-21]，本文構造了一個有效的基于證書的數字簽名方案，該方案包括系統初始化、密鑰提取、證書生成、簽名生成和簽名驗證五個算法。算法具體描述如下：

（1）系統初始化：給定系統安全參數k，CA建立系統參數如下：

（4）簽名生成：設待簽消息為m，則用戶執行如下：

5 安全性與性能分析

5.1 安全性分析

本文的方案在構造時參照了文獻[20]的方案，主要的區別在于所構造的方案使用的是雙公鑰PKA=(XA,YA)，因此，在簽名驗證時首先必須驗證公鑰PKA的合法性，一旦公鑰驗證等式不成立，則直接終止協議，因而可以更好地保障方案的安全性。其次，在生成證書之前，首先生成簽名者的私鑰SKA及公鑰PKA，然后將公鑰PKA綁定到證書CertA和簽名σ中。這樣一來，攻擊者在選擇好Hash函數H1后，就不能再計算公鑰PKA，也無法完成替換公鑰，克服了替換公鑰的攻擊。而且，由于CA將公鑰PKA和簽名者身份信息IDA一起Hash運算后產生證書CertA，這就使得CA無法針對特定用戶生成特定的系統參數，可以有效克服惡意CA的攻擊。

（1）正確性

定理1本文定義的基于證書的數字簽名方案是正確的。

證明設σ是由簽名算法所產生的對應于消息m、身份IDA和公鑰PKIDA的簽名，則方案的正確性可以容易地驗證如下：

首先，通過以下等式驗證公鑰的合法性：

其次，驗證所產生的簽名σ=(U,V)滿足簽名驗證等式，具體驗證如下：

（2）不可偽造性：正如3.2節所述，基于證書簽名方案的不可偽造性是通過敵手A∈{AI,AII}和挑戰者C之間的游戲Game∈{Game1,Game2}來定義的。本方案的不可偽造性是在隨機預言機模型下證明的，在證明過程中，參考了文獻[23-24]的證明技巧。具體證明過程如下。

引理1在隨機預言機模型和q-強SDH困難假設下，本文定義的基于證書的數字簽名方案具有抵抗類型I敵手AI的存在不可偽造性。

證明假設AI能夠以一定的優勢攻破本文的方案，則可以構造一個算法C，利用AI解決q-強SDHP。設AI是一個類型I敵手，算法C的目標是對于消息m*和身份ID*，能夠偽造有效的簽名，解決q-強SDHP。

因此，如果AI能夠攻破本文的簽名方案，則算法C就可以利用AI獲得q-強SDHP的一個解，從而出現矛盾。

引理2在隨機預言機模型和E-inv-CDH困難問題假設下，本文定義的基于證書的數字簽名方案具有抵抗敵手AII的存在不可偽造性。

證明假設AII能夠以一定的優勢攻破本文的方案，則可以構造一個算法C，利用AII解決E-inv-CDHP。設AII是一個類型II敵手，算法C的目標是對于消息m*和身份ID*，能夠偽造有效的簽名，解決E-inv-CDHP。

③H2詢問：H2詢問與引理1相同。

這樣，算法C已成功輸出一個E-inv-CDHP的解。

因此，如果AII能夠攻破本文的簽名方案，則算法C就可以利用AII獲得E-inv-CDHP的一個解，從而出現矛盾。

定理2在隨機預言機模型，以及q-強SDHP和E-inv-CDHP困難問題假設下，本文定義的基于證書簽名方案在適應性選擇消息、選擇身份攻擊下是存在不可偽造的。

證明由引理1和引理2，該定理可證。

結論1本文定義的基于證書的簽名方案是安全的。

證明根據3.2節的定義5，顯然，從上述定理1和定理2可證。

5.2 性能分析

考慮到對運算在計算時間上是相對比較耗費時間的一種運算，本文構造的方案通過預先計算g=e(P,P)，并將其并入系統參數中一起公開發布，提高了方案的效率，而且方案在簽名產生階段不需要任何對運算，簽名驗證階段也僅僅需要一個對運算。下面，將把本文定義的新方案與現有的使用雙線性對運算、基于證書數字簽名方案進行一個分析比較，比較結果列于表1。其中，M表示標量乘；SM表示形如aP+bQ的同步標量乘；E表示指數運算；P表示雙線性對運算。

表1 效率比較

從表1可見，本文定義的基于證書的數字簽名方案在整體效率上是比較高的。

6 結束語

本文構造了一個高效的基于證書的數字簽名方案，并在隨機預言機模型下，以及q-強SDHP和E-inv-CDHP困難假設下，證明了所定義方案的安全性，同時簡要分析了方案的性能，并進行了效率比較。由于在基于證書的數字簽名系統中，證書管理簡單，又不存在密鑰的托管問題，因此，如何設計更多可證安全、有效的基于證書的簽名方案是一項很有意義的工作，值得進一步的研究和探索。

[1]Shamir A.Identity-based cryptosystems and signature schemes[C]// LNCS 196：CRYPTO 1984.Berlin：Springer-Verlag，1985：47-53.

[2]Gentry C.Certificate-based encryption and the certificate revocation problem[C]//LNCS 2656：EUROCRPYT 2003.Berlin：Springer-Verlag，2003：272-293.

[3]Kang B G，Park J H，Hahn S G.A certificate-based signature scheme[C]//LNCS 2964：CT-RSA 2004.Berlin：Springer-Verlag，2004：99-111.

[4]Li J，Huang X，Mu Y，et al.Certificate-based signature：security model and efficient construction[C]//LNCS 4582：EuroPKI’07. Berlin：Springer，2007：110-125.

[5]Liu K，Baek J，Susilo W，et al.Certificate-based signature schemes without pairings or random oracles[EB/OL].[2013-03-10]. http：//eprint.iacr.org/.

[6]Wu Wei，Mu Yi，Susilo W，et al.Certificate-based signatures revisited[J].Journal of Universal Computer Science，2009，15（8）：1659-1684．

[7]王雯娟，黃振杰，郝艷華.一個高效的基于證書數字簽名方案[J].計算機工程與應用，2011，47（6）：89-92.

[8]李志敏，徐馨，李存華.高效的基于證書數字簽名設計方案[J].計算機應用研究，2012，19（4）：1430-1433.

[9]楊波，肖自碧.基于證書的簽名方案[J].北京郵電大學學報，2012，35（5）：73-76.

[10]陳江山，黃振杰.一個高效的基于證書簽名方案[J].計算機工程與應用，2012，48（30）：98-102.

[11]黃茹芬，農強，黃振杰.一類可證安全的基于證書盲簽名[J].計算機應用研究，2012，29（12）：4622-4625.

[12]Li J G，Huang X Y，Zhang Y C.An efficient short certificate-based signature scheme[J].Journal of Systems and Software，2012，85（2）：314-322.

[13]吳晨煌，郭瑞景，陳智雄.高效的基于證書短簽名方案[J].計算機系統應用，2013，22（2）：129-132.

[14]李繼國，錢娜，黃欣沂，等.基于證書強指定驗證者簽名方案[J].計算機學報，2012，35（8）：1579-1587.

[15]黃茹芬，農強.基于證書的任意指定驗證人簽名方案[J].太原師范學院學報：自然科學版，2012，11（3）：70-73.

[16]周萍，何大可.高效不含雙線性對的基于證書簽名方案[J].計算機應用研究，2013，30（5）：1504-1507.

[17]Huang Rufen，Nong Qiang.A new efficient certificate-based signature scheme without bilinear pairings[C]//LNIT 31，2012：101-108.

[18]Girault M.Self-certified public keys[C]//LNCS 547：Eurocrypt 1991.Berlin：Springer-Verlag，1991：490-497.

[19]Liu J，Au M，Susilo W.Self-generated-certificate public key cryptography and certificateless signature/encryption scheme in the standard model[C]//ACM ASIACCS’07.New York：ACM Press，2007：273-283.

[20]張玉磊，王彩芬，張永潔，等.基于雙線性對的高效無證書簽名方案[J].計算機應用，2009，29（5）：1330-1333.

[21]明洋，王育民.有效的無證書簽名方案[J].電子科技大學學報，2008，37（2）：175-177.

[22]Boneh D，Lynn B，Shacham H.Short signatures from the weil pairing[C]//LNCS 2248：Asiacrypt 2001.Berlin：Springer-Verlag，200l：514-532.

[23]Boneh D，Boyen X.Short signatures without random oracles[C]// LNCS 3027：EUROCRYPT 2004.Berlin：Springer-Verlag，2004：56-73.

[24]Choi K Y，Park J H，Hwang J Y，et al.Efficient certificateless signature schemes[C]//LNCS 4521：ACNS 2007.Berlin：Springer-Verlag，2007：443-458.

HUANG Rufen,NONG Qiang,HUANG Zhenjie

Department of Computer Science＆Engineering,Minnan Normal University,Zhangzhou,Fujian 363000,China

The certificate-based encryption is a new public key encryption paradigm which combines public key encryption and identity-based encryption while it preserves their features.This paper proposes an efficient construction of certificate-based signature scheme using bilinear maps,with rigorous security proofs under the random oracle model.The security of the scheme is based on the infeasibility of theq-strong Diffie-Hellman problem and the expand inversed computational Diffie-Hellman problem.The analysis shows that this new scheme satisfies the security requirements such as correctness and unforgeability,and has high security.It not only simplifies the certificate management process,but also overcomes the private key escrow problem.Furthermore,its overall performance is relatively high.

digital signature;certificate-based;random oracle model;provably secure;bilinear pairings

基于證書公鑰密碼系統是近年來提出的一種新型公鑰密碼體制，它結合了傳統公鑰密碼體制和基于身份密碼體制的優點，克服了其存在的問題。利用雙線性映射，提出了一個基于證書的數字簽名方案，在隨機預言機模型下給出了嚴格的安全證明。方案的安全性基于q強Diffie-Hellman問題和擴展的逆計算Diffie-Hellman問題的困難性。分析表明，所構造的新方案滿足正確性和存在不可偽造性，具有較高的安全性，不僅簡化了證書管理過程，克服了密鑰托管問題，而且方案的整體性能比較高。

數字簽名；基于證書；隨機預言模型；可證明安全；雙線性對

A

TP309

10.3778/j.issn.1002-8331.1305-0222

HUANG Rufen,NONG Qiang,HUANG Zhenjie.Efficient provably secure certificate-based signature scheme.Computer Engineering and Applications,2013,49（24）：55-60.

國家自然科學基金（No.61170246）；福建省自然科學基金（No.2012J01295）。

黃茹芬（1963—），女，副教授，研究領域為密碼學與網絡安全；農強（1978—），男，講師，研究領域為密碼學與網絡安全；黃振杰（1964—），男，博士后，教授，研究領域為密碼學與信息安全。E-mail：zzhrf@126.com

2013-05-17

2013-08-22

1002-8331（2013）24-0055-06

CNKI出版日期：2013-10-11http://www.cnki.net/kcms/detail/11.2127.TP.20131011.1653.010.html