多密鑰中心的基于分級(jí)身份的簽名方案

摘 要：提出一個(gè)多密鑰授權(quán)中心的基于分級(jí)身份的簽名方案。 首先， 方案具有多個(gè)密鑰中心，降低對(duì)密鑰中心的信任假設(shè)、提高方案的健壯性； 其次，這個(gè)方案是可證明安全的，即在隨機(jī)應(yīng)答模型下，方案在給定身份和選擇明文攻擊下是不可偽造的；此外，新的基于分級(jí)身份簽名方案是安全歸約緊致的方案。

關(guān)鍵詞：簽名;基于身份;分級(jí); 多密鑰中心

中圖分類號(hào)：TP309 文獻(xiàn)標(biāo)識(shí)碼：A

An Efficient Hierarchical Identity Based Signature Scheme with Multiple Private Key Generators

ZHAI Hongyan， ZENG Jixia

(Guangzhou City Polytechnic，Guangzhou 510405，China)

Abstract:A new hierarchical identitybased signature (HIBS) schemes is proposed. Contributions are many folds: First， there are multiple private key generators in the new scheme; Second， it is provably secure and has very good exact security against existential forgery for selective-ID attack in the standard model; Finally， security reduction of the scheme is very tight.

Key words:signature;identity based; hierarchical;multiPKG

1 引 言

Shamir于1984年首次提出基于身份的密碼體制^［1］ ， 用以簡(jiǎn)化基于證書的公鑰密碼體制中的密鑰管理以及公鑰證書撤消。在這個(gè)系統(tǒng)中，只有密鑰產(chǎn)生中心（PKG）能夠計(jì)算出每個(gè)人的私鑰。最近，一個(gè)比較高效的基于身份的加密方案^［2］被提出，Boneh等人提出了在標(biāo)準(zhǔn)模型下的基于身份的加密方案^［3，4］。 給定身份攻擊下安全的基于身份的加密方案有一個(gè)很重要的應(yīng)用是在文獻(xiàn)［5］中提出。 然而， 在基于身份的密碼系統(tǒng)中，只有一個(gè)PKG會(huì)影響到系統(tǒng)的效率， 這點(diǎn)和基于證書的密碼系統(tǒng)十分類似， 因此需要一種分級(jí)的基于身份的密碼系統(tǒng)， 在這種系統(tǒng)中， 多個(gè)PKG按照樹狀結(jié)構(gòu)分布。然而，現(xiàn)有的基于分級(jí)身份的簽名方案存在一個(gè)問題是，第一層的PKG在計(jì)算用戶私鑰時(shí)，由于只有一個(gè)PKG，從而可以計(jì)算出所有其它用戶的私鑰，導(dǎo)致系統(tǒng)的健壯性不夠。為了提高系統(tǒng)的健壯性，我們提出了多個(gè)密鑰中心的基于分級(jí)身份的簽名方案。本文的貢獻(xiàn)有如下幾個(gè)方面： 首先，提出一個(gè)新的基于分級(jí)身份的簽名方案，方案效率非常高。 同時(shí)，第一層的密鑰是由多個(gè)密鑰中心發(fā)放的，從而提高系統(tǒng)安全性。

2 多密鑰中心的基于身份加密的定義

一個(gè)基于分級(jí)身份的簽名方案由四個(gè)算法組成， 即系統(tǒng)初始化， 密鑰產(chǎn)生， 簽名和驗(yàn)證算法。系統(tǒng)初始化算法通過輸入安全參數(shù)k和系統(tǒng)分級(jí)層數(shù)（深度）l， 輸出整個(gè)系統(tǒng)的公開參數(shù)以及系統(tǒng)主密鑰sk；在密鑰生成算法中： 給定第用戶身份ID=( ID1， …， IDj) 和用戶ID′的私鑰dID'， 輸出私鑰dID；在簽名算法中， 給定明文M和的接收者的身份信息ID以及私鑰dID， 產(chǎn)生相應(yīng)的簽名；通過驗(yàn)證算法，給定簽名和用戶身份， 輸出1， 如果它是一個(gè)有效簽名， 否則輸出0。

本文還需要利用雙線性對(duì)進(jìn)行方案的構(gòu)造，我們?cè)谙旅婧?jiǎn)單的介紹雙線性對(duì)的定義和具有的性質(zhì)。雙線性對(duì)的這些基礎(chǔ)知識(shí)如下：

設(shè)G1和G2是兩個(gè)階為q的循環(huán)群，q為大素?cái)?shù)。定義雙線性映射e:G1×G1→G2滿足以下性質(zhì)： e(ga，hb)=e(g，h)ab，對(duì)g(shù)，h∈G1，a，b∈Zq成立；以及g，h∈G1，使e(g，h)≠1；

3 基于分級(jí)身份的簽名方案

G1和G2是兩個(gè)階為q的循環(huán)群，e:G1×G1→G2為雙線性對(duì)，同時(shí)我們假設(shè)第j層用戶的I(xiàn)D為ID=（I1，…， Ij-1， Ij）∈Zjq，明文M∈G2

1）系統(tǒng)初始化： 假設(shè)系統(tǒng)中最多只有l(wèi)個(gè)分級(jí)。 在第一級(jí)中有N個(gè)PKG，此外，有一個(gè)中心PKG。中心PKG隨機(jī)選取α∈Z*q， 計(jì)算g1=gα，然后隨機(jī)選擇l+1個(gè)參數(shù)g2，h1，…，hl∈G1。中心PKG首先選擇N-1個(gè)隨機(jī)數(shù)α1，α2，…，αN－1∈Z*q，然后計(jì)算αN=α－(α1+α2+…+αN－1)∈Z*q并且將α1，α2，…，αN－1，αN分別發(fā)送給N個(gè)PKG。最后，整個(gè)系統(tǒng)的公開參數(shù)為G1，G2，e，q，g，g1，g2，h1，…，hl。

2）密鑰提取： 當(dāng)由PKG發(fā)放私鑰給第一層用戶時(shí)，需要N個(gè)PKG分別計(jì)算部分私鑰：其中第i個(gè)PKG計(jì)算如下，假設(shè)用戶身份為ID，計(jì)算(gαi2(gIDh1)ri，gri)，第一層用戶I(xiàn)D可計(jì)算出私鑰(gα2(gIDh1)r，gr)，計(jì)算方法即將來自N個(gè)PKG的私鑰進(jìn)行相乘。對(duì)于第j層用戶的身份為I(xiàn)D = （I1，…， Ij-1， Ij），我們定義l個(gè)函數(shù)Fj(x)=gx1hj， 其中2≤j≤l。同時(shí)第j－1層用戶I(xiàn)D′=（I1，…， Ij-1）私鑰為(gα2∏j－1k=1Fk(Ik)rk， gr1， …， grj－1)， 由第j－1層用戶I(xiàn)D′可以計(jì)算第j層用戶ID的私鑰：dID=(gα2∏jk=1Fk(Ik)rk， gr1， …， grj－1， )， 其中rj∈Z*q由用戶I(xiàn)D′選定。

3） 簽名： 用戶ID的私鑰為dID=(a0，a1，…，aj)， 用戶I(xiàn)D對(duì)文件M進(jìn)行簽名， 選擇一個(gè)隨機(jī)數(shù)t∈Z*q， 計(jì)算T=gt，A=a0#8226; ［H(M，gt)］t，則簽名為σ=（A， a1，…， aj， T）。

4） 簽名驗(yàn)證： 給定I(xiàn)D， M以及簽名σ=（A， a1，…， math display='block'

semantics

mrow

msub

mia/mi

mij/mi

/msub

/mrow

annotation encoding='MathType-MTEF'

/annotation

e(g，

/math

， T）， 驗(yàn)證如下等式： A)=e(g1，g2)#8226; e(H(M，T)， T) ∏ji=1e(Fi(Ii)， ai)。 若等式成立， 則此簽名有效； 否則簽名無效。

效率分析

對(duì)于任何級(jí)數(shù)j的用戶， 簽名階段只需要群G1中的兩次指數(shù)運(yùn)算和一次乘法運(yùn)算， 與級(jí)數(shù)j無關(guān)， 而文章［9］ 簽名產(chǎn)生卻需要j+2次指數(shù)運(yùn)算。 因此， 新方案的效率在簽名產(chǎn)生是很快的。另外，我們?cè)谟?jì)算第一層的用戶私鑰時(shí)，還可以利用門限(k，N)方法，從而實(shí)現(xiàn)讓k個(gè)PKG結(jié)合就可以產(chǎn)生第一層用戶的私鑰，實(shí)現(xiàn)更高的安全性。其它層次用戶私鑰的計(jì)算方法不變，因此效率還是和前一種方法相同。

安全分析

我們通過下面的安全游戲來說明這個(gè)這個(gè)方案的安全性：

攻擊者將攻擊的目標(biāo)身份I(xiàn)D*給挑戰(zhàn)者B， B然后輸出公開參數(shù)交給攻擊者， 自己保存相應(yīng)的私鑰；攻擊者進(jìn)行k次詢問q1， …， qk， 其中每次詢問都是私鑰詢問或簽名詢問； 最后我們定義攻擊者成功偽造簽名當(dāng)且僅當(dāng)攻擊者輸出（M#8226;， ID#8226;， σ）是一個(gè)有效簽名，同時(shí)ID#8226;沒有詢問過私鑰提取的應(yīng)答機(jī)以及（M#8226;， ID#8226;）沒有詢問過簽名應(yīng)答機(jī)。

定義1 計(jì)算離散對(duì)數(shù)（CDH）問題： 對(duì)x，y∈Z*q ，給定G1中元素g，gx，gy，計(jì)算gxy；

我們說(t，ε)-CDH假設(shè)在群G1中成立是指在多項(xiàng)式時(shí)間t內(nèi)沒有算法能以不可忽略的概率ε解決CDH問題

定理1 假設(shè)CDH假設(shè)在群G1成立， 那么這個(gè)基于分級(jí)身份的簽名是安全的。

證明： 假設(shè)一個(gè)攻擊者A能夠成功偽造簽名， 那么就可以構(gòu)造一個(gè)算法B解決CDH問題。 首先任意給定算法B三元組g，gx，gy，要求B計(jì)算gxy。

A在得到系統(tǒng)參數(shù)之前公布他將攻擊的目標(biāo)身份I(xiàn)D*=(I#8226;1， …， I#8226;k) ∈Zjq，B令g1=gx，g2=gy， hi=g-I#8226;i1gai ， 1≤i≤l， I*k+1 ，…， I*l是B隨機(jī)選擇的。

A 詢問qE次I(xiàn)D私鑰提取的詢問，限制是ID不等于ID*以及不是ID*的任何前綴。模擬和［3］完全相同， 在此省略。A接著qS次簽名的詢問： 當(dāng)A詢問消息M關(guān)于身份 ID=(I1， …， Ij)的簽名時(shí)，則B如上可計(jì)算出它的私鑰并進(jìn)行簽名。

如果A詢問結(jié)束并且偽造了目標(biāo)身份I(xiàn)D*=(I#8226;1， …， I#8226;k)的對(duì)文件M的簽名： σ*=(gxy∏ki=1Fi(I*i)r'i#8226;［H(M，gr')］r'， gr'，gr′1 …，gr′k)。B從已經(jīng)詢問的H列表中找是否存在（M，u'）， 若不存在， 則B宣布失敗； 否則存在（M，u'）滿足H(M，gr')=gu'，也就是說B解決了CDH問題。 從而如果CDH假設(shè)成立， 新的分級(jí)的基于身份的簽名方案是安全的。我們的定理中， 安全歸約是很緊的。 

4 總 結(jié)

本文提出一個(gè)高效率的具有多個(gè)PKG的基于分級(jí)身份的簽名方案。新的基于分級(jí)身份的簽名方案在隨機(jī)應(yīng)答模型下是給定身份攻擊下安全的，即使攻擊者選擇明文和身份進(jìn)行攻擊。 同時(shí)，它的安全性是基于計(jì)算DiffieHellman困難假設(shè)的。新方案通過提出多個(gè)密鑰中心來實(shí)現(xiàn)方案的健壯性，即使某一個(gè)PKG不誠(chéng)實(shí)，也無法產(chǎn)生出某個(gè)用戶的私鑰。新方案的安全性證明不依賴于分叉原理，從而安全歸約的效率很高。

參考文獻(xiàn)

［1］ SHAMIR A. Identitybased cryptosystems and signature schemes ［A］. BLAKLEY G R， CHAUM David.1984 Advances in CryptologyCRYPTO Proceedings ［C］. USA: Springer， 1984， LNCS 196: 47-53.

［2］ BONEH D，F(xiàn)RANKLIN M. IdentityBased Encryption from theWeil Pairing. KILIAN Joe. 2001 Advances in CryptologyCRYPTO Proceedings ［C］. USA: Springer， 2001， LNCS 2139: 213-229.

［3］ BONEH D， BOYEN X. Efficient SelectiveID Secure IdentityBased Encryption Without Random Oracles［A］. CACHIN Christian， CAMENISCH Jan. 2004 Advances in CryptologyEUROCRYPT Proceedings ［C］. Switzerland: Springer， 2004， LNCS 3027: 223-238.

［4］ BONEH D， BOYEN X. Secure Identity Based Encryption Without Random Oracles ［A］. FRANKLIN Matthew K. 2004 Advances in CryptologyCRYPTO Proceedings［C］.USA: Springer， 2004， LNCS 3152: 443-459.

［5］ BONEH D， KATZ J. Improved Efficiency for CCASecure Cryptosystems Built Using Identity-Based Encryption ［A］. MENEZES Alfred. 2005 Topics in CryptologyCTRSA Proceedings ［C］. USA: Springer， 2005， LNCS 3376: 87-103.

［6］ GENTRY C， SILVERBERG A. Hierarchical IDBased Cryptography ［A］. ZHENG Yuliang. 2002 Advances in CryptologyASIACRYPT ［C］. New Zealand: Springer， 2002， LNCS 2501: 548-566.

［7］ BONEH D， BOYEN X， GOH E J. Hierarchical Identity Based Encryption with Constant Size Ciphertext ［A］. CRAMER Ronald. 2005 Advances in Cryptology-EUROCRYPT Proceedings ［C］. Denmark: Springer， 2005， LNCS 3494: 440-456.

［8］ LI Jin， ZHANG Fangguo， WANG Yanming. A New Hierarchical IDBased Cryptosystem and CCASecure PKE ［A］. ZHOU Xiaobo et al.2006 EUC Proceedings ［C］. KOREA: Springer， 2006， LNCS 4097:362-371.

［9］ CHOW S M， HUI C K， YIU S M， CHOW K P. Secure Hierarchical Identity Based Signature and Its Application［A］. Lopez Javier et al. 2004 ICICS Proceedings ［C］. Spain: Springer， 2004， LNCS 3269:480-494.

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文