汤鹏志,刘启文,左黎明
(华东交通大学理学院,南昌 330013)
一种基于身份的部分盲签名改进方案
汤鹏志,刘启文,左黎明
(华东交通大学理学院,南昌 330013)
对现有基于身份的部分盲签名方案进行安全性分析,发现大多方案存在公共协商信息可被篡改的漏洞,即攻击者可以在不被察觉的情况下将盲化的消息乘以部分盲因子,从而消除掉方案中的部分盲特性,同时可以伪造签名中的公共协商信息。为此,提出一种改进的部分盲签名方案,以解决基于身份的部分盲签名方案中公共协商信息被伪造的问题。分析方案的部分盲性和不可伪造性,证明其满足部分盲性。在随机预言机模型下,改进方案对适应性选择消息和身份攻击是不可伪造的,与现有基于身份的部分盲签名方案相比,具有更高的效率。
部分盲签名;基于身份;随机预言机模型;双线性对;伪造
盲签名是一种非常有用的密码技术[1-2],它允许签名者在不知道签名内容的情况下与签名申请者交互产生一个合法的签名。盲签名必须具备盲性和不可伪造性这2个基本特性。盲性是指允许一个用户获得一个关于消息 m的签名,但是,签名者不知道任何关于m的信息;并且,签名是不可追踪的,也就是说当m的签名公布时,签名者不能确定什么时候对m进行了签名。不可伪造性是指签名者才能产生合法的签名。由于盲性和不可伪造性,盲签名被广泛应用在电子现金系统[3-5]和电子选举系统中[6-7],保护用户的隐私。 但是在电子现金系统中,盲签名有较大的缺陷,例如,银行的数据库必须保存每个使用过的电子货币以防货币被重复使用,这使得数据量成几何级数增加。另外,由于盲签名的不可追踪,使得一些违法行为如偷税漏税、黑市交易洗钱等难以监管。为了解决这些问题,文献[8]提出了部分盲签名的概念。部分盲签名是盲签名的一种扩展,允许为用户产生关于某个消息m的盲签名,签名中需嵌入一个由用户和签名者协商的声明信息c,声明信息c在整个签名过
程中都是可见的。在电子现金系统中,部分盲签名比盲签名效率更高。自部分盲签名的概念提出以来,各种部分盲签名方案随即被提出。不过在很多方案中,存在用户和签名者协商的声明信息c被替换的漏洞。文献[9]指出文献[10]的方案中,存在声明信息 c被替换的漏洞。文献[11]指出文献[12]方案也存在声明信息 c可替换的漏洞。文献[13]提出了一种高效无证书盲签名方案,并在随机预言机下证明了该方案是安全的。文献[14]提出了一种无秘密信道的高效无证书部分盲签名方案,证明了该方案在随机预言机下是安全的。与基于证书的签名体制相比,基于身份的签名体制简化了密钥的管理、验证及传输等过程。
在文献[15]提出的基于身份的签名方案基础上,文献[16]提出了一个高效的基于身份的部分盲签名方案,通过分析该方案,发现攻击者可以在不被察觉的情况下替换用户和签名者协商的声明信息c;在文献[16]方案的基础上提出了一种改进方案,改进方案不仅满足部分盲性,并且可以防止敌手替换声明信息c;同时,在随机预言机模型下,证明了改进方案对适应性选择消息和身份攻击是不可伪造的,并且比文献[16]方案更高效。
本文首先给出对文献[16]的攻击方法,然后提出一个改进方案,并进行安全性分析,最后分析了改进方案的效率。
定义1 双线性映射:假设 G1是一个阶为大素数q的加法循环群,P是它的一个生成元,G2是一个阶为q的乘法循环群。若映射e:G1×G1→G2满足以下3条性质,则称这个映射为双线性映射。(1)双线性性:对于任意(aU,bV)=e(U,V)ab。
(2)非退化性:存在 U,V∈G1,使得 e(U,V)≠1G2。
(3)可计算性:对于任何的U,V∈G1,存在一个高效的算法来计算e(U,V)的值。
定义2 计算Diffie-Hellman问题(CDHP):任给计算abP。
定义3 判定Diffie-Hellman问题(DDHP):任给,判断c=ab mod P是否成立。
如果在群G1上,DDHP容易但CDHP困难,则G1称为间隙Diffie-Hellman群(GDH群)。
攻击 假定敌手是签名申请者A,A与签名者S协商约定的声明信息 c,系统设置和密钥提取同文献[16]方案。
(3)盲签名:S收到h*后,计算V′=h*k′Ppub+ H3(c)SID,把V′发给A。
(4)脱盲:A收到 V′后,计算 V=H3(c′)H3(c)-1V′+βhPpub。消息(m,c)的部分盲签名为(U,V)。
事实上,由 h*=H3(c)H3(c′)-1h′易知,V′= H3(c)(h′k′H3(c′)-1Ppub+SID),V=(h′k′Ppub+H3(c′)SID)+βhP,可以验证以下等式成立:
e(V,P)=e(hU+H3(c′)QID,Ppub)
因此,通过以上步骤,得到了一个合法的签名(ID,m,c′,(U,V)),成功地用c′替换了c。为了抵抗这种攻击,提出一个改进方案,不仅能抵抗攻击1,而且比文献[16]中的方案更高效。
4.1 系统设置
可信中心CA随机选取阶为q的加法交换群G1和乘法交换群G2,G1是GDH群。P是G1的一个生成元。构造双线性对e:G1×G1→G2。随机选择系统主密钥系统公钥为Ppub=sP,选择强hash函数和 H3:公开系统参数
P,Ppub,H1,H2,H3}。
4.2 用户密钥生成
用户 U发送身份 IDU∈{0,1}n给可信中心CA,CA计算QU=H1(ID),SU=sQU,通过安全信道将SU发送给用户 U。U验证 e(SU,P)=e(QU,Ppub)是否成立;若成立,接受SU作为签名私钥,否则拒绝。
4.3 签名
用户A为部分盲签名申请者,用户B为签名者;m为待签名消息,c∈{0,1}*为A和B协商的声明信息;部分盲签名方案如下:
(3)盲签名:B收到 h′后,计算 V′=(h′k′+
H3(c))Ppub+SB,将V′发给用户A。
(4)脱盲:A收到V′后,计算V=V′+βhPpub。消息m的部分盲签名为(c,U,V)。
4.4 验证
验证者收到部分盲签名(IDB,m,c,(U,V))后,先计算QB=H1(ID),h=H2(ID,m,c,U),H3(c),验证等式e(V,P)=e(hU+H3(c)P+QID,Ppub)是否成立。如果成立,(IDB,m,c,(U,V))为有效的部分盲签名,否则签名无效。
定理1 改进方案的验证等式是正确的。
证明:
所以验证等式e(V,P)=e(hU+H3(c)P+QB,Ppub)正确。
定理2 改进方案满足部分盲性。
证明:给定一个有效签名(ID,m,c,(U,V))和任一组部分盲签名发布过程中签名者保留下来的视图(k′,U′,h′,V′),令:
其中,h=H2(ID,m,c,U),式(1)和式(2)可以确定唯一一组解(α,β);而(ID,m,c,(U,V))是一个有效签名,从而有:
另一方面,有:
联立式(1)~式(4),有:
所以,e(V′+βhPpub,P)=e(V,P),即V=V′+ βhPpub;因此,如果消息m的盲化因子是 α,β,那么盲签名发布过程中签名者保留下来的签名视图(K′,U′,h′,V′)所对应的签名就是(IDB,m,c,(U,V));故在有效盲签名和任意视图之间都存在唯一的α和β,使得签名和视图相对应,即使签名者拥有无限的计算资源,也无法确定盲签名发布过程中的签名视图与签名之间的对应关系。
定理3 改进方案可以抵抗攻击1。
证明:在部分盲签名方案中,声明信息c被替换的主要原因是可以通过构造参数从签名中提取声明信息c。改进方案中,签名 V′=(h′k′+H3(c))Ppub+SB,如果攻击者在 h′中嵌入 H3(c),即 h′= H3(c)h*,则V′=H3(c)[(h*k′+1)Ppub+H3(c)-1SB],显然攻击者无法完整地将H3(c)提取出来。因此,改进方案可以抵抗攻击1。
定理4 如果一个适应性选择消息和身份攻击的伪造者可以在多项有界的时间 t内以不可忽略的优势Adν攻破改进方案,那么存在一个算法可以在多项式有界的时间t′内以不可忽略的优势Adν′求解CDHP问题;其中,t′=(t+t1qH1+t2qH2+t3qH3+分别是随机预言机H1,H2,H3的提问次数;qE是密钥提取次数;qS是签名询问次数;t1,t2,t3分别是询问一次随机预言机H1,H2,H3所需的时间;t4是一次密钥提取所需的时间;t5是一次签名询问的时间。
证明:假设存在一个攻击者A以概率Adν在时间t内攻破改进方案;下面构造一个算法 B解决CDHP问题。
算法B的输入是一个CDHP问题实例。已知P,χP,yP∈G1,其中,χ,y∈Z*q,目标是计算 χyP∈G1。为了充分利用攻击者A的攻击能力,算法B模拟挑战者与攻击者 A进行交互,回答攻击者 A的H1,H2,H3随机预言询问、密钥询问和签名询问。由于改进方案是对文献[16]的一种改进,因此,两者安全性分析非常类似,3个哈希询问以及密钥提取询问与原方案基本相同。具体过程如下:
(1)系统设置
选取阶为素数 q的加法交换群G1和乘法交换群G2,P是 G1的一个生成元。构造双线性对 e:G1×G1→G2。系统公钥为Ppub=χP,即用χ模拟系统主密钥,选择随机预言机 H1:{0,1}*→G1,H2:系统公开参数Params={G1,G2,q,P,Ppub,H1,H2,H3},将系统公开参数Params发送给攻击者A。
(2)H1询问
攻击者A至多能做qH1次H1询问,B通过维护由(IDi,QIDi,a)组成的一个列表L1仿真H1。B随机地选择K(1≤K≤qH1),记IDK=ID*。当B收到A关于IDi(1≤i≤qH1)的询问,B首先检查L1:
1)如果L1中已经存在项(IDi,QIDi,ai),则B将QIDi返回给A作为IDi的H1哈希值。
2)否则,A没有做过关于IDi的H1询问。若i= K,则B选取令QID*=b(yP);若i≠K,
(3)H2询问
A至多能做qH2次H2询问,B通过维护由(IDi,mi,ci,Ui,hi)组成的列表L2仿真H2。当B收到A关于(IDi,mi,ci,Ui)(1≤i≤qH2)的询问,B首先查询L2:若L2中已经存在项(IDi,mi,ci,Ui,hi),将hi作为回复返回给A;否则,B选取hi∈RZ*q,将hi作为回复返回给A,并将(IDi,mi,ci,Ui,hi)添加到L2中。
(4)H3询问
A至多能做 qH3次 H3询问,B通过维护由组成的列表L3仿真H3。当B收到A关于ci(1≤i≤qH3)的询问时,B首先检查L3:若L3中已经存在项那么 B将作为回复返回给 A。否则,B随机地选取hi∈RZ*q,将hi=H3(ci)作为回复返回给A,并将添加到L3中。
(5)密钥提取询问
A至多能做qE次密钥提取询问。当B收到A关于IDi(0≤i≤qE)的密钥提取询问(假设已经做过关于IDi的H1询问,否则先做关于IDi的H1询问),B从列表L1中找出项(IDi,QIDi,ai):若IDi≠ID*,B计算SIDi=χQIDi=χ(aiP)=ai(χP),将SIDi返回给A;否则,算法B终止。
(6)签名询问
A最多能做qS次签名询问。当B收到A关于的签名询问(假设已经做过关于IDi的H1询问和关于ci的H3询问,否则先做关于IDi的H1询问和关于ci的H3询问,且A没有做过关于IDi的密钥提取询问),B查询L1和L3,从中找出项(IDi,QIDi,ai)和(ci,);然后随机选取k,,计算若hi)已经在L2中,那么重新选取k和h,并计算U;计算并将添加到L2。B将σ=(U,V)作为回复返回给A。
因为:
(7)伪造
如果B没有终止,那么A在没有做过关于ID*的密钥提取询问和关于(ID*,m*,c*)的签名询问的条件下,以一个不可忽略的概率伪造一个关于消息(m*,c*)的签名(ID*,U,V)。根据分叉引理[17],通过对A哈希重放,B可以得到关于消息m*,c*的2个有效签名和(ID*,其中,QID*=byP,是随机预言机H1关于询问ID*的应答;h,h′是随机预言机H2关于询问(ID*,m*,c*,U)的应答;h~是随机预言机H3关于询问c*的应答,并且h≠h′。
(8)CDGHP问题的求解
联立上述两式,可得:
χyP即为算法 B的输出。因此,群 G1上的CDHP问题(P,χP,yP)得以解决。
以上描述了算法B的模拟过程,下面分析算法B模拟成功概率和所需的时间。挑战者与攻击者A进行1/Adν轮交互(挑战者与攻击者进行一轮交互包括qH1+qH2+qH3次随机预言机询问,qE次密钥询问,qs次签名询问)能够成功伪造一个合法的签名,所需时间为Adν;成功分叉的概率是;因此,算法 B成功输出的χyP的优势为,所需时间为:故定理4得证。
由于方案中计算资源消耗主要分布在签名发布和签名验证阶段,而用户密钥生成一次,可以用于多次签名,因此只考虑签名发布和签名验证阶段的时间复杂度。为了方便描述,用Tpair表示一次双线性运算所需的时间,用Tmul表示群G1中一次标量乘运算所需的时间,用Texp表示群G2中一次幂乘运算所需的时间,TH表示一次Map2Point哈希运算所需的时间。
其他的计算花费,如G1中的加法运算、G2中的乘法运算等相对Tmul,Tpair,Texp可忽略不计。
将改进方案与其他方案进行计算性能方面的比较,如表1所示。改进方案在签名发布阶段只有5次G1中的标量乘法运算,比文献[16]方案少了一次群G1中的标量乘运算;相对于文献[12]方案在签名发
布阶段具有明显优势;虽然,文献[11]方案在签名验证阶段比改进方案更高效,但是,其也存在类似文献[16]方案中的安全漏洞。具体数据比较如表1所示;因此,改进方案是一种较为安全高效的部分盲签名方案。
表1 计算复杂度比较
在文献[16]基于身份的部分盲签名方案基础上,本文提出一种新的安全高效的部分盲签名方案。通过调整签名和哈希函数的参数,解决了原方案中协商信息被消除替换的漏洞。但新方案的安全性依赖于哈希函数的随机性,且存在密钥托管问题。因此,下阶段的工作是在随机预言机模型和标准模型下,研究基于自证明公钥的部分盲签名方案。
[1] Chaum D.Blind Signature for Untraceable Payments[C]// Proceedings of Crypto’82.Berlin,Germany:Springer,1983:199-203.
[2] Chaum D.Security Without Identification:Transaction Systems to Make Big Brother Obsolete[J].Communications of the ACM,1985,28(10):1030-1044.
[3] Chaum D,Fiat A,Naor M.Untraceable Electronic Cash[C]//Proceedings of Crypto’88.Berlin,Germany: Springer,1988:319-327.
[4] Chaum D,Den B,Van E,et al.Efficient O ff-line Electronic Check[C]//Proceedings of Eurocrypt’89. Berlin,Germany:Springer,1990:294-301.
[5] Brands S.Untraceable Off-line Cash in Wallets with Observers[C]//Proceedings of Crypto’93.Berlin,Germany:Springer,1993:302-318.
[6] 孟江涛,冯登国,胡振宇.电子选举的安全协议[J].中国科学院研究生院学报,2002,19(3):295-305.
[7] 王文龙,王泽成,李志斌.基于椭圆曲线的电子选举协议[J].计算机工程,2003,29(22):144-145.
[8] Abe M,Fujisaki E.How to Date Blind Signatures[C]//Proceedings of Cryptology-Asiacrypt’96. Berlin,Germany:Springer-Verlag,1996:244-251.
[9] 辛向军,李发根,肖国镇.对几种部分盲签名方案的安全性分析与改进[J].西安电子科技大学学报,2006,33(6):953-955.
[10] 张 彤,王育民.几种部分盲签名的算法设计及其安全性分析[J].西安电子科技大学学报,2004,31(6):963-966.
[11] 崔 巍,辛 阳,胡程瑜,等.高效的基于身份的(受限)部分盲签名[J].北京邮电大学学报,2008,31(4):53-57.
[12] 李明祥,邓艳君,安广文.一种高效的基于身份的部分盲签名方案[J].计算机应用研究,2010,27(11):4299-4302.
[13] 黄茹芬,农 强,黄振杰.一个高效的无证书盲签名方案[J].计算机工程,2013,39(2):130-136.
[14] 汤鹏志,李晓雄,左黎明,等.高效安全无证书部分盲签名[J].计算机机工程与设计,2013,34(2):439-446.
[15] Shim K A.An ID-based Aggregate Signature Scheme with Constant Pairing Computations[J].Journal of System s and Software,2010,83(10):1873-1880.
[16] 何俊杰,王 娟,祁传达.安全高效的基于身份的部分盲签名方案[J].计算机应用,2012,32(5):1388-1391.
[17] Pointchevel D,Stern J.Security Proofs for Signature Schemes[C]//Proceedings of Eurocrypt’96.Berlin,Germany:Springer,1996:387-398.
编辑 顾逸斐
A Modified Scheme of Partially Blind Signature Based on ID
TANG Pengzhi,LIU Qiwen,ZUO Liming
(School of Science,East China Jiaotong University,Nanchang 330013,China)
The security of the existing ID-based partial blind signature scheme proposed is analyzed.Most schemes with the loophole that public consultations vulnerability information can be tampered with,the adversary can get rid of the partial blind property of the signature without being detected by multiplying the reverse of the partial blind factor to the blind message,and the adversary can forge the public consultations vulnerability information in the signature.To cope with the problem that the consultation public information may be forged in some schemes,it presents a modified ID-based partial blind signature scheme.Partially blind and unforgeable of the modified scheme are analyzed,and it proves that new scheme has partial blindness.The modified scheme has adaptive chosen ID and ciphertext security in the random oracle model,and has more efficiency than the previous partial blind signature schemes.
partially blind signature;ID-based;random oracle model;bilinear pairing;forgery
汤鹏志,刘启文,左黎明.一种基于身份的部分盲签名改进方案[J].计算机工程,2015,41(10):139-143.
英文引用格式:Tang Pengzhi,Liu Qiwen,Zuo Liming.A Modified Scheme of Partially Blind Signature Based on ID[J].Computer Engineering,2015,41(10):139-143.
1000-3428(2015)10-0139-05
A
TP301
10.3969/j.issn.1000-3428.2015.10.026
国家自然科学基金资助项目(61240025);江西省高校科技落地计划基金资助项目(KJLD12067);华东交通大学校立科研基金资助项目(11JC04)。
汤鹏志(1961-),男,教授,主研方向:信息安全;刘启文(通讯作者),硕士研究生;左黎明,副教授、硕士。
2014-08-25
2014-10-17E-mail:liuqiwengu@163.com