标准模型下基于双线性对的前向安全环签名方案 - 电子与信息学报200902

第31卷第2期电子与信息学报Vol.31No.22009年2月JournalofElectronics&InformationTechnologyFeb.2009标准模型下基于双线性对的前向安全环签名方案王玲玲①②张国印①马春光①①(哈尔滨工程大学计算机科学与技术学院哈尔滨150001)②(青岛科技大学信息科学技术学院青岛266061)摘要：该文针对环签名存在的密钥泄漏问题，基于前向安全数字签名和双线性对，提出一种新的前向安全环签名方案。方案的前向安全性保证了签名密钥可定期更新，即使当前时间段的签名密钥被泄漏，敌手也不能伪造先前的签名。在全面考虑了实际攻击者的能力后，给出了方案在标准模型下的安全性证明。关键词：环签名；前向安全；双线性对；标准模型；密钥更新中图分类号：TP309文献标识码：A文章编号：1009-5896(2009)02-0448-05AForward-SecureRingSignatureSchemeBasedonBilinearPairinginStandardModelWangLing-ling①②ZhangGuo-yin①MaChun-guang①①(CollegeofComputerScienceandTechnology,HarbinEngineeringUniversity,Harbin150001,China)②(CollegeofInformationScience&Technology,QingdaoUniversityofScience&Technology,Qingdao266061,China)Abstract:Sincetheproposedringsignatureshasthekeyexposureproblem,anewforward-secureringsignatureschemebasedonbilinearpairingsisproposed.Forwardsecurityoftheschememeansthatevenifthesecretkeyofcurrenttimeperiodiscompromised,somesecurityremains.Itisimpossibletoforgethesignaturerelatingtothepast.Secretkeyisevolvedwithdifferentperiodtimewhilethepublickeyisfixedinthelifetime.Theschemeisproventobesecureagainstadaptivechosenmessageattackinthestandardmodel.Keywords:Ringsignature;Forward-secure;Bilinearpairings;Standardmodel;Keyevolution1引言普通签名方案都有一个严重的缺陷：一旦签名密钥泄露，先前用该密钥签署的所有文档均失效。为了降低因密钥等秘密泄露而带来的损失，1997年，Anderson[1]首次提出了前向安全的概念。前向安全就是把整个有效时间分成若干个周期，在每个周期开始时使用单向更新函数定时更新密钥，而验证签名的公钥在整个有效时间内保持不变。即使当前周期的签名密钥被泄露，也并不影响此周期前签名的有效性。Bellare和Miner[2]设计了第一个有效的前向安全签名方案。随后，文献[3-5]提出了更为简单、实用的新方案。2001年，Rivest等[6]在如何匿名泄漏秘密的背景下提出了一种新型签名技术——环签名。环签名可以让用户以一种完全匿名的方式对消息进行签名。任何验证者都能确信这个签名是来自于环中的某个成员，但却不能确认实际签名者的身份。自环签名的概念被提出后，引起了各国学者的广泛关注[710]−。环签名作为一种特殊的数字签名，也存在密钥泄漏的问题。2006年，Liu等[11]首次针对环签名存在的密钥泄漏2007-07-31收到，2008-07-04改回黑龙江省自然科学基金(F2004-06)，哈尔滨工程大学基础研究基金(HEUFT05067)和黑龙江省博士后科研启动基金资助课题问题，提出了采用前向安全和密钥封装技术的解决方案，并且在随机预言模型下证明了方案在分解Blum整数和强RSA问题困难的前提下的安全性。随机预言模型[12]作为一种非标准化的计算模型，是由Bellare和Rogaway于1993年提出的。在这个模型中，任何具体的对象例如哈希函数，都被当作随机对象。它允许人们规约参数到相应的计算，哈希函数被作为一个预言返回值，对每一个新的查询，将得到一个随机的应答。然而，该模型没有全面考虑实际攻击者的能力，并且存在缺陷，如哈希函数是确定的，不能总是返回随机的应答等。已有环签名方案的安全性大都是在随机预言模型下考虑的。2006年，Chow等[13]首次在标准模型下提出了基于新安全假设的环签名方案(CLW)。Bender等[14]在陷门置换存在的前提下，也提出了标准模型下安全的环签名方案(BKM)，然而他们的方案只适用于环成员个数为2个的情况。随后，Shacham和Waters[15]在已有方案的基础上，提出了在标准模型下高效的环签名方案(SWR)。本文在解决了环签名存在的密钥泄漏问题的同时，还全面考虑了实际攻击者的能力，提出了在标准模型下基于双线性对的前向安全环签名方案FSRS-BP。由于双线性对上的计算简便和椭圆曲线上点的表示所需位数较短，使得本方案第2期王玲玲等：标准模型下基于双线性对的前向安全环签名方案449的计算简便，并且可以得到简短的密钥和签名，从而减小了存储量和计算代价。2相关定义本文将采用合数阶有限群构造双线性映射，其详细定义和性质可参见文献[16]。定义1(双线性对(bilinearpairing)[16])令G和TG分别是阶为合数N的加法群和乘法群，其中Npq=，p，q均为大素数，并且G上的离散对数问题是难解的。P是G的一个生成元，即GP=。可定义两个群之间的双线性映射为:TeGGG×→，且满足以下性质：(1)双映射性(,)(,)abeaPbQePQ=，对所有的,PQG∈，*,NabZ∈均成立。(2)非退化性存在,PQG∈，使得(,)1TGePQ≠，其中1TG是TG的幺元。(3)可计算性对于,PQG∈，存在有效算法来计算(,)ePQ。本文构造的FSRS-BP安全性基于(q,n)-DsjSDH问题，与文献[13]类似，我们将给出加法群G上(q,n)-DsjSDH问题的定义。定义2((q,n)-DsjSDH问题[13])给定,,PQxQG∈，对于1in≤≤，选取互不相同的整数*iNaZ∈和单向哈希函数**():{0,1}iNHZ⋅→。任选非零mτ和,iτσ，其中1qτ≤≤，1in≤≤且满足,1(())niiiixaHmPττσ=+=∑。计算满足等式**1(())niiiiixaHmrPσ=++=∑且*()()iiiHmrHmτ+≠的*m和*(,)iirσ，1in≤≤是困难的。定义3(前向安全环签名方案模型)一个前向安全的环签名方案一般由5个多项式时间算法组成FSRS=(SET,IKG,KE,SIG,VER)。(1)系统设置算法SET给定安全参数，返回系统公共参数params。(2)初始密钥生成算法IKG输入params和用户选择的任意信息，返回该用户的初始私钥，和验证公钥。(3)密钥进化算法KE输入系统所处的时段和前一时段的私钥，用户计算现时段的私钥，公钥保持不变。(4)环签名算法SIG系统给定环成员的公钥集，签名用户代表环群体用其私钥对消息m进行签名，最后输出签名。(5)签名验证算法VER接收者收到环签名后，用公钥验证环签名是否合法。定义4如果FSRS满足以下性质，则FSRS是安全的。(1)正确性如果按照正确的签名步骤对消息m进行签名，并且在传播的过程中签名没有被篡改，那么环签名满足签名验证等式。(2)不可伪造性任何攻击者能代表一个不包括他自己的环，对消息m成功伪造一个环签名的概率是可以忽略的。(3)无条件匿名性给定一个合法签名，任何验证者猜对代表环进行签名的真实签名者身份的概率是可以忽略不计的。(4)前向安全性用户的私钥定期更新，公钥保持不变。已知某用户第j时段的私钥，得到该用户第j-1时段私钥的概率是可以忽略的。3标准模型下基于双线性对的前向安全环签名方案依照定义3，本文设计了一种基于双线性对的前向安全环签名方案FSRS-BP=(SET-BP,IKG-BP,KE-BP,SIG-BP,VER-BP)。假设环中有n个成员1{,,}nUUU=。(1)系统设置算法SET-BP选择定义1所示的双线性对:TeGGG×→，||||TGGN==，N为合数，且GP=R=。选择单向哈希函数**():{0,1}iNHZ⋅→，1i≤n≤。签名密钥的有效期分为T个时段。系统公共参数为1{,,,,,,}nePRHHT。(2)初始密钥生成算法IKG-BP用户iU任选,0,0,iixy*RNZ∈，计算22,0,0,TTiiiiuxRvyR==。iU的验证公钥为{,}iiiPKuv=，初始私钥为,0,0,0{,}iiiSKxy=。(3)密钥进化算法KE-BP系统一旦进入第(1jj≤)T≤时段，用户iU使用第1j−时段的私钥,1ijSK−=,1,1{,}ijijxy−−，计算2,,1modijijxxN−=，2,,1modijijyyN−=。由归纳法可知2,,0jijixx=，22,0,TTjiijxx−=。此时，立刻从系统中删除第1j−时段的私钥,1ijSK−。系统在第j时段的签名密钥对为,(,)ijiSKPK，其中,,,{,}ijijijSKxy=，iPK={,}iiuv。(4)环签名算法SIG-BP用户sU希望代表群体对消息m进行签名。并且系统现在进入了第j时段。用户sU执行如下操作：(a)对于{1,,}\ins∈，选择*iRNzZ∈，计算iizRσ=。(b)对于{1,,}in∈，选择*iRNrZ∈，通过以下等式计算W。{1,,}\(())iiiiiinsPWzuHmRrv∈⎡⎤⎢⎥=+⋅++⎢⎥⎢⎥⎣⎦∑(c)通过,,,{,}sjsjsjSKxy=计算()()22,,1()TjTjssjSssjxHmryWσ−−=++输出环签名为11{(,),,(,)}nnrrσσ。(5)签名验证算法VER-BP接收方收到消息m的环签名11{(,),,(,)}nnrrσσ，用n个成员的公钥验证等式：1[(,(()))](,)niiiiiieuHmRrvePRσ=++=∏若等式成立则接收签名，否则拒绝。4安全性分析定理1FSRS-BP满足签名验证的正确性。450电子与信息学报第31卷证明接收方收到环签名{11(,),,(,)nnrrσσ}，若该签名是按照第3节步骤产生的，并且在传输的过程中没有改变，则有()()()()1{1,,}/222,,,0222,0,0,0{1,,[(,(()))](,(()))[(,(()))]1(),(),()TjTjTTTTniiiiisssssiiiiiiinssjSssjssssiiiiiineuHmRrveuHmRrveuHmRrvexHmryWxRHmRryRezRxRHmRryRσσσ−−=∈∈++=++⋅++=+++⎡⎤+⋅++⎢⎥⎣⎦∏∏()()}/22,,{1,,}/22,,{1,,}/(,)(),(),=(,)TjTjTjTjsiijiiijinsiijiiijinseWRezxHmryRReWzxHmryRRePR−−−−∈∈⎛⎞⎟⎜⎟⎜=⋅++⎟⎜⎟⎜⎟⎜⎝⎠⎛⎞⎟⎜⎟⎜=+++⎟⎜⎟⎜⎟⎜⎝⎠∏∑∑所以FSRS-BP的验证算法是正确有效的。定理2如果(q,n)-DsjSDH问题是难解的，则在标准模型下FSRS-BP满足环签名的不可伪造性。证明假设在第j时段，敌手A成功伪造了消息m的签名，则存在多项式时间算法B，可以通过与A合作来解决(q,n)-DsjSDH问题。给定(q,n)-DsjSDH问题的一个实例：,,PSzSG∈