徐國(guó)愚，王穎鋒，馬小飛，王科鋒，顏若愚

(河南財(cái)經(jīng)政法大學(xué) 計(jì)算機(jī)與信息工程學(xué)院，鄭州 450002)

(*通信作者電子郵箱toxuguoyu@sohu.com)

面向分級(jí)身份密碼批驗(yàn)簽的錯(cuò)誤簽名混合篩選算法

徐國(guó)愚*，王穎鋒，馬小飛，王科鋒，顏若愚

(河南財(cái)經(jīng)政法大學(xué) 計(jì)算機(jī)與信息工程學(xué)院，鄭州 450002)

(*通信作者電子郵箱toxuguoyu@sohu.com)

針對(duì)分級(jí)身份密碼(HIBC)批驗(yàn)簽過(guò)程中的錯(cuò)誤簽名快速識(shí)別問(wèn)題，設(shè)計(jì)實(shí)現(xiàn)了一種錯(cuò)誤簽名混合篩選算法。針對(duì)HIBC簽名算法不完全聚合的特點(diǎn)，首先將所有簽名作為樹(shù)葉構(gòu)造平衡二叉樹(shù)，然后通過(guò)拆分攻克與指數(shù)測(cè)試方法查找錯(cuò)誤簽名，并且利用計(jì)算中間值的關(guān)聯(lián)性減少計(jì)算開(kāi)銷。算法性能分析表明，當(dāng)批驗(yàn)簽中錯(cuò)誤簽名數(shù)大于2時(shí)，該算法計(jì)算開(kāi)銷低于獨(dú)立測(cè)試、通用折半拆分、指數(shù)測(cè)試以及裁剪搜索算法，能夠有效篩選出HIBC批驗(yàn)簽中的錯(cuò)誤簽名，可以應(yīng)用在云計(jì)算認(rèn)證等應(yīng)用場(chǎng)景中。

批驗(yàn)簽；錯(cuò)誤簽名篩選算法；分級(jí)身份密碼；平衡二叉樹(shù)；云計(jì)算

0 引言

分級(jí)身份密碼機(jī)制(Hierarchical Identity Based Cryptography， HIBC)具有標(biāo)識(shí)產(chǎn)生公鑰、密鑰分級(jí)派生等特點(diǎn)，被廣泛應(yīng)用在云計(jì)算、延遲容忍網(wǎng)絡(luò)等環(huán)境中[1-3]。HIBC批驗(yàn)簽機(jī)制是指驗(yàn)簽者能夠?qū)Χ鄠€(gè)簽名者的HIBC簽名進(jìn)行批量驗(yàn)簽，其效率優(yōu)于對(duì)其單獨(dú)驗(yàn)簽[4-6]。但是當(dāng)批驗(yàn)簽中存在錯(cuò)誤簽名時(shí)，將使得批驗(yàn)簽失敗，例如惡意節(jié)點(diǎn)發(fā)送虛假簽名，因此需要采用錯(cuò)誤簽名篩選機(jī)制將錯(cuò)誤簽名快速篩選出來(lái)。

目前，針對(duì)批驗(yàn)簽的錯(cuò)誤簽名篩選方法大致可以分為三類：拆分攻克方法[7]、指數(shù)測(cè)試方法[8]以及混合測(cè)試方法[9]。2010年，Matt[10]提出了一種混合測(cè)試算法——裁剪搜索(Triple Pruning Search， TPS)算法，分析表明TPS算法相對(duì)其他算法具有更高的運(yùn)算效率。但是，TPS方法僅考慮了完全聚合的批驗(yàn)簽方案，當(dāng)將其應(yīng)用到不完全聚合的HIBC批驗(yàn)簽算法時(shí)，未能利用過(guò)程數(shù)值的重復(fù)可用性降低計(jì)算開(kāi)銷。本文針對(duì)上述問(wèn)題，提出一種面向HIBC批驗(yàn)簽的錯(cuò)誤簽名混合篩選算法(TPS for HIBC, TPSH)，在TPS算法的基礎(chǔ)上，利用先前計(jì)算數(shù)值參與后續(xù)計(jì)算步驟，從而進(jìn)一步減少計(jì)算開(kāi)銷。為方便描述，本文以文獻(xiàn)[5]中的HIBC批驗(yàn)簽算法為例，對(duì)該TPSH算法進(jìn)行描述。同時(shí)，本文算法僅需要少量改動(dòng)即可應(yīng)用于其他基于雙線性對(duì)的批驗(yàn)簽算法中[11-12]。

1 HIBC批驗(yàn)簽算法簡(jiǎn)介

文獻(xiàn)[5]設(shè)計(jì)實(shí)現(xiàn)了一種HIBC批驗(yàn)簽算法，能夠?qū)IBC簽名進(jìn)行批驗(yàn)證，減少計(jì)算開(kāi)銷。算法包括初始化、私鑰生成、簽名、驗(yàn)簽及批驗(yàn)簽5個(gè)部分。

令W=Pm+mPm′，隨機(jī)選取s∈Zp，計(jì)算簽名為σ=(S1,S2)，其中：

(2)

4)驗(yàn)簽。驗(yàn)簽方收到簽名σ后通過(guò)式(3)進(jìn)行驗(yàn)證：

(3)

5)批驗(yàn)簽。令n個(gè)消息m1,m2,…,mn的簽名為σ1,σ2,…,σn，其中σi=(Si,1,Si,2)。隨機(jī)選取(δ1,δ2,…,δn)∈Zp，通過(guò)式(4)對(duì)所有簽名進(jìn)行批驗(yàn)簽：

可以看出，對(duì)n個(gè)簽名進(jìn)行獨(dú)立驗(yàn)簽時(shí)需要2n次雙線性對(duì)運(yùn)算，而進(jìn)行批驗(yàn)簽時(shí)僅需n+1次，能夠減少n-1次雙線性對(duì)運(yùn)算。但是采用批驗(yàn)簽算法所面臨的一個(gè)問(wèn)題是，當(dāng)批驗(yàn)簽的簽名中存在錯(cuò)誤簽名時(shí)，將使得批驗(yàn)簽失敗。因此，本文采用TPSH算法將其中的錯(cuò)誤簽名快速篩選出來(lái)。

2 TPSH算法

TPSH算法的基本過(guò)程是將所有簽名作為樹(shù)葉構(gòu)造平衡二叉樹(shù)，利用拆分攻克與指數(shù)測(cè)試方法，測(cè)試整個(gè)樹(shù)中是否存在錯(cuò)誤簽名數(shù)小于3的子樹(shù)，若找到則返回該子樹(shù)中所有錯(cuò)誤簽名的位置，之后繼續(xù)在樹(shù)中尋找錯(cuò)誤簽名數(shù)小于3的子樹(shù)直到找出所有的錯(cuò)誤簽名。同時(shí)，算法利用相關(guān)計(jì)算中間值的關(guān)聯(lián)性，優(yōu)化計(jì)算過(guò)程，減少計(jì)算開(kāi)銷。

為了能夠?qū)ι鲜鯤IBC批驗(yàn)簽算法進(jìn)行拆分攻克與指數(shù)測(cè)試，首先將HIBC批驗(yàn)簽式(4)轉(zhuǎn)化成式(5)：

(5)

可以看出當(dāng)A=1時(shí)，式(5)等于式(4)。相應(yīng)的定義Ai為n個(gè)簽名中第i個(gè)簽名的獨(dú)立驗(yàn)證公式，如式(6)所示。當(dāng)Ai=1時(shí)，說(shuō)明第i個(gè)簽名正確：

Ai=e(Bi,-P)·Ei

(6)

在式(6)的基礎(chǔ)上定義函數(shù)aj,[X]，如式(7)所示，其中：0≤j≤2，X表示樹(shù)或者子樹(shù)，Low(X)為X中最左側(cè)葉子節(jié)點(diǎn)的序號(hào)，up(X)為X中最右側(cè)葉子節(jié)點(diǎn)的序號(hào)。在樹(shù)中，定義右側(cè)葉子節(jié)點(diǎn)序號(hào)總是大于左側(cè)葉子節(jié)點(diǎn)序號(hào)。函數(shù)aj,[X]將用于錯(cuò)誤簽名驗(yàn)證中的計(jì)算。當(dāng)j=0且X為所有簽名構(gòu)成的樹(shù)時(shí)，aj,[X]=A。

(7)

TPSH的具體驗(yàn)證過(guò)程如算法1所示，其流程與TPS相類似，不同之處在于H_Get0函數(shù)、H_Get1函數(shù)、H_Get2函數(shù)以及TPSHQuadSolver函數(shù)的實(shí)現(xiàn)方法。

算法1TPSH算法。

輸入:X

//X是消息與簽名列表 輸出:錯(cuò)誤簽名列表。

1)

if(X=Tr) then

//X為樹(shù)節(jié)點(diǎn)

2)

a0,[X]=H_Get0(X)

3)

if(a0,[X]=1) then return

4)

a1,[X]=H_Get1(X)

5)

z=Shanks(X)

6)

ifz≠0 then

7)

print(mz,sz)

8)

return

9)

a2,[X]=H_Get2(X)

10)

(z1,z2)=FastFactor(X)

11)

if(z1≠0) then

12)

Print(mz1,sz1),(mz2,sz2)

13)

return

14)

(SearchLeft,SearchRight)=

TPSHQuadSolver(X,Left(X),Right(X),E[X])

//錯(cuò)誤簽名數(shù)≥3,進(jìn)入子樹(shù)查找

15)

if (SearchLeft=true) then

16)

TPSH(Left(X))

17)

if (SearchRight=true) then

18)

TPSH(Right(X))

19)

if (X=Tr) then

20)

PrintList()

21)

return

在算法1中，首先進(jìn)行初始化批驗(yàn)簽第2)～3)行，通過(guò)H_Get0函數(shù)計(jì)算a0,[Tr]，Tr表示所有簽名所組成的樹(shù)，并且保存中間相關(guān)計(jì)算變量供后續(xù)計(jì)算使用。由式(7)可得式(8)：

若a0,[Tr]=1則說(shuō)明所有簽名均正確，否則說(shuō)明樹(shù)中的錯(cuò)誤簽名總數(shù)(簡(jiǎn)記為w)大于0。

算法2H_Get0(X)。

輸入:X

//X是消息與簽名對(duì)列表 輸出：a0,[X]的值。

1)

if(X=Tr)then

//X為根節(jié)點(diǎn)

2)

VB0|X|=B|X|//Bi的定義見(jiàn)式(5)，需要保存在緩存中

3)

fori=|X|-1downto1do

4)

5)

forj=|X|downto1do

6)

Ej=e(Dj,Tj)e(P1,P2) //計(jì)算Ei，其中e(P1,P2)為固定值，可提前計(jì)算

7)

EB0|X|=E|X|

8)

fori=|X|-1downto1do

9)

10)

11)

return(ɑ0,[X]) //第1)～11)行測(cè)試的是樹(shù)，返回a0,[Tr]的結(jié)果，

//如果是1，則說(shuō)明正確，無(wú)錯(cuò)誤簽名。

12)

P=Parent(X);L=Left(P);R=Right(P)

//X為子樹(shù),定義P為X的父親節(jié)點(diǎn)，P的相關(guān)數(shù)值已提

//前計(jì)算并保存，L為P的左孩子節(jié)點(diǎn)，R為P的右孩子節(jié)點(diǎn)

13)

if(X=R)then

//X為P的右子樹(shù)

14)

a0,[X]=a0,[P]·a-10,[L]//利用a0,[P],a-10,[L]可直接獲得a0,[X]

15)

a-10,[X]=a-10,[P]a0,[L]

//保存a-10,[X]供后續(xù)計(jì)算使用

16)

return(ɑ0,[R])

17)

elseif(X=L)then

//X為P的左子樹(shù)

18)

s=lowbnd(X);u=upbnd(X)

19)

WB0s,u=VB01-VB0u+1

20)

FB0s,u=EB01·EB0-1u+1

21)

if(s≠1)then

22)

if(WB01,s-1) then

//如果WB01,s-1已經(jīng)計(jì)算過(guò)

23)

WB0s,u=WB0s,u-WB01,s-1

24)

else

25)

WB01,s-1=VB01-VB0s

26)

WB0s,u=WB0s,u-WB01,s-1

27)

if(FB01,s-1) then

//如果FB01,s-1已經(jīng)計(jì)算過(guò)

28)

FB0s,u=FB0s,u·FB0-11,s-1

29)

else

30)

FB01,s-1=EB01·EB0-1s

31)

FB0s,u=FB0s,u·FB0-11,s-1

32)

a0,[X]=e(WB0s,u,-P)·FB0s,u

//計(jì)算出ɑ0,[X]

33)

if(a0,[X]=a0,[P])then

34)

a0,[X]=a-10,[P]

35)

return(ɑ0,[X])

算法3為H_Get1的實(shí)現(xiàn)算法，用于計(jì)算a1,[X]。1)～9)行用于計(jì)算a1,[Tr]，由于Ei值在計(jì)算a0,[Tr]中已經(jīng)計(jì)算，并將相關(guān)值保存在EB0i中，所以避免了重新計(jì)算Ei所帶來(lái)的雙線性對(duì)運(yùn)算，計(jì)算a1,[X]僅需一次雙線性對(duì)運(yùn)算。10)～37)行用于在TPSHQuadSolver函數(shù)中計(jì)算子樹(shù)中的a1,[X]值，其方法與函數(shù)H_Get0中類似。另外，函數(shù)H_Get2用于計(jì)算a2,[X]，其過(guò)程與函數(shù)H_Get1類似，在本文中不再描述。

算法3H_Get1(X)。

輸入:X，表示消息與簽名對(duì)列表。 輸出:a1,[X]的值。

1)

if(X=Tr)then

//X為根節(jié)點(diǎn)，需要計(jì)算a0,[Tr]

2)

VB1|X|=VB0|X|

//VB0i值見(jiàn)H_Get0

3)

fori=|X|-1downto1do

4)

VB1i=VB1i+1+VB0i

5)

EB1|X|=EB0|X|

//EB0i值見(jiàn)H_Get0

6)

forj=|X|-1to1do

7)

EB1j=EB1j+1·EB0j

8)

a1,[X]=e(VB11,-P)·EB1j

9)

return(ɑ1,[X])

10)

P=Parent(X);L=Left(P);R=Right(P);X′=Sibling(X) //X為子樹(shù),定義P為X的父親節(jié)點(diǎn)，P的相關(guān)數(shù)值已提前

//計(jì)算并保存，L為P的左孩子節(jié)點(diǎn)，R為P的右孩子節(jié)點(diǎn)，

//X′為X的兄弟節(jié)點(diǎn)

11)

if(a0,[X]=a0,[P])then//P中的錯(cuò)誤簽名全部在X中，且w>1

12)

a1,[X]=a1,[P]

13)

a-11,[X]=a-11,[P]

14)

return(a1,[R])

15)

if (X=R)then

//右孩子節(jié)點(diǎn)

16)

a1,[X]=a1,[P]·a-11,[L]

17)

a-11,[X]=a-11,[P]a1,[L]

18)

return(a1,[R])

19)

elseif(X=L)then

//左孩子節(jié)點(diǎn)

20)

s=lowbnd(X);u=upbnd(X)

21)

WB1s,u=VB11-(VB1u+1+u·VB0u+1)

22)

FB1s,u=EB11·EB1-1u+1

23)

if(s≠1)then

24)

if(WB11,s-1)then

//如果WB11,s-1已經(jīng)計(jì)算過(guò)

25)

WB1s,u=WB1s,u-WB11,s-1

26)

else

27)

WB11,s-1=VB11-(VB1s+(s-1)VB0s)

28)

WB1s,u=WB1s,u-WB11,s-1

29)

if(FB11,s-1)then

30)

FB1s,u=FB1s,u·FB1-11,s-1

31)

else

32)

FB11,s-1=EB11·EB1-1s

33)

FB1s,u=FB1s,u·FB1-11,s-1

34)

a1,[X]=e(WB1s,u,-P)·FB1s,u//計(jì)算出a1,[X]

35)

if(a1,[X]=a1,[P])then

36)

a1,[X]=a-11,[P]

37)

return(a1,[X])

相對(duì)于原始的TPS算法而言，TPSH在計(jì)算aj,[X]時(shí)，利用Ei等中間值參與計(jì)算，并通過(guò)輕量級(jí)GT域上的乘法運(yùn)算代替復(fù)雜雙線性對(duì)運(yùn)算，減少了aj,[X]的計(jì)算開(kāi)銷，提高了計(jì)算效率。

3 算法分析與比較

本章將對(duì)算法效率與安全性進(jìn)行分析與比較。首先對(duì)TPSH算法的效率進(jìn)行分析與比較。為方便比較，令|Tr|表示所有進(jìn)行批驗(yàn)證的簽名數(shù)量，TA表示G上的加法運(yùn)算，TT表示GT上的乘法運(yùn)算，TP表示雙線性對(duì)運(yùn)算。

TPSH要求初始化批驗(yàn)簽時(shí)，采用小指數(shù)測(cè)試方法。首先包括測(cè)試簽名樹(shù)Tr中所有簽名元素是否在G中，接著計(jì)算a0,[Tr]。如果a0,[Tr]=1，則說(shuō)明所有簽名正確；如果a0,[Tr]≠1，則將計(jì)算中的所有Bi及Ei的相關(guān)計(jì)算變量VB0i，EB0i保存。另外，調(diào)用H_Get1計(jì)算a1,[Tr]及調(diào)用H_Get2計(jì)算a2,[Tr]的開(kāi)銷均為:|Tr|·(TA+TT)+TP。

下面給出篩選錯(cuò)誤簽名的具體開(kāi)銷。

將本文的TPSH算法與獨(dú)立測(cè)試、通用折半拆分(GeneralizedBinarySplitting，GBS)算法[13]、指數(shù)測(cè)試算法[8]以及TPS算法[10]進(jìn)行比較：獨(dú)立測(cè)試表示對(duì)各簽名依次進(jìn)行測(cè)試，為基準(zhǔn)測(cè)試方案；GBS算法屬于組測(cè)試技術(shù)，當(dāng)錯(cuò)誤簽名數(shù)較小時(shí)，該算法的性能優(yōu)于其他組測(cè)試技術(shù)。由于該算法需要在運(yùn)算前給出錯(cuò)誤簽名w的估計(jì)值dw，估計(jì)值dw的正確性將影響算法的計(jì)算性能，在此處取GBS算法的最優(yōu)值，即令錯(cuò)誤簽名值估計(jì)值與實(shí)際值一致(dw=w)；指數(shù)測(cè)試方法通過(guò)在算法中增加指數(shù)，能夠快速定位錯(cuò)誤簽名位置；TPS算法為T(mén)PSH的原始未改進(jìn)方案。

依據(jù)文獻(xiàn)[14]統(tǒng)計(jì)各操作的開(kāi)銷，令群的階r為160 b，橢圓曲線E定義在域Fp上，p為160 b。在計(jì)算比較中，以域Fp上的乘法運(yùn)算為單位(簡(jiǎn)記為t)，并且采用雙線性對(duì)成對(duì)運(yùn)算(double pairing)，各項(xiàng)密碼的平均單次計(jì)算時(shí)間分別為：TP=7 013t，TT=15t，TA=11t。

性能分析主要比較在不同批驗(yàn)簽與錯(cuò)誤簽名數(shù)量的情況下，各方案的單次平均計(jì)算開(kāi)銷，分析比較結(jié)果如圖1所示。

圖1 算法單次平均計(jì)算開(kāi)銷的比較

在圖1(a)中，設(shè)置一次批驗(yàn)簽的簽名數(shù)量n=8?？梢钥闯觯寒?dāng)錯(cuò)誤簽名總數(shù)w=2，TPSH算法的單次平均計(jì)算開(kāi)銷與指數(shù)測(cè)試算法及TPS算法大體相同，其主要原因是當(dāng)w<3時(shí)，3種算法均使用相同的指數(shù)測(cè)試方法。但是當(dāng)w≥3時(shí)，TPSH的單次平均計(jì)算開(kāi)銷小于上述兩種算法，其原因是：指數(shù)測(cè)試方法的計(jì)算開(kāi)銷隨著w成指數(shù)增長(zhǎng)，所以當(dāng)w≥3后開(kāi)銷上升變快；TPS算法在測(cè)試本文HIBS算法時(shí)，由于未能利用先前雙線性對(duì)計(jì)算數(shù)值參與后續(xù)計(jì)算步驟，從而導(dǎo)致計(jì)算開(kāi)銷增大；而本文的TPSH算法充分考慮HIBS算法的特點(diǎn)，通過(guò)劃分子樹(shù)進(jìn)行指數(shù)測(cè)試，避免了計(jì)算開(kāi)銷的指數(shù)增長(zhǎng)。同時(shí)，通過(guò)相關(guān)計(jì)算中間值的關(guān)聯(lián)性，采用GT乘法運(yùn)算代替雙線性對(duì)運(yùn)算，進(jìn)一步減少了計(jì)算量，因此計(jì)算開(kāi)銷較小。另外，不管錯(cuò)誤簽名總數(shù)w為何值，TPSH算法的計(jì)算開(kāi)銷均小于獨(dú)立測(cè)試及GBS算法。

在圖1(b)中，設(shè)置批驗(yàn)簽的簽名數(shù)量n=16，TPSH算法受簽名數(shù)量n的影響不大，其性能依然優(yōu)于其他算法。另外，可以看出在各算法中，指數(shù)測(cè)試方法受批驗(yàn)簽數(shù)量及錯(cuò)誤簽名數(shù)量的影響最大。綜上所述，TPSH的計(jì)算開(kāi)銷受批驗(yàn)簽數(shù)量及錯(cuò)誤簽名數(shù)量的影響較小,當(dāng)w≥3時(shí)，TPSH的計(jì)算開(kāi)銷小于獨(dú)立測(cè)試、GBS算法、指數(shù)算法以及TPS算法。

在安全性方面，由于本算法主要用于提高HIBC算法中批驗(yàn)簽判斷式的計(jì)算效率，所以其安全性依賴于HIBC批驗(yàn)簽算法自身的安全性。

4 結(jié)語(yǔ)

本文針對(duì)HIBC批驗(yàn)簽中的錯(cuò)誤簽名篩選問(wèn)題，設(shè)計(jì)實(shí)現(xiàn)了一種錯(cuò)誤簽名混合篩選算法TPSH。該算法利用拆分攻克、指數(shù)測(cè)試以及中間值關(guān)聯(lián)特性簡(jiǎn)化了錯(cuò)誤簽名的篩選計(jì)算，與現(xiàn)有的獨(dú)立測(cè)試、GBS算法、指數(shù)算法以及TPS算法相比計(jì)算開(kāi)銷更小。下一步，將研究如何對(duì)TPSH進(jìn)行形式化安全證明以及應(yīng)用TPSH算法提高云計(jì)算的接入認(rèn)證效率。

References)

[1] KALYANI D, SRIDEVI R.Survey on identity based and hierarchical identity based encryption schemes [J].International Journal of Computer Applications, 2016, 134(14): 32-37.

[2] 田俊峰,孫可輝.基于HIBC的云信任分散統(tǒng)一認(rèn)證機(jī)制[J].計(jì)算機(jī)研究與發(fā)展,2015,52(7):16660-16671.(TIAN J F, SUN K H.Trust distributed based authentication mechanism using hierarchical identity based cryptography [J].Journal of Computer Research and Development, 2015, 52(7): 16660-16671.)

[3] FIDA M R, ALI M, ADNAN A, et al.Region based security architecture for DTN [C]// Proceedings of the 2011 Eighth International Conference on Information Technology: New Generations.Piscataway, NJ: IEEE, 2011: 387-392.

[4] ZHU H J, LIN X D, LU R X, et al.An opportunistic batch bundle authentication scheme for energy constrained DTNs [C]// Proceedings of the 2010 IEEE Conference on Computer Communications.Piscataway, NJ: IEEE, 2010: 1-9.

[5] 徐國(guó)愚,陳性元,杜學(xué)繪.大規(guī)模延遲容忍網(wǎng)絡(luò)中基于分級(jí)身份簽名的認(rèn)證方案研究[J].電子與信息學(xué)報(bào),2013,35(11):2615-2622.(XU G Y, CHEN X Y, DU X H.An authentication scheme using hierarchical identity based signature in large-scale delay tolerant networks [J].Journal of Electronics & Information Technology, 2013, 35(11): 2615-2622.)

[6] NOISTERNIG M, HOLLICK M.Efficient solutions for the authenticated fragmentation problem in delay-and disruption-tolerant networks [C]// Proceedings of the 17th ACM International Conference on Modeling, Analysis and Simulation of Wireless and Mobile Systems.New York: ACM, 2014: 177-185.

[7] LAW L, MATT B J.Finding invalid signatures in pairing based batches [C]// Proceedings of the Eleventh IMA International Conference on Cryptography and Coding.Berlin: Springer, 2007: 35-53.

[8] LEE S, CHO S, CHOI J, et al.Batch verification with DSA-type digital signatures for ubiquitous computing [C]// Proceedings of the 2005 International Conference on Computational and Information Science.Berlin: Springer, 2005: 125-130.

[9] MATT B J.Identification of multiple invalid signatures in pairing-based batched signatures [C]// Proceedings of the 2009 International Workshop on Public Key Cryptography.Berlin: Springer, 2009: 337-356.

[10] MATT B J.Identification of multiple invalid pairing-based signatures in constrained batches [C]// Proceedings of the 2010 International Conference on Pairing-Based Cryptography.Berlin: Springer, 2010: 78-95.

[11] WESOLOWSKI M.Batch verification of elliptic curve digital signa-tures [D].Waterloo, Ontario: University of Waterloo, 2015: 51-88.

[12] AKINYELE J A, GREEN M, HOHENBERGER S, et al.Machine-generated algorithms, proofs and software for the batch verification of digital signature schemes [J].Journal of Computer Security, 2014, 22(6): 867-912.

[13] ZAVERUCHA G M, STINSON D R.Group testing and batch verification [C]// Proceedings of the 2009 International Conference on Information Theoretic Security.Berlin: Springer, 2009: 140-157.

[14] GRANGER R, PAGE D, SMART N P.High security pairing-based cryptography revisited [C]// Proceedings of the 2006 International Algorithmic Number Theory Symposium.Berlin: Springer, 2006: 480-494.

This work is partially supported by the National Natural Foundation of China (61602153, U1404605), the Key Project of Science and Technology Research of Henan Provincial Department of Education (15A520044, 14A520079), the Henan Science and Technology Research Project in 2016 (162102210273).

XU Guoyu, born in 1982, Ph.D., lecturer.His research interests include security protocol, cloud computing authentication.

WANG Yingfeng, born in 1976, Ph.D., lecturer.Her research interests include parallel computing, information security.

MA Xiaofei, born in 1981, M.S., lecturer.His research interests include wireless network, network security.

WANG Kefeng, born in 1982, Ph.D., lecturer.His research interests include identity based signature algorithm.

YAN Ruoyu, born in 1974, Ph.D., associate professor.His research interests include network security.

Hybrid algorithm for identifying error signatures in hierarchical identity based cryptography batch verification

XU Guoyu*, WANG Yingfeng, MA Xiaofei, WANG Kefeng, YAN Ruoyu

(CollegeofComputerandInformationEngineering,HenanUniversityofEconomicsandLaw,ZhengzhouHenan450002,China)

Focusing on the issue of identifying error signatures in Hierarchical Identity Based Cryptography (HIBC) batch verification, a hybrid algorithm of identifying the error signatures was proposed.Firstly, a balanced binary tree was built which used all signatures as the leaves.Secondly, divide-and-conquer and exponent testing methods were used to find error signatures.Meanwhile, the relevance of temporary computing values was used to reduce computing cost.The performance analyses show that the proposed algorithm costs less computation than the individual, the generalized binary splitting, the exponential and the triple pruning search algorithms when there are more than two error signatures.The proposed algorithm can effectively identify error signatures in HIBC batch verification and can be applied in cloud computing authentication.

batch verification; error signature identifying algorithm; Hierarchical Identity Based Cryptography (HIBC); balanced binary tree; cloud computing

2016-08-06;

2016-09-08。 基金項(xiàng)目:國(guó)家自然科學(xué)基金資助項(xiàng)目(61602153,U1404605)；河南省教育廳科學(xué)技術(shù)研究重點(diǎn)項(xiàng)目(15A520044,14A520079)；2016年河南省科技攻關(guān)計(jì)劃項(xiàng)目(162102210273)。

徐國(guó)愚(1982—)，男，安徽廬江人，講師，博士，CCF會(huì)員，主要研究方向：安全協(xié)議、云計(jì)算接入認(rèn)證； 王穎鋒(1976—)，女，吉林德惠人，講師，博士，CCF會(huì)員，主要研究方向：并行計(jì)算、信息安全； 馬小飛(1981—)，男，河南洛陽(yáng)人，講師，碩士，主要研究方向：無(wú)線網(wǎng)絡(luò)、網(wǎng)絡(luò)安全； 王科鋒(1982—),男,河南浚縣人，講師，博士，主要研究方向：基于身份的簽名算法； 顏若愚(1974—),男，湖南邵陽(yáng)人，副教授，博士，主要研究方向：網(wǎng)絡(luò)安全。

1001-9081(2017)01-0217-05

10.11772/j.issn.1001-9081.2017.01.0217

TP309.2; TP393.08

A