葛榮亮，高德智，梁景玲，張云

（山東科技大學(xué)信息科學(xué)與工程學(xué)院，山東青島266510）

傳統(tǒng)的公鑰密碼系統(tǒng)需要管理用戶的證書，在管理證書的過程中需要大量的計算和存儲開銷。為此，1984年Shamir[1]首先提出了關(guān)于身份的數(shù)字簽名的構(gòu)想。這個方案簡化了證書管理的過程，但是存在著密鑰托管問題和安全信道的問題。

1991年Girault[2]提出了自認(rèn)證公鑰（SCK）的概念，這篇文章結(jié)合了基于身份的概念和傳統(tǒng)PKI應(yīng)用的概念。1997年P(guān)etersen和Hoster[3]擴(kuò)展了Girault的方法寫了一篇關(guān)于自認(rèn)證密鑰概念和應(yīng)用的文章。2001年Shao[4]提出了基于自認(rèn)證公鑰的加密系統(tǒng)，但這篇文章缺少安全模型與安全證明。2002年Lee[5]提出了一個自認(rèn)證的簽名方案，但是這個方案不安全。后來又有一些方案相繼被提了出來，2007年Shao[6]提出了基于橢圓曲線上雙線性對的自認(rèn)證簽名方案，在這個方案中，認(rèn)證中心（CA）將部分私鑰通過變換隱藏，然后發(fā)給用戶，用戶收到后首先恢復(fù)私鑰，然后簽名。相比于基于身份的簽名方案，自認(rèn)證方案能夠很好的解決安全信道問題。

現(xiàn)在數(shù)字簽名技術(shù)有了更為廣泛的應(yīng)用，但在一些特殊的環(huán)境中有限制，比如在傳感器、手機(jī)、個人數(shù)字助理（PDA）中，當(dāng)需要對多個簽名同時驗證的時候，就會產(chǎn)生突出的效率問題。為了應(yīng)對這類問題。2003年Boneh[7]等人第一次提出了一個聚合簽名方案，即將n個簽名聚合成單一的簽名。2004年，Cheon[8]等人提出了第一個基于身份的聚合簽名方案，并指出不是所有的基于身份的簽名方案都能變換成聚合簽名方案。2007年，Gong[9]等人提出了基于雙線性映射的兩個無證書聚合簽名方案，這兩個方案可以用在不同的環(huán)境中。2010年孫華[10]等人提出了一種安全有效的基于身份的聚合簽名方案，這個方案具有較高的效率。

本文提出了一個自認(rèn)證聚合簽名方案。該方案參考了文獻(xiàn)[10]的簽名方案，并加入自認(rèn)證的過程，使方案具有更高的安全性，同時利用計算Diffie-Hellman問題的困難性，在隨機(jī)預(yù)言模型下證明了方案的安全性。

1 預(yù)備知識

簡要回顧雙線性對的概念和一些相關(guān)的數(shù)學(xué)知識：

雙線性對：令G1是階為q的加法循環(huán)群，G2是階為q的乘法循環(huán)群，P是G1的生成元，Z是階為q的非零素域，令e：G1×G1→G2是滿足下列條件的一個雙線性映射：

1）雙線性：對于任意P，Q∈G1，以及a，b∈Z，滿足e（aP，bQ）=e（P，Q）ab；

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

3）可計算性：對于任意P，Q∈G1，存在一個有效的算法計算e（P，Q）。

在群G1上，可以定義以下幾個密碼學(xué)問題：

計算性Diffie-Hellman問題（CDHP）：對于任意a，b∈Z和P∈G1，已知（P，aP，bP），計算abP，如果離散對數(shù)問題可解，CDH問題可解，反之，不一定成立。

判定性Diffie-Hellman問題（DDHP）：給定P，aP，bP，cP對于a，b，c∈Z，判斷c=ab（modq）是否成立。

雙線性Diffie-Hellman問題（BDHP）：給定P，aP，bP，cP對于任意未知的a，b，c∈Z，計算e（P，P）abc。

Gap Diffie-Hellman問題（GDHP）：在多項式時間內(nèi)，判斷性Diffie-Hellman（DDHP）問題是可解的，而不存在多項式時間算法能以不可忽略的概率解決計算Diffie-Hellman（CDH）問題。任何多項式時間內(nèi)算法A能夠成功解決CDH問題的可能性定義為：Succ=Pr[A（P，aP，bP）=abP:a，b，c∈Z]。CDH問題假設(shè)對于每一個多項式時間內(nèi)的算法，Succ可忽略。

2 一個自認(rèn)證聚合簽名方案

本方案一共包含6個算法，具體算法如下：

2.1 系統(tǒng)建立算法

認(rèn)證中心（CA）完成以下步驟：

1）選取階為q的加法循環(huán)群G1和乘法循環(huán)群G2，取群G1的兩個生成元P和Q，設(shè)雙線性對e：G1×G1→G2；

3）選取兩個Hash函數(shù)：H1：{0，1}*×G1→G1，H2：{0，1}*×G1→，則系統(tǒng)參數(shù)為params={G1，G2，e，P，Q，Ppub，H1，H2}。

2.2 公鑰生成算法

身份為IDi的第i個用戶隨機(jī)取xi∈Z*q作為秘密值，然后計算Pi=（Xi，Yi）用戶公鑰，其中Xi=xiP，Yi=xiPpub，那么任何人都可以通過檢驗等式e（Xi，Ppub）=e（Yi，P）是否成立來驗證Pi的正確性。

2.3 部分私鑰提取算法

第i個用戶發(fā)送自己的身份IDi∈{0，1}*和公鑰Pi給CA，然后CA計算局部私鑰Di=sH1（IDi，Pi），s是CA的主密鑰。CA取ki∈，計算Wi=kiP，Zi=Di+kiXi，然后CA（Wi，Zi）將通過公共渠道發(fā)給用戶。

用戶收到（Wi，Zi）后，首先恢復(fù)Di，即計算Di=Zi-xiWi，然后通過下面的式子

來驗證Di的正確性。如果上式成立，則接受Di，否則拒絕。此時用戶實際上擁有私鑰（Di，xi）。事實上這里的Di是Boneh[11]等人提出的一個關(guān)于消息（IDi，Pi）的短簽名。在上述過程中，認(rèn)證中心（CA）將局部私鑰隱藏在Zi，這樣就可以把包含私鑰的信息通過公共渠道發(fā)給用戶。因此就能很好地解決安全信道的問題。

2.4 單個簽名生成與驗證算法

第i個用戶，也即第i個簽名者，收到認(rèn)證中心（CA）傳來的Di后，計算Si=xiDi作為自己的全私鑰。

然后簽名者對消息mi∈{0，1}*進(jìn)行簽名：

1）隨機(jī)選取ri∈，計算Ui=riP；

2）計算hi=H2（mi，Ui）；

3）計算Vi=Si+riQ+hiDi，則消息mi上的簽名是σi=（Ui，Vi）。

給定身份為IDi的簽名者的公鑰Pi，消息mi以及簽名σi，就可以驗證簽名。首先，計算hi=H2（mi，Ui），di=H1（IDi，Pi），然后驗證等式e（Vi，P）=e（di，Yi）e（Q，Ui）e（hidi，Ppub）是否成立，如果等式成立則σi是一個有效的簽名。

2.5 聚合簽名算法

這一階段，任何人可以作為聚合簽名的生成者，他可以將n個簽名聚合成一個簽名。假設(shè)U是簽名者集合，S∈U為生成聚合簽名者的集合，現(xiàn)設(shè)S中共有n個用戶，他們的身份為ID1，ID2，…，IDn每個用戶都有對消息mi的簽名σi=（Ui，Vi）。那么聚合簽名生成者在收到n個簽名σi后，則產(chǎn)生的聚合簽名是σ=（U1，…，Un，V）。

2.6 聚合簽名驗證算法

給定用戶身份IDi，相應(yīng)公鑰Pi，消息mi，以及簽名σ=（U1，…，Un，V），驗證者執(zhí)行以下步驟：

1）計算hi=H2（mi，Ui），di=H1（IDi，Pi），其中（i=1，…，n）；

3）如果等式成立，則σ是一個有效的聚合簽名。下面是方案的正確性推導(dǎo)：

由此可得本方案是正確的。

3 安全模型與安全證明

首先給出安全模型，介紹第一類型的敵手和第二類型的敵手，接下來提供在隨機(jī)預(yù)言模型下方案的安全性證明。

3.1 安全模型

在一個無證書的公鑰密碼學(xué)（CL-PKC）中存在著兩種類型的攻擊對手，分別是Type-1敵手和Type-2敵手。Type-1敵手A1不能獲取CA的主密鑰，但是他能替換個體的公鑰。Type-2敵手A2能夠獲取CA主密鑰，但是不能替換個體公鑰。

這里可以把A1看作一般的適應(yīng)性偽造者，而A2可以看作是不可信的CA或者是盜用主密鑰的敵手。可以通過一個敵手A={A1，A2}和一個挑戰(zhàn)者C之間的游戲定義聚合簽名方案的安全模型。

1）系統(tǒng)建立：挑戰(zhàn)者運(yùn)行系統(tǒng)建立算法，獲取系統(tǒng)參數(shù)params。然后對于Type-1敵手，挑戰(zhàn)者自己保存主密鑰。這里敵手先選取秘密值x*，計算相應(yīng)的公后替換用戶的公鑰，C記錄有效的替么對于身份為DID的用戶，敵手詢問用戶的部分私鑰DID，挑戰(zhàn)者回復(fù)（W，Z），然后敵手就可以通過計算恢復(fù)DID。對于Type-2敵手，C直接告訴敵手主密鑰。

2）詢問：相對于身份ID為的用戶，A向挑戰(zhàn)者C提出任意信息的詢問，C返回在用戶公鑰下的簽名σ。

3）響應(yīng)：A詢問結(jié)束后，輸出一個有效的聚合簽名σ*，同時在這個過程中至少有一個消息mi上的簽名σi，A是沒有詢問過的。那么，就認(rèn)為敵手A獲勝。定義A獲勝的概率為A的優(yōu)勢，記為Adv（A）。

定義1一個敵手A以（t，N，ε，qH，qE，qs）攻破一個聚合簽名方案，是指A的運(yùn)行時間至多t，而且A進(jìn)行了至多qH次Hash函數(shù)詢問、qE次局部私鑰詢問、qs次簽名詢問，取得的Adv（A）至少為ε。而簽名方案是（t，N，ε，qH，qE，qs）抗存在性偽造，是指不存在敵手A以（t，N，ε，qH，qE，qs）攻破聚合簽名方案。

3.2 安全證明

假設(shè)CDH問題在隨機(jī)預(yù)言模型下是困難的，下面將給出聚合簽名方案的安全證明。

定理1如果存在一個Type-1敵手A以（t，N，ε，qp，qH，qE，qs）攻破聚合簽名方案，那么就可以構(gòu)造一個算法B在多項式時間內(nèi)，以不可忽略的概率解決CDH問題。

證明：針對該方案，存在擁有最多ε優(yōu)勢和最多運(yùn)行時間t的Type-1敵手A1，他以（t，ε）-攻破該方案。假設(shè)A1進(jìn)行了至多qH次Hash函數(shù)詢問、qp次公鑰詢問、qE次局部私鑰詢問、qs次簽名詢問。現(xiàn)設(shè)e是自然對數(shù)的底數(shù)，tG1為群中計算標(biāo)量乘法所需時間，t是偽造的簽名轉(zhuǎn)化成CDH問題所需的時間。則存在（t*，ε*）的算法B以概率ε*≥ε/（qE+n）e，在時間t*≤φ（qH1，qH2，qE，qs，qP）tG1+t內(nèi)解決CDH問題。

假設(shè)B構(gòu)造了一個（P，aP，bP，abP）的CDH問題，現(xiàn)在要計算abP。

H1-Hash詢問：A1做一個H1-Hash詢問，B為了響應(yīng)隨機(jī)預(yù)言機(jī)H1的詢問，維護(hù)一張五元組的列表L1:（IDi，Pi，wi，yi，zi），該表初始值為空，當(dāng)敵手A1對IDi進(jìn)行H1-Hash詢問時，算法響應(yīng)如下：

①如果IDi已經(jīng)存在于L1中，B響應(yīng)H1（IDi，Pi）=wi；

②否則B隨機(jī)生成y∈{0，1}，令Pr（y=0）=δ，其中δ為某一概率值；

③B隨機(jī)取z∈Z*q，如果y=0，B計算wi=z（bP）；若y=1，計算wi=zP；

④B把（IDi，Pi，wi，yi，z）加到列表L1中，并且返回給A1的值為H1（IDi，Pi）=wi。

H2-Hash詢問：為了響應(yīng)H2-Hash詢問，算法B維護(hù)一張三元組的列表L2：（mi，Ui，ci），當(dāng)敵手進(jìn)行詢問時算法B響應(yīng)如下：

2）公鑰詢問：A1進(jìn)行公鑰詢問，B響應(yīng)如下：

①B維護(hù)一張列表L3：（IDi，Pi，xi），如果詢問值已經(jīng)存在，則返回Pi值；

②否則選取xi∈，計算Pi=（Xi，Yi）=（xiP，xiPpub），將（xi，Xi，Yi）添加到L3中，并返回Pi值。

3）公鑰替換詢問：A1為了獲得新的公鑰，進(jìn)行公鑰替換詢問，B查找列表L3，如果存在則更新，否則進(jìn)行一個公鑰詢問，然后更新。

4）部分私鑰詢問：A1進(jìn)行部分私鑰（IDi，Pi）詢問，B響應(yīng)如下：

①如果IDi，Pi以前被詢問過，則B從L1中找出其值；

②否則B用IDi，Pi做H1-Hash詢問；

③如果y=0，則B失敗中止；否則，B計算Di=z（aP）。

5）簽名詢問：A1詢問（IDi，Pi，mi）上的簽名，B從L1中找到相應(yīng)元組，然后執(zhí)行以下步驟：

①如果y=0，則B失敗，中止；

②否則表明H1（IDi，Pi）=ziP，B隨機(jī)取ri∈，計算Ui=riPi；

③如果三元組（mi，Ui，ci）已在L2中，那么B取出ci，否則隨機(jī)取c∈。將（mi，Ui，c）添加到L2中。

6）輸出：假設(shè)簽名偽造成功，敵手A1輸出有效簽名σ=（U1，…，Un，V）。但是A1沒有詢問在ID1下對消息m1的簽名。偽造成功的條件為y1=0，yi=1（2≤i≤n），B在此過程中沒有中止。由y1=0可知，H1（IDi，Pi）=zi（bP），而由yi=1可知，H1（IDi，Pi）=ziP。那么對于i≥2，可以算得Vi=S*i+ri（tP）+cizi（aP），即有e（Vi，P）=e（Yizi+tUi+zici，Ppub）=e（di，Yi）e（Q，Ui）e（hidi，Ppub），其中，hi=H2（mi，Ui），di=H1（IDi，Pi）。

那么算法B可以計算abP出的值：

為了完成驗證，將給出算法B解決CDH問題的概率是ε*≥ε/（qE+n）e，首先分析B成功的3個事件：

E1：B沒有因為A1的局部私鑰詢問失敗而中止。

E2：A1生成一個有效的聚合簽名。

E3：E2發(fā)生的時候，同時有y1=0和yi=1（2≤i≤n）。

當(dāng)上面3個事件都發(fā)生時，B才能夠成功，它的概率可以表示為Pr[E1∧E2∧E3]，將其分解為Pr[E1∧E2∧E3]=Pr[E1]Pr[E1

推論1：B沒有因為A1的局部私鑰詢問失敗而中止的概率至少為Pr[E1]≥（1-δ）qE。

證明：由于Pr[y=0]=δ，那么Pr[y=1]=1-δ，因為敵手A1至多進(jìn)行qE次詢問，所以事件E1的概率為Pr[E1]≥（1-δ）qE。

推論2：算法B沒有因為A1的局部私鑰詢問失敗而中止，A1的攻擊與B的運(yùn)行相關(guān)，與真實的攻擊一致，因此有

推論3：算法B沒有因為A1輸出一個有效簽名而失敗中

證明：上面的情況產(chǎn)生必須有事件E2發(fā)生，且y1=0和yi=1（2≤i≤n），那么其概率值為δ（1-δ）（n-1）。

所以可以計算出ε*=Pr[E1∧E2∧E3]≥（1-δ）qE εδ（1-δ）（n-1）=εδ（1-δ）（n-1）。當(dāng)δ=1/（qE+n）時，εδ（1-δ）（qE+n-1）達(dá)到最大值，即有ε*≥ε/（qE+n）e。

在構(gòu)造CDH問題中，算法B運(yùn)行的時間與A1進(jìn)行詢問的時間以及將偽造簽名轉(zhuǎn)化成CDH問題的時間t有關(guān)。那么存在一個多元一次函數(shù)φ，使總的運(yùn)行時間至多為φ（qH1、qH2，qE，qs，qp）tG1+t。

對于敵手A2的攻擊，構(gòu)造過程與敵手A1類似，就省略了。

由上面的證明可知，算法B可以在敵手A的幫助下解決CDH問題，而CDH問題被認(rèn)為是難解的，所以方案在隨機(jī)預(yù)言模型下是安全的，具有不可偽造性。

4 結(jié)論

本文應(yīng)用橢圓曲線上雙線性對的技術(shù)，提出了一個自認(rèn)證的聚合簽名方案。該方案參考了已有的聚合簽名的方案，重新構(gòu)造了一個新的方案，然后將自認(rèn)證的過程引入到該方案中，這樣就能有效地解決密鑰托管和安全信道問題，同時保持聚合簽名的特性。最后利用計算Diffie-Hellman問題的困難性，證明了該方案在隨機(jī)預(yù)言模型下是安全的。

[1]SHAMIRA.Identity-basedcryptosystemsandsignatureschemes[C]//Proceedings of Crypto’84.Germany:G.Blakley and David Chaum，eds.volume 196 of LNCS.1981:47-53.

[2]GIRAULT M.Self-certified public keys[C]//Proceedings of Eurocrypt’91.USA:Springer-Verlag Berlin，Heidelberg，1991:491-497.

[3]PETERSEN H，HOSTER P.Self-certified keys-concept and application[C]//Proceedings of the Communication and Multimedia Security’97.USA:Chapman，Hall，1997:102-116.

[4]SHAO Zu-hua.Cryptographic systems using self-certified public key based on discrete logarithms[C]//IEE.[S.L.]:Comput.Digit.Teach，2001，148（6）：233-237.

[5]LEE B，KIM K.Self-certified signature[C]//Progress in Cryptology-Indocrypt’2002.LNCS 2551.Germany:Springer-Verlag Berlin，2002:199-214.

[6]SHAO Zu-hua.Self-certified signature scheme from pairing[J].The Journal of Systems and Software，2007（80）:388-395.

[7]BONEH D，GENTRY C.Aggregate and verifiably encrypted signature from bilinear maps[C]//Advance in Cryptography-EUROCRYPT 2003.LNCS 2656.Germany:[S.N.]，2003:416-432.

[8]Cheon J H，Kim Y，Yood H J.A new ID-based signature with batch verification[EB/OL].[2011-02-16].Cryptology ePrint Archive，Report 2004/13.http://eprint.iacr.org/2004/131.pdf.

[9]GONGZheng，LONGYu，HONGXuan，etal.Twocertificateless aggregate signature from bilinear maps[C]//IEEE.Qingdao China:[S.N.]，2007:188-193.

[10]孫華，鄭雪峰，于義科，等.一種安全有效的基于身份的聚合簽名方案[J].計算機(jī)科學(xué)，2010，37（5）:62-65.SUN Hua，ZHENG Xue-feng，YU Yi-ke，et al.Secure and efficient identity-based aggregate signature scheme[J].Computer Science，2010，37（5）:62-65.

[11]BONEH D，LYNN B，SHACHAM H.Short signature from the Weil pairing[C]//Advance in Cryptology-Asiacrypt’01.Germany:Springer-Verlag Berlin，2001:514-532.