0 引言

基于证书的数字签名需要将签名者身份和公钥通过数字证书绑定,从而证书储存、发布以及撤销等问题就需要考虑。与传统的基于证书的数字签名相比,基于身份的密码体制^[1]的公钥是用户的个人信息(如证件号、E-mail地址、居住地址等),而不再使用公钥证书,这样就避免了繁琐的证书管理问题,从而提高了管理效率。自此以后,许多的基于身份的密码体制签名方案相继出现,包括:环签名^[2]、不可否认签名^[3-4]、指定验证者签名^[5]、盲签名^[6]等。

与其他签名方案相比,不可否认签名方案^[7]的独特之处就在于如果没有签名者的合作,那么签名就不能得到验证。同时,为了防止签名者否认自己签过的有效签名,特意添加了一个否认协议。对于一个所谓的伪造签名,签名者要么选择拒绝验证它,要么执行否认协议验证其为伪造签名。因此,一个不可否认签名由三部分组成:签名算法、验证协议和否认协议。随着不可否认签名方案的问世,相继出现了不少不可否认签名方案:基于离散对数的不可否认签名方案^[7-8]、基于RSA体制的不可否认签名方案^[9]、可交换的不可否认签名方案^[10]、代理不可否认签名方案^[11]、无证书的不可否认签名方案^[12-13]等。

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

1 预备知识 1.1 双线性对

设G₁是素数q阶加法循环群,G₂是素数q阶乘法循环群,P是群G₁的一个生成元。e:G₁×G₁→G₂是双线性映射,满足:

1) 双线性性:任取P,Q∈G₁,a,b∈Z_q^*,有e(aP,bQ)=e(P,Q)^ab。

2) 非退化性:存在P,Q∈G₁,使得e(P,Q)≠1_G2,其中:1_G2是群G₂的单位元。

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

1.2 数学问题

设G₁是素数q阶加法循环群,G₂是素数q阶乘法循环群,P是群G₁的一个生成元,给定一个双线性映射e:G₁×G₁→G₂。

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

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

2 安全模型

定义1 如果概率多项式时间敌手赢得以下游戏是可以忽略的,那么称基于身份的不可否认签名方案具有不可伪造性。

系统初始化 挑战者B生成系统参数parameters,并将其发送给敌手F。

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

私钥查询 敌手F选择身份ID_i,将其发送给挑战者B。挑战者B执行私钥生成算法生成私钥s_i,并将其发送给敌手F。

签名查询 敌手F选择签名者的身份ID_i和消息m,将其发送给挑战者B。挑战者B执行签名算法生成签名σ,并将其发送给敌手F。

确认/否认查询 敌手F选择消息—签名对(m,σ′)和身份ID_i,将其发送给挑战者B。挑战者B执行确认/否认算法生成确认/否认协议,并将其结果发送给敌手F。

伪造 敌手F输出一个四元组(m^*,σ^*,ID^*,T^*),其中σ^*为身份ID^*在公钥T^*下对消息m^*的有效签名。如果敌手F没有查询过ID^*的私钥,并且没有查询过ID^*对m^*的签名,那么敌手F在游戏中获胜。

定义敌手F获胜的优势为:Adv(F)=Pr[F获胜]。

定义2 如果概率多项式时间敌手赢得以下游戏是可以忽略的,那么称基于身份的不可否认签名方案具有不可见性。

系统初始化 同定义1。

第一次查询 同定义1。

挑战 敌手D产生一个挑战(m^*,ID^*,T^*),并且对身份ID^*没有进行过私钥查询。挑战者B随机选取b∈{0,1},若b=1,则挑战者B发送有效签名σ^*给敌手D；否则,将随机的在签名空间中取一个签名σ^*发送给敌手D。

第二次查询 与第一次查询一样,敌手D执行多项式次数的适应性查询,但不能进行ID^*的私钥查询,以及(m^*,σ^*,ID^*,T^*)的确认/否认查询。

响应 敌手D输出b′∈{0,1},如果b′=b,则敌手D在游戏中获胜。

定义敌手D获胜的优势为:

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

3 本文方案

1) 参数设置:给定安全参数k,私钥生成中心(Private Key Generator,PKG)生成两个素数q(q>2^k)阶群G和G₁,P为G的一个生成元,双线性映射e:G×G→G₁;选择主密钥s∈Z_q^*,计算P_pub=sP,Z=e(P,P);选择四个Hash函数:H₁:{0,1}^*×G→Z_q^*,H₂:{0,1}^*×{0,1}^*×G×G→G,H₃,H₄:{0,1}^*→Z_q^*。PKG公布系统参数: parmas={q,G,G₁,P,e,Z,P_pub,H₁,H₂,H₃,H₄}。

2) 私钥生成:对于用户ID_i,PKG任意选取t_i∈Z_q^*,计算T_i=t_iP,d_i=H₁(ID_i,T_i),s_i=t_i+sd_i,然后通过安全通道将s_i传送给用户ID_i。

3) 签名:签名者ID_A对消息m进行签名。ID_A任意选取r∈Z_q^*,然后计算R=rP,F=H₂(m,ID_A,R,T_A),ρ=e(F,R)^s_A。最后输出对消息m的签名σ=(ρ,R)。

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

① ID_A计算d_B=H₁(ID_B,T_B)。

② ID_A任意选取U∈G; y,v∈Z_q^*,并计算Y= yP, M=e(P,U+T_B+d_BP_pub),N=Z^y,O=e(F,Y)。

③ ID_A计算h₃=H₃(M,N,O,m,R,σ)∈Z_q^*。

④ ID_A计算A=Y+(h₃+v)s_AR。

ID_A将(U,v,h₃,A)发送给ID_B。ID_B将作以下工作进行检验:

ID_B计算

M′=e(P,U+T_B+d_BP_pub)

N′=e(P,A)e(R,T_A+d_AP_pub)^-(h₃+v)

O′= ρ^-(h₃+v)e(F,A)

ID_B接受ID_A的证明当且仅当h₃=H₃(M′,N′,O′,m,R,σ)。

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

① ID_A计算d_B=H₁(ID_B,T_B)。

② ID_A任意选取U∈G;v,α∈Z_q^*,并计算M=e(P,U+T_B+d_BP_pub),B=(e(F,R)^s_A/ρ)^α。

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

a) 任意选取j∈Z_q^*,并计算J= jP,Y=Z^je(R,T_A+d_AP_pub)^v,W=e(F,J)ρ^v。

b) 计算 h₄=H₄(B,M,Y,W,m,R,σ)∈Z_q^*。

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

ID_B计算

M′=e(P,U+T_B+d_BP_pub)

Y′=e(P,Q)e(R,T_A+d_AP_pub)^β

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

ID_B接受ID_A的证明当且仅当h₄=H₄(B,M′,Y′,W′,m,R,σ)。

引理1 确认协议和否认协议都是一个完整的和稳固的指定验证者的零知识证明系统。

证明

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

2) 稳固性:首先作两个群同构: f_P:G→G₁,f_P(X)=e(X,P);g_P:Z_q^*→G,g_P(x)=xP。

确认协议的稳固性:假设证明者对同一个委托(M,N,O)可以产生两个正确的响应A和A′,并且有两个不同的挑战h₃和h′₃,则有e(P,(h₃-h′₃)^-1(A-A′))=e(R,T_A+d_AP_pub),e(F,(h₃-h′₃)^-1(A-A′))= ρ。由此可得: f_P^-1(e(R,T_A+d_AP_pub))=(h₃-h′₃)^-1(A-A′)= f_F^-1(ρ),进一步可得g_R(f_P^-1(e(R,T_A+d_AP_pub)))=g_R(f_F^-1(ρ))。

否认协议的稳固性:如果证明者能够产生满足否认协议中的I和α,那么根据双线性对的性质可得:I=αf_P^-1(e(R,T_A+d_AP_pub)),从而可得: B=e(F,α f_P^-1(e(R,T_A+d_AP_pub)))/ρ^α。当B≠1,则有e(F,α f_P^-1(e(R,T_A+d_A·P_pub)))/ρ^α≠1,即e(F,f_P^-1(e(R,T_A+d_AP_pub)))≠ρ,从而可得该签名ρ是一个无效的签名。

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

由于确认协议和否认协议的证法类似,本文以确认协议为例进行说明。

首先选取一个门限委托Commit(U)=e(P,U+T_B+d_AP_pub),ID_B将用他的私钥s_B来计算委托碰撞。给出(U,v,A,h₃),ID_B将会找出(U′,v,A,h′₃),使得Commit(U)=Commit(U′)。这样虽然ID_B能用他的私钥来模仿一个确认/否认协议的副本,但是他不能说服第三方接受这是一个有效或无效的签名。下面给出ID_B如何产生一个确认协议:

给出一个二元组(m,σ=(ρ,R,T_A,L_A)),ID_B选取U′∈G,h′₃∈Z_q^*,并计算M=e(P,U′),N=e(P,A)e(R,T_A+d_AP_pub)^h′₃,O= ρ^h′₃e(H₂(m,ID_A,R,T_A),A),h₃=H₃(M,N,O,m,R,σ),然后计算v=-h₃-h′₃,U=U′-s_BP,其中s_B是ID_B的私钥。这样ID_B用自己的私钥s_B很容易建立一个(U,v,h₃,A)的有效证明。

4 安全性分析

定理1 在随机预言模型下,如果CBDH问题是难解的,那么该方案对敌手F的攻击是存在不可伪造防备的。

证明 假设存在一个敌手F能以ε_F的优势给出一个有效的伪造签名,那么存在一个算法B能以ε_B的优势解决一个随机的(P,aP,bP,cP)CBDH问题。B作为F的一个挑战者,可以给F提供系统参数parmas=(q,G,G₁,P,Z,P_pub=aP,e,H₁,H₂,H₃,H₄),其中B也不知道a。

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

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

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

H₃、H₄查询:B将以随机的方式回答H₃、H₄查询,并将其结果分别储存在列表L₃和L₄中。

私钥查询:当F对身份ID作私钥查询时,B先从L₁中找出(ID,T,x,X)。若X=1,则输出失败并停止游戏;若X=0,则B以(T+xP_pub)作为私钥回答F。

签名查询:当F对身份ID和消息m查询时,B将随机选取r∈Z_q^*,计算R=rP,并检查如果L₂中已存在(m,ID,R,T,…),那么重新的随机选取r∈Z_q^*,计算R=rP,直到L₂中没有(m,ID,R,T,…)为止。当r被找到后,B随机选取y∈Z_q^*,并将(m,ID,R,T,y,0)储存到L₂中,此时H₂(m,ID,R,T)= yP。最后,B计算ρ=e(yR,T+x·P_pub),并给出一个签名σ=(ρ,R)。

确认/否认查询:当F对(m,σ′=(ρ′,R),T_A,ID_A,ID_B)进行确认/否认查询时,其中ID_A是所谓的签名者,ID_B是所谓的验证者。B将会有以下三种回答方式:

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

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

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

在游戏最后,F输出一个四元组(m^*,σ^*,ID^*,T^*),其中σ^*=(ρ^*,R^*),它是所谓的签名者ID^*对消息m^*在公钥T^*下的有效签名。这时,B将在L₁和L₂中找出(ID^*,T^*,x^*,X)和(m^*,ID^*,R^*,T^*,y^*,Y)。若X=0或Y=0,则B输出失败并停止游戏;若L₂中没有(m^*,ID^*,R^*,T^*,y^*,Y),则B输出失败并停止游戏。否则,σ^*是一个有效的签名。然后B计算${{\frac{{{\rho }^{*}}}{e\left( {{r}^{*}}{{y}^{*}}\left( cP \right),{{T}^{*}} \right)}}^{\frac{1}{{{r}^{*}}{{x}^{*}}{{y}^{*}}}}}$,即可得到e(P,P)^abc,从而解决了假设中的(P,aP,bP,cP)CBDH问题。

为了计算B成功的概率,本文设在时间t内,敌手F至多进行了q_H1次H₁查询,q_H2次H₂查询,q_H3次H₃查询,q_H4次H₄查询,q_E次私钥查询,q_s次签名查询,q_CD次确认/否认协议查询。首先给出B失败的情况:在进行私钥查询时,若H₁(ID,T)=xb,则失败;在进行确认/否认协议查询时,若H₁(ID^*,T^*)=x^*b且H₂(m^*,ID^*,R^*,T^*)= y^*(cP),则失败;在伪造(m^*,σ^*,ID^*,T^*)时,若H₁(ID^*,T^*)=x^*或H₂(m^*,ID^*,R^*,T^*)= y^*P。很容易算得B能够避免这些失败的概率为δ₁^q_E(1-δ₁)δ₂^q_CD(1-δ₂),其中δ₁和δ₂最大值分别为$\frac{{{q}_{E}}}{{{q}_{E}}+1}、\frac{{{q}_{CD}}}{{{q}_{CD}}+1}$,从而可得δ₁^q_E(1-δ₁)δ₂^q_CD(1-δ₂)≈$\frac{1}{{{e}^{2}}({{q}_{E}}+1)({{q}_{CD}}+1)}$，其中e为自然常数。同时,F没有查询H₂(m^*,ID^*,R^*,T^*)的概率为1/q。还有B在模仿确认/否认协议中产生碰撞的概率为(q_H3+q_CD)/q(假设q_H3≈q_H4)。通过以上分析,可以得出B成功的优势ε_B至少为$\frac{{{\varepsilon }_{F}}-(2{{q}_{{{H}_{3}}}}+{{q}_{CD}}+1)/q}{{{e}^{2}}({{q}_{E}}+1)({{q}_{CD}}+1)}$

定理2 在随机预言模型下,如果DBDH问题是难解的,那么该方案对敌手D的攻击是存在不可见防备的。

证明 假设存在一个敌手D能以ε_D的优势在没有签名者帮助下区分一个签名是否有效,那么存在一个算法B能以ε_B的优势解决一个随机的(P,aP,bP,cP,h)DBDH问题。B作为D的一个挑战者,可以给D提供系统参数parmas=(q,G,G₁,P,P_pub=aP,Z,e,H₁,H₂,H₃,H₄),其中B也不知道a。

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

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

在第一次查询之后,D输出一个三元组(m^*,ID^*,T^*),希望由此建立一个挑战。那么B将从L₁中找出(ID^*,T^*,x,X),若X=0,则输出失败并停止游戏。否则,B随机选取r^*∈Z_q^*,再计算R^*=r^*P,并检查L₂中是否已存在(m^*,ID^*,R^*,T^*,…),存在则重新随机选取r^*∈Z_q^*,计算R^*=r^*P,直到L₂中没有(m^*,ID^*,R^*,T^*,…)为止。当r^*被找到后,B随机选取y^*∈Z_q^*,并将(m^*,ID^*,R^*,T^*,y^*,1)储存到L₂中,此时H₂(m^*,ID^*,R^*,T^*)= y^*(cP)。B计算$\frac{{{\rho }^{*}}}{e({{r}^{*}}{{y}^{*}}(cP),{{T}^{*}})}={{h}^{{{r}^{*}}{{x}^{*}}{{y}^{*}}}}$,并给出一个挑战签名σ^*=(ρ^*,R^*)。由此可得如果D能够区分一个签名的有效性,那么h=e(P,P)^abc,从而σ^*就一定是ID^*对m^*的有效签名。

挑战阶段结束后,D开始第二次查询,但是他不能进行ID^*的私钥查询以及(m^*,σ^*,ID^*,T^*)的确认/否认查询。

最后,D输出一个b′∈{0,1}。若D认为该挑战签名是有效的,则输出b′=1,那么B也输出1意味着(P,aP,bP,cP,h)是一个有效的DBDH元组。若D认为该挑战签名是无效的,则输出b′=0,那么B也输出0意味着(P,aP,bP,cP,h)是一个无效的DBDH元组。这就表明如果D能够区分一个挑战签名是否有效,那么B能够成功区分一个DBDH元组的是否有效。

为了计算B成功的概率,本文设在时间t内,敌手D至多进行了q_H1次H₁查询,q_H2次H₂查询,q_H3次H₃查询,q_H4次H₄查询,q_E次私钥查询,q_s次签名查询,q_CD次确认/否认协议查询。首先给出B失败的情况:在进行私钥查询时,若H₁(ID,T)=xb,则失败;在挑战阶段,若B以H₁(ID^*,T^*)=x^*回答D,则失败。很容易算得B能够避免这些失败的概率为δ₁(^q_E1-δ₁),其中δ₁最大值为q_E/(q_E+1),从而可得δ₁^q_E(1-δ₁)≈1/e(q_E+1)。通过以上分析,可以得出B成功的优势ε_B至少为ε_De(q_E+1)。

5 效率分析

在密码学运算中,双线性对运算的成本远大于椭圆曲线上的点乘运算的成本。将本文方案与其他已有的不可否认签名方案进行了计算性能方面的比较,比较结果如表 1所示。为了更清晰地反映计算效率,通过引用文献^[14]中的密码运算时间,即一次双线性对的运算时间为20.01ms,一次基于双线性对的点乘运算的运算时间为6.38ms,进而用了一种简单的方式进行了效率比较,例如文献^[3]方案中用了24次双线对运算,16次基于双线性对的点乘运算,则执行一次方案所消耗的时间为20.01×24+6.38×16=582.32ms。这样,从表 1中可以直观看出,本文方案执行一次所消耗的时间是最少的,因而计算效率更高。

6 结语

本文提出了一个新的基于身份的不可否认签名方案,在随机预言模型下证明了其不可伪造性和不可见性。通过与以往提出的方案相比,双线性对使用的次数有所减少,因而计算效率更高,更有实用价值。