《标准模型下基于身份的可证安全签名方案.pdf》由会员分享，可在线阅读，更多相关《标准模型下基于身份的可证安全签名方案.pdf（4页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第 33卷 第 10 期2008 年 10月武 汉 大 学 学 报#信 息 科 学 版Geomatics and Information Science of Wuhan UniversityVol.33 No.10Oct.2008收稿日期:2008-08-28。项目来源:国家自然科学基金资助项目(60473029)。文章编号:1671-8860(2008)10-1076-04文献标志码:A标准模型下基于身份的可证安全签名方案张乐友1,2 胡予濮2(1 西安电子科技大学应用数学系,西安市太白南路 2 号,710071)(2 西安电子科技大学计算机网络与信息安全教育部重点实验室,西安市太白南路2
2、 号,710071)摘 要:在标准模型下设计高效可证明安全的签名方案具有现实意义。基于 Waters 和 Paterson 最近提出的签名方案,提出了两种有效的标准模型下的基于身份的签名方案:一种为(t,n)门限方案,在计算 Diffie-Hel-lman 假设(CDH 问题)下,方案被证明具有不可伪造性和健壮性;另一种为分级签名方案,该方案签名算法效率高,仅需两次指数运算。在 CDH 困难问题假设下,该方案被证明是安全的。关键词:(t,n)门限签名方案;分级签名方案;标准模型;可证明安全;CDH 问题中图法分类号:T P 309 基于身份的密码体制最初是由 Shamir 1于1984 年提出
3、,其目的是为了简化密钥管理。在基于身份的密码体制中,用户的公钥是直接从其身份信息(如姓名、身份证号、E-mail 地址等)得到,而私钥则是由一个称为私钥生成中心(PKG)的可信方生成。自 1984 年来,人们相继提出了许多实用的基于身份的签名方案,但一个满意的基于身份的加密方案直到 2001 年才被提出 2。目前,主要存在标准模型和随机预言机模型两种方法。在随机预言机模型中,Hash 函数看作是理想的,而实际应用的 Hash 函数却并非如此,因而有一些密码学家(如 Canetti、Goldreich 等)对基于随机预言机的安全性证明持否定态度,他们也的确提出了一些签名和加密方案,在随机预言机模
4、型下证明安全的,但在实际中是不安全的 6。为获得令人高度信任的方案,在标准模型下设计出高效可证明安全的门限签名方案具有现实意义。在过去的几年里,门限签名有了很大的发展,然而目前大多数的门限签名都是在随机预言机模型下证明安全的 3-5。文献 10 首次提出了标准模型下的(t,n)门限短签名方案,但其安全性基于一个强的困难问题假设(SDH)。文献 12 基于一般的困难问题假设(CDH 问题)提出了标准模型下的(t,n)门限签名方案,但此方案并不是基于身份的。本文利用 Waters 与 Paterson 最近提出的签名方案 7,8,提出了一种有效的标准模型下基于身份的(t,n)门限签名方案,其安全性
5、基于一般的困难问题假设。在基于身份的密码系统中,只有一个 PKG会影响到系统的效率,这和基于证书的密码系统十分类似,因此,需要一种基于分级身份的密码系统。本文提出了一种标准模型下的分级签名方案,该方案 的安全性同样基于 一般的困难问题)CDH 问题,安全证明不需要随机预言机。1 预备知识1.1 CDH问题定义 1 计算 Diffie-Hellman 问题(CDH 问题)。设 G 为素数阶 p 的循环群,g 为 G 的生成元,对任意的 a,b I zp,已知 ga、gb,计算 gab。解决 CDH 问题是利用 PPT 算法 A 满足对 E 0,E=Prob gabz A(g,ga,gb),如果
6、E是可忽略的,称 CDH 问题是困难的。1.2 双线性映射设G、G1为素数阶 p 的循环群,g 为G 的生成元,则双线性映射e:G G yG1具有如下性质。1)双线性性,对所有的 u,v I G,a,b I zp,都有e(ua,vb)=e(u,v)ab。2)非退化性,e(g,g)X 1。第 33 卷第 10期张乐友等:标准模型下基于身份的可证安全签名方案3)实效性,对于任意 u,v I G,e(u,v)是实际有效可计算的。2 基于身份的门限签名方案2.1 基于身份的门限签名方案基于 Paterson 8与 Waters 7签名方案,本文给出了门限签名方案。1)系统建立(System Setup
7、)。设 G、G1为素数阶 p 的循环群,随机选取 AI zp,g 为 G 的任意生成元,计算 g1=gA,随机选取 g2,h,u0,uc0I G与两个n 维向量 U=(ui),Uc=(uci),其中 ui,uciIG,公共参数为:P=(G,G1,g,h,g1,g2,u0,U,uc0,Uc)主密钥为 A,在本方案中,所有的成员 P=(P1,P2,Pn)都可分享相同的系统公共参数。2)门限密钥生成算法(ThK)。PKG 随机选取 t-1 次多项式 f(x)=a0+a1x+a2x2+,+at-1xt-1,aiI z*p,令 a0=A;计算 f(i),i=1,n,及 Vk=(V1k,V2k,Vnk)=
8、(gf(1),gf(2),gf(n),并广播 Vk。PKG 继续计算主密钥分享份额 Sik=gf(i)2,i=1,n。门限密钥提取,给定身份 ID 将它解析为比特串 ID=(ID1,ID2,IDn),PKG 随机选取 rI zp,计算私钥分享:对 i=1,n 有 Di=(di1,di2)=(gf(i)2(uc00ni=1ucIDii)r,gr),并秘密传输给 Pi。Pi首先验证 e(g,di1)=e(Vik,g2)e(uc00ni=1ucIDii,di2)如果成立,则接受;否则拒绝。3)门限签名算法(ThS)。将要签名的消息M,解析为比特串:M=(m1,m2,mn)产生部分签名。对任意的 s
9、I zp,每个成员 Pi计算Ri1=di1(u00ni=1umii)s,Ri2=gr,Ri3=gs,产生的部分签名为 Ri=(Ri1,Ri2,Ri3)。产生门限签名。门限签名的产生可由任何成员完成,设 D 为指定的生成者,D 首先对每个部分签名验证有效性:e(Ri1,g)#e(Ri2,uc00ni=1ucIDii-1)#e(Ri3,u00ni=1umii)-1=e(g2,Vik)如果成立,说明签名有效,否则,认为该成员不诚实。设 8 为 t 个诚实者的集合,D 通过计算如下式子产生最终的签名 R=(R1,R2,R3):R1=0i I 8RLii1,R2=0i I 8RLii2,R3=0i I
10、8RLii3式中,Li为相应的 Lagrange 系数。4)签名验证算法(T hV)。给定公钥 Y、消息M 及签名R,计算:e(g1,g2)=e(R1,g)#e(R2,uc00ni=1ucIDii)-1#e(R3,u00ni=1umii)-1如果成立,输出有效信息;否则,输出无效。2.2 门限签名的安全性分析2.2.1 正确性签名的正确性:e(R1,g)e(R2,uc00ni=1ucIDii)-1#e(R3,u00ni=1umii)-1=0i I 8(e(Ri1,g)e(Ri2,uc00ni=1ucIDii)-1#e(Ri3,u00ni=1umii)-1)Li=e(g,g2)Ei I 8Lif
11、(i)=e(g1,g2)2.2.2 安全性分析为了证明本方案的安全性,由文献 11 可得:引理 1 如果基本签名方案是一个不可伪造的安全方案,且相应的门限签名方案是可模拟的,则此门限签名是不可伪造的。定义 2 如果以下的性质成立,则称门限签名方案是可模拟 12:1)密钥产生算法(ThK)是可模拟的。输入公钥 Y 和被敌手腐蚀的t-1 个成员的私有分享,存在一个模拟器能模拟敌手在(ThK)中输出 Y的视图(view)。2)签名算法是可模拟的。输入公钥 Y、消息M 和它的签名 R以及被敌手腐蚀的 t-1 个成员的私有分享,存在一个模拟器 能模拟敌手在(T hS)中输出消息 M 及签名 R的视图(v
12、iew)。定理 1 在 CDH 困难问题的假设下,本文提出的(t,n)门限签名方案是安全的。证明(1)健壮性。由于我们的方案来自文献 7,8,所以本文方案的健壮性是满足的。(2)不可伪造性。由于基本签名方案在CDH 困难问题的假设下是不可伪造的 8,所以由引理 1 只需证明本文的方案是可模拟的。设敌手腐蚀的 t-1 个成员为 P1,P2,Pt-1,模拟器的构造与文献 9 类似,由定义 2 依次证明密钥产生算法、签名算法是可模拟的。从文献 7,8 易得密钥产生算法(T hK)是可模拟的。1077武 汉 大学 学报#信息 科 学版2008 年 10 月 签名算法是可模拟的。输入公钥 Y、消息M 和
13、它的签名 R以及被敌手腐蚀的t-1 个成员的私有分享,另外,模拟器还拥有系统参数。首先,模拟器可利用腐蚀的 t-1 个成员的私有分享,计算出门限密钥以及部分签名 Ri=(Ri1,Ri2,Ri3),i=1,t-1;然后根据公式 R1=0i I 8RLii1,R2=0i I 8RLii2,R3=0iI 8RLii3,模拟器计算 R1/0t-1i=1RLii1,R2/0t-1i=1RLii2,R3/0t-1i=1RLii3,可以得到 Rt=(Rt1,Rt2,Rt3)。容易验证 Rt与真实的签名服从相同的概率分布,模拟器能模拟敌手在 ThS 中输出消息 M及签名R的视图。3 分级签名方案基于 Pate
14、rson 与 Waters 的签名方案,给出一种新的分级签名方案(定义见文献 13)。系统建立。设系统分级层数为 l,G、G1为素数阶 p 的循环群,随机选取 AI zp,g,g2为 G 的任意生成元,计算 g1=gA,随机选取 hij,g2,i,u0与ukI G i=1,l,j=1,niand k=1,n。设H=(hij),G2=(g2,i),U=(ui)。系统参数为param=(g,g1,g2,u0,G2,H,U),主密钥为 gA2。密钥提取算法。给定 k 级身份 ID=(v1,v2,vk),k-1 级身份 IDk-1=(v1,v2,vk-1)及相应的密钥:dIDk-1=(d0,d1,dk
15、-1)=(gA2Fk-1i=1(Fi)ri,gr1,gr2,grk-1)式中,vi=(vi1,vini),vijI 0,1,且 Fi=g2iFnij=1hvijij,则对应于 ID 的密钥计算如下。随机选取rkI zp,计算dID=(d0,d1,dk)=(gA2Fki=1(Fi)ri,gr1,gr2,grk)签名算法。给定消息 M=(m1,m2,mn),miI 0,1。随机选取 r I zp,则 M 的签名为:R=(R0,R c,R1,Rk)=(d0(u0Fnk=1umkk)r,gr,gr1,gr2,grk)验证算法。给定消息 M=(m1,m2,mn)及其签名 R=(R0,R c,R1,Rk)
16、,检验 e(R0,g)=e(g1,g2)#e(R c,u0Fnk=1umkk)#Fki=1 e(Fi,Ri)若相等,则认为签名有效;否则签名无效。3.1 有效性本方案与已有的相比,在密钥产生阶段,指数运算有所增加。但在签名阶段,比较前后算法便可发现只需两次指数运算,因此效率大大增加。3.2 安全性定理 2 在计算性 Diffie-Hellman 假设下,该方案对适应性选择消息攻击是存在性不可伪造的。然而,文中的方案存在着与文献 7,8 同样的问题,即公共参数过多的问题。文献 8 中提出了一些改进办法,这些办法可以用到本文的方案中。当然,如何进一步减少这些参数而不影响方案的安全性,是下一步值得深
17、入研究的课题。参 考 文 献1 Shamir A.Identity-based Cryptosystems and Signa-ture Schemes C.CRYPT O 1984,Lectures Notesin Computer Science 196,Santa Barbara,Califor-nia,19852 Boneh D,Franklin M.Identity Based Encryptionfrom theWeil PairingC.CRYPTO 2001,LecturesNotes in Computer Science 2139,California,20013 Cha
18、J,Cheon J.An Identity-Based Signature fromGap Diffe-Hellman GroupsC.PKC 2003,LectureNotes in Computer Science 2567,Miami Florida,20034 Ch X,Liu J M,Wang X M.An Identity-Based Sig-nature and Its Threshold Version C.AINA 2005,Taipei,20055 Chen X F,Zhang F G.New ID-Based T hresholdSignature Scheme from
19、 Bilinear Pairings C.IN-DOCRYPT 2004,LNCS 3348,M adras,India Ber-lin,20046 Canetti R,Goldreich O,Halevi S.The RandomOracle Methodology,Revisited C.Annual ACMSTOC,New York,19987 WatersB.EfficientIdentity-basedEncryptionWithout Random Oracles C.Eurocrypt 2005,Lectures Notes in Computer Science 3494,Aa
20、rhus,Demark,20058 Paterson K G,Schuldt J C N.Efficient Identity-Based Signatures Secure in the Standard Model C.ACISP 2006,LNCS 4058,Melbourne,Australia,20069 Gennaro R,Jarecki S.Secure Distributed Key Gen-eration for Discrete-Log Based Cryptosystems J.J.Cryptology,2007,20:51-8310 Wang H,Zhang Y Q,F
21、eng D G.Short T hreshold1078 第 33 卷第 10期张乐友等:标准模型下基于身份的可证安全签名方案Signature Schemes Without Random Oracles C.Indocrypt 2005,Lectures Notes in Computer Sc-ience 3797,Bangalore,India,2005 11 Gennaro R,Jarecki S.Robust T hreshold DSS Sig-natures C.Eurocrypt.96,Lecture Notes in Com-puter Science 1070.Zarag
22、oza,Spain,1996 12 徐静.标准模型下可证安全的门限签名方案 J.计算机学报,2006,29(9):1 636-1 64013 Chow S SW,Hui L C K,Yiu S,et al.Secure H-ierarchical Identity Based Signature and Its Applica-tion C.ICICS 2004,LNCS 3269,Notes in Com-puter Science 1070,Malaga,Spain,1996第一作者简介:张乐友,博士生,研究方向为密码学与信息安全。E-mail:lyzhang Provable Secur
23、e Identity Based Signature Schemein the Standard ModelZHA NG Leyou1,2 H U Yup u2(1 Department of Applied Mathematics,Xidian University,2 South T aibai Road,Xi.an 710071,China)(2 Key Laboratory of Computer Networks and Information Security,Ministry of Education,Xidian U niversity,2 South T aibai Road
24、,Xi.an 710071,China)Abstract:T o design a signature scheme which are efficient and provably secure in the stand-ard model is suitable for applications.T wo signature schemes based on Paterson.s and Wa-ters.s signature schemes are proposed.A(t,n)threshold signature scheme is presented atfirst and is
25、provable secure in the standard model under CDH assumption.T he other contr-ibution in this paper is to construct a new hierarchical identity based signature scheme.It hasa highly efficient signing algorithm which requires only two exponentiation operations and isprovably secure under CDH assumption
26、 in the standard model.Key words:(t,n)threshold signature scheme;hierarchical signature scheme;standard mod-el;provably secure;CDH assumptionAbout the first author:ZHANG Leyou,Ph.D candidate,majors in information security.E-mail:lyzhang (上接第 1075页)server spoofing attacks,forge attacks,etc.According
27、to security properties comparisons a-mong Peyravian-Zunics scheme,Hwang-Yeh.s scheme,Peyravian-Jeffries scheme,and ourproposed scheme,the proposed scheme is more secure and practical over insecure network.Key words:password;password authentication;Hash function;attackAbout the first author:WANGBangju,Ph.D candidate,majors in information security and cryptography.E-mail:wangbangju 1079