基于身份的公开验证签密方案

文章编号:1001-9081(2012)01-0099-05 doi:10.3724/SP.J.1087.2012.00099

摘 要:基于双线性对，提出了一个基于身份的签密方案。在计算DiffieHellman(CDH)问题困难的假设下，证明了方案在随机预言模型下能够抵抗自适应性选择消息和身份攻击。方案基于身份，不需要证书，从而简化了密钥管理。此外，所提方案不仅可用于公开验证，在不需要泄露接收者私钥的前提下，可由第三方认证密文确实是对应明文的有效签密值。

关键词:签密方案；公开验证；可证安全；基于身份；随机预言模型

中图分类号:TP309.7 文献标志码:A

Abstract: Using bilinear pairing, a new identitybased signcryption scheme was proposed in this paper. Under the assumption that the Computational DiffieHellman (CDH) problem is hard, the newly proposed scheme had been proved to be secure against the existing unforgeability on adaptively chosen message/ciphertext and identity attack in random oracle model. The advantage of the proposed scheme is that it is identitybased which needs no certificates so that it has a simple key management. In addition, the proposed scheme can provide public verifiability, and it allows a third party to convince that the signcryption is valid for the given message without providing the receivers private key.

Key words: signcryption scheme; public verification; provably secure; identitybased; random oracle model

0 引言

在不安全信道中进行安全通信通常要求保证信息的机密性和认证性，消息的机密性可用加密方案来实现，数字签名技术则可用来防止消息被伪造，而签密方案可用来同时满足这两种性质。1997年，Zheng［1］首次提出了数字签密的概念，并给出了一个可实际使用的方案，该方案比使用独立的签名方案和加密方案来进行“先加密再签名（StE）”或者“先签名再加密（EtS）”更为高效。之后，Baek等［2］给出了安全签密方案的标准模式，并利用随机预言模型对Zheng提出的方案［1］进行了安全性证明。基于身份的密码系统允许人们使用任意字符串作为他自己的公钥来唯一地验证他的身份，因此基于身份的密码系统在一定程度上可以有效地替代公开密钥基础设施。2002年，Lee［3］首次将数字签密方案和基于身份系统结合起来。随后，Libert等［4］指出文献［3］中提出的方案不是语义安全的并提出了三个新方案，但这三个方案均不能同时满足公开验证性和前向安全性。2006年，张串绒等［5］对文献［3］中的方案进行了改进，使得改进后的算法是一个安全的可公开验证签密方案。Chow等［6］也设计了一个能同时满足公开验证性和前向安全性的签密方案，然而他们的方案需要两个私钥：一个用于签密；一个用于解签密。除了基于身份的签密方案外，还有一些基于PKI(Public Key Infrastructure)的签密方案被提出［7-10］。

通常，在签密方案中，由于消息被隐藏，密文的合法性只有在密文被解密后才能够被验证，因此，在不知道接收者私钥的情况下，第三方没有办法验证密文的合法性。公开验证签密方案是指在不知道明文的前提下，任意人均可验证密文合法性的签密方案。第三方可验证的签密方案则允许密文接收者在提供一些额外信息的基础上，可以让第三方相信密文确实是对应明文的签密值，而不需要泄露他的私钥。在实际应用中，可公开验证的签密方案的应用范围非常广泛，例如可公开验证的签密方案可用来在安全电子邮件系统中过滤垃圾邮件。该垃圾邮件过滤系统能够在不知道消息的前提下验证密文的真实性，即验证该加密签名是否是由声称的发送者发送的。此外，在其他一些应用中需要使用到签密方案的第三方验证性，例如在私人合同签署中，加密签名的接收者需要让第三方相信发送者签署了在签密方案中隐藏的消息，而不需要泄漏他自己的私钥或者任何利用他的私钥在签名验证过程中所得到的信息。

本文提出了一个新的基于身份的签密方案，并且证明了该方案不仅能够保持前向安全性（称一个基于身份的签密方案能够提供前向安全性（Forward Security），是指即使能够获得发送方的私钥，也不可能知晓发送方之前签署加密的消息内容），而且该方案能够被公开验证和第三方验证。最后在基于计算DiffieHellman(Computational DiffieHellman, CDH)问题困难的假设下，利用随机预言模型给出了方案的安全证明。

1 预备知识

1.1 可用于公开验证的基于身份签密方案的标准模式

基于身份的可公开验证签密方案通常由如下算法组成：参数生成算法、密钥生成算法、签密算法、解密验证算法、公开验证算法、第三方验证算法（如果方案可以被第三方验证）。

1)参数生成算法。给定安全参数1K，私钥生成中心（Private Key Generator, PKG）生成主密钥s和公开参数params，其中params是公开的，s由PKG秘密保存。

2)密钥生成算法。给定任意一个用户ID（可以是任意字符串），PKG利用参数（params,s）生成用户的私钥K，并通过安全信道将私钥K发送给用户。本算法简记为Extract。

3)签密算法。用户A可利用本算法使用自己的私钥KA，B的身份IDB，对消息m进行签密得到σ，并将σ发送给用户B。本算法简记为Signcrypt。

4)解密验证算法。当得到签密值σ后，如果σ是用户A发送给B的关于消息m的有效签密值，用户B可使用自己的私钥KB，A的身份IDA，利用本算法获得消息m值；或者“Invalid”，即得到的签密值是无效的。本算法简记为Unsigncrypt。

5)公开验证算法。本算法允许任意第三方在不知道消息m值的情况下，仍可验证签密值σ的真实性。给定输入(σ,IDA,IDB），如果σ是真实的签密值，算法输出“Valid”；否则输出“Invalid”。本算法简记为PublicVerify。

6)第三方验证算法。本算法允许接收方B通过提供一些额外信息（非私钥KB）向任意第三方证明签密值σ的真实性。给定输入φ（σ以及B提供的一些额外信息）、A的身份IDA、B的身份IDB，如果σ是一个有效的由A发送给B的关于消息m的签密值，算法输出“Valid”；否则输出“Invalid”。本算法简记为TPVerify。

1.2 形式化的安全定义

定义1 称一个基于身份的签密方案对于自适应选择密文和身份攻击（indistinguishability of identitybased signcryptions under adaptive chosen ciphertext and identity attack, INDIDSCCCIA）仍可保持明文的秘密性，如果不存在敌手能够在多项式时间内以不可忽略的优势赢得下面的游戏。

参数生成 应答者C选择安全参数1K运行参数生成算法得到公开参数params以及主密钥s。C将参数params发送给A。

第1阶段 敌手A向C提交一系列查询，查询次数为多项式次数，方式为自适应查询，即下一次查询的内容可依赖于以前查询的结果。可进行的查询内容如下。

1)密钥查询。A选择身份ID向C进行查询，C计算Extract(ID)=KID，并将结果发送给A。

2)签密值查询。A提交身份IDi和IDj以及明文m，C对明文进行签密，得到σ=Signcrypt(m,Ki,IDj)，并将σ发送给A。

3)签名解密查询。A提交身份IDi和IDj以及密文σ，C计算Extract(IDj)=Kj，然后C对密文σ解密，计算Unsigncrypt(σ,IDi,IDj)，并将得到的明文m或者“Invalid”发送给A。

4)挑战。由敌手A来决定第1阶段何时结束。当结束后，A选择两个等长的明文m0和m1，以及两个用于挑战的实体身份IDi和IDj，其中IDj没有在第1阶段出现过。C选择一个随机数b，b∈{0,1},计算σ=Signcrypt(mb,Ki,IDj)，并将σ发送给A。

第2阶段 A可以向C提交一系列类似于第1阶段的查询，但A不可以查询IDj的私钥，也不允许查询Unsigncrypt(σ,IDi,IDj)来获得σ对应的明文。

猜测 A选择b′，如果b′=b，则A赢得游戏。

A在上述游戏中的优势定义为Adv(A)=|2Pr(b′=b)-1|，其中Pr(b′=b)表示b′=b的概率。

定义2 称一个基于身份的签密方案对于自适应选择消息和身份攻击（existential unforgeability of identitybased signcryptions under adaptive chosen message and identity attacks, EUFIDSCCMIA）是不可伪造的，如果不存在敌手能够在多项式时间内以不可忽略的优势赢得下面的游戏。

1)参数生成。应答者C选择安全参数1K运行参数生成算法得到公开参数params以及主密钥s。C将参数params发送给A。

2)查询阶段。敌手A可向C提交INDIDSCCCIA游戏中第1阶段中所提供的参数查询，查询次数为多项式次数，方式为自适应查询。

3)伪造。由敌手A来决定查询阶段何时结束。当结束后，A向C提交(σ,IDi,IDj)，其中A不可以在查询阶段查询IDi的私钥，也不允许查询Unsigncrypt(σ,IDi,IDj)来获得σ对应的明文，但A可以查询IDj的私钥。如果Unsigncrypt(σ,IDi,IDj)存在有效值，则A赢得游戏。

A在游戏中的优势Adv(A)即为A赢得游戏的概率。

1.3 双线性映射和DiffieHellman问题

设(G1,＋)和(G2,•)是两个q阶循环群，双线性映射ê:G1×G1G2满足如下性质。

1)双线性性。任意P,Q∈G1，a,b∈Zq，有等式ê(aP,bQ)=ê(P,Q)ab成立。

2)非退化性。存在Q,R∈G1，使得ê(Q,R)≠1。

3)可计算性。任意P,Q∈G1，存在有效的算法计算ê(P,Q)。

假定存在双线性映射ê:G1×G1G2使得如下问题是难于求解的。

定义3 给定q阶循环群(G,＋)，P是G的生成元，CDH问题是指，任意给定三元组(P,aP,bP)，计算abP，其中a，b是未知的。

定义4 给定q阶循环群(G1,＋)和(G2,•)，ê:G1×G1G2是一个可容许的双线性映射，P是G1的一个生成元，计算双线性DiffieHellman问题（Computational Bilinear DiffieHellman, CBDH）是指，任意给定四元组(P,aP,bP,cP)，计算ê(P,P)abc，其中a，b，c是未知的。

本文始终假定CDH问题是困难的，这意味着不存在有效的多项式时间算法能够以不可忽略的概率计算该问题。对于CDH问题和CBDH问题，有如下结论。

命题1 在(G1,＋)和(G2,•)中，CBDH问题都可以在多项式时间内规约为CDH问题。

证明 1）如果可以解决G1中的CDH问题，即，若P是G1的一个生成元，对于任意aP和bP，abP可计算。那么，对于任意aP,bP,cP，abcP可计算，因此ê(P,P)abc==ê(abcP,P)也可计算。即在G1中，CBDH问题可以在多项式时间内规约为CDH问题。

2）如果可以解决G2中的CDH问题，令P是G1的一个生成元，则ê(P,P)=g是G2的一个生成元，则对于ga和gb，可计算gab，再由gab和gc，可计算gabc，即得到了ê(P,P)abc。也就是说，在G2中，CBDH问题可以在多项式时间内规约为CDH问题。

2 新的基于身份的公开验证签密方案

G1，G2，ê如第1章所定义，设Hi(i=1,2,3,4)是4个安全的密码学哈希函数，其中H1:{0,1}*G1，H2:G2{0,1}n，H3:{0,1}n×G1×G1×G1G1，H4:{0,1}n×G1×G2×G1×G1{0,1}n。令E，D分别是一个安全对称密码算法的加、解密算法，其中明、密文以及密钥的长度均为n。方案细节如下。

参数生成算法 P是G1的任意一个生成元，任选s∈Z*q，Ppub=sP。其中，主密钥为s，由PKG秘密保存，公开参数params为(G1,G2,q,n,P,Ppub,ê,H1,H2,H3,H4,E,D)。

密钥生成算法 具有身份为ID的用户向PKG提交自己的身份ID，PKG计算用户的公钥QID=H1(ID)∈G1，用户的私钥KID=sQID，并通过安全信道将私钥KID发送给用户。

签密算法 为了给B发送信息m∈{0,1}n，用户A可使用本算法生成签名：

1)任意选择x∈Z*q；

2)计算U=xP；

3)计算α=ê(Ppub,QB)x；

4)计算β=H2(α)；

5)计算γ=H4(m,α,U,QA,QB)；

6)计算c=Eβ(mγ)；

7)计算R=H3(c,U,QA,QB)；

8)计算V=xR＋KA；

9)密文σ=(U,V,c)。

签名解密验证算法 当得到A发送的σ=(U,V,c)后，用户B可使用本算法对签名进行验证，得到明文。

1)计算R′=H3(c,U,QA,QB)。

2)计算ê(V,P)，ê(R′,U)ê(QA,Ppub)，判断两个数值是否相等：如果不等，算法返回“Invalid”，说明得到的签密值是无效的；否则，继续。

3)计算α′=ê(U,KB)。

4)计算β′=H2(α′)。

5)计算m′γ′=Dβ′(c)。

6)计算H4(m′,α′,U,QA,QB)，如果γ′≠H4(m′,α′,U,QA,QB)，说明得到的签密值是无效的；否则，签名值有效，m′即为A发送的消息m。

公开验证算法 此算法即为签名解密验证算法的前两步。

1)计算R′=H3(c,U,QA,QB)。

2)计算ê(V,P)，ê(R′,U)ê(QA,Ppub)，判断两个数值是否相等：如果不相等，算法返回“Invalid”，说明该签密值是无效签名；否则，返回“Valid”，接受其为有效签名。

第三方验证算法 接收方B向第三方提供(σ,α′,IDA,IDB)。第三方可使用本算法对签名进行验证。

1)计算R′=H3(c,U,QA,QB)。

2)计算ê(V,P)，ê(R′,U)ê(QA,Ppub)，判断两个数值是否相等：如果不等，算法返回“Invalid”，第三方认为该签密值是无效签名；否则，继续。

3)计算β=H2(α′)。

4)计算mγ=Dβ(c)。

5)计算H4(m, β,U,QA,QB)，如果γ≠H4(m, β,U,QA,QB)，算法返回“Invalid”，第三方认为该签密值是无效签名；否则，承认此签名值是对应消息m的有效签名。

3 方案安全性分析

本章对方案的安全性进行分析。首先是对方案中签名验证算法的正确性和签名解密算法的一致性进行验证。签名的正确性的验证过程事实上即为证明方案的公开验证算法的正确性，即方案可被公开验证。签名算法的一致性则说明了当签密值是有效签名时，接收方可在给出某些信息的前提下（非私钥或者任何利用他的私钥在签名验证过程中所得到的信息）让第三方验证签名的有效性，即可被第三方验证。

方案中签名验证的正确性和签名解密算法的一致性可验证如下。在签名验证中，如果等式ê(V,P)=ê(R′,U)ê(QA,Ppub)成立，则承认该签名为有效签名。事实上，该等式左侧可计算如下：

ê(V,P)=ê(xR＋KA,P)=ê(xR,P)ê(KA,P)=ê(R,P)xê(sQA,P)=ê(R,U)ê(QA,sP)=ê(R′,U)ê(QA,Ppub)

签名解密算法的一致性验证即为验证所使用的加解密密钥β是否等于β′，即验证等式α=α′是否成立。事实上，α′=ê(U,KB)=ê(xP,sQB)=ê(sP,QB)x=ê(Ppub,QB)x=α。

因此，如果该签密值是有效签名，则接收方可在不泄漏他自己的私钥或者任何利用他的私钥在签名验证过程中所得到的信息的前提下让第三方验证签名的有效性。

下面利用第1章给出的安全性定义来讨论方案的安全性，可证明本方案是INDIDSCCCIA安全的和EUFIDSCCMIA安全的；并且论证了当方案是INDIDSCCCIA安全和EUFIDSCCMIA安全时，方案也是前向安全的和内在安全的。

定理1 在随机预言模型下，如果存在敌手A能够以不可忽略的优势ε赢得INDIDSCCCIA游戏，那么应答者C能够以O(ε)的优势ε′解决CBDH问题。

证明 如果存在敌手A能够以不可忽略的优势ε赢得INDIDSCCCIA游戏，下面证明应答者C可以O(ε)的优势ε′利用A来解决CBDH问题。在游戏中，A可以向C查询随机预言模型H1，H2，H3，H4的输出值。通常，这些值是随机生成的，为了避免碰撞，C使用4个列表L1，L2，L3，L4来存储回答的这些输出值。假定应答者C收到(P,aP,bP,cP)，P是G1的一个生成元，C利用A通过INDIDSCCCIA游戏来计算ê(P,P)abc。

参数生成 应答者C选择Ppub=aP，公开参数params为(G1,G2,q,P,Ppub)。C将参数params发送给A。

第1阶段 在此阶段敌手A可向C查询，可进行的预言模型查询如下。

1)H1随机预言模型(ΩH1)查询。当A查询关于某一身份IDi的哈希值时，C检查列表L1，如果该身份曾经被查询，C将之前的回答响应值返回给A；否则C随机选择di，di∈Z*q，计算Qi=diP，将(IDi,Qi)存储在列表L1中，并将Qi返回给A。在A的所有查询中，C随机选择身份IDi0，并设置ΩH1(IDi0)=bP。由于bP是CBDH问题给出的随机值，因此并不影响ΩH1的随机性。

2)H2随机预言模型（ΩH2）查询。当A查询关于某一α的哈希值时，C检查列表L2，如果该数值曾经被查询，C将之前的回答响应值返回给A；否则，C随机选择β，将(α, β)存储在列表L2中，并将β返回给A。

3)H3随机预言模型（ΩH3）查询。当A查询(c,U,Qi,Qj)的哈希值时，C响应如下。如果(c,U,QA,QB,R)在列表L3中，C将之前的回答响应值R返回给A；否则，如果i≠i0，C随机选择r，r∈Z*q，计算R=rPpub；如果i=i0，C计算R=rQj。C将(c,U,Qi,Qj,R)存储在列表L3中，并将R返回给A。

4)H4随机预言模型（ΩH4）查询。当A向ΩH4查询(m,U,α,Qi,Qj)的输出值时，C响应如下。如果(m,U,α,Qi,Qj,γ)在列表L4中，C将之前的回答响应值γ返回给A；否则，随机选择γ∈Z*q，将(m,U,α,Qi,Qj,γ)存储在列表L4中，并将γ返回给A。

5)密钥生成模型（ΩExtract）查询。A提交身份IDi，C响应如下。如果i≠i0，C计算Qi=ΩH1(IDi)，以及i的私钥Ki=aQi=diPpub；如果i＝i0，C挑战CBDH问题失败，因为C不知道a值，故无法计算i0的私钥Ki0=abP。C将(IDi,Qi)存储在列表L1中，并将Ki返回给A。

6)签密模型（ΩSigncrypt）查询。A提交发送方身份IDi和接收方身份IDj以及消息m，C响应如下。如果i≠i0，C计算i的私钥并利用签密算法生成σ；如果i＝i0，C利用如下步骤计算σ。

①任意选择r,x∈Z*q，计算U=xP－r-1Qi。

②计算α=ê(U,KB)。

③计算β=ΩH2(α)。

④计算γ=ΩH4(m,U,α,Qi,Qj)。

⑤计算c=Eβ(mγ)。

⑥计算R=rPpub。

⑦计算V=rxPpub。

将(c,U,Qi,Qj,R)存储在列表L3中，如果L3中有相同的R，则重新选择r，计算U，R，V值。C将签密值σ=(U,V,c)返回给A。

7)签名解密模型（ΩUnsigncrypt）查询。对于A的签名解密查询，C响应如下。如果j≠i0，C计算j的私钥Kj，并利用签名解密算法对σ进行解密。如果σ是一个有效签密值，C将计算得到的m′返回给A；否则返回“Invalid”给A。如果j＝i0，C可计算得到i的私钥Ki，并做如下计算。

①如果PublicVerify(σ,IDi,IDj)=“Invalid”，C返回“Invalid”给A；否则继续。

②随机选择r∈Z*q，计算R=ΩH3(c,U,QA,QB)。

③验证等式ê(U,Qj)=ê(r-1R,P)是否成立，如果不成立，返回“Invalid”给A；否则继续。

④计算α′=ê(r-1R,Ppub)。

⑤计算β′=ΩH2(α′)。

⑥计算m′γ′=Dβ′(c)。

如果γ′=ΩH4(m′,U,α′,Qi,Qj)，C将m′返回给A；否则返回“Invalid”给A。

8)公开验证模型（ΩTPVerify）查询。对于A的第三方验证查询，C响应如下。如果j≠i0，C计算j的私钥Kj，并利用签名解密算法对σ进行解密，如果σ是一个有效签密值，C返回φ给A；否则返回“Invalid”给A。如果j=i0，C如同ΩUnsigncrypt中一样计算，如果σ是一个有效签密值，C返回φ给A；否则返回“Invalid”给A。

挑战阶段 在第1阶段结束后，A选择两个等长的明文m0和m1，以及两个用于挑战的实体身份IDi和IDj，并将它们发送给C。如果j≠i0，C挑战CBDH问题失败；否则C选择随机数b，b∈{0,1},并按照如下步骤对mb进行签密计算。

1)任意选择r∈Z*q，计算R*=rP。

2)计算i的私钥Ki。

3)计算V*=rcP＋Ki。

任意选择c*∈{0,1}|n|，令U*=cP，C将签密值σ*=(U*,V*,c*)返回给A。

第2阶段 A向C提交一系列类似于第1阶段的查询，但A不可以查询IDj的私钥，也不允许查询ΩUnsigncrypt(σ*,IDi,IDj)和ΩTPVerify(σ*,IDi,IDj)来获得σ*对应的明文。

为了从σ*中解出mb，即求解出b值，A需要查询ΩH2或ΩH4。如果A查询ΩH2，那么C可以得到α*=ê(U,KB)=ê(cP,abP)=ê(P,P)abc。如果A查询ΩH4，那么A同样需要计算α*，因此C可以解决CBDH问题。

C解决CBDH问题的概率分析 令qH1，qH2，qH3，qH4，qE分别是A可以向ΩH1，ΩH2，ΩH3，ΩH4，ΩExtract提交的最大查询次数。如果A查询IDi0的私钥，由于C不知道a值，故无法提供i0的私钥Ki0=abP，记此事件为E1。E1不发生的概率为：

Pr(E1)=((qH1－1)/qH1)((qH1－2)/(qH1－1))…((qH1－qE)/(qH1－qE+1))=(qH1－qE)/qH1

如果A不选择i0作为挑战阶段的消息接收者，那么C也无法解决CBDH问题，记此事件为E2。E2不发生的概率为：

Pr(E2)=((qH1－qE－1)/(qH1－qE))(1/(qH1－qE－1))此处左、右括号不匹配，是否应该添加一个右括号“)”？请明确。=1/(qH1－qE)

C从列表L2或者L4中选择值来响应CBDH问题的概率为1/(qH2+qH4)原文中，此处是不是多了一个右括号，请明确。，故C解决CBDH问题的概率ε′为：

ε′=ε((qH1－qE)/qH1)(1/(qH1－qE))(1/(qH2+qH4))=ε(1/qH1(qH2+qH4))

因此，如果存在敌手A能够以不可忽略的优势ε赢得INDIDSCCCIA游戏，找到b′，使得b′=b，那么应答者C能够以O(ε)的优势ε′解决CBDH问题。

在签密模型中，如果i=i0，C计算得到的σ的有效性可被验证如下。事实上，在签名解密验证过程中σ的有效性是通过判断ê(V,P)，ê(R,U)ê(Qi,Ppub)是否相等来验证的，而在签密模型中得到的ê(R,U)ê(Qi,Ppub)可被计算如下。

ê(R,U)ê(Qi,Ppub)=ê(rPpub,xP－r-1Qi)ê(Qi,Ppub)

=ê(rPpub,xP)ê(rPpub,r-1Qi)-1ê(Qi,Ppub)

=ê(rxPpub,P)ê(Ppub,Qi)-1ê(Qi,Ppub)

=ê(rxPpub,P)

=ê(V,P)

因此，签密模型中计算得到的签密值σ是有效的。

特别地，当方案是INDIDSCCCIA安全的，方案同样是前向安全的（即使能够获得发送方的私钥，也不可能知晓发送方之前签署加密的消息内容）。因为在定理1证明过程中的挑战阶段，敌手A可以查询发送者i的私钥Ki，也就是说，即使发送方的私钥被泄露了，该签密方案仍可保持明文的秘密性，因此方案是前向安全的。

定理2 在随机预言模型下，如果存在敌手A能够以不可忽略的优势ε赢得EUFIDSCCMIA游戏，那么应答者C能够以O(ε)的优势ε′解决CDH问题。

证明 如果存在敌手A能够以不可忽略的优势ε赢得EUFIDSCCMIA游戏，下面证明应答者C可以O(ε)的优势ε′利用A来解决CDH问题。在游戏中，A可以向C查询随机预言模型H1，H2，H3，H4的输出值。通常，这些值是随机生成的，为了避免碰撞，C使用4个列表L1，L2，L3，L4来存储回答的这些输出值。假定应答者C收到(P,aP,bP)，P是G1的一个生成元，C利用A通过INDIDSCCCIA游戏来计算abP。

参数生成 应答者C选择Ppub=aP，公开参数params为(G1,G2,q,P,Ppub)。C将参数params发送给A。

查询阶段 在此阶段敌手A可向C查询，可进行的预言模型查询和定理1相同，此处不再赘述。

伪造阶段 查询阶段结束后，A向C提交(IDi,IDj,σ)。其中A不可以在查询阶段查询IDi的私钥，也不允许查询Unsigncrypt(σ,IDi,IDj)来获得σ对应的明文，但A可以查询IDj的私钥。如果i=i0，并且σ是一个有效签密值，此时C从列表L3中恢复r值，计算Ki0=V－rU，得到abP。事实上，由于V－rU=xR＋Ki0－rU=xrP＋Ki0－rU=rU＋Ki0－rU=Ki0=abP，因此C可解决CDH问题。

C解决CDH问题的概率分析 令qH1，qH2，qH3，qH4，qE分别是A可以向ΩH1，ΩH2，ΩH3，ΩH4，ΩExtract提交的最大查询次数。如果A查询IDi0的私钥，由于C不知道a值，故无法提供i0的私钥Ki0=abP，记此事件为E1，E1不发生的概率为：

Pr(E1)=((qH1－1)/qH1)((qH1－2)/(qH1－1))…((qH1－qE)/(qH1－qE+1))=(qH1－qE)/qH1

如果A不选择i0作为伪造阶段的消息发送者，那么C也无法解决CDH问题，记此事件为E2，E2不发生的概率为：

Pr(E2)=((qH1－qE－1)/(qH1－qE))(1/(qH1－qE－1))此处左、右括号不匹配，是否应该添加一个右括号“)”？请明确。=1/(qH1－qE)

故C解决CDH问题的概率ε′为：

ε′=ε((qH1－qE)/qH1)(1/(qH1－qE))=ε(1/qH1)

因此，如果存在敌手A能够以不可忽略的优势ε赢得EUFIDSCCMIA游戏，那么应答者C能够以O(ε)的优势ε′解决CDH问题。

特别地，如果方案是EUFIDSCCMIA安全的，方案可以满足签密方案的内在安全性（即使知道接收方的私钥，该方案生成的签名仍是不可伪造的）。原因在于在定理2的证明过程中，敌手A可以在查询阶段查询伪造阶段所使用的接收者j的私钥Kj，因此有结论，如果方案是EUFIDSCCMIA安全的，方案满足签密方案的内在安全性。

4 结语

本文提出了一个新的基于身份的签密方案，方案具有前向安全性、可公开验证性以及可被用于第三方验证。利用随机预言模型，在基于CDH问题是难解的假设下，本文证明了方案的安全性。事实上，如何利用CDH问题以及判定DiffieHellman(Decisional DiffieHellman, DDH)“BDH”的中文全称是什么，英文全称又是什么，而“判定DiffieHellman”的英文全称和英文缩写是什么，请说明。问题（包括它们的变形，如CBDH问题）的难解性，来设计更多可证安全、有效的基于身份的签密方案是一个有意义的课题，也是作者下一步要进行的工作。

参考文献:

[1]

ZHENG YULIANG. Digital signcryption or how to achieve cost (signature & encryption)

[2]

BAEK J, STEINFELD R, ZHENG Y. Formal proofs for the security of signcryption ［C］// PKC 2002: Proceedings of the 5th International Workshop on Practice and Theory in Public Key Cryptosystems: Public Key Cryptography, LNCS 2274. Berlin: SpringerVerlag, 2002: 80-98.

[3]

LEE M J. Identitybased signcryption ［EB/OL］. ［2011-04-11］. eprint.省略/ report 2002/98.

[4]

LIBERT B, QUISQUATER J J. Efficient signcryption with key privacy from Gap DiffieHellman groups ［C］// PKC 2004: Proceedings of the 7th International Workshop on Theory and Practice in Public Key Cryptography, LNCS 2947. Berlin: SpringerVerlag, 2004: 187-200.

[5]

张串绒,肖国镇.一个可公开验证签密方案的密码分析和改进［J］.电子学报,2006,34(1):177-179.

[6]

CHOW S M, YIU S M, HUI C K, et al. Efficient forward and provably secure IDbased signcryption scheme with public verifiability and public ciphertext authenticity ［C］// ICICS 2003: Proceedings of the 6th International Conference on Information Security and Cryptology, LNCS 2971. Berlin: SpringerVerlag, 2004: 352-369.

[7]

MU Y, VARADHARAJAN V. Distributed signcryption ［C］// INDOCRYPT 2000: Proceedings of the First International Conference on Progress in Cryptology, LNCS 1977. Berlin: SpringerVerlag, 2000: 155-164.

[8]

PIEPRZYK J, POINTCHEVAL D. Parallel authentication and publickey encryption ［C］// ACISP 2003: Proceedings of the 8th Australasian Conference on Information Security and Privacy, LNCS 2727. Berlin: SpringerVerlag, 2003: 387-401.

[9]

YANG G, WONG D S, DENG X. Analysis and improvement of a signcryption scheme with key privacy ［C］// ISC 2005: Proceedings of the 8th International Conference on Information Security, LNCS 3650. Berlin: SpringerVerlag, 2005: 218-232.CHOW S S M, YIU S M, HUI L C K, CHOW K P. Efficient forward and provably secure IDbased signcryption scheme with public verifiability and public ciphertext authenticity ［C］// ICISC 2003, LNCS 2971. Berlin: SpringerVerlag, 2004: 352-369.与文献6重复。

[10]

TSO R, OKAMOTO T, OKAMOTO E. ECDSA―Verifiable signcryption scheme with signature verification on the signcrypted message ［C］// Inscrypt 2007: Proceedings of the Third SKLOIS Conference on Information Security and Cryptology, LNCS 4990. Berlin: SpringerVerlag, 2008: 11-24.

收稿日期:2011-06-03;修回日期:2011-07-12。

基金项目:江苏省自然科学基金资助项目(BK20082140)；淮海工学院引进人才科研启动基金资助项目(KQ10121)；淮海工学院校内课题项目(KX10530)。

作者简介:李志敏(1981-)，女，辽宁沈阳人，讲师，博士，主要研究方向：密码学、信息安全、网络安全； 徐馨(1976-)，女，江苏连云港人，讲师，硕士，主要研究方向：信息安全、网络安全、算法分析； 李存华(1963-)，男，江苏徐州人，教授，博士，主要研究方向：数据库理论与系统、数据挖掘、模式识别。