第31卷第1期通信学报V ol.31No.1 2010年1月Journal on Communications January 2010 安全的无可信PKG的部分盲签名方案
冯涛1,2,3，彭伟1，马建峰3
(1. 兰州理工大学计算机与通信学院, 甘肃兰州 730050;
2. 福建师范大学网络安全与密码技术重点实验室, 福建福州 350007;
3. 西安电子科技大学计算机网|络与信息安全教育部重点实验室, 陕西西安 710071)
摘要：利用gap Diffie-Hellman(GDH)群，在部分盲签名机制的基础上，提出了一个有效的基于身份的无可信私钥生成中心(PKG，private key generator)的部分盲签名方案。方案中PKG不能够伪造合法用户的签名，因为它只能生成一部分私钥。在随机预言模型下，新方案能抵抗适应性选择消息攻击和身份攻击下的存在性伪造，其安全性依赖于CDHP问题。该方案满足正确性和部分盲性，与Chow方案相比具有较高的效率。
关键词：基于身份的签名；密钥托管；双线性对；部分盲签名
中图分类号：TP309 文献标识码：A 文章编号：1000−436X(2010)01-0128-07
Provably cure partially blind signature without trusted PKG
FENG Tao1,2,3，PENG Wei1，MA Jian-feng3
石肖念什么(1.School of Computer and Communication, Lanzhou University of Technology, Lanzhou 730050, China;
2. Key Lab of Network Security and Cryptology, Fujian Normal University, Fuzhou 350007, China;
富士苹果图片
3. Ministry of Education Key Laboratory of Computer Networks and Information Security, Xidian University, Xi’an 710071, China)
Abstract: Using gap Diffie-Hellman groups, bad partially blind signature scheme, an efficient ID-bad partially blind signature scheme without trusted private key generator (PKG) was propod. In this scheme, PKG was prevented from forging a legal ur’s signature becau it only generated partial private key. Under the random oracle model, the pro-pod scheme was proved to be cure against existential forgery on adaptively chon message and ID attack. The cu-rity of scheme relied on the hardness of the computational Diffie-Hellman problem (CDHP). The propod scheme satis-fies curity properties: correctness and partial blindness. Compared with the Chow et al.’s scheme, the new scheme needs less computational cost and is more efficient.
Key words: ID-bad signature; key escrow; bilinear pairing; partially blind signature
收稿日期：2009-09-02；修回日期：2009-12-21
基金项目：国家高技术研究发展计划(“863”计划)基金资助项目(2007AA01Z429)；国家自然科学基金资助项目(60972078)；甘肃省高等学校基本科研业务费基金资助项目(0914ZTB186)；甘肃省自然科学基金资助项目(2007GS04823)；兰州理工大学博士基金资助项目(BS14200901)；网络安全与密码技术福建省高校重点实验室开放课题(09A006)
Foundation Items: The National High Technology Rearch and Development Program of China (863 Program)(2007AA01Z429); The National Natural Science Foundation of China(60972078); Universities Basic Scientific Rearch Operation Cost of Gansu Prov-ince(0914ZTB186); The Natural Science Foundation of Gansu Province (2007GS04823); The Ph.D. Programs Foundation of Lanzhou University of Technology (BS14200901); Funds of Key Lab of Fujian Province University Network Security and Cryptology (09A006)
第1期冯涛等：安全的无可信PKG的部分盲签名方案·129·
1引言
学潮汕话
传统的基于PKI的密码体制中，用户的公钥与其身份之间的绑定关系是通过数字证书形式来获得的，证书管理过程需要很大的计算量和较强的存储能力。为简化复杂的证书管理，Shamir提出了基于身份的密码体制(IBC, ID bad cryptosystem)[1]，该系统中用户的公钥直接从其身份信息(如姓名、E-mail地址等)得到，而私钥则是由一个称为私钥生成中心(PKG, private key generator)的可信方生成。但是PKG利用系统范围内的主密钥为用户生成私钥，不可避免地导致了IBC系统所固有的密钥托管问题，即PKG知道所有用户的私钥。由于在许多特定的应用环境下(比如ad hoc网络)一个可被小组所有成员信任的可信中心并不存在，或者PKG被攻陷后会给系统带来严重的后果，所以设计基于身份的高效、安全的无可信中心的IBC方案就显得很有吸引力。
近年来，双线性对成为构造基于身份的密码学方案的重要工具，Hess在文献[2]中提出了一种可证明安全的IBS签名方案。随后Cha和Cheon[3]提出了一种基于GDH群和身份的签名机制，同时在随机预言模型下证明了该机制能抵抗适应性选择消息和固定ID的存在性伪造攻击。Al−Riyami等人提出了一个无证书的公钥加密方案(CL−PKE) [4]，其安全性是由CDHP的困难性来保证的。文献[5]通过将2个部分公钥绑定一个相同的ID，提出了一个基于身份的无可信中心的签名方案。
盲签名是Chaum[6]提出的用户与签名人之间的一个交互协议，该签名过程与一般的数字签名的不同之处在于签名者并不知道他所签发文件的具体内容，签名者也不可能将签名过程与最终所得的签名对应起来。盲签名的这种性质称为盲性，这种特性使得盲签名这种技术被广泛应用于具有匿名性要求的领
域(如电子支付或匿名的电子选举等)，这样可以较好地保护人们的隐私，确保网上提交的信息不被第三方窃取。然而在完全盲签名中，签名者不知道最终签名的任何信息，因而这样的签名系统是不完善的，可能造成签名被非法使用等问题。理想的盲签名方案将致力于解决匿名性和可控性之间的矛盾，部分盲签名[7]克服了完全盲签名的缺点。部分盲签名允许签名者将协商好的公共信息嵌入到签名中，以便在签名者不知道所签署消息具体内容情况下有效保护签名者的合法权益。
自从Abe和Fujisaki[7]提出了第一个基于RSA 的部分盲签名方案后，各种基于不同数学难题的部分盲签名方案相继被提出。Zhang等提出了一个基于双线性对的部分盲签名方案[8]；Okamoto[9]提出了在标准模型下安全的基于双线性对的部分盲签名方案。然而以上各种方案都不是基于身份的密码系统，Zhang和Kim提出了基于身份的盲签名方案[10]；Chen等人首次构造了一个可证明安全的基于身份的限制性部分盲签名方案[11]；Chow等人在文献[12]提出了第一个基于身份的部分盲签名方案，并在随机预言机模型下是可证明安全的；文献[13]在此基础上给出了具有较高效率的部分盲签名方案；张学军在基于身份无可信PKG签名的基础上提出一个基于身份的无可信PKG的盲签名方案[14]，并进行了安全性分析。
在基于身份的盲签名系统中，用m表示用户待签名消息，而c表示用户和签名者协商后的消息。根据系统是否存在可信任PKG，可以将其分为以下4类并将其总结如表1所示。
表1基于身份的盲签名方案的分类
可信PKG 无可信PKG
完全盲签名
用1个私钥对m签名,
如文献[10]方案
用2个私钥对m签名,
如文献[14]方案
部分盲签名
用1个私钥对(m,c)签名,
如文献[12,13]方案
用2个私钥对(m,c)签名,
本文研究
在文献[12,13]方案中系统必须无条件信任PKG，由于PKG可以使用系统的主密钥计算出任意一个签名者的私钥，从而伪造系统内合法用户有效的签名而且验证方无法判断PKG是否有欺骗行为。为解决以上不足，本文在现有方案的基础上引入2个签名私钥进行部分盲签名的研究，提出了一个基于身份的无可信PKG的部分盲签名方案，并证明了其安全性。
2预备知识
2.1双线性对
设G1是由P生成的循环加法群，其阶为素数q；G2是具有相同阶q的乘法循环群。双线性对是指具有下列性质的映射e: G1×G1→G2：
中国存款利率1) 双线性：e(aP,bQ)=e(P,Q)ab，对所有P,Q∈G1
和所有a,b∈*
q
Z；
2) 非退化性：存在P,Q∈G1使得e(P,Q)≠1；
·130·通信学报第31卷
3) 可计算性：存在有效算法可以计算e(P,Q)，对所有P,Q∈G1。
群G1可以取有限域上的超奇异椭圆曲线或超椭圆曲线，线性对可以用超奇异椭圆曲线上的Weil 对或经改造的Tate对来构造。火歌词
2.2 相关数学问题
设群G1是q阶循环加法群，P为G1的生成元，可定义以下数学问题。
1) 离散对数问题(DLP)：给定P,Q∈G1，找出正整数n∈*
q
Z，使得P=nQ。
2) 判定Diffie-Hellman问题(DDHP)：给定P,aP,bP,cP∈G1，其中a,b,c∈*q Z，判断c≡ab(mod q)是否成立。
沂水地下大峡谷3) 计算Diffie-Hellman问题(CDHP)：给定P,aP,bP∈G1，对a,b∈*q Z，求出abP。
在本文中，我们认为离散对数问题(DLP)和计算Diffie-Hellman问题(CDHP)是难解的。
定义1 gap Diffie-Hellman群(GDH)：G1中如果存在多项式时间算法可以解决DDHP，但计算CDHP是困难的，则称群G1为gap Diffie-Hellman 群。
3基于身份的无可信PKG的部分盲签名3.1参数描述
1) 一个明文空间M：M={M1, M2}
M1表示用户待签名消息的集合，而M2表示用户和签名者协商后的消息集合；
2) 一个身份空间ID：所有可能的参与者的身份的集合；
3) 一个签名空间Δ：Δ={Δ1, Δ2}
Δ1表示签名者对盲化之后的消息所有可能的签名组成的集合；
Δ2表示用户对签名者所作的签名脱盲之后所有可能的签名组成的集合；
4) 一个签名私有密钥空间X:X={X1, X2}是用来生成签名的可能私钥集合
X1是由签名者生成的可能的部分私钥集合；
X2是由PKG生成的可能的部分私钥集合；
5) 一个验证公开密钥空间Y:Y={Y1,Y2}用来验证签名的可能公钥集合
Y1是由签名者生成的可能的部分公钥集合；Y2是由PKG生成的可能的部分公钥集合。3.2 基于身份的无可信PKG的部分盲签名方案的
形式化描述
定义2 基于身份的无可信PKG的部分盲签名方案由4个部分：Setup、Extract、Issue、V erify组成。
Setup系统初始化算法
k→(parameters, x PKG, y PKG)，输入安全参数k，PKG输出主密钥x PKG、系统公钥y PKG以及相应的系统参数；PKG保密x PKG公开系统参数和y PKG。
Extract 密钥生成算法
1) Gen X1：l→X1；输入安全参数l，具有身份为id的签名者生成自己的部分私钥x1∈X1。
2) Gen Y1：X1→Y1；签名者依据公开参数和x1计算出自己的部分公钥y1∈Y1。
3) Gen Y2：ID×Y1→Y2；PKG根据y1计算签名者的部分公钥y2∈Y2。
4) Gen X2：Y2→X2；PKG根据y2计算签名者的部分私钥x2∈X2，并通过安全的信道将x2发送给签名者。于是身份为id∈ID的签名者得到自己的私钥对(x1,x2)和公钥对(y1,y2)。
Issue签名过程是一个签名者与用户之间的概率多项式时间的交互式签名协议，假定m1∈M1是用户待签名信息，定义签名算法如下：
1) Agree：签名者和用户共同协商一个公共信息m2∈M2。
2) Blind：用户任意选定随机数r，输入(r,m1,m2)该算法输出一个被盲化了的消息m′。
3) Sign：当签名者收到m′后，输入(m′,x1,x2)该算法输出一个盲签名σ′∈Δ1。
4) Unblind：当用户收到盲签名σ′后，输入2)中生成的随机数r和σ′，脱盲得到用户签名σ∈Δ2。
Verify 验证算法
Verify：M×Δ2×Y→{True, Fal}；也即Verify(id, m1,m2,y1,y2,σ)={True, Fal}。如果上式验证成功则输出True，否则输出Fal。
3.3 基于身份的无可信PKG的部分盲签名方案的
伪造攻击模型
定义3根据PKG在部分盲签名协议中所扮演的不同角色，定义了以下3种情形下的攻击模型。
1) 情形1：在协议的执行过程中，PKG不会被攻击者腐败，PKG按照协议的要求完成各个步骤，同时保密自己的所有输入、输出及中间结果。
2) 情形2：在协议的执行过程中，PKG完全按照协议的要求完成协议的各个步骤，但是PKG可
第1期冯涛等：安全的无可信PKG的部分盲签名方案·131·
能将签名者的部分私钥x2泄漏给攻击者。
3) 情形3：在协议的执行过程中，PKG可以假冒具有身份id的合法签名者，伪造用户私钥对(x1,x2)，并泄漏给攻击者。
对数字签名最一般的攻击是适应性选择消息攻击，适应性攻击者拥有目标用户的公钥，并且可以将该用户用作预言机签名服务的提供者，对它选择的任何消息签名。然后攻击者根据收集到的消息签名对，
适应性改写它的提问。在提问了足够多的适应性选择消息并得到相应的签名之后，这个攻击者的目标是输出一个对目标用户的公钥有效的消息签名对。
论语全文原文如果一个基于身份的无可信PKG部分盲签名方案能够抵抗适应性选择消息攻击和ID攻击下的存在性伪造，则称该方案是安全的。也即在下面的游戏中不存在多项式时间算法A通过借助挑战者C 而能够以一个不可忽略的概率优势赢得以下游戏。
Setup：首先C执行Setup算法，然后将系统参数发送给攻击者A。
Attack：攻击者A以适应性的方式进行如下几类询问。
1) Hash function query：C对输入的问题进行杂凑运算，并将计算的值发送给A。
2) Extract query：对于给定身份信息id及其公钥(y1,y2)，C返回对应于id的部分私钥x2，其中x2是由算法GenX2生成的。
3) Issue query：对于给定身份信息id和消息(m1,m2)，C返回一个由算法Issue计算生成的签名σ，其中σ=Issue(m1,m2,x1,x2)，并将σ发送给攻击者A。
Forgery：最后攻击者A输出(id,m1,m2,σ)，如果(id,m1,m2)和id在Extract和Issue询问中都没有出现过，并且在定义3的各种情形下，满足下式：
Verify(id,m1,m2,y1,y2,σ)=True
即σ是消息(m1,m2)对应id的有效签名，则称攻击者A赢得了游戏。
4高效的无可信PKG的部分盲签名方案
设e:G1×G1→G2是一个双线性对，且满足2.1节中的各种性质。
Setup：PKG随机选取一整数s PKG∈*q Z，计算
出系统公钥Q PKG=s PKG P，并选择以下强无碰撞函数H1:{0,1}*→G1,H2:{0,1}*×G1→*q Z和H3:{0,1}*→G1。然后PKG将s PKG作为系统私钥保存，并且公开系统参数parameters={G1,G2,e,P,q,Q PKG,H1,H2,H3}。
Extract：假定id表示签名者的唯一可识别的身份，PKG对其进行物理鉴定确信id具有唯一性。签名者选取s1∈*q Z作为其第一部分私钥，然后计算
Q1=s1P并发送Q1给PKG。PKG计算出S2=s PKG Q2，其中Q2=H1(id,Q1)并将S2发送给签名者，于是签名者得到其私钥对(s1,S2)和公钥对(Q1,Q2)。
Issue：假设用户要得到消息m的部分盲签名，c为用户和签名者事先协商的公共信息。基于身份的无可信PKG部分盲签名由以下步骤组成。
1) 签名者选取一个随机数r∈*q Z，计算U=rQ2，并把U发送给请求用户。
2) 用户随机选取α,β∈*q Z，计算U′=αU+αβQ2，
w=α−1H2(m||c,U′)+β及R=αQ1，将w发送给签名者。
3) 签名者计算V=S2(r+w)+s1H3(c)，将V返回
给用户。
4) 用户收到V后计算V′=αV，则(U′,V′,R)为签名人对消息(m,c)的部分盲签名，其中c为公共信息。Issue过程中用户和签名者之间的交互过程如下：
α,β∈*q Z
R=αQ1
U′=αU+αβQ2
w=α-1H2(m||c,U′)+β
U
V V=S2(r+w)+s1H3(c)
r∈*q Z,U=rQ2
w
V′=αV
用户签名者
Verify：验证者收到身份为id的签名者对(m,c)的签名(U′,V′,R)，验证如下：埃菲尔铁塔图片大全
e(V′,P)=e(U′+H2(m||c,U′)Q2,Q PKG)e(H3(c),R)
若该式成立则通过验证，否则失败。
5 新方案的安全性和执行效率分析
5.1安全性
定理1 新方案满足正确性。
证明
e(V′,P)
=e(α (r+w)S2+αs1H3(c),P)
=e((αr+αβ+H2(m||c,U′))Q2,s PKG P)e(H3(c),αs1P)
·132· 通 信 学 报 第31卷
=e (αU+αβQ 2+H 2(m ||c ,U ′)Q 2,Q PKG )e (H 3(c ),αQ 1) =e (U ′+H 2(m ||c ,U ′)Q 2,Q PKG )e (H 3(c ),R ) 定理2 新方案具有部分盲性。
证明 关于部分盲性的定义可以参考文献[12]中的定义7，本文提出的基于身份的部分盲签名方案满足部分盲特性。其证明思路如下：对于任意给定的一个有效的部分盲签名(m ,c ,U ′,V ′,R )以及在部分盲签名发布中产生的中间变量(U ,V ,w )，总是存在一对唯一的盲因子，因为α,β是随机选择的，所以方案的盲性满足。证明如下。
对于给定的(U ′,V ′,R )和部分盲签名发布中产生的中间变量(U ,V ,w )，考虑如下的方程：
V ′=αV (1) w =α−1H 2(m ||c ,U ′)+β (2)
U ′=αU +αβQ 2 (3) 根据以上3个等式可知，一定存在唯一的
α∈*q Z 使得式(1)成立；
进一步可以通过等式(2)计算出唯一的β，即β=w −α−1H 2(m ||c ,U ′)。因为(U ′,V ′,R )是有效的部分盲签名，因此： e (V ′,P )=e (U ′+H 2(m ||c ,U ′)Q 2,Q PKG )e (H 3(c ),R ) 成立，可以推导出下式也成立：
e (V ′,P )=e (U ′,Q PKG )e (H 3(c ),R )e (H 2(m ||c ,U ′)Q 2,Q PKG )
下面考虑α, β是否满足式(3)：
e (αU +αβQ 2,Q PKG )
=e (αU+α(w −α−1H 2(m ||c ,U ′))Q 2,Q PKG )
=e (α(r+w )Q 2,Q PKG )e (H 2(m ||c ,U ′)Q 2,Q PKG )−1 =e (α(r+w )S 2,P )e (H 2(m ||c ,U ′)Q 2,Q PK
G )−1
=e (α(r+w )S 2,P )e (H 3(c ),R )e (V ′,P )−1e (U ′,Q PKG ) =e (α (r+w )S 2+αs 1H 3(c ),P )e (V ′,P ) −1e (U ′,Q PKG ) =e (αV ,P )e (V ′,P )−1e (U ′,Q PKG ) =e (U ′,Q PKG )
由双线性映射的非退化性可知：
e (U ′,Q PKG )=e (αU+αβQ 2,Q PKG )⇔U ′=αU+αβQ 2 因此，盲因子α,β在部分盲签名的生成中总是存在，所以，部分盲签名的生成协议是无链接的，由文献[12]中部分盲性定义可知，本方案具有部分盲性。
定理3 新方案能够抵抗适应性选择消息和身份攻击下的存在性伪造。
证明 本定理的证明方法参考了Pointcheval 在文献[15]中对数字签名方案不可伪造性的证明过程，并且在Forking Lemma [15]的基础上进行了本方案的安全性讨论。由于给出的方案无需可信的PKG ，攻击者A 可以联合不诚实的PKG 共同伪造签名信息。下面分3种情况进行讨论。
情形1 PKG 是诚实的，攻击者A 伪造一个有效签名。
假定H 1、H 2和H 3是随机预言机，A 是一个概率多项式时间图灵机。假设A 可以向随机预言机H 1、
H 2和H 3分别询问q 1、q 2和q 3个问题；向Issue 询问q s 个问题，在时间界限T 内生成一个有效的签名(U ′,V ′,R )。
首先C 把系统公共参数parameters 发送给A ，其中将aP 作为系统公钥发送给A ，用a 来模拟系统主密钥。C 试图通过模拟所有的预言机来得到一个对应于任意选定的值r ∈*q Z ，能够像真正的签名者一样对任意的消息(m ,c )进行签名。A 可以进行下
列询问。
H 1−Queries ：A 可以在任何时候向随机预言机H 1询问。C 通过将二元组(Σi ,Q (2,i ))保存到列表L 1来模拟随机预言机，其中Σi 是一个二元组(id i ,Q (1,i ))。当输入询问Σ，C 回答：
1) 当询问Σ已经在表L 1中，输出相同的值； 2) 否则C 随机选择一个新值输出，并将该值添加到表L 1中。
Extract −Queries ：A 可以要求回答对应于任意身份id i 和公钥(Q (1,i ),Q (2,i ))的部分私钥。
如果Q (2,i )≠H 1(id i ,Q (1,i ))，则C 返回无效；否则通过运行Extract 算法得到并输出对应于id i 的部分私钥S (2,i )。
H 2−Queries ：A 在任何时候向随机预言机H 2询问问题，C 通过将二元组(Σi ,w i )保存到列表L 2来模拟随机预言机，其中Σi 是一个三元组(m i ,c i ,i U ′)，当输入询问Σ，C 回答：
1) 当询问Σ已经在表L 2中，输出相同的值； 2) 否则C 随机选择一个新值输出，并将该值添加到表L 2中。
类似地可以定义H 3−Queries ，C 也需要维护一个列表L 3，如果要询问的问题已经在列表中，则直接输出相同的值；否则C 选择一个新值输出，并将该值添加到表L 3中。
Issue −Queries ：
C 通过对签名请求(id i ,m ,c )进行签名来模拟签名预言机，C 按照上面的方法模拟H 2和H 3的输入输出。最后A 以一个不可忽略的概率对一个输入消息(m ,c )输出一个签名(U ′,V ′,R )，而且满足：
