﻿ 可证明安全的基于身份的不可否认签名方案
 计算机应用   2016, Vol. 36 Issue (10): 2738-2741  DOI: 10.11772/j.issn.1001-9081.2016.10.2738 0

### 引用本文

WANG Xiong, DENG Lunzhi. Provably secure undeniable signature scheme based on identity[J]. JOURNAL OF COMPUTER APPLICATIONS, 2016, 36(10): 2738-2741. DOI: 10.11772/j.issn.1001-9081.2016.10.2738.

### 文章历史

Provably secure undeniable signature scheme based on identity
WANG Xiong, DENG Lunzhi
School of Mathematical Science, Guizhou Normal University, Guiyang Guizhou 550001, China
Abstract: Concerning the low efficiency of identity-based undeniable signature schemes, a new identity-based undeniable signature scheme was proposed. Under the assumption that it is hard to solve the Computational Bilinear Diffie-Hellman (CBDH) problem and the Decisional Bilinear Diffie-Hellman (DBDH) problem, the proposed scheme was proven to be unforgeable and invisible in the random oracle model, and it reduced the number of bilinear pairing operations. Analysis shows that the proposed scheme is more efficient than undeniable signature schemes proposed by Libert, Duan and Behnia, and it is more suitable for the computation-constrained environment.
Key words: identity-based cryptography    undeniable signature    bilinear pairing    random oracle model
0 引言

2004年,Libert等[3]首次提出了基于身份的不可否认签名方案,并在随机预言模型下给出了安全性证明;2006年,唐春明等[4]提出了一个使用双线性对构造基于身份的不可否认签名方案,但是,该方案的私钥是由两部分构成的,而且零知识证明系统的具体构造过程并没有在文中给出,最主要的是没有给出具体而严谨的数学证明过程,只是简要地分析了安全性。本文基于Libert等[3]构造的适应性攻击模型,提出了一个新的可证明安全的基于身份的不可否认签名方案,并在随机预言模型下给出了严谨的不可伪造性和不可见性证明；同时,通过对方案的计算效率分析可知,本文方案的计算效率更高,因而具实用价值。

1 预备知识 1.1 双线性对

G1是素数q阶加法循环群,G2是素数q阶乘法循环群,P是群G1的一个生成元。e:G1×G1G2是双线性映射,满足:

1) 双线性性:任取P,QG1,a,bZq*,有e(aP,bQ)=e(P,Q)ab

2) 非退化性:存在P,QG1,使得e(P,Q)≠1G2,其中:1G2是群G2的单位元。

3) 可计算性:对任意的P,QG1,存在一个高效的方法可计算e(P,Q)

1.2 数学问题

G1是素数q阶加法循环群,G2是素数q阶乘法循环群,P是群G1的一个生成元,给定一个双线性映射e:G1×G1G2

1) 计算双线性Diffie-Hellman(Computational Bilinear Diffie-Hellman,CBDH)问题:对给定的四元组(P,aP,bP,cP),其中a,b,cZq*,能否计算出e(P,P)abc

2) 判断双线性Diffie-Hellman(Decisional Bilinear Diffie-Hellman,DBDH)问题:对给定的五元组(P,aP,bP,cP,h),其中a,b,cZq*,hG2,判断h=e(P,P)abc是否成立。

2 安全模型

Hash函数查询:敌手F可以向挑战者B查询任何的Hash函数值。

 $Adv(D)=\left| \Pr [{b}'=b]-\frac{1}{2} \right|$
3 本文方案

1) 参数设置:给定安全参数k,私钥生成中心(Private Key Generator,PKG)生成两个素数q(q>2k)阶群GG1,PG的一个生成元,双线性映射e:G×GG1;选择主密钥sZq*,计算Ppub=sP,Z=e(P,P);选择四个Hash函数:H1:{0,1}*×GZq*,H2:{0,1}*×{0,1}*×G×G→G,H3,H4:{0,1}*Zq*。PKG公布系统参数: parmas={q,G,G1,P,e,Z,Ppub,H1,H2,H3,H4}。

2) 私钥生成:对于用户IDi,PKG任意选取tiZq*,计算Ti=tiP,di=H1(IDi,Ti),si=ti+sdi,然后通过安全通道将si传送给用户IDi

3) 签名:签名者IDA对消息m进行签名。IDA任意选取r∈Zq*,然后计算R=rP,F=H2(m,IDA,R,TA),ρ=e(F,R)sA。最后输出对消息m的签名σ=(ρ,R)

4) 确认协议:验证者IDB想要验证签名σ是消息m的有效签名,但是他需要签名者IDA的帮助才能够完成检验。他将(m,σ)和(IDB,TB)发送给IDA,IDA将通过以下的确认协议产生一个非交互式的指定验证者的证明,来证明签名σ是签名者IDA对消息m的有效签名。

IDA计算dB=H1(IDB,TB)。

IDA任意选取UG; y,vZq*,并计算Y= yP, M=e(P,U+TB+dBPpub),N=Zy,O=e(F,Y)

IDA计算h3=H3(M,N,O,m,R,σ)∈Zq*

IDA计算A=Y+(h3+v)sAR

IDA将(U,v,h3,A)发送给IDBIDB将作以下工作进行检验:

IDB计算

M′=e(P,U+TB+dBPpub)

N′=e(P,A)e(R,TA+dAPpub)-(h3+v)

O′= ρ-(h3+v)e(F,A)

IDB接受IDA的证明当且仅当h3=H3(M′,N′,O′,m,R,σ)。

5) 否认协议:为了证明IDB给出的签名σ不是IDA对消息m的有效签名,IDA将作以下工作:

IDA计算dB=H1(IDB,TB)。

IDA任意选取UG;v,αZq*,并计算M=e(P,U+TB+dBPpub),B=(e(F,R)sA)α

IDA用零知识的方式证明了一个二元组(I,α)∈G×Zq*是否满足:B=e(F,I)/ρα,e(P,I)=e(R,TA+dA·Ppub)α。要达到这个目标,IDA又必须作如下工作:

a) 任意选取jZq*,并计算J= jP,Y=Zje(R,TA+dAPpub)v,W=e(F,J)ρv

b) 计算 h4=H4(B,M,Y,W,m,R,σ)∈Zq*

c) 计算 Q=J+(h4+v)I,β=v-(h4+v)α;IDA将(B,U,v,h4,Q,β)发送给IDBIDB首先检验,若B=1,则IDB拒绝该证明;否则,IDB将作以下工作进行检验:

IDB计算

M′=e(P,U+TB+dBPpub)

Y′=e(P,Q)e(R,TA+dAPpub)β

W′=e(F,Q)ρβB-(h4+v);

IDB接受IDA的证明当且仅当h4=H4(B,M′,Y′,W′,m,R,σ)。

1) 完整性:协议的完整性在方案中是显然的。

2) 稳固性:首先作两个群同构: fP:GG1,fP(X)=e(X,P);gP:Zq*G,gP(x)=xP

3) 协议为指定验证者的零知识证明

4 安全性分析

F将对B进行多项式次数的各种查询。不失一般性,不妨设每次查询互不相同;F在将身份ID用作对其他查询之前,必先对ID进行H1查询。

H1查询:B以(ID,T,x,X)的格式设置列表L1。当F查询H1(ID,T)时,B将随机选取xZq*和一个数X∈{0,1},并记Pr[X=0]=δ1,则Pr[X=1]=1-δ1。若X=1,则B将以H1(ID,T)=xb回答F;若X=0,则B将以H1(ID,T)=x回答F。同时将(ID,T,x,X)储存在L1中。

H2查询:B以(m,ID,R,T,y,Y)的格式设置列表L2。当F查询H2(m,ID,R,T)时,B首先检查L2,如果L2中已存在(m,ID,R,T,y,Y),并且若Y=1,则B将以H2(m,ID,R,T)= y(cP)回答F;若Y=0,则B将以H2(m,ID,R,T)= yP回答F。如果L2中没有(m,ID,R,T,…),那么B将随机选取yZq*和一个数Y∈{0,1},并记Pr[Y=0]=δ2,则Pr[Y=1]=1-δ2。同时作同上一样的回答,并将(m,ID,R,T,y,Y)储存在L2中。

H3H4查询:B将以随机的方式回答H3H4查询,并将其结果分别储存在列表L3L4中。

1) 如果(m,IDA,R,TA,…)没有在L2中出现,那么B将会利用签名预言生成一个有效的签名σ=(ρ,R)。然后检查,若ρ′= ρ,则返回确认协议;否则,返回否认协议。

2) 如果(m,IDA,R,TA,y,Y)在L2中且Y=0,则B给出一个有效签名σ=(ρ=e(yR,TA+xPpub),R)。然后检查,若ρ′= ρ,则返回确认协议;否则,返回否认协议。

3) 如果(m,IDA,R,TA,y,Y)在L2中且Y=1,则BL1中找出(IDA,TA,x,X)。若X=1,则B输出失败并停止游戏;若X=0,则B给出一个有效签名σ=(ρ=e(y(cP),TA+xPpub)r,R)。然后检查,若ρ′= ρ,则返回确认协议;否则,返回否认协议。

D将对B进行多项式次数的各种查询。不失一般性,不妨设每次查询互不相同;D在将身份ID用作对其他查询之前,必先要对ID进行H1查询。在第一次查询时,除了对H2查询之外,其他查询同定理1中定义的查询相同。

H2查询:B以(m,ID,R,T,y,Y)的格式设置列表L2。当D查询H2(m,ID,R,T)时,B首先检查L2,如果L2中已存在(m,ID,R,T,y,Y),并且若Y=1,则B将以H2(m,ID,R,T)= y(cP)回答D;若Y=0,则B将以H2(m,ID,R,T)= yP回答D。如果L2中没有(m,ID,R,T,…),那么B将随机选取yZq*,将以H2(m,ID,R,T)= yP回答D。同时将(m,ID,R,T,y,0)储存在L2中。

5 效率分析

6 结语

 [1] SHAMIR A. Identity based cryptosystems and signature schemes[C]//Proceedings of CRYPTO 84 on Advances in Cryptology. Berlin: Springer, 1985: 47-53. (0) [2] 王文强, 陈少真. 一种基于身份的高效的环签名方案[J]. 计算机应用, 2009, 29 (11) : 2990-2997. ( WANG W Q, CHEN S Z. Efficient identity-based ring signature scheme[J]. Journal of Computer Applications, 2009, 29 (11) : 2990-2997. doi: 10.3724/SP.J.1087.2009.02990 ) (0) [3] LIBERT B, QUISQUATER J-J. Identity based undeniable signa-tures[C]//CT-RSA 2004: Proceedings of the 2004 Cryptographers' Track at the RSA Conference. Berlin: Springer, 2004: 112-125. http://cn.bing.com/academic/profile?id=1705735391&encoded=0&v=paper_preview&mkt=zh-cn (0) [4] 唐春明, 赵延孟. 使用双线性对构造基于身份的不可否认签名[J]. 深圳大学学报(理工版), 2006, 23 (1) : 85-89. ( TANG C M, ZHAO Y M. Identity-based undeniable signatures from bilinear pairings[J]. Journal of Shenzhen University (Science & Engineering), 2006, 23 (1) : 85-89. ) (0) [5] KANCHARRLA P K, GUMMADIDALA S, SAXENA A. Identity based strong designated verifier signature scheme[J]. Informatica, 2007, 18 (2) : 239-252. (0) [6] 褚万霞, 张建中. 高效的基于身份的盲签名方案[J]. 计算机工程与应用, 2010, 46 (36) : 112-113. ( CHU W X, ZHANG J Z. Efficient identity-based blind signature scheme[J]. Computer Engineering and Applications, 2010, 46 (36) : 112-113. ) (0) [7] CHAUM D, VAN ANTWERPEN H. Undeniable signatures[C]//Proceedings the CRYPTO 1989 on Advances in Cryptology. Berlin: Springer, 1990: 211-216. (0) [8] CHAUM D. Zero-knowledge undeniable signatures[C]//EUROCRYPT 1990: Proceedings of the 1990 Workshop on the Theory and Application of Cryptographic Techniques Aarhus. Berlin: Springer, 1991: 458-464. http://link.springer.com/chapter/10.1007/3-540-46877-3_41 (0) [9] 李昕, 刘建辉. 基于RSA的XML不可否认签名方法研究[J]. 计算机应用研究, 2009, 26 (5) : 1900-1907. ( LI X, LIU J H. Research of RSA-based XML undeniable signature method[J]. Application Research of Computers, 2009, 26 (5) : 1900-1907. ) (0) [10] LI F, GAO W, WANG Y, et al. Short convertible undeniable signature from pairing[J]. Journal of Software, 2013, 8 (12) : 2983-2990. (0) [11] 吴晨煌, 黄振杰. 代理不可否认签名[J]. 计算机应用, 2006, 26 (11) : 2592-2595. ( WU C H, HUANG Z J. Proxy undeniable signatures[J]. Journal of Computer Applications, 2006, 26 (11) : 2592-2595. ) (0) [12] DUAN S. Certificateless undeniable signature schemes[J]. Information Sciences, 2008, 178 (3) : 742-755. doi: 10.1016/j.ins.2007.08.009 (0) [13] BEHNIA R, HENG S-H, GAN C-S. An efficient certificateless undeniable signature scheme[J]. International Journal of Computer Mathematics, 2015, 92 (7) : 1313-1328. doi: 10.1080/00207160.2014.948869 (0) [14] DENG L, ZENG J, QU Y. Certificateless proxy signature from RSA[J]. Mathematical Problems in Engineering, 2014, 2014: Article ID 373690. (0)