分層的基于身份簽名的研究綜述
2008-12-31 00:00:00李明祥鄭雪峰閆鵬
計算機應用研究 2008年11期
(北京科技大學 信息工程學院， 北京 100083)
摘要：為了提高基于身份的密碼系統的效率，提出了分層的基于身份的密碼系統。分層的基于身份的簽名是其重要組成部分。首先敘述了分層的基于身份的簽名的定義和安全模型；然后分析了幾個分層的基于身份的簽名方案的構造方法、安全性和執行效率；最后指出了其下一步的研究方向。
關鍵詞：分層的基于身份的簽名； 雙線性映射； 安全模型
中圖分類號：TP309文獻標志碼：A
文章編號：1001-3695(2008)11-3201-03
Survey of hierarchical identity-based signature
LI Ming-xiang， ZHENG Xue-feng， YAN Peng
(School of Information Engineering， University of Science Technology Beijing， Beijing 100083， China)
Abstract:This paper proposed the hierarchical identity-based cryptosystem in order to improve the efficiency of the identity-based cryptosystem. Additionally， the hierarchical identity-based signature is an important part of the hierarchical identity-based cryptosystem. At first， described the definition and the security model of a hierarchical identity-based signature scheme. Secondly， introduced several hierarchical identity-based signature schemes. And analyzed the construction， security and efficiency of the schemes. Finally， pointed out the development trend and study direction of hierarchical identity-based signature schemes.
Key words：hierarchical identity-based signature(HIBS); bilinear map; security model
1984年Shamir[1]提出了基于身份的密碼系統的思想。在基于身份的系統中，用戶的公鑰是用戶身份信息，用戶的私鑰由私鑰生成中心(private key generators， PKG)產生。2001年Boneh等人[2]利用橢圓曲線上的雙線性映射設計了第一個實用的基于身份的加密方案。此后基于身份的密碼系統的研究迅速活躍起來。在基于身份的密碼系統中，PKG不但要生成用戶的私鑰，而且還要驗證用戶身份，以及建立傳輸用戶私鑰的安全通道。雖然一個PKG可以完成這些任務，但是這樣PKG的工作負擔是比較重的。特別在用戶的數量比較多時更是如此。
2002年Horwitz等人[3]提出了分層的基于身份的密碼系統的思想，Gentry等人[4]設計了第一個分層的基于身份的加密(hierarchical identity-based encryption， HIBE)方案。在分層的系統中，PKG以樹狀結構分布，根PKG只為其下一層的PKG或用戶產生私鑰，下層的PKG又為它下一層的PKG或用戶產生私鑰，并且身份的驗證和私鑰的傳輸也可以在局部完成。這樣分層的系統就解決了一個PKG工作負擔過重的問題。
2003年Canetti等人[5]定義了一個弱安全模型，即Selective-ID模型。2004年Canetti等人[6]又提出了一種構造CCA2安全的分層的基于身份的加密方案的方法。根據這些結果人們提出了幾個分層的基于身份的加密方案[7，8]，并在標準模型下證明了方案的安全性。此外，還提出了幾個分層的基于身份的簽名（HIBS)方案[4，9~12]。在文獻[4]中，Gentry和Silverberg提出了第一個HIBS方案，但是沒有給出該方案的安全性證明。文獻[9]是第一個可證安全的HIBS方案。文獻[10]是第一個在標準模型下可證安全的HIBS方案。文獻[11]也是一個在標準模型下可證安全的HIBS方案，并且方案的性能是比較優越的。文獻[12]是我國學者李進等人提出的HIBS方案。
1雙線性映射
設G和G1是兩個階為素數p的循環乘法群，g是G的生成元。并假設G和G1的離散對數問題是困難的。如果映射e:G×G→G1具有如下性質，則該映射是雙線性映射：
q-SDH問題。G的q-SDH問題是難解的，該假設就是q-SDH假設。
2HIBS的定義
在分層的基于身份的簽名方案中，用戶和PKG的身份以向量形式表示，如深度為j的身份可以表示為ID｜j=(I1，I2，…，Ij)。一個分層的基于身份的簽名方案由四個算法組成：
a)系統初始化算法Setup。該算法根據輸入的安全參數k輸出系統參數params和主密鑰msk。
b)私鑰生成算法KeyGen。該算法的輸入是系統參數params、身份ID｜j和上一層PKG的密鑰dID｜j-1；輸出是ID｜j的密鑰dID｜j。
c)簽名算法Sign。該算法的輸入為系統參數params、信息m和身份ID的密鑰dID；輸出為ID在m上的簽名σ。
d)驗證算法Verify。該算法的輸入是系統參數params、簽名σ、信息m和身份ID。如果σ是ID在m上的簽名，則輸出accept；否則輸出reject。
這些算法必須滿足基于身份的簽名方案的一致性要求，即如果σ=Sign(params，m，dID)，則Verify(params，σ，m，ID)=accept。
3HIBS的安全模型
在適應性選擇消息和身份的攻擊下抵抗存在性偽造的安全模型(EU-ID-CMIA)是基于身份的簽名的標準安全模型。根據這個安全模型可以定義分層的基于身份的簽名的安全模型。設C為挑戰者，A為敵手， 則定義HIBS安全模型的游戲可敘述如下：
a)建立。挑戰者運行簽名方案的Setup算法得到系統參數params和主密鑰msk，并將params發送給敵手，秘密保存msk。
b)詢問。敵手A適應性地向挑戰者提出一定數量的詢問，并且每次詢問都是下面兩種情形的一種：
（a）私鑰詢問。敵手可以詢問任何身份ID的密鑰dID。挑戰者運行KeyGen（b）簽名詢問。敵手可詢問任何身份ID在任何消息m上的簽名σ。挑戰者首先運行
根據Canetti等人定義的Selective-ID模型，可以定義HIBS方案的Selective-ID模型。該模型的游戲與上面的游戲基本上一樣，只是敵手A在建立階段開始前就將目標身份ID*透露給挑戰者C。顯然，這是一個比較弱的安全模型。Yuen等人[10]定義了HIBS方案的Gauntlet-ID模型。該模型的游戲與上面的游戲類似，只是在偽造階段要求ID*和它的前綴不能作為簽名詢問的輸入。可以看出，這也是一個比較弱的安全模型。
4幾種HIBS方案
41Gentry-Silverberg HIBS方案[4]
Gentry和Silverberg提出了一個從HIBE方案構造HIBS方案的方法。該方法簡單敘述如下：設簽名人的身份為ID=(I1，I2，…，Ik)， 消息為m，則簽名人ID以HIBE方案的主密鑰msk為私鑰生成身份ID~=(I1，I2，…，Ik，m)的私鑰dID~，即簽名人ID對消息m的簽名。驗證人任意選擇消息m′，并以身份ID~加密m′，然后以dID~解密得到密文。如果密文能正確解密，則簽名是有效的。根據這個方法，Gentry和Silverberg構造了一個HIBS方案，但是沒有給出該方案的安全性證明，并且Gentry-Silverberg方案的效率比較低。
42Chow-Hui HIBS方案[9]
根據Boneh和Boyen[7]提出的HIBE方案，Chow等人[9]設計了一個HIBS方案，并且該方案的系統參數params和私鑰生成算法KeyGen與Boneh-Boyen HIBE方案是一樣的。這樣Boneh-Boyen HIBE方案與Chow-Hui HIBS方案就組成了一個完整的分層的基于身份的密碼系統。
1)方案描述
在驗證階段，驗證人根據Boneh-Boyen HIBE方案以ID｜j加密任意消息，再以σ解密得到密文。因此，本方案雖然不是直接根據文獻[4]的方法構造的，但是它也借鑒了這一方法。
3)安全性Chow和Hui在隨機預言模型下基于CDH假設證明了本方案是Selective-ID安全的。
4)效率本方案在驗證階段雙線性映射運算的次數與分層深度成正比，因此其效率比較低。
43Yuen-Wei HIBS方案[10]
根據Boneh等人[8]提出的密文長度恒定的HIBE方案，Yuen和Wei[10]設計了一個簽名長度恒定的HIBS方案。
1)方案描述
Setup:設HIBS方案的最大深度為l，根PKG隨機選擇G的生成元g，g2，g
2)構造方法本方案是直接構造的。
3)安全性為了證明這個方案的安全性，Yuen和Wei設計了一個強假設，即OrcYW假設；定義了一個弱安全模型，即Gauntlet-ID模型。Yuen和Wei在標準模型下基于OrcYW假設證明了本方案是安全的；在Gauntlet-ID模型下基于l-DHI*假設也證明了本方案是安全的。雖然Yuen-Wei HIBS方案在標準模型下是可證安全的，但是其安全性證明是基于強假設或在弱安全模型下得到的，因此安全性不高。
4)效率本方案在簽名階段無須雙線性映射運算，在驗證階段只需七次雙線性映射運算，因此其效率比較高。
44Au-Liu HIBS方案[11]
2006年Gentry[13]提出了一個性能優越的基于身份的加密方案，根據這個方案的分層的擴展形式，Au和Liu設計了一個性能優越的HIBS方案。
1)方案描述
2)構造方法本方案是按照文獻[4]提出的方法構造的。
3)安全性Au和Liu在標準的安全模型下沒有使用隨機預言證明了本方案是安全的，并且困難假設是比較標準的q-SDH假設，因此本方案的安全性比較高。
4)效率可以看出，本方案在簽名階段無須雙線性映射運算，在驗證階段只需四次雙線性映射運算，因此其效率高。另外，Au-Liu HIBS方案的簽名長度也是恒定的。
45李進等人的HIBS方案[12]
李進等人提出了兩個分層的基于身份的簽名方案，這兩個方案基本上是按照文獻[4]提出的方法構造的。李進等人在隨機預言模型下證明了它們是Selective-ID安全的。另外這兩個方案的效率也是比較高的。
5結束語
在過去的幾年里，國內外學者對分層的基于身份的簽名進行了比較深入的探討，并取得了一些研究成果。目前，分層的基于身份的簽名（HIBS）方案依然存在一些需要解決的問題：a)安全性不強；b)效率不高；c)安全歸約不是緊的。因此，設計安全性強、效率高和安全歸約緊的HIBS方案是下一步研究的方向。另外，HIBS同樣具有基于身份的密碼系統固有的一些問題，如密鑰托管、公鑰撤銷等。怎樣解決這些問題也是HIBS下一步需要研究的內容。
參考文獻：
[1]SHAMIR A. Identity-based cryptosystems and signature schemes[C]//Proc of CRYPTO 1984， LNCS 196. Berlin: Springer-Verlag， 1984:47-53.
[2] BONEH D， FRANKLIN M. Identity-based encryption from the Weil pairing[C]//Proc of CRYPTO 2001， LNCS 2139. Berlin: Springer-Verlag， 2001:213-229.
[3]HORWITZ J， LYNN B. Towards hierarchical identity-based encryption[C]//Proc of EUROCRYPT 2002， LNCS 2332. Berlin: Sprin-ger-Verlag， 2002:466-481.
[4]GENTRY C， SILVERBERG A. Hierarchical ID-based cryptography[C]//Proc of ASIACRYPT 2002， LNCS 2501. Berlin: Springer-Verlag， 2002:548-566.
[5]CANETTI R， HALEVI S， KATZ J. A forward-secure public-key encryption scheme[C]//Proc of EUROCRYPT 2003， LNCS 2656. Berlin: Springer-Verlag， 2003:255-271.
[6]CANETTI R， HALEVI S， KATZ J. Chosen-ciphertext security from identity-based encryption[C]//Proc of EUROCRYPT 2004， LNCS 3027. Berlin: Springer-Verlag， 2004:207-222.
[7]BONEH D， BOYEN X. Efficient Selective-ID secure identity-based encryption without random oracles[C]//Proc of EUROCRYPT 2004， LNCS 3027. Berlin:Springer-Verlag， 2004:223-238.
[8]BONEH D， BOYEN X， GOH E J. Hierarchical identity-based encryption with constant size ciphertext[C]//Proc of EUROCRYPT 2005， LNCS 3494. Berlin: Springer-Verlag， 2005:440-456.
[9]CHOW S S M， HUI L C K， YIU S M， et al. Secure hierarchical identity-based signature and its application[C]//Proc ofICICS 2004， LNCS 3269. Berlin: Springer-Verlag， 2004:480-494.
[10]YUEN T H， WEI V K. Constant-size hierarchical identity-based signature/signcryption without random oracles[EB/OL]. (2005-11-17) [2008-03-03]. http://eprint.iacr.org/2005/412.
[11]AU M H， LIU J K， YUEN T H， et al. Efficient hierarchical identity-based signature in the standard model[EB/OL]. (2007-02-21)[2008-03-03]. http://eprint.iacr.org/2007/068.
[12]李進，張方國，王燕鳴. 兩個高效的基于分級身份的簽名方案[J]. 電子學報，2007，35(1):150-152.
[13]GENTRY C. Practical identity-based encryption without random oracles[C]//Proc of EUROCRYPT 2006， LNCS 4404. Berlin: Sprin-ger-Verlag， 2006:445-464.
