王夢殊，祁正華

(南京郵電大學 計算機學院，江蘇 南京 210003)

無雙線性對的無證書聚合簽密方案

王夢殊，祁正華

(南京郵電大學 計算機學院，江蘇 南京 210003)

無證書聚合簽密是把多個用戶對不同消息產生的不同簽密聚合成一個簽密，不僅保證信息傳輸的機密性和認證性，而且降低了信息傳輸的功耗，因此應用于大規(guī)模分布式通信中的多對一模式。聚合簽密方案大多需要進行雙線性對運算，效率不高。為此，提出了一種高效的無線性對的無證書聚合簽密方案。該方案在隨機預言模型下應用離散對數，對原有的無雙線性對聚合簽名算法進行了改進，形成了更為安全、高效的聚合簽密方案?；谒岢龅木酆虾灻芊桨赴踩Ｐ停治鲅芯苛穗S機預言模型下提出方案的不可偽造性和機密性，并對其有效性和可行性進行了驗證。理論分析表明，所提出的方案在多個簽密者存在的條件下，不僅具有機密性、不可偽造性，還具有更高的計算效率。

無證書聚合簽密；隨機預言模型；無雙線性對；離散對數問題

0 引 言

簽密[1]在合理邏輯步驟里同時完成信息的簽名與伽馬。2009年,Selvi等[2]提出了基于身份的簽密方案，并證明了其安全性。祁正華[3]進行了基于身份的簽密方案研究；于剛[4]進行了若干簽密研究。聚合簽密能將多個密文進行聚合且提供批量驗證，極大降低了信息傳輸的功耗，大幅提升了簽密驗證的效率，適用在大規(guī)模分布式通信的多對一模式下。Ren等[5]提出了一種可證明安全的聚合簽密方案；蘇愛東等[6]提出了一種密文長度固定的聚合簽密方案,但未給出形式化的安全性證明。

無證書密碼體制于2003年由Al-Riyami等[7]提出，解決了公鑰證書管理及驗證問題和密鑰托管問題。Barbosa等[8]提出了無證書簽密方案并給出了安全模型。陸海軍[9]和Eslami等[10]在隨機預言模型下分別提出了可證明安全的無證書聚合簽密方案；Qi等[11]提出了無證書環(huán)簽密方案，但是上述簽密方案中用了較多雙線性對運算,因此效率較低。Qi等[12]對基于身份的聚合簽密進行了安全性分析,但使用了雙線性對。周彥偉等[13]提出的無證書聚合簽名方案運算量小，無需進行雙線性運算，因此參考其無雙線性對的特點,提出了無雙線性對的無證書聚合簽密方案并進行了理論分析。

1 相關基礎

1.1 離散對數問題

離散對數問題(Discrete Logarithm Problem,DLP)：設G是q階循環(huán)群，q為素數。給定兩個元素P,Q∈G，找到使Q=nP成立的整數n。

1.2 聚合簽密方案的安全模型

文獻[4]定義的安全模型,無證書聚合簽密方案將面臨A1和A2兩類敵手的攻擊。

A1類敵手不知道系統(tǒng)的主密鑰，但可以進行公鑰替換操作,或利用所有用戶的公鑰來對系統(tǒng)主密鑰進行攻擊，因此A1類敵手為惡意用戶。A2類敵手已知系統(tǒng)主密鑰，具有計算所有用戶部分公鑰私鑰的能力，但不可以替換用戶公鑰,因此A2類敵手為惡意的KGC。

選擇密文攻擊下的機密性和適應性，選擇消息攻擊下的不可偽造性。方案機密性證明中，U1是A1類敵手的挑戰(zhàn)者,U2是A2類敵手的挑戰(zhàn)者,不可偽造性證明中，T1是A1類敵手的挑戰(zhàn)者,T2是A2類敵手的挑戰(zhàn)者。文獻[14]詳細介紹了無證書聚合簽密方案在A1和A2兩類敵手適應性選擇消息攻擊下不可偽造性的定義及相應游戲，不再敘述。

定義1：類型A1攻擊下的密文機密性。類型A1的攻擊者不能在多項式時間內，以不可忽略的優(yōu)勢贏得以下博弈，則該簽密方案在選擇密文攻擊下具有不可區(qū)分性。

SETUP：挑戰(zhàn)者U1將生成的系統(tǒng)公共參數發(fā)送給敵手A1并保存系統(tǒng)主密鑰。

第一階段：敵手能夠多項式次執(zhí)行的詢問如下：

部分密鑰生成問詢：A1輸入(IDi,Xi)進行問詢,就可得到(yi,Yi)。

私鑰生成問詢:A1輸入IDi問詢,得到SKi=(xi,yi)。

簽密問詢:A1輸入(IDi,mi,IDB)問詢,得到：

δi=(V,Vi,Si,Wi)=Signcryption(IDi,mi,IDB)

解簽密問詢:A1輸入簽密δi和身份(IDi,IDB)問詢,U1可進行解簽密,將解簽密結果返回A1。

挑戰(zhàn)階段:A1選擇要挑戰(zhàn)的兩個明文mi(i∈{0,1})和兩個身份IDi,IDB,不能在第一階段詢問IDB的私鑰。U1選擇一個隨機的比特b,計算δ*=Signcryption(mb,IDi,IDB)，將δ*發(fā)送A1。

第二階段：類似于第一階段,A1能夠多項式次執(zhí)行詢問，并且不能詢問用戶IDB私鑰或對δ*進行解簽密詢問。

猜測階段：最后A1提交一個比特b',若b'=b,那么A1在此游戲中獲勝。游戲中敵手的優(yōu)勢為Adv[A1]=|Pr[b'-b]-0.5|。

定義2:類型A2攻擊下的密文機密性。類型A2的攻擊者不能在多項式時間內，以不可忽略的優(yōu)勢贏得以下博弈，則該簽密方案在選擇密文攻擊下具有不可區(qū)分性[15]。

SETUP：挑戰(zhàn)者U2將生成的系統(tǒng)公共參數發(fā)送給敵手A2并保存系統(tǒng)主密鑰。

第一階段：敵手可適應性地進行以下多項式數量級的詢問：部分密鑰生成問詢、私鑰生成問詢、簽密問詢、解簽密問詢與定義1的問詢一樣,由A1問詢變成A2問詢,但不進行公鑰替換詢問。

第二階段：類似于第一階段,A2能夠多項式次執(zhí)行詢問，并且不能詢問用戶IDB的私鑰或對δ*進行解簽密詢問。

猜測階段與定義1中類似,最終A2獲勝。

2 基于離散對數問題的聚合簽密方案

無證書聚合簽密由7個算法組成，分別是系統(tǒng)初始化、用戶密鑰設置、部分私鑰提取、簽密、聚合簽密和聚合解簽密。

用戶密鑰設置：用戶ui隨機選取秘密值xi,計算公開參數Xi=xiP。

簽密:用戶ui對發(fā)送給IDB的消息mi簽密如下:

(2)計算hi2=H2(IDi‖mi,V,Zi);

(3)計算Ti=H3(Vi,IDB,V,aiXB);

(4)計算Wi=Ti⊕(mi‖IDi),Si=ai+(xi+yi)hi2。這樣δi=(V,Vi,Si,Wi)為ui對IDB消息mi的簽密。

解簽密:IDB對ui發(fā)送的簽密δi=(V,Vi,Si,Wi)的解簽密步驟如下：

(1)計算Ti=H3(Vi,IDB,V,xBVi),IDi‖mi=Wi⊕Ti;

(2)計算Zi=ai(YB+Ppubhi1)=yBVi,hi1=H1(IDi,Xi,Yi)，hi2=H2(IDi‖mi,V,Zi)；

(3)根據等式SiP=Vi+(Xi+Yi+Ppubhi1)hi2進行檢測,若正確輸出對應消息mi‖IDi,否則驗證失敗。

(1)計算Ti=H3(Vi,IDB,V,xBVi),IDi‖mi=Wi⊕Ti;

(2)計算Zi=ai(YB+Ppubhi1)=yBVi;

3 安全性分析

3.1 正確性

方案的正確性證明如下:

通過SiP=Vi+(Xi+Yi+Ppubhi1)hi2對簽密進行驗證：

3.2 安全性

詢問階段：敵手A1進行下述詢問：

H1查詢：當A1向預言機H1詢問H1(IDi,Xi,Yi)時,T1進行下述操作：

①如果列表L1中存在相應的元組,則T1返回hi1給A1;

H2查詢:當A1向預言機H2詢問H2(IDi‖mi,V,Zi)時,T1進行下述操作：

①如果列表L2中存在相應元組,則T1返回給A1;

H3查詢:當A1向預言機H3詢問H3(Vi,IDB,V,aiXB)時,T1進行下述操作:

①如果列表L3中存在相應的元組,則T1返回給A1;

部分密鑰生成詢問：當A1要對IDi和公開參數Xi進行部分密鑰生成詢問時,T1進行如下操作：

①若Lk中存在相應元組,則T1返回相應的值(yi,Yi)給A1；

私鑰生成詢問：當A1要對IDi的私鑰生成執(zhí)行問詢時,T1進行如下操作：

①如果列表Lsk中存在元組,則返回相應的值SKi=(xi,yi)給A1；

公鑰生成詢問：當A1要對身份IDi的公鑰生成執(zhí)行詢問時，T1進行下述操作：

①如果Lpk中存在元組,則返回PKi=(Xi,Yi)給A1;

簽密詢問：當T1收到A1關于發(fā)送方身份、消息、接收方身份簽密詢問時,執(zhí)行操作如下：

①如果IDi=IDj，則T1放棄,終止模擬；

聚合簽密詢問：當T1收到A1關于發(fā)送方身份、消息、接收方身份的簽密詢問時，執(zhí)行如下步驟：

②否則T1棄權，停止模擬。

解簽密問詢:當T1收到A1關于發(fā)送者身份、接收者身份、簽密的解簽密詢問時，T1查詢L1，判斷其中是否存在IDi對應的元組：

①倘若L1中存在IDi所對應的元組且IDi≠IDj,按照解簽密算法進行解密,并驗證SiP=Vi+(Xi+Yi+Ppubhi1)hi2是否成立,若成立T1返回1給A1,否則返回0；

②如果L1中存在IDi所對應的元組且IDi=IDj,則當L2中存在IDi相對應的元組時,T1返回1給A1,否則返回0；

③如果L1中不存在IDi所對應的元組,則當L2中存在IDi對應的元組時,T1返回1給A1,否則返回0。

①如果對于所有的IDi(1≤i≤n),都有IDi≠IDj,就將模擬中止。

①如果成立,則T1輸出

作為離散對數問題的有效解;

②否則,T1沒有解決離散對數問題。

詢問：敵手A2對預言機H1,H2,H3，私鑰生成,公鑰生成,簽密和解簽密的詢問過程與引理1相同。

部分密鑰生成詢問：當A2執(zhí)行對IDi和公開參數Xi的部分密鑰生成詢問時,T1進行如下操作：

①如果列表Lk中存在相應元組,則T1返回相應值(yi,Yi)給A1;

解簽密問詢:當T2收到A2關于發(fā)送者身份,接收者身份,簽密(1≤i≤n)的解簽密詢問時,T2查詢L1中是否存在IDi對應的元組:

①若L1中存在IDi對應的元組且IDi≠IDj,則按解簽密算法進行解密,并驗證SiP=Vi+(Xi+Yi+Ppubhi1)hi2是否成立,如果成立,則T2返回1給A2,否則返回0。

②如果L1中存在IDi所對應的元組且IDi=IDj,則當L2中存在IDi相對應的元組時,T2返回1給A2,否則返回0。

①如果對所有IDi都有IDi≠IDj,終止模擬。

如果等式成立,則T2輸出：

作為離散對數問題的有效解;否則,T2沒有解決離散對數問題。

引理3：在隨機預言模型下，若不存在任何多項式數量級的敵手A1在下面的游戲中能以不可忽略優(yōu)勢獲勝，那么稱該方案具有機密性。

詢問：敵手A1詢問過程與引理1相似。

第一階段,A1或許產生兩個長度相等的消息mi0,mi1來接受挑戰(zhàn)。隨機選擇并通過執(zhí)行簽密算法獲得ui對發(fā)送給IDB的關于消息mib的簽密和聚合簽密{δi,δ},返回δ*給敵手A1。

結束時,猜想A1被返回，若等式成立，則輸出1;否則,輸出0。由于敵手A1不能進行解簽密詢問，應用進行H2問詢。這里Zi=yBVi,yB是接收者的部分密鑰,并且yB=rknow+bhi1,YB=rknowP,Zi=ai(YB+Ppubhi1)=yBVi,b=(hi1)-1((Vi)-1[ai(YB+Ppubhi1)]-rknow),由于離散對數問題中計算n是困難的,因此已知Zi和Vi求取b也是困難的。

引理4：在隨機預言模型下，若不存在任何多項式數量級的敵手A2在下面的游戲中能以不可忽略優(yōu)勢獲勝，那么稱該方案具有機密性。

詢問：敵手A2詢問過程與引理2相似。

在第一階段和第二階段與引理3模擬類似,不同的是這里Zi=yBVi,yB是接收者的部分密鑰,并且yB=b+shi1,YB=bP,Zi=ai(YB+Ppubhi1)=yBVi,則有b=(Vi)-1ai(YB+Ppubhi1)-shi1。由于離散對數問題中計算n是困難的,因此已知Zi和Vi求取b也是困難的。

3.3 效率分析

表1是上述方案與文獻[6,9,17-18]的簽密方案進行性能比較的結果。耗時比較大的計算主要有雙線性對運算、冪運算和數乘運算,d表示雙線性運算,h表示指數運算,t代表G上的點乘運(由于其他方案都使用了雙線性運算,因此將群G記為G1，G2，G2為G1的雙線性映射)。

表1 簽密方案運算量比較

表1分析了5種聚合簽密方案的運算量，點乘運算對比對運算和指數運算耗時少許多。文中方案簽密者只需2次點乘運算,而文獻[9,17-18]都需要進行雙線性對運算,文獻[9]在簽密時運算量較小,但解簽密時高于文中方案。文獻[6]的指數運算較大,且其在解簽密階段比文中方案多了許多雙線性運算和指數運算。因此文中方案較為高效。

4 結束語

為提高無證書聚合簽名和無證書簽密方案的有效性和安全性，在隨機預言模型具有可證安全性的基礎上，提出了無雙線性對的聚合簽密方案。該方案基于離散對數難題，避免了雙線性對運算。由于離散對數難題至今未能解決，因此該方案更為安全可靠。在簽密者人數不止一個的情況下，提高了簽密和解簽密的計算效率。

[1] Zheng Y.Digital signcryption or how to achieve cost (signature & encryption)?cost (signature)+cost (encryption)[C]//Annual international cryptology conference.Berlin:Springer,1997:165-179.

[2] Selvi S S,Vivek S S,Shriram J,et al.Identity based aggregate signcryption schemes[C]//International conference on progress in cryptology-indocrypt.[s.l.]:[s.n.],2009:378-397.

[3] 祁正華.基于身份的簽密方案研究[D].南京:南京郵電大學,2012.

[4] 于 剛.若干簽密方案研究[D].鄭州:解放軍信息工程大學,2012.

[5] Ren Xunyi,Qi Zhenghua,Yang Geng.Provably secure aggregate signcryption scheme[J].ETRI Journal,2012,34(3):421-428.

[6] 蘇愛東,張永翼.密文長度固定的全聚合簽密方案[J].計算機應用研究,2015,32(9):2820-2822.

[7] Riyami S A,Paterson K.Certificatless public key cryptography[C]//Proceedings of the ASIACRYPT.Berlin:Springer-Verlag,2003:452-473.

[8] Barbosa M,Farshim P.Certificateless signcryption[C]//Proceedings of ASIACCS.Tokyo,Japan:ACM Press,2008:369-372.

[9] 陸海軍.聚合簽名與聚合簽密研究[D].杭州:杭州師范大學,2012.

[10] Eslami Z,Nasrollah P.Certificateless aggregate signcryption:security model and a concrete construction secure in the random oracle model[J].Journal of King Saud University Computer and Information Sciences,2014,26(3):276-286.

[11] Qi Zhenghua,Yang Geng,Ren Xunyi.Provably secure certificateless ring signcryption scheme[J].China Communications,2011,8(3):99-106.

[12] QI Zhenghua,Ren Xunyi,Yang Geng.Provably secure general aggregate signcryption scheme in the random oracle model[J].China Communications,2012,9(11):107-116.

[13] 周彥偉,楊 波,張文政.高效可證安全的無證書聚合簽名方案[J].軟件學報,2015,26(12):3204-3214.

[14] Zhang L,Qin B,Wu Q H,et al.Efficient many-to-one authentication with certificate-less aggregate signatures[J].Computer Networks,2010,54(14):2482-2491.

[15] 高鍵鑫，吳曉平，秦艷琳，等.無雙線性對的無證書安全簽密方案[J].計算機應用研究,2014,31(4):1195-1198．

[16] 王大星,騰濟凱.可證明安全的基于身份的聚合簽密方案[J].計算機應用,2015,35(2)：412-415.

[17] Han Yiliang,Chen Fei.The multilinear mapsbased certificateless aggregate signcryption scheme[C]//International conference on cyber-enabled distributed computing and knowledge discovery.[s.l.]:[s.n.],2015:92-99.

[18] Liu Jianhua,Zhao Changxiao,Mao Kefei.Efficient certificateless aggregate signcryption scheme based on XOR[J].Computer Engineering and Applications,2016,26(3):176-186.

A Certificateless Aggregate Signcryption Scheme without Bilinear Pairing

WANG Meng-shu，QI Zheng-hua

(School of Computer Science and Technology,Nanjing University of Posts and Telecommunications,Nanjing 210003,China)

Certificateless aggregate signcryption scheme can aggregate different signcryptions generated by multi-users corresponding to various information into one signcryption,which can not only ensure the confidentiality and certification in information transmission but also reduce power dissipation.Therefore,it is applied in the multiple-to-single mode in large-scale distributed communication.Most aggregate signcryption schemes need computation of bilinear pairing with poor efficiency.For that,an efficient certificateless aggregate signcryption schemes without bilinear pairing is proposed,where disperse logarithm is employed in random oracle model to improve the original aggregate signature algorithm without bilinear pairing for safer and more effective one.Based on the proposed aggregate signcryption security model,investigation and analysis on the presented scheme with random oracle model is performed and validation on its effectiveness and feasibility also conducted.Theoretical analysis shows that in the presence of multiple signcrypter it owns not only the confidentiality and unforgeability but also higher computational efficiency.

certificateless aggregate signcryption;random oracle model;without bilinear pairing;discrete logarithm problem

2016-09-01

2016-12-07 網絡出版時間：2017-07-05

國家自然科學基金資助項目(61073188)

王夢殊(1993-)，女，碩士研究生，研究方向為網絡與信息安全；祁正華，副教授，博士研究生，研究方向為網絡與信息安全。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170705.1651.048.html

TP301

A

1673-629X(2017)08-0115-06

10.3969/j.issn.1673-629X.2017.08.024