葛榮亮，高德智，梁景玲，張?jiān)?/p>

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

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

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]提出了一個(gè)自認(rèn)證的簽名方案，但是這個(gè)方案不安全。后來(lái)又有一些方案相繼被提了出來(lái)，2007年Shao[6]提出了基于橢圓曲線上雙線性對(duì)的自認(rèn)證簽名方案，在這個(gè)方案中，認(rèn)證中心（CA）將部分私鑰通過(guò)變換隱藏，然后發(fā)給用戶，用戶收到后首先恢復(fù)私鑰，然后簽名。相比于基于身份的簽名方案，自認(rèn)證方案能夠很好的解決安全信道問(wèn)題。

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

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

1 預(yù)備知識(shí)

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

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

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

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

3）可計(jì)算性：對(duì)于任意P，Q∈G1，存在一個(gè)有效的算法計(jì)算e（P，Q）。

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

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

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

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

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

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

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

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

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

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

3）選取兩個(gè)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個(gè)用戶隨機(jī)取xi∈Z*q作為秘密值，然后計(jì)算Pi=（Xi，Yi）用戶公鑰，其中Xi=xiP，Yi=xiPpub，那么任何人都可以通過(guò)檢驗(yàn)等式e（Xi，Ppub）=e（Yi，P）是否成立來(lái)驗(yàn)證Pi的正確性。

2.3 部分私鑰提取算法

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

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

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

2.4 單個(gè)簽名生成與驗(yàn)證算法

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

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

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

2）計(jì)算hi=H2（mi，Ui）；

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

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

2.5 聚合簽名算法

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

2.6 聚合簽名驗(yàn)證算法

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

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

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

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

3 安全模型與安全證明

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

3.1 安全模型

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

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

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

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

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

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

3.2 安全證明

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

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

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

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

H1-Hash詢問(wèn)：A1做一個(gè)H1-Hash詢問(wèn)，B為了響應(yīng)隨機(jī)預(yù)言機(jī)H1的詢問(wèn)，維護(hù)一張五元組的列表L1:（IDi，Pi，wi，yi，zi），該表初始值為空，當(dāng)敵手A1對(duì)IDi進(jìn)行H1-Hash詢問(wèn)時(shí)，算法響應(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計(jì)算wi=z（bP）；若y=1，計(jì)算wi=zP；

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

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

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

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

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

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

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

①如果IDi，Pi以前被詢問(wèn)過(guò)，則B從L1中找出其值；

②否則B用IDi，Pi做H1-Hash詢問(wèn)；

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

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

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

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

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

6）輸出：假設(shè)簽名偽造成功，敵手A1輸出有效簽名σ=（U1，…，Un，V）。但是A1沒(méi)有詢問(wèn)在ID1下對(duì)消息m1的簽名。偽造成功的條件為y1=0，yi=1（2≤i≤n），B在此過(guò)程中沒(méi)有中止。由y1=0可知，H1（IDi，Pi）=zi（bP），而由yi=1可知，H1（IDi，Pi）=ziP。那么對(duì)于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可以計(jì)算abP出的值：

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

E1：B沒(méi)有因?yàn)锳1的局部私鑰詢問(wèn)失敗而中止。

E2：A1生成一個(gè)有效的聚合簽名。

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

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

推論1：B沒(méi)有因?yàn)锳1的局部私鑰詢問(wèn)失敗而中止的概率至少為Pr[E1]≥（1-δ）qE。

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

推論2：算法B沒(méi)有因?yàn)锳1的局部私鑰詢問(wèn)失敗而中止，A1的攻擊與B的運(yùn)行相關(guān)，與真實(shí)的攻擊一致，因此有

推論3：算法B沒(méi)有因?yàn)锳1輸出一個(gè)有效簽名而失敗中

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

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

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

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

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

4 結(jié)論

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