面向分级身份密码批验签的错误签名混合筛选算法
2017-04-17徐国愚王颖锋马小飞王科锋颜若愚
徐国愚，王颖锋，马小飞，王科锋，颜若愚
(河南财经政法大学 计算机与信息工程学院，郑州 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
