湯小超， 王 斌， 楊 睛， 李 純

（揚州大學 信息工程學院，江蘇 揚州 225127）

近年來人們對數(shù)字簽名的變體進行了多方面的研究［1－2］。聚合簽名方案［2］將來自不同的n 個用戶的對n個消息的n個不同的簽名進行聚合，從而生成一個聚合簽名。聚合簽名可以簡化信息驗證的過程，從而減少驗證簽名需要的計算量和數(shù)據存儲。聚合簽名分為無序的聚合簽名［2］和順序的聚合簽名［3］2種。

由于基于身份的公鑰密碼系統(tǒng)［4］存在固有的密鑰托管問題，文獻［5］提出了無證書的公鑰密碼系統(tǒng)，該系統(tǒng)的私鑰由用戶和密鑰生成中心（key generate center，KGC）共同生成，所以無證書的公鑰密碼系統(tǒng)解決了密鑰托管的問題，以該方案為基礎，研究者提出了許多無證書的簽名方案。文獻［6］提出了基于雙線性映射的2個無證書聚合簽名方案。文獻［7］利用雙線性映射構造方案，提高了簽名以及驗證過程中計算效率。文獻［8］提出在消息簽名階段不需要雙線性映射的計算，而且在驗證階段也只需要2步的雙線性映射的計算，所以該方案在簽名驗證時更加高效。

文獻［9］的方案是在無證書簽名方案的基礎上提出的，并給出了正式的安全模型，本文將該方案［9］的部分密鑰提取部分與自認證體制［10］相結合，保證了密鑰分配中心生成部分密鑰在信道傳輸時的安全性，并對文獻［9］方案的簽名、聚合簽名及聚合驗證部分進行了改進，提出了一種無證書的順序聚合簽名方案，并進行了安全性分析。性能分析表明，新提出的順序聚合簽名方案可以改善聚合簽名的效率。

1 無證書的順序聚合簽名方案

無證書的順序聚合簽名方案是在文獻［9］方案的基礎上進行擴展得到的，該方案包含以下算法。

1.1 系統(tǒng)設置

KGC選取一個安全參數(shù)k。選取一個循環(huán)群G1，G1的生成元為P，其階為素數(shù)p。一個循環(huán)群G2，其階也為素數(shù)p。雙線性映射e：G1×G1→G2。除此之外，KGC再選取一個隨機數(shù)λ∈作為系統(tǒng)主密鑰，計算PT＝λ·P。選取3個Hash函數(shù)如下：

H1：｛0，1｝＊→G1，

H2：｛0，1｝＊→G1，

H3：｛0，1｝＊→G1。

所以系統(tǒng)的參數(shù)列表為：

params＝ 〈G1，G2，e，P，PT，H1，H2，H3〉。

消息空間為：

M ＝ ｛0，1｝＊。

其中，PT為系統(tǒng)公鑰。

1.2 生成用戶密鑰

一個用戶 Ui，其身份為IDi＝｛0，1｝＊ ，Ui隨機選取一個數(shù)作為用戶私鑰，計算Xi＝xi·P，Yi＝xi·PT，Pi＝（Xi，Yi）作為用戶公鑰。

1.3 生成部分私鑰

用戶Ui將自己的身份IDi和自己的公鑰Pi傳送給KGC，接著KGC計算出Di＝λ·Qi，其中Qi＝H1（IDi，Pi），并將Di作為部分私鑰。KGC隨機選取一個數(shù)，計算Ai＝ai·P，Bi＝Di＋ai·Xi，最后 KGC通過公共的通道將（Ai，Bi）發(fā)送給相應的用戶Ui。

用戶Ui收到KGC發(fā)送的（Ai，Bi）信息后，計算Di＝Bi－xi·Ai，用戶Ui就可得到部分私鑰Di。用戶將Di和xi作為簽名密鑰。

1.4 簽名

用戶U1的身份為ID1，選取消息m1∈M 和簽名密鑰D1、x1，P1＝（X1，Y1）作為用戶公鑰。具體簽名步驟如下：

（1）選取一個隨機數(shù)r1∈Z＊p，并計算R1＝r1·P。

（2）計算W1＝H3（m1‖ID1‖P1‖R1）。

（3）計算V1＝D1＋x1·W1＋r1·x1·P。

（4）σ1＝（R1，V1）。用戶 U1對消息m1的簽名即為σ1。

1.5 順序聚合簽名

1.5.1 用戶 U2簽名

（1）用戶U2收到用戶 U1發(fā)來的σ1＝（R1，V1）、m1、ID1時，首先計算W1、Q1，即

W1＝ H3（m1‖ID1‖P1‖R1），

Q1＝ H1（ID1，P1），

然后驗證e（V1，P）＝e（PT，Q1）e（W1，X1）e（R1，X1）是否成立。如果等式不成立，則停止聚合簽名；如果等式成立，則執(zhí)行以下步驟。

用戶U2的身份為ID2，選取消息m2∈M 和簽名密鑰D2和x2，具體簽名步驟如下：

步驟1 設R1＝r1·P，選取一個隨機數(shù)r2∈，并計算R2，即

R2＝R1＋r2·P＝r1·P＋r2·P＝（r1＋r2）·P。

步驟2 計算W2＝H3（m2‖ID2‖P2‖R1）。

步驟3 V1′＝V1＋r2·X1＝D1＋x1·W1＋（r1＋r2）·x1·P；V2′＝D2＋x2·W2＋x2·R2，V2＝V1′＋V2′。

步驟4 輸出聚合簽名σ2＝（R1，R2，V2）。用戶U2對添加消息m2后的聚合簽名即為σ2，并將σ2、｛m1，m2｝、｛ID1，ID2｝發(fā)送給用戶 U3。

1.5.2 用戶 Ui簽名

用戶 Ui（i≥3）收到用戶 Ui－1發(fā)來σi－1＝（R1，Ri－1，Vi－1），｛m1，m2，…，mi－1｝，｛ID1，ID2，…，IDi－1｝時，首先計算Wj、Qj，即

Wj＝H3（mj‖IDj‖Pj‖R1），1≤j≤i－1；

Qj＝ H1（IDj，Pj），1≤j≤i－1。然后驗證是否成立。如果等式不成立，則說明前面的簽名存在錯誤；如果等式成立，則說明前面的聚合簽名都正確，則用戶Ui對消息mi執(zhí)行以下步驟：

步驟1 設Ri－1＝ri－1·P，選取一個隨機數(shù)，并計算：

Ri＝Ri－1＋ri·P＝ri－1·P＋ri·P＝

（ri－1＋ri）·P。

步驟2 計算Wi＝H3（mi‖IDi‖Pi‖R1）。

步驟3Vi－1′＝Vi－1＋，Vi′＝Di＋xi·Wi＋xi·Ri，Vi＝Vi－1′＋Vi′。

步驟4 輸出聚合簽名σi＝（R1，Ri，Vi）。

2 方案的安全和效率

為了驗證安全性分析結果，本文給出了數(shù)論假設，即可計算Diffie－Hellman（CDH）問題為：

?P，aP，bP∈G1，

2.1 安全性分析

首先在CDH安全假設的條件下對單個簽名的安全性進行分析。

定理1 如果攻擊者A能以概率ε對單個簽名進行偽造，則可以構造一個求解器以相同的概率解決CDH問題。

證明 設攻擊者A的一次運行能以概率ε輸出對消息m1的偽造簽名σ1＝（R1，V1），滿足驗證方程為：

設W1＝H3（m1‖ID1‖P1‖R1），將H3（·）視為random oracle，即攻擊者必須提交x，才能獲取y＝H3（x）的值，而不能自行求值，且y的值在H3（·）的值域上隨機分布。

因此一次成功的偽造簽名必須把m1‖ID1‖P1‖R1作為輸入查詢H3（·），否則H3（·）在m1‖ID1‖P1‖R1上得到的輸出是隨機、不可預測的。設m1‖ID1‖P1‖R1出現(xiàn)在攻擊者對H3（·）的第i次查詢。

現(xiàn)在回卷攻擊者狀態(tài)，在攻擊者的第2次運行中保持攻擊者對H3（·）的前i－1次查詢的回答不變，但重新選取對H3（·）的第i次查詢m1‖ID1‖P1‖R1及之后查詢的回答。

設攻擊者第2次運行輸出的偽造簽名為σ1＝（R1，V1），m1，驗證方程為：為在第2次運行中對m1‖ID1‖P1‖R1所選取的回答。2個驗證方程（1）、（2）相除，可得：

設有一個算法B給定輸入為P，aP，bP∈G1，

其中，試圖求解CDH問題，即計算abP。

算法B模擬攻擊者A的安全試驗環(huán)境，并回答A發(fā)出的random oracle查詢，B設置第1個用戶的公鑰為X1＝bP，對H3（·）采取的模擬方法如下：

攻擊者提交x，B選取w∈Zp，返回w·（aP）作為H3（x）的值。

第1次運行攻擊者時，對m1‖ID1‖P1‖R1，B選取wi∈Zp，設置W1＝H3（m1‖ID1‖P1‖R1）＝wi·（aP）。

第2次運行攻擊者時，B選取wi∈Zp，設置W1＝H3（m1‖ID1‖P1‖R1）＝wi·（aP），將W1、W1代入方程（3），則有：

e（V1－V1，P）＝e（（wi－wi）·aP，bP）。故e（（wi－wi）－1·（V1－V1），P）＝e（abP，P），則abP為（wi－wi）－1·（V1－V1）。

由CDH 假設可知，根據（P，aP，bP，G1）計算abP的結果是不可行的，以上結果與數(shù)論假設矛盾，定理得證。

根據順序聚合的簽名過程，每次聚合本質上是將當前簽名人生成的獨立簽名和已有的部分聚合簽名進行線性疊加。若一個攻擊者A′可以針對某個用戶偽造其參與順序聚合簽名，則在順序聚合簽名的某個位置，必然存在一個對該用戶的簽名偽造，且能通過驗證。由上述關于單個簽名的安全分析可知，本文構造的順序聚合簽名方案也是安全的。

2.2 效率分析

本文通過計算量和通信量比較2種方案的效率（假設有n個用戶參與），結果見表1所列，對于計算代價較小的運算忽略不計。表1中，M為點乘運算；H為Hash函數(shù)運算；E為雙線性運算。從表1可看出，文獻［9］提出的方案和本文方案的計算量是基本相同的。因為本方案對文獻［7］中方案的隨機數(shù)Ri（1≤i≤n）也進行了聚合，在文獻［9］方案中需要傳輸數(shù)據｛R1，R2，…，Rn｝，而在本方案中只需要傳輸R1、Rn即可，所以在通信開銷方面本方案是優(yōu)于文獻［9］的。

表1 效率比較

3 結束語

本文提出了一種無證書的順序聚合簽名方案，該方案不同于現(xiàn)有的聚合簽名方案，因為現(xiàn)有的簽名方案大多是無序的，而該方案的簽名是有順序的。本方案的部分密鑰生成過程中引入了自認證簽名方案，解決了部分密鑰的安全問題，同時相對聚合簽名，方案的效率也較高。在隨機預言模型下證明了該方案可以防止攻擊者的偽造攻擊。

［1］ 薛益民，米軍利.可撤銷匿名性的盲代理群簽名方案［J］.合肥工業(yè)大學學報：自然科學版，2013，36（12）：1465－1467.

［2］ Boneh D，Gentry C，Lynn B，et al.Aggregate and verifiably encrypted signatures from bilinear maps［C］／／Advance in Cryptology－EUROCRYPT 2003，Warsaw，Poland.Berlin：Springer，2003：416－432.

［3］ Lysyanskaya A，Micali S，Reyzin L，et al.Sequential aggregate signatures from trapdoor permutations［C］／／Advances in Cryptology－EUROCRYPT 2004，Interlaken，Switzerland.Berlin：Springer，2004：74－90.

［4］ Shamir A.Identity－based cryptosystems and signature schemes［C］／／Advances in Cryptology：Proceedings of CRYPTO 84.Berlin：Springer，1985：47－53.

［5］ Al－Riyami S S，Paterson K G.Certificateless public key cryptography［C］／／Advances in Cryptology－ASIACRYPT 2003，Taipei，Taiwan.Berlin：Springer，2003：452－473.

［6］ Gong Zheng，Long Yu，Hong Xuan，et al.Two certificateless aggregate signature from bilinear maps ［C］／／Eighth ACIS International Conference，2007：188－193.

［7］ 曹素珍，王彩芬，程文華，等.一種高效的無證書聚合簽名方案［J］.計算機工程，2011，37（18）：157－159，166.

［8］ Li Fengyin，Liu Peiyu.An efficient certificateless signature scheme from bilinear parings［C］／／Network Computing and Information Security（NCIS），2011：35－37.

［9］ Zhang Lei，Zhang Futai.A new certificateless aggregate signature scheme［J］.Computer Communications，2009，32（6）：1079－1085.

［10］ Shao Zuhua.Self－certified signature scheme from pairings［J］.The Journal of Systems and Software，2006，80（3）：388－395.