面向分級身份密碼批驗簽的錯誤簽名混合篩選算法

徐國愚，王穎鋒，馬小飛，王科鋒，顏若愚

(河南財經政法大學 計算機與信息工程學院，鄭州 450002)

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

面向分級身份密碼批驗簽的錯誤簽名混合篩選算法

徐國愚*，王穎鋒，馬小飛，王科鋒，顏若愚

(河南財經政法大學 計算機與信息工程學院，鄭州 450002)

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

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

批驗簽；錯誤簽名篩選算法；分級身份密碼；平衡二叉樹；云計算

0 引言

分級身份密碼機制(Hierarchical Identity Based Cryptography， HIBC)具有標識產生公鑰、密鑰分級派生等特點，被廣泛應用在云計算、延遲容忍網絡等環境中[1-3]。HIBC批驗簽機制是指驗簽者能夠對多個簽名者的HIBC簽名進行批量驗簽，其效率優于對其單獨驗簽[4-6]。但是當批驗簽中存在錯誤簽名時，將使得批驗簽失敗，例如惡意節點發送虛假簽名，因此需要采用錯誤簽名篩選機制將錯誤簽名快速篩選出來。

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

1 HIBC批驗簽算法簡介

文獻[5]設計實現了一種HIBC批驗簽算法，能夠對HIBC簽名進行批驗證，減少計算開銷。算法包括初始化、私鑰生成、簽名、驗簽及批驗簽5個部分。

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

(2)

4)驗簽。驗簽方收到簽名σ后通過式(3)進行驗證：

(3)

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

可以看出，對n個簽名進行獨立驗簽時需要2n次雙線性對運算，而進行批驗簽時僅需n+1次，能夠減少n-1次雙線性對運算。但是采用批驗簽算法所面臨的一個問題是，當批驗簽的簽名中存在錯誤簽名時，將使得批驗簽失敗。因此，本文采用TPSH算法將其中的錯誤簽名快速篩選出來。

2 TPSH算法

TPSH算法的基本過程是將所有簽名作為樹葉構造平衡二叉樹，利用拆分攻克與指數測試方法，測試整個樹中是否存在錯誤簽名數小于3的子樹，若找到則返回該子樹中所有錯誤簽名的位置，之后繼續在樹中尋找錯誤簽名數小于3的子樹直到找出所有的錯誤簽名。同時，算法利用相關計算中間值的關聯性，優化計算過程，減少計算開銷。

為了能夠對上述HIBC批驗簽算法進行拆分攻克與指數測試，首先將HIBC批驗簽式(4)轉化成式(5)：

(5)

可以看出當A=1時，式(5)等于式(4)。相應的定義Ai為n個簽名中第i個簽名的獨立驗證公式，如式(6)所示。當Ai=1時，說明第i個簽名正確：

Ai=e(Bi,-P)·Ei

(6)

在式(6)的基礎上定義函數aj,[X]，如式(7)所示，其中：0≤j≤2，X表示樹或者子樹，Low(X)為X中最左側葉子節點的序號，up(X)為X中最右側葉子節點的序號。在樹中，定義右側葉子節點序號總是大于左側葉子節點序號。函數aj,[X]將用于錯誤簽名驗證中的計算。當j=0且X為所有簽名構成的樹時，aj,[X]=A。

(7)

TPSH的具體驗證過程如算法1所示，其流程與TPS相類似，不同之處在于H_Get0函數、H_Get1函數、H_Get2函數以及TPSHQuadSolver函數的實現方法。

算法1TPSH算法。

輸入:X

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

1)

if(X=Tr) then

//X為樹節點

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])

//錯誤簽名數≥3,進入子樹查找

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中，首先進行初始化批驗簽第2)～3)行，通過H_Get0函數計算a0,[Tr]，Tr表示所有簽名所組成的樹，并且保存中間相關計算變量供后續計算使用。由式(7)可得式(8)：

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

算法2H_Get0(X)。

輸入:X

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

1)

if(X=Tr)then

//X為根節點

2)

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

3)

fori=|X|-1downto1do

4)

5)

forj=|X|downto1do

6)

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

7)

EB0|X|=E|X|

8)

fori=|X|-1downto1do

9)

10)

11)

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

//如果是1，則說明正確，無錯誤簽名。

12)

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

//X為子樹,定義P為X的父親節點，P的相關數值已提

//前計算并保存，L為P的左孩子節點，R為P的右孩子節點

13)

if(X=R)then

//X為P的右子樹

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]供后續計算使用

16)

return(ɑ0,[R])

17)

elseif(X=L)then

//X為P的左子樹

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已經計算過

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已經計算過

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

//計算出ɑ0,[X]

33)

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

34)

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

35)

return(ɑ0,[X])

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

算法3H_Get1(X)。

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

1)

if(X=Tr)then

//X為根節點，需要計算a0,[Tr]

2)

VB1|X|=VB0|X|

//VB0i值見H_Get0

3)

fori=|X|-1downto1do

4)

VB1i=VB1i+1+VB0i

5)

EB1|X|=EB0|X|

//EB0i值見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為子樹,定義P為X的父親節點，P的相關數值已提前

//計算并保存，L為P的左孩子節點，R為P的右孩子節點，

//X′為X的兄弟節點

11)

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

12)

a1,[X]=a1,[P]

13)

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

14)

return(a1,[R])

15)

if (X=R)then

//右孩子節點

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

//左孩子節點

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已經計算過

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//計算出a1,[X]

35)

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

36)

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

37)

return(a1,[X])

相對于原始的TPS算法而言，TPSH在計算aj,[X]時，利用Ei等中間值參與計算，并通過輕量級GT域上的乘法運算代替復雜雙線性對運算，減少了aj,[X]的計算開銷，提高了計算效率。

3 算法分析與比較

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

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

下面給出篩選錯誤簽名的具體開銷。

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

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

性能分析主要比較在不同批驗簽與錯誤簽名數量的情況下，各方案的單次平均計算開銷，分析比較結果如圖1所示。

圖1 算法單次平均計算開銷的比較

在圖1(a)中，設置一次批驗簽的簽名數量n=8。可以看出：當錯誤簽名總數w=2，TPSH算法的單次平均計算開銷與指數測試算法及TPS算法大體相同，其主要原因是當w<3時，3種算法均使用相同的指數測試方法。但是當w≥3時，TPSH的單次平均計算開銷小于上述兩種算法，其原因是：指數測試方法的計算開銷隨著w成指數增長，所以當w≥3后開銷上升變快；TPS算法在測試本文HIBS算法時，由于未能利用先前雙線性對計算數值參與后續計算步驟，從而導致計算開銷增大；而本文的TPSH算法充分考慮HIBS算法的特點，通過劃分子樹進行指數測試，避免了計算開銷的指數增長。同時，通過相關計算中間值的關聯性，采用GT乘法運算代替雙線性對運算，進一步減少了計算量，因此計算開銷較小。另外，不管錯誤簽名總數w為何值，TPSH算法的計算開銷均小于獨立測試及GBS算法。

在圖1(b)中，設置批驗簽的簽名數量n=16，TPSH算法受簽名數量n的影響不大，其性能依然優于其他算法。另外，可以看出在各算法中，指數測試方法受批驗簽數量及錯誤簽名數量的影響最大。綜上所述，TPSH的計算開銷受批驗簽數量及錯誤簽名數量的影響較小,當w≥3時，TPSH的計算開銷小于獨立測試、GBS算法、指數算法以及TPS算法。

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

4 結語

本文針對HIBC批驗簽中的錯誤簽名篩選問題，設計實現了一種錯誤簽名混合篩選算法TPSH。該算法利用拆分攻克、指數測試以及中間值關聯特性簡化了錯誤簽名的篩選計算，與現有的獨立測試、GBS算法、指數算法以及TPS算法相比計算開銷更小。下一步，將研究如何對TPSH進行形式化安全證明以及應用TPSH算法提高云計算的接入認證效率。

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的云信任分散統一認證機制[J].計算機研究與發展,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] 徐國愚,陳性元,杜學繪.大規模延遲容忍網絡中基于分級身份簽名的認證方案研究[J].電子與信息學報,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。 基金項目:國家自然科學基金資助項目(61602153,U1404605)；河南省教育廳科學技術研究重點項目(15A520044,14A520079)；2016年河南省科技攻關計劃項目(162102210273)。

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

1001-9081(2017)01-0217-05

10.11772/j.issn.1001-9081.2017.01.0217

TP309.2; TP393.08

A