王夢(mèng)殊,祁正華
(南京郵電大學(xué) 計(jì)算機(jī)學(xué)院,江蘇 南京 210003)
無(wú)雙線性對(duì)的無(wú)證書(shū)聚合簽密方案
王夢(mèng)殊,祁正華
(南京郵電大學(xué) 計(jì)算機(jī)學(xué)院,江蘇 南京 210003)
無(wú)證書(shū)聚合簽密是把多個(gè)用戶(hù)對(duì)不同消息產(chǎn)生的不同簽密聚合成一個(gè)簽密,不僅保證信息傳輸?shù)臋C(jī)密性和認(rèn)證性,而且降低了信息傳輸?shù)墓?,因此?yīng)用于大規(guī)模分布式通信中的多對(duì)一模式。聚合簽密方案大多需要進(jìn)行雙線性對(duì)運(yùn)算,效率不高。為此,提出了一種高效的無(wú)線性對(duì)的無(wú)證書(shū)聚合簽密方案。該方案在隨機(jī)預(yù)言模型下應(yīng)用離散對(duì)數(shù),對(duì)原有的無(wú)雙線性對(duì)聚合簽名算法進(jìn)行了改進(jìn),形成了更為安全、高效的聚合簽密方案?;谒岢龅木酆虾灻芊桨赴踩P?,分析研究了隨機(jī)預(yù)言模型下提出方案的不可偽造性和機(jī)密性,并對(duì)其有效性和可行性進(jìn)行了驗(yàn)證。理論分析表明,所提出的方案在多個(gè)簽密者存在的條件下,不僅具有機(jī)密性、不可偽造性,還具有更高的計(jì)算效率。
無(wú)證書(shū)聚合簽密;隨機(jī)預(yù)言模型;無(wú)雙線性對(duì);離散對(duì)數(shù)問(wèn)題
簽密[1]在合理邏輯步驟里同時(shí)完成信息的簽名與伽馬。2009年,Selvi等[2]提出了基于身份的簽密方案,并證明了其安全性。祁正華[3]進(jìn)行了基于身份的簽密方案研究;于剛[4]進(jìn)行了若干簽密研究。聚合簽密能將多個(gè)密文進(jìn)行聚合且提供批量驗(yàn)證,極大降低了信息傳輸?shù)墓?,大幅提升了簽密?yàn)證的效率,適用在大規(guī)模分布式通信的多對(duì)一模式下。Ren等[5]提出了一種可證明安全的聚合簽密方案;蘇愛(ài)東等[6]提出了一種密文長(zhǎng)度固定的聚合簽密方案,但未給出形式化的安全性證明。
無(wú)證書(shū)密碼體制于2003年由Al-Riyami等[7]提出,解決了公鑰證書(shū)管理及驗(yàn)證問(wèn)題和密鑰托管問(wèn)題。Barbosa等[8]提出了無(wú)證書(shū)簽密方案并給出了安全模型。陸海軍[9]和Eslami等[10]在隨機(jī)預(yù)言模型下分別提出了可證明安全的無(wú)證書(shū)聚合簽密方案;Qi等[11]提出了無(wú)證書(shū)環(huán)簽密方案,但是上述簽密方案中用了較多雙線性對(duì)運(yùn)算,因此效率較低。Qi等[12]對(duì)基于身份的聚合簽密進(jìn)行了安全性分析,但使用了雙線性對(duì)。周彥偉等[13]提出的無(wú)證書(shū)聚合簽名方案運(yùn)算量小,無(wú)需進(jìn)行雙線性運(yùn)算,因此參考其無(wú)雙線性對(duì)的特點(diǎn),提出了無(wú)雙線性對(duì)的無(wú)證書(shū)聚合簽密方案并進(jìn)行了理論分析。
1.1 離散對(duì)數(shù)問(wèn)題
離散對(duì)數(shù)問(wèn)題(Discrete Logarithm Problem,DLP):設(shè)G是q階循環(huán)群,q為素?cái)?shù)。給定兩個(gè)元素P,Q∈G,找到使Q=nP成立的整數(shù)n。
1.2 聚合簽密方案的安全模型
文獻(xiàn)[4]定義的安全模型,無(wú)證書(shū)聚合簽密方案將面臨A1和A2兩類(lèi)敵手的攻擊。
A1類(lèi)敵手不知道系統(tǒng)的主密鑰,但可以進(jìn)行公鑰替換操作,或利用所有用戶(hù)的公鑰來(lái)對(duì)系統(tǒng)主密鑰進(jìn)行攻擊,因此A1類(lèi)敵手為惡意用戶(hù)。A2類(lèi)敵手已知系統(tǒng)主密鑰,具有計(jì)算所有用戶(hù)部分公鑰私鑰的能力,但不可以替換用戶(hù)公鑰,因此A2類(lèi)敵手為惡意的KGC。
選擇密文攻擊下的機(jī)密性和適應(yīng)性,選擇消息攻擊下的不可偽造性。方案機(jī)密性證明中,U1是A1類(lèi)敵手的挑戰(zhàn)者,U2是A2類(lèi)敵手的挑戰(zhàn)者,不可偽造性證明中,T1是A1類(lèi)敵手的挑戰(zhàn)者,T2是A2類(lèi)敵手的挑戰(zhàn)者。文獻(xiàn)[14]詳細(xì)介紹了無(wú)證書(shū)聚合簽密方案在A1和A2兩類(lèi)敵手適應(yīng)性選擇消息攻擊下不可偽造性的定義及相應(yīng)游戲,不再敘述。
定義1:類(lèi)型A1攻擊下的密文機(jī)密性。類(lèi)型A1的攻擊者不能在多項(xiàng)式時(shí)間內(nèi),以不可忽略的優(yōu)勢(shì)贏得以下博弈,則該簽密方案在選擇密文攻擊下具有不可區(qū)分性。
SETUP:挑戰(zhàn)者U1將生成的系統(tǒng)公共參數(shù)發(fā)送給敵手A1并保存系統(tǒng)主密鑰。
第一階段:敵手能夠多項(xiàng)式次執(zhí)行的詢(xún)問(wèn)如下:
部分密鑰生成問(wèn)詢(xún):A1輸入(IDi,Xi)進(jìn)行問(wèn)詢(xún),就可得到(yi,Yi)。
私鑰生成問(wèn)詢(xún):A1輸入IDi問(wèn)詢(xún),得到SKi=(xi,yi)。
簽密問(wèn)詢(xún):A1輸入(IDi,mi,IDB)問(wèn)詢(xún),得到:
δi=(V,Vi,Si,Wi)=Signcryption(IDi,mi,IDB)
解簽密問(wèn)詢(xún):A1輸入簽密δi和身份(IDi,IDB)問(wèn)詢(xún),U1可進(jìn)行解簽密,將解簽密結(jié)果返回A1。
挑戰(zhàn)階段:A1選擇要挑戰(zhàn)的兩個(gè)明文mi(i∈{0,1})和兩個(gè)身份IDi,IDB,不能在第一階段詢(xún)問(wèn)IDB的私鑰。U1選擇一個(gè)隨機(jī)的比特b,計(jì)算δ*=Signcryption(mb,IDi,IDB),將δ*發(fā)送A1。
第二階段:類(lèi)似于第一階段,A1能夠多項(xiàng)式次執(zhí)行詢(xún)問(wèn),并且不能詢(xún)問(wèn)用戶(hù)IDB私鑰或?qū)Ζ?進(jìn)行解簽密詢(xún)問(wèn)。
猜測(cè)階段:最后A1提交一個(gè)比特b',若b'=b,那么A1在此游戲中獲勝。游戲中敵手的優(yōu)勢(shì)為Adv[A1]=|Pr[b'-b]-0.5|。
定義2:類(lèi)型A2攻擊下的密文機(jī)密性。類(lèi)型A2的攻擊者不能在多項(xiàng)式時(shí)間內(nèi),以不可忽略的優(yōu)勢(shì)贏得以下博弈,則該簽密方案在選擇密文攻擊下具有不可區(qū)分性[15]。
SETUP:挑戰(zhàn)者U2將生成的系統(tǒng)公共參數(shù)發(fā)送給敵手A2并保存系統(tǒng)主密鑰。
第一階段:敵手可適應(yīng)性地進(jìn)行以下多項(xiàng)式數(shù)量級(jí)的詢(xún)問(wèn):部分密鑰生成問(wèn)詢(xún)、私鑰生成問(wèn)詢(xún)、簽密問(wèn)詢(xún)、解簽密問(wèn)詢(xún)與定義1的問(wèn)詢(xún)一樣,由A1問(wèn)詢(xún)變成A2問(wèn)詢(xún),但不進(jìn)行公鑰替換詢(xún)問(wèn)。
第二階段:類(lèi)似于第一階段,A2能夠多項(xiàng)式次執(zhí)行詢(xún)問(wèn),并且不能詢(xún)問(wèn)用戶(hù)IDB的私鑰或?qū)Ζ?進(jìn)行解簽密詢(xún)問(wèn)。
猜測(cè)階段與定義1中類(lèi)似,最終A2獲勝。
無(wú)證書(shū)聚合簽密由7個(gè)算法組成,分別是系統(tǒng)初始化、用戶(hù)密鑰設(shè)置、部分私鑰提取、簽密、聚合簽密和聚合解簽密。
用戶(hù)密鑰設(shè)置:用戶(hù)ui隨機(jī)選取秘密值xi,計(jì)算公開(kāi)參數(shù)Xi=xiP。
簽密:用戶(hù)ui對(duì)發(fā)送給IDB的消息mi簽密如下:
(2)計(jì)算hi2=H2(IDi‖mi,V,Zi);
(3)計(jì)算Ti=H3(Vi,IDB,V,aiXB);
(4)計(jì)算Wi=Ti⊕(mi‖IDi),Si=ai+(xi+yi)hi2。這樣δi=(V,Vi,Si,Wi)為ui對(duì)IDB消息mi的簽密。
解簽密:IDB對(duì)ui發(fā)送的簽密δi=(V,Vi,Si,Wi)的解簽密步驟如下:
(1)計(jì)算Ti=H3(Vi,IDB,V,xBVi),IDi‖mi=Wi⊕Ti;
(2)計(jì)算Zi=ai(YB+Ppubhi1)=yBVi,hi1=H1(IDi,Xi,Yi),hi2=H2(IDi‖mi,V,Zi);
(3)根據(jù)等式SiP=Vi+(Xi+Yi+Ppubhi1)hi2進(jìn)行檢測(cè),若正確輸出對(duì)應(yīng)消息mi‖IDi,否則驗(yàn)證失敗。
(1)計(jì)算Ti=H3(Vi,IDB,V,xBVi),IDi‖mi=Wi⊕Ti;
(2)計(jì)算Zi=ai(YB+Ppubhi1)=yBVi;
3.1 正確性
方案的正確性證明如下:
通過(guò)SiP=Vi+(Xi+Yi+Ppubhi1)hi2對(duì)簽密進(jìn)行驗(yàn)證:
3.2 安全性
詢(xún)問(wèn)階段:敵手A1進(jìn)行下述詢(xún)問(wèn):
H1查詢(xún):當(dāng)A1向預(yù)言機(jī)H1詢(xún)問(wèn)H1(IDi,Xi,Yi)時(shí),T1進(jìn)行下述操作:
①如果列表L1中存在相應(yīng)的元組
H2查詢(xún):當(dāng)A1向預(yù)言機(jī)H2詢(xún)問(wèn)H2(IDi‖mi,V,Zi)時(shí),T1進(jìn)行下述操作:
①如果列表L2中存在相應(yīng)元組
H3查詢(xún):當(dāng)A1向預(yù)言機(jī)H3詢(xún)問(wèn)H3(Vi,IDB,V,aiXB)時(shí),T1進(jìn)行下述操作:
①如果列表L3中存在相應(yīng)的元組
部分密鑰生成詢(xún)問(wèn):當(dāng)A1要對(duì)IDi和公開(kāi)參數(shù)Xi進(jìn)行部分密鑰生成詢(xún)問(wèn)時(shí),T1進(jìn)行如下操作:
①若Lk中存在相應(yīng)元組
私鑰生成詢(xún)問(wèn):當(dāng)A1要對(duì)IDi的私鑰生成執(zhí)行問(wèn)詢(xún)時(shí),T1進(jìn)行如下操作:
①如果列表Lsk中存在元組
公鑰生成詢(xún)問(wèn):當(dāng)A1要對(duì)身份IDi的公鑰生成執(zhí)行詢(xún)問(wèn)時(shí),T1進(jìn)行下述操作:
①如果Lpk中存在元組
簽密詢(xún)問(wèn):當(dāng)T1收到A1關(guān)于發(fā)送方身份、消息、接收方身份
①如果IDi=IDj,則T1放棄,終止模擬;
聚合簽密詢(xún)問(wèn):當(dāng)T1收到A1關(guān)于發(fā)送方身份、消息、接收方身份
②否則T1棄權(quán),停止模擬。
解簽密問(wèn)詢(xún):當(dāng)T1收到A1關(guān)于發(fā)送者身份、接收者身份、簽密
①倘若L1中存在IDi所對(duì)應(yīng)的元組且IDi≠I(mǎi)Dj,按照解簽密算法進(jìn)行解密,并驗(yàn)證SiP=Vi+(Xi+Yi+Ppubhi1)hi2是否成立,若成立T1返回1給A1,否則返回0;
②如果L1中存在IDi所對(duì)應(yīng)的元組且IDi=IDj,則當(dāng)L2中存在IDi相對(duì)應(yīng)的元組
③如果L1中不存在IDi所對(duì)應(yīng)的元組,則當(dāng)L2中存在IDi對(duì)應(yīng)的元組
①如果對(duì)于所有的IDi(1≤i≤n),都有IDi≠I(mǎi)Dj,就將模擬中止。
①如果成立,則T1輸出
作為離散對(duì)數(shù)問(wèn)題的有效解;
②否則,T1沒(méi)有解決離散對(duì)數(shù)問(wèn)題。
詢(xún)問(wèn):敵手A2對(duì)預(yù)言機(jī)H1,H2,H3,私鑰生成,公鑰生成,簽密和解簽密的詢(xún)問(wèn)過(guò)程與引理1相同。
部分密鑰生成詢(xún)問(wèn):當(dāng)A2執(zhí)行對(duì)IDi和公開(kāi)參數(shù)Xi的部分密鑰生成詢(xún)問(wèn)時(shí),T1進(jìn)行如下操作:
①如果列表Lk中存在相應(yīng)元組
解簽密問(wèn)詢(xún):當(dāng)T2收到A2關(guān)于發(fā)送者身份,接收者身份,簽密
①若L1中存在IDi對(duì)應(yīng)的元組且IDi≠I(mǎi)Dj,則按解簽密算法進(jìn)行解密,并驗(yàn)證SiP=Vi+(Xi+Yi+Ppubhi1)hi2是否成立,如果成立,則T2返回1給A2,否則返回0。
②如果L1中存在IDi所對(duì)應(yīng)的元組且IDi=IDj,則當(dāng)L2中存在IDi相對(duì)應(yīng)的元組
①如果對(duì)所有IDi都有IDi≠I(mǎi)Dj,終止模擬。
如果等式成立,則T2輸出:
作為離散對(duì)數(shù)問(wèn)題的有效解;否則,T2沒(méi)有解決離散對(duì)數(shù)問(wèn)題。
引理3:在隨機(jī)預(yù)言模型下,若不存在任何多項(xiàng)式數(shù)量級(jí)的敵手A1在下面的游戲中能以不可忽略?xún)?yōu)勢(shì)獲勝,那么稱(chēng)該方案具有機(jī)密性。
詢(xún)問(wèn):敵手A1詢(xún)問(wèn)過(guò)程與引理1相似。
第一階段,A1或許產(chǎn)生兩個(gè)長(zhǎng)度相等的消息mi0,mi1來(lái)接受挑戰(zhàn)。隨機(jī)選擇并通過(guò)執(zhí)行簽密算法獲得ui對(duì)發(fā)送給IDB的關(guān)于消息mib的簽密和聚合簽密{δi,δ},返回δ*給敵手A1。
結(jié)束時(shí),猜想A1被返回,若等式成立,則輸出1;否則,輸出0。由于敵手A1不能進(jìn)行解簽密詢(xún)問(wèn),應(yīng)用
引理4:在隨機(jī)預(yù)言模型下,若不存在任何多項(xiàng)式數(shù)量級(jí)的敵手A2在下面的游戲中能以不可忽略?xún)?yōu)勢(shì)獲勝,那么稱(chēng)該方案具有機(jī)密性。
詢(xún)問(wèn):敵手A2詢(xún)問(wèn)過(guò)程與引理2相似。
在第一階段和第二階段與引理3模擬類(lèi)似,不同的是這里Zi=yBVi,yB是接收者的部分密鑰,并且yB=b+shi1,YB=bP,Zi=ai(YB+Ppubhi1)=yBVi,則有b=(Vi)-1ai(YB+Ppubhi1)-shi1。由于離散對(duì)數(shù)問(wèn)題中計(jì)算n是困難的,因此已知Zi和Vi求取b也是困難的。
3.3 效率分析
表1是上述方案與文獻(xiàn)[6,9,17-18]的簽密方案進(jìn)行性能比較的結(jié)果。耗時(shí)比較大的計(jì)算主要有雙線性對(duì)運(yùn)算、冪運(yùn)算和數(shù)乘運(yùn)算,d表示雙線性運(yùn)算,h表示指數(shù)運(yùn)算,t代表G上的點(diǎn)乘運(yùn)(由于其他方案都使用了雙線性運(yùn)算,因此將群G記為G1,G2,G2為G1的雙線性映射)。
表1 簽密方案運(yùn)算量比較
表1分析了5種聚合簽密方案的運(yùn)算量,點(diǎn)乘運(yùn)算對(duì)比對(duì)運(yùn)算和指數(shù)運(yùn)算耗時(shí)少許多。文中方案簽密者只需2次點(diǎn)乘運(yùn)算,而文獻(xiàn)[9,17-18]都需要進(jìn)行雙線性對(duì)運(yùn)算,文獻(xiàn)[9]在簽密時(shí)運(yùn)算量較小,但解簽密時(shí)高于文中方案。文獻(xiàn)[6]的指數(shù)運(yùn)算較大,且其在解簽密階段比文中方案多了許多雙線性運(yùn)算和指數(shù)運(yùn)算。因此文中方案較為高效。
為提高無(wú)證書(shū)聚合簽名和無(wú)證書(shū)簽密方案的有效性和安全性,在隨機(jī)預(yù)言模型具有可證安全性的基礎(chǔ)上,提出了無(wú)雙線性對(duì)的聚合簽密方案。該方案基于離散對(duì)數(shù)難題,避免了雙線性對(duì)運(yùn)算。由于離散對(duì)數(shù)難題至今未能解決,因此該方案更為安全可靠。在簽密者人數(shù)不止一個(gè)的情況下,提高了簽密和解簽密的計(jì)算效率。
[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].南京:南京郵電大學(xué),2012.
[4] 于 剛.若干簽密方案研究[D].鄭州:解放軍信息工程大學(xué),2012.
[5] Ren Xunyi,Qi Zhenghua,Yang Geng.Provably secure aggregate signcryption scheme[J].ETRI Journal,2012,34(3):421-428.
[6] 蘇愛(ài)東,張永翼.密文長(zhǎng)度固定的全聚合簽密方案[J].計(jì)算機(jī)應(yīng)用研究,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].杭州:杭州師范大學(xué),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] 周彥偉,楊 波,張文政.高效可證安全的無(wú)證書(shū)聚合簽名方案[J].軟件學(xué)報(bào),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] 高鍵鑫,吳曉平,秦艷琳,等.無(wú)雙線性對(duì)的無(wú)證書(shū)安全簽密方案[J].計(jì)算機(jī)應(yīng)用研究,2014,31(4):1195-1198.
[16] 王大星,騰濟(jì)凱.可證明安全的基于身份的聚合簽密方案[J].計(jì)算機(jī)應(yīng)用,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 網(wǎng)絡(luò)出版時(shí)間:2017-07-05
國(guó)家自然科學(xué)基金資助項(xiàng)目(61073188)
王夢(mèng)殊(1993-),女,碩士研究生,研究方向?yàn)榫W(wǎng)絡(luò)與信息安全;祁正華,副教授,博士研究生,研究方向?yàn)榫W(wǎng)絡(luò)與信息安全。
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