新的强指定多个验证者签名方案

新的强指定多个验证者签名 2007年10月 第30卷第5期 北京邮电大学 JournalofBeijingUniversityofPostsandTelecommunications 0ct.2007 V01.30NO.5 文章编号:1007—5321(2007)05—0001—04 新的强指定多个验证者签名方案 杨波,肖自碧2,杨义先,胡正名1,钮心忻 (1.北京邮电大学信息安全中心,北京100876;2.武汉科技大学理学院,武汉430081) 摘要:基于Chmleon哈希和D.Boneh的多方密钥协商方案,提出了1个新的强指定多个验证者签名方案.该方 案中,只有签名者指定的个验证者可以各自独立地验证签名,并且即使其中某个指定验证者将自己的秘密值泄 露,其他任何人也无法验证签名的真伪.表明,新方案满足不可转发性,不可伪造性以及签名者身份保密的性 质,并且具有较高的效率. 关键词:指定多个验证者签名;多线性映射;签名者身份保密性 中图分类号:TP309文献标识码:A StrongMulti-DesignatedVerifiersSignatureScheme YANGBo,XIAoZi—bi,YANGYi—xian,HUZheng—ming,NIUXin—xin (1.InformationSecurityCenter,BeijingUniversityofPostsandTelecommunications,Beiji ng100876,China; 2.SchoolofScience,WuhanUniversityofScienceandTechnology,Wuhan430081,China) Abstract:BasedonChameleonHashandD.Boneh'Soneroundmulti—partykeyagreementprotocol,a multi—designatedverifierssignatureschemewasproposed.Thesignaturecanbeverifiedindepende ntly byeachofthe扎designatedverifiersdesignatedbythesignerandnooneelsethanthedesignatedper— soncanbeconvincedbythissignatureevenifoneofthedesignatedverifiersrevealsthesecretv alue. Thesecurityanalysisoftheproposedschemeshowsthatitsatisfiesnon—transferability,unforgeability, privacyofsigner'Sidentityandwithlowcomputationalcost. Keywords:multi—designatedverifierssignature;multilinearmap;privacyofsigner'Sidentity 0引言 指定验证者签名(DVS,designatedverifiersig— nature)是由Jakobsson,Sako,Impagliazzo提出的一 种特殊的签名E1],它只能提供对消息真实性的认 证,但不像传统数字签名那样提供抗否认服务,从而 能有效地保护签名者的隐私.这种签名方案被广泛 应用于电子选举,电子拍卖以及招标等领域.文献 [1]提出的DVS方案具有签名者模糊的性质,即签 名的有效性虽然可以公开验证,但是第3方却无法 确定该签名究竟是签名者Alice还是指定的验证者 Bob所做的,原因是后者可以伪造原始签名人的签 名.但是,如果第3方在Alice发送签名后而Bob尚 未收到签名前就将签名截获,由于签名是可以公开 验证的,故第3方完全有理由确定签名人就是 Alice.为了解决这个问题,Saeednia等提出了强 DVS方案_2J.该方案设计的特别之处是在验证签 名有效性的过程中必须用到指定验证者的秘密密 钥,即使第3方截获了Alice发送给Bob的文本,但 由于并不知道Bob的私钥,所以无法验证签名的有 效性,从而无法确信Alice是否对某个消息签过名. Laguillaumie和Vergnaud对此概念进行了加强,提 收稿日期:2006—11—27 基金项目:国家"973计划"项目(2007cB311203);国家自然科学基金项目(90604022); 北京市自然科学基金项目(4062025) 作者简介:杨波(1973一),男,博士生,E—mail:cookieyb73@126.com. 2北京邮电大学第3O卷 出了签名者身份保密的概念J. 在现实生活中签名的接收者往往不止1个人, Laguillaumie和Vergnaud首次提出了指定多个验证 者签名(MDVS,multi—designatedverifierssignature) 的形式化定义[4],并提出了利用环签名方案构造 MDVS的方法,但是效率较低.特别地,利用Joux 的3方密钥协商方案,文献[4]构造了1个基于双线 性映射的指定2个验证者的签名方案.但是,在该 方案中,如果其中1个指定验证者向敌手泄漏了3 方共享的秘密值,则敌手就能验证签名的有效性,并 相信该签名确实是原始签名人对消息m的签名. 本文利用Chameleon哈希和D.Boneh的多方 密钥协商方案[,提出了1个新的MDVS方案.该 方案具有如下性质:个指定的验证者可以独立地 验证签名;即使其中某个指定验证者将秘密值透露 给其他人,也无法使他人相信该签名是由原始签名 人所签署的,因为个指定的验证者可以联合伪造 对任意消息m的签名;在验证签名时需要用到 个指定的验证者和签名者共享的会话密钥,所以该 方案具有强壮性. 1背景知识 1.1Chameleon哈希函数 Krawczyk和Rabin在文献[6]中给出了 Chameleon哈希函数的形式化定义,并基于离散对 数问题提出了具体的Chameleon哈希函数. "Chameleon"一词是指拥有陷门信息的人能将函数 的输入变为他所选择的任何值,而不改变最终的输 出结果.Chameleon哈希函数与用户C的公,私钥 对(Pc,Sc)有关,通常称该私钥为陷门信息.由公 钥Pc定义1个Ctmmeleon哈希函数,记为CIBqc(?,?), 任何知道公钥P的人都可以计算出相应的哈希 值.对输入消息m和随机串r,该函数产生1个哈 希值CHHc(m,r),满足下面的性质. 1)抗碰撞.对于不知道陷门信息S的人,函 数是抗碰撞的.即要找到2组不同的值m,r1和 m2,r2满足CHHc(m1,1)=CHHc(m2,r2)在计 算上是不可行的. 2)陷门碰撞.对于任意给定的输入,拥有陷门 信息sc的人都可以找到碰撞,即存在多项式时间 算法,输入私钥Sc,消息m1,随机串r1和消息m2, 输出满足等式CHHc(m1,r1):CHHc(m2,r2) 的r,. 1.2,1.线性映射 定义1设G1,G2为阶为素数P的乘法循环 群,如果它满足下面的性质,映射e:Gj—G2是1个 一 线性映射. 1)线性性.如果a1,…,a?Z且z1,…,z? G,则有 e(z1,…,z:n)=e(Xl,…,z).1'…'. 2)非退化性.如果g为G1的生成元,则e(g,一, g)为G2的生成元.' 定义2如果满足以下性质,1个一线性映射 称为密码学上的一线性映射. 1)群G1和G2中的运算可有效地计算. 2)映射e可有效地计算. 3)群G中的离散对数问题是难解的. 本文假设G1,G2中的元素都以二进制串的形 式表示,即G1,G2{0,1}. 1.3复杂度假设 定义3多线性Diffie—Hellman问题.给定g, g.一,ga~1,计算e(g,…,g)一.川. 定义4多线性Diffie—Hellman假设.不存在有 效的多项式时间算法可以解多线性Diffie—Hellman 问题. 2指定多个验证者签名 2.1定义 MUDV签名由5个算法构成. 1)初始化.为概率算法,输入为安全参数愚,输 出为公开参数. 2)签名者密钥生成.为概率算法,输入为公开 参数和签名者A,输出为1对密钥(PKA,SKA). 3)验证者密钥生成.为概率算法,输入为公开 参数和验证者B,输出为1对密钥(PKB,SKB). 4)指定个验证者签名.输入消息m,签名私 钥SKA,7"/个验证者的验证公钥PKB(:1,2,…, 7"/)以及公开参数,输出1个对消息m的(B1,…, B)一指定验证者签名.这个算法可以是概率性算 法也可以是确定性算法. 5)指定7"/个验证者验证.为确定性算法,输入 签名,消息m,签名公钥PKA,验证私钥SKB(i:1, 2,…,)以及公开参数,检验是否是关于PKA, PKB. ,…,PKB有效的(B1,…,B)一指定验证者 签名. 第5期杨波等:新的强指定多个验证者签名方案3 2.2安全性要求 MDVS方案必须满足4个要求. 1)正确性.签名者用有效的签名算法生成的 (B1,…,B)一指定验证者签名一定会通过验证 算法. 2)不可伪造性.给定签名者A,如果不知A的 私钥或所有验证者B(i=1,2,…,)的私钥,那么 生成1个有效的(B,,B)一指定验证者签名在计 算上是不可行的. 3)不可转发性.即使个指定验证者将他们 的秘密值泄露给其他人,也不能使其他人相信 (B】,…,B)一指定验证者签名的有效性. 强指定多个验证者签名方案还须满足. 4)签名者身份保密(强壮性).给定消息m和 对消息的(B一,B)一指定验证者签名,如果不 知某个B的私钥或签名者的私钥,判定是用哪对 签名密钥生成的在计算上是不可行的. 3新的强指定n个验证者签名方案 新的强指定个验证者签名方案基于 Chameleon哈希和多线性映射提出,步骤如下. 1)初始化.设G1,G2为2个阶为素数P的乘 法循环群,g为G1的生成元.e:G一G2为密码学 上的一线性映射,h1:{0,1}一为密码学哈希函 数. 2)签名者密钥生成.签名者A随机选取zA? ,计算YA=gXA?G1,(YA,zA)是签名者的公私 钥对. 3)验证者密钥生成.验证者B随机选取z? ,计算Y=gz?G1,个验证者B一,B的公 私钥对为(,z),i=1,2,…,. 4)指定个验证者签名.对消息m?,选 择秘密的随机数r?,计算Y=?Y,M= =l HB(m,r)=Ymg(B表示个验证者B一,B); 再随机选取是?且gcd(是,P)=1,计算S= e(Yl,…,Y)A,t=h1(S),y=g舡,= 是一{1(M)一zAh1(y)}.将(m,r,y,)以及Y1,…, 发送给他指定的每个验证者B. 5)验证.每个验证者独立地计算S=e(y一, Y一1,YA,Y+1,…,Y)t,t=h1(S),然后再计算 Y=?Y以及Chameleon哈希值M=HB(m,r)== l y.检验等式y3h1'ghl(M)t是否成立. 4方案的分析 4.1安全性分析 1)正确性.由于 e(Y1,…,Y一1,YA,Y+1,…,Y)= e(g1,…,g一1,gA,gz+1,…,g)i= e(g,…,g)I'"XnXA=e(gX1,…,gn)A 故个指定验证者和签名者将得到相同的会话密 钥S.验证算法的正确性如下. 'gk1' [k3+XAh1(y)It:hl(M)t 2)不可转发性.个指定验证者可以联合伪 造对消息的签名.每个指定验证者B分别计算 Xim—m)的值,则r=r+?37im—m).由于f=l n,n HB(,r)==(?)grg(m-re')善=i=l g善xigrg一蚤=gmi=1g=(?)gr=i=l Yg=HB(m,r) 故(m,r,y,)是对m的有效签名.因此,即使其 中某个指定验证者将秘密值透露给其他人,也无法 使他人相信该签名是由原始签名人所签署的.但是 个指定验证者中的任何人如果没有参与合谋伪 造,则他在独立地验证了签名的有效性后都将相信 该签名的真实性. 3)不可伪造性.首先,Chameleon哈希函数 HB(m,r)=Ymg是抗碰撞的.要找到1组不同的 值m,r,使HB(m,r)=HB(m,r),即要满足 ymg=y,g=gry(一" ,这对不知陷门信息 的人来说等价于解决离散对数问题.其次,签名算 法实质上是对消息m的Chameleon哈希值做广义 的E1Gamal签名[,其不可伪造性依赖于E1Gamal 签名方案的安全性. 4)签名者身份的保密性.验证签名时需要用 到签名者和个指定验证者共享的会话密钥s,该 密钥S由D.Boneh的多方密钥协商[]得到,而 D.Boneh的多方密钥协商协议的安全性基于多线性 Diffie-Hellman假设.对于窃听者来说,即使他能截 获到签名者发给指定验证者的文本,但由于他无法 4北京邮电大学第30卷 得到验证签名所需要的会话密钥S,所以无法利用 签名验证算法进行验证,即所能看到的文本与长度 和分布都相同的随机串是不可区分的,从而也就无法确信所截获的文本是否是发送者对某消息的签名, 4.2效率分析 对于指定2个验证者的签名,将新方案与文献 [4]中的方案比较.两者的签名生成算法都需要4 次求幂,1次求逆和1次对的运算,故效率相当.而 签名验证过程中,文献[4]中的方案需要2次求幂和 4次对的运算,而新方案需6次求幂和1次对的运 算.由于对的计算相对求幂的计算复杂度要高得 多,所以新方案效率较高. 5结束语 指定多个验证者签名在多用户的情形下显得非 常重要.本文提出了一个新的强指定多个验证者签 名方案,利用该方案,个指定验证者可以独立地 验证签名,任何无关的其他人都无法验证签名的真 伪.分析表明,该方案具有不可转发性,不可伪造性 以及签名者身份保密的性质. 参考文献: [1]JakobssonM,SakoK,ImpagliazzoR.Designatedverifi— erproofsandtheirapplications[C]ffAdvancesinCryptol— ogy-Eurocrypt'96.Berlin:Springer-Verlag,1996:143— 154. [2]SaeedniaS,KramerS,MarkovitchO.Anefficient strongdesignatedverifiersignaturescheme[c]?Infor— mationSecurityandCryptology.Berlin:Springer-Ver— lag,2003:143—154. [3]LaguillaumieF,VergnaudD,Designatedverifiersigna— ture:anonymityandefficientconstructionfromanybilin— earmap[C]?FourthConferenceonSecurityinCommu— nicationNetworks'04(SCN04).Berlin:Springer-Ver— lag,2004:107—121. [4]LaguillaumieF,VergnaudD,Multi—designatedverifiers signatures[C]?InformationandCommunicationsSecuri— ty,Berlin:Springer-Verlag,2004:495—507. [5]BonehD,SilverbergA.Applicationsofmultilinearforms tocryptography[EB/OL].2002[2006—10—27].http:? eprint,iacr.org/2002/080. [6]KrawczykH,RabinT.Chameleonsignatures[C]?Pro— ceedingofNetworkandDistributedSystemSecurity.San Diego.[S.n,],2000:143—154. [7]AlfredJMenezes,PaulCvanOorsehot,ScottAVan— stone.Handbook0fappliedcryptography(5thprinting) [M],BocaRaton:CRCPress,2001,451—462. 新一代网络的网络管理理论及实验平台 研究单位:北京邮电大学网络与交换技术国家重点实验室 研究人员:孟洛明王智立陈兴渝李文琼刘会永芮兰兰王颖成璐詹志强高志鹏 王柏熊翱张若英 结题时间:2007年3月 本课题为国家自然科学基金重大研究计划项目(90204002),研究为新一代网络管理的模型化方法 及方法学,新一代网络管理参考模型,新一代网络管理理论验证及模型系统,新一 代网络管理的. 研究小组在建模方法,模型研究,标准研究,模型验证4个层次上开展工作,提出了新一代网络的网络管 理参考模型,新一代网络的管理信息模型,新一代网络的管理接口模型分析和设计的通用方法,新一代网络 的网络管理测试模型,新一代网络的SLA建模方法,研制了5个模型系统,并基于研制的模型系统完成了实 验工作,基本形成了新一代网络的网络管理理论基础.研究成果形成了5项国际标准,包括ITuTM.3017, ITu—TM.3031,ITu—TQ.838.1,ITu—TQ.827.1和ITu—TM.3342,并获得国际学术奖,国家科技进步二 等奖及省部级科学技术(科技进步)二等奖,发表论文61篇,其中被(SCI)和《EI》收录42篇,被《ISTP》收录 13篇.