电子科技大学学报  2015, Vol. 44 Issue (6): 887-891       
引用本文
何明星, 李鹏程, 李虓. 高效的可证明安全的无证书数字签名方案[J]. 电子科技大学学报, 2015, 44(6): 887-891.
HE Ming-xing, LI Peng-cheng, LI Xiao. Efficient and Provably Secure Certificateless Signature from Bilinear Pairings[J]. Journal of University of Electronic Science and Technology of China, 2015, 44(6): 887-891.
高效的可证明安全的无证书数字签名方案    [PDF全文]
何明星, 李鹏程, 李虓    
西华大学计算机与软件工程学院 成都 610039
收稿日期: 2013-07-21; 修回日期: 2014-03-01.
基金项目: 科技部支撑计划(2011BAH26B00);四川省国际合作项目(2009HH0009);四川省高校创新团队项目(13TD0005)
作者简介: 何明星(1964-),男,博士,教授,主要从事密码学与信息安全方面的研究.
摘要: 无证书公钥密码体制结合了基于身份和传统PKI公钥密码体制的优势,克服了基于身份公钥密码体制的密钥托管问题及PKI系统的证书管理问题,具有很高的效率。该文提出一个在随机预言机模型下可证明安全的无证书数字签名方案。该方案只需分别在系统初始化阶段、验证阶段预进行一次双线性对运算,而在签名阶段不需要进行计算。计算结果证明该方案比以往的无证书数字签名方案具有更高的计算效率和通信效率,且具有随机预言机模型下的可证明安全性。
关键词: 双线性对     无证书数字签名     可证明安全     数字签名    
Efficient and Provably Secure Certificateless Signature from Bilinear Pairings
HE Ming-xing, LI Peng-cheng, LI Xiao    
School of Computer and Software Engineering, Xihua University Chengdu 610039
Abstract: Certificateless cryptography aims at combining the advantages of identity based and traditional certificate-based public key cryptography, so as to avoid the key escrow problem inherent in the identity based system and certificate management in public key infrastructure. In this paper, we propose a new efficient certificateless signature scheme and prove its security in the random oracle model. Furthermore, via pre-computing a bilinear pairing in the setup phase, our scheme only needs to compute one pairing in the verify stage. It is more efficient in computation complexity and communication complexity than that of many previous schemes.
Key words: bilinear pairing     certificateless signature     provable security     signature    

文献[1]首次提出了基于身份的数字签名方案。文献[2]第一次提出双线性对的概念，并利用双线性对构造了一个基于身份的数字签名方案。文献[3]首次构造了一个无证书数字签名方案，该方案也是基于双线性对的，但并没有对该方案进行严格的安全性证明和安全性分析。文献[4]论证了文献[3]的不安全性，容易受到公钥替换攻击，敌手可以假冒用户对任意消息进行伪造签名。文献[5, 6]中的方案也不能抵抗公钥替换攻击。此外，经过分析发现文献[6]中用户还可以恢复出SEM拥有的对应于该用户私钥的另一部分私钥，使得该签名方案无仲裁性质。文献[7]构造了一个高效的无证书数字签名方案，它基于离散对数困难性假设，该方案在签名中不需要“双线性对”运算，在验证阶段仅需2次“双线性对”运算。但文献[8]发现文献[7]的方案也不能抵抗公钥替换攻击。文献[9, 10, 11]也从不同侧面对安全性和有效性进行了更加深入和广泛的讨论。本文在这些成果基础上提出一个新的在随机预言机模型下可证明安全的无证书数字签名方案，且比以往的无证书数字签名方案具有更高的计算效率和通信效率。

1 无证书数字签名模型 1.1 无证书数字签名

一个无证书数字签名系统由密钥生成中心(key generate center, KGC)、签名者(signaturer)、验证者(verifier)3个合法参与者构成。包含7个多项式时间算法：

1) 系统初始化算法：输入系统安全参数${{1}^{k}}$后，返回KGC的主私钥(master secret key,MSK)以及系统全局参数。

2) 部分私钥提取算法：输入用户身份字符串$\text{ID}\in {{\{0,1\}}^{*}}{{\{0,1\}}^{*}}$表示所有的比特串集合)、系统主私钥MSK及系统公开参数，由KGC返回用户部分私钥D。

3) 设置秘密值算法：用户随机选择一个秘密值x，用于生成用户的公钥及私钥。

4) 用户公钥生成算法：用户输入秘密值x及系统公开参数后，生成自己的公钥PK。

5) 用户私钥生成算法：用户输入秘密值x及由KGC生成的部分私钥D，返回完整的私钥SK。

6) 签名算法：该算法是概率多项式时间算法。签名发送者在执行算法过程中，输入待签名消息$m\in {{M}_{\text{CLS}}}$、签名发送者身份$\text{I}{{\text{D}}_{S}}$、完整私钥$\text{S}{{\text{K}}_{S}}$和公钥$\text{P}{{\text{K}}_{S}}$、签名验证方身份$\text{I}{{\text{D}}_{R}}$、全局参数及一些随机数$r\in {{R}_{\text{CLS}}}$。算法执行完毕后，若签名正确则输出消息$m\in {{M}_{\text{CLS}}}$对应的签名$\sigma \in {{\Sigma }_{\text{CLS}}}$；否则输出错误标识“$\bot $”。

7) 签名验证算法：输入签名$\sigma \in {{\Sigma }_{\text{CLS}}}$、签名发送者用户身份$\text{I}{{\text{D}}_{S}}$、公钥$\text{P}{{\text{K}}_{S}}$、签名验证方身份$\text{I}{{\text{D}}_{R}}$及系统全局参数。算法由签名验证者执行完毕后，若验证签名正确则输出“接受签名”；否则输出错误标识“$\bot $”。

1.2 无证书数字签名体制的敌手

无证书数字签名体制的敌手[3]分为两类：1) 敌手${{A}_{I}}$定义为外部的恶意敌手，是主动敌手，不知道系统的主私钥MSK，但拥有替换用户公钥的能力；2) 敌手${{A}_{II}}$是一个诚实但好奇(honest-but- curious)的KGC，是一个被动敌手，拥有系统的主私钥MSK，但不能替换用户的公钥。

在随机预言机模型下，一个无证书数字签名方案的可证明安全性，可通过一个挑战者C与敌手${{A}_{I}}$或者${{A}_{II}}$进行交互来确定。

1.2.1 游戏1(针对敌手${{A}_{I}}$)

1) 系统初始化：挑战者C输入系统安全参数$\ell $，运行初始化算法，获取系统主私钥MSK及全局参数，然后将系统全局参数发送给敌手${{A}_{I}}$，并对系统主私钥MSK保密。

2) 攻击阶段：敌手${{A}_{I}}$可以进行多项式次的交互询问。

① 请求公钥询问$\text{PK(I}{{\text{D}}_{i}}\text{)}$：当敌手${{A}_{I}}$向挑战者提交一个合法的身份$\text{I}{{\text{D}}_{i}}$并请求询问该$\text{I}{{\text{D}}_{i}}$的公钥后，挑战者返回提交$\text{I}{{\text{D}}_{i}}$相对应的公钥$\text{PK(I}{{\text{D}}_{i}}\text{)}$$\text{PK(I}{{\text{D}}_{i}}\text{)}$。

② 替换公钥询问$\text{PKR}(\text{I}{{\text{D}}_{i}},\text{P}{{\text{{K}'}}_{\text{I}{{\text{D}}_{i}}}})$：当敌手${{A}_{I}}$向挑战者提交一个合法的身份$\text{I}{{\text{D}}_{i}}$以及一个伪造的合符系统格式的公钥$\text{P}{{\text{{K}'}}_{\text{I}{{\text{D}}_{i}}}}$后，挑战者应该利用提交的伪造公钥$\text{P}{{\text{{K}'}}_{\text{I}{{\text{D}}_{i}}}}$替换掉敌手提交$\text{I}{{\text{D}}_{i}}$的当前公钥$\text{P}{{\text{K}}_{\text{I}{{\text{D}}_{i}}}}$。

③ 秘密值询问$\text{SV}(\text{I}{{\text{D}}_{i}})$：当敌手${{A}_{I}}$向挑战者提交一个合法的身份$\text{I}{{\text{D}}_{i}}$并请求询问该$\text{I}{{\text{D}}_{i}}$的秘密值xi后，如果该$\text{I}{{\text{D}}_{i}}$的公钥未被替换，那么挑战者向敌手返回该$\text{I}{{\text{D}}_{i}}$对应的秘密值${{x}_{\text{I}{{\text{D}}_{i}}}}$；否则模拟失败。

④ 部分私钥提取询问$\text{PPK}(\text{I}{{\text{D}}_{i}})$：当敌手${{A}_{I}}$向挑战者提交一个合法的身份$\text{I}{{\text{D}}_{i}}$并请求询问该$\text{I}{{\text{D}}_{i}}$的部分私钥后，挑战者返回提交$\text{I}{{\text{D}}_{i}}$相对应的部分私钥${{D}_{\text{I}{{\text{D}}_{i}}}}$。

⑤ 私钥提取询问$\text{PPK}(\text{I}{{\text{D}}_{i}})$：当敌手${{A}_{I}}$向挑战者提交一个合法的身份$\text{I}{{\text{D}}_{i}}$并请求询问该$\text{I}{{\text{D}}_{i}}$的私钥后，挑战者返回提交$\text{I}{{\text{D}}_{i}}$相对应的私钥$\text{S}{{\text{K}}_{\text{I}{{\text{D}}_{i}}}}$，如果该$\text{I}{{\text{D}}_{i}}$对应的公钥被替换，则模拟失败。

⑥ 签名询问$\text{Sig}({{M}_{i}},\text{I}{{\text{D}}_{i}},\text{P}{{\text{K}}_{i}})$：敌手${{A}_{I}}$可以对任何用户$\text{I}{{\text{D}}_{i}}$对消息${{M}_{i}}$的签名进行询问，挑战者收到一个挑战$({{M}_{i}},\text{I}{{\text{D}}_{i}},\text{P}{{\text{K}}_{i}})$后，挑战者C对消息${{M}_{i}}$生成一个签名${{\sigma }_{i}}$作于对敌手${{A}_{I}}$的回答。这里要求对消息${{M}_{i}}$生成签名${{\sigma }_{i}}$对于用户$\text{I}{{\text{D}}_{i}}$和其对应的公钥$\text{P}{{\text{K}}_{\text{I}{{\text{D}}_{i}}}}$是有效的。

3) 伪造阶段：最后，若敌手${{A}_{I}}$输出一个元组$({{M}^{*}},{{\sigma }^{*}},\text{I}{{\text{D}}^{*}},\text{P}{{\text{K}}_{\text{I}{{\text{D}}^{*}}}})$，当且仅当满足以下3个条件，敌手${{A}_{I}}$获得该游戏的胜利。

① 对于用户$\text{I}{{\text{D}}^{\text{*}}}$和其对应的公钥$\text{P}{{\text{K}}_{\text{I}{{\text{D}}^{\text{*}}}}}$，元组中签名${{\sigma }_{i}}$是有效的。

② 敌手${{A}_{I}}$没有对用户$\text{I}{{\text{D}}^{\text{*}}}$进行过部分私钥提取询问。

③ 敌手${{A}_{I}}$没有以元组$({{M}^{*}},\text{I}{{\text{D}}^{*}},\text{P}{{\text{K}}_{\text{I}{{\text{D}}^{*}}}})$在签名询问中进行交互。

1.2.2 游戏2

与游戏1不同之处：${{A}_{II}}$仅有请求公钥询问$\text{PK}(\text{I}{{\text{D}}_{i}})$、秘密值询问$\text{SV}(\text{I}{{\text{D}}_{i}})$、私钥提取询问$\text{SK}(\text{I}{{\text{D}}_{i}})$、签名询问$\text{Sig}({{M}_{i}},\text{I}{{\text{D}}_{i}},\text{P}{{\text{K}}_{i}})$的能力。${{A}_{II}}$不像${{A}_{I}}$具有公钥替换的能力$\text{PKR}(\text{I}{{\text{D}}_{i}},\text{P{K}'ID)}$：当${{A}_{I}}$向挑战者提交一个合法的身份$\text{I}{{\text{D}}_{i}}$及一个伪造的符合系统格式的公钥$\text{P}{{\text{{K}'}}_{\text{ID}}}$后，挑战者应利用提交的伪造公钥$\text{P{K}'ID}$替换${{A}_{I}}$提交$\text{I}{{\text{D}}_{i}}$的当前公钥$\text{P}{{\text{K}}_{\text{ID}}}_{_{i}}$。

2. 高效的无证书数字签名方案 2.1 无证书数字签名方案描述

系统初始化算法分为以下5个步骤：

1) KGC首先生成素数q阶的加法循环群${{G}_{1}}$及乘法循环群${{G}_{2}}$，任意选择一个生成元$P\in {{G}_{1}}$。

2) KGC任意选择$s\in Z_{q}^{*}$作为系统主私钥($Z_{q}^{*}$表示由q决定的乘法群)。

3) KGC计算得到系统主公钥${{P}_{0}}=sP\in {{G}_{1}}$。

4) KGC预计算双线性对$e(P,P)=g\in {{G}_{2}}$，e是一个双线性映射。

5) 最后，KGC选择两个密码学安全的Hash函数${{H}_{1}}:{{\{0,1\}}^{*}}\to Z_{q}^{*}$和${{H}_{2}}:{{\{0,1\}}^{*}}\times 2{{G}_{2}}\to Z_{q}^{*}$($\times $表示集合间的笛卡尔积)。

KGC执行完系统初始化算法后，得到系统主私钥$s\in Z_{q}^{*}$、系统主公钥${{P}_{0}}$及系统全局公开参数$<{{G}_{1}},{{G}_{2}},q,e,P,{{P}_{0}},g,{{H}_{1}},{{H}_{2}}>$。

部分私钥提取算法分为两个步骤：

1) 对每一个用户${{U}_{i}}$，KGC首先计算出身份哈希值${{Q}_{i}}={{H}_{1}}(\text{I}{{\text{D}}_{i}})\in Z_{q}^{*}(\text{I}{{\text{D}}_{i}}\in {{\{0,1\}}^{*}})$。

2) KGC计算出用户${{Q}_{i}}={{H}_{1}}(\text{I}{{\text{D}}_{i}})\in Z_{q}^{*}(\text{I}{{\text{D}}_{i}}\in {{\{0,1\}}^{*}})$的部分私钥${{D}_{i}}={{(s+{{Q}_{i}})}^{-1}}P\in {{G}_{1}}$。KGC将${{D}_{i}}$通过安全信道传送给相应的用户${{U}_{i}}$。

设置秘密值算法执行步骤：用户${{U}_{i}}$随机选择一个秘密值${{x}_{i}}\in Z_{q}^{*}$。值得注意的是，秘密值xi对用户外的所有人保密，在执行用户公钥生成算法和用户私钥生成算法中所用到的秘密值必须是这里选择的秘密值xi。

用户公钥生成算法执行分为两个步骤：

1) 计算得到身份哈希值：

${{Q}_{i}}={{H}_{1}}(\text{I}{{\text{D}}_{i}})\in Z_{q}^{*}(\text{I}{{\text{D}}_{i}}\in {{\{0,1\}}^{*}})$ (1)

2) 用户${{U}_{i}}$计算得到公钥：

$\text{P}{{\text{K}}_{i}}={{x}_{i}}({{P}_{0}}+Q{}_{i}P)\in {{G}_{1}}$ (2)

用户私钥生成算法执行步骤：用户${{U}_{i}}$获得自己的部分私钥${{D}_{i}}$和个人秘密值${{x}_{i}}\in Z_{q}^{*}$后得到私钥$\text{S}{{\text{K}}_{i}}= < {{x}_{i}},{{D}_{i}}>\in (Z_{q}^{*},{{G}_{1}})$。必须指出，在HLL方案中，用户利用私钥生成算法获得完整的私钥必须在KGC执行完部分私钥提取算法及通过公钥生成算法获得个人秘密值xi后执行。

签名算法执行步骤：假设签名方为Alice，其对应的私钥$\text{S}{{\text{K}}_{A}}= < {{x}_{A}},{{D}_{A}}>= < {{x}_{A}},{{(s+{{Q}_{A}})}^{-1}}P>$，相应的公钥$\text{P}{{\text{K}}_{A}}={{x}_{A}}({{P}_{0}}+Q{}_{A}P)$。签名验证方为Bob，其对应的私钥$\text{S}{{\text{K}}_{B}}= < {{x}_{B}},{{D}_{B}}>= < {{x}_{B}},{{(s+{{Q}_{B}})}^{-1}}P>$，相应的公钥$\text{P}{{\text{K}}_{B}}={{x}_{B}}({{P}_{0}}+Q{}_{B}P)$。签名的消息为M，M对于签名方及验证方均是已知的。具体执行步骤如下：

1) Alice选择一个随机值$k\in Z_{q}^{*}$并计算$R={{g}^{{{x}_{A}}}}T={{g}^{k}}\in {{G}_{2}}$。

2) Alice计算$U={{H}_{2}}(M||R||T)\in Z_{q}^{*}$。

3)Alice计算得到消息签名$U={{H}_{2}}(M||R||T)\in Z_{q}^{*}$。

最后，Alice通过公开信道将签名$\sigma =$发送给Bob。

签名验证算法执行步骤：Bob在接收到Alice发送的签名$\sigma =$后验证签名。

1) Bob首先计算${U}'={{H}_{2}}(M||R||T)\in Z_{q}^{*}$。

2) Bob验证等式：

$R=e(V+\text{P}{{\text{K}}_{A}},{U}'({{P}_{0}}+{{Q}_{A}}P))$ (3)

若成立，则接受签名；否则拒绝签名。

2.2 无证书数字签名方案的正确性分析

在一般的数字签名中，签名的原始消息对于签名发送方以及签名验证方均是公开的，所以如果对消息的签名在传输过程中没有被敌手篡改，那么签名验证方在收到签名后，首先计算出正确的${U}'={{H}_{2}}(M||R||T)\in Z_{q}^{*}$，有$U={U}'\in Z_{q}^{*}$，签名则能通过式(3)的验证，即：

$\begin{align} & e(V+\text{P}{{\text{K}}_{A}},{U}'({{P}_{0}}+{{Q}_{A}}P))= \\ & e({{x}_{A}}({{U}^{-1}}{{D}_{A}}-{{P}_{0}}-{{Q}_{A}}P)+\text{P}{{\text{K}}_{A}},{U}'({{P}_{0}}+{{Q}_{A}}P)) \\ \end{align}$ (4)

3 无证书数字签名方案的安全性证明

定理 1 无证书数字签名方案在k-CCA困难性假设及随机预言机(Random Oracle)模型下，对敌手${{A}_{I}}$可抵抗存在性伪造攻击。

证明：挑战者算法C首先与敌手${{A}_{I}}$交互生成k-CCA困难问题的实例。

$P\in {{G}_{1}},sP\in {{G}_{1}},({{t}_{0}},{{t}_{1}},\cdots ,{{t}_{k}})\in Z_{q}^{\text{*}}$ (5)

$({{(s+{{t}_{1}})}^{-1}}P,{{(s+{{t}_{2}})}^{-1}}P,\cdots ,{{(s+{{t}_{k}})}^{-1}}P)\in {{G}_{1}}$ (6)

初始化阶段：设置${{P}_{\text{Pub}}}=sP,g=e(P,P)$。值得注意的是系统主私钥$s\in Z_{q}^{*}$是保密的。随后C随机选择一个指数$l\in \{1,2,\cdots ,k\}$，这里$k\le {{q}_{{{H}_{1}}}}$。

1) ${{H}_{1}}$询问

${{A}_{I}}$可以不重复地对每一个身份$\text{I}{{\text{D}}_{i}}(i\in \{1,2,\cdots ,k\})$进行询问：

① 若$i\ne l$，C向${{A}_{I}}$返回${{Q}_{\text{ID}}}={{t}_{i}}$，并将元组$(i,\text{ID},{{Q}_{\text{ID}}}={{t}_{i}})$添加进一个初始化为空的表${{L}_{1}}$；

② 若$i=l$，则C向${{A}_{I}}$返回身份值${{Q}_{\text{ID}}}={{t}_{0}}$，并将元组$(i,\text{ID},{{Q}_{\text{ID}}}={{t}_{0}})$添加进${{H}_{1}}$哈希询问所维护的表${{L}_{1}}$。

2) ${{H}_{2}}$询问

对于${{A}_{I}}$提起的每一个询问$({{M}_{i}},R,T)$：

① C首先检查表${{L}_{2}}$，若表中存在一个元组$({{M}_{i}},R,T,{{h}_{2}})$，那么C向${{A}_{I}}$返回相对应的Hash值；

② 否则，C任意选择一个Hash值${{h}_{2}}\in Z_{q}^{*}$返回给${{A}_{I}}$，并将相应的元组$({{M}_{i}},R,T,{{h}_{2}})$添加进表${{L}_{2}}$；

③ 提取部分私钥询问，${{A}_{I}}$就一个身份$\text{I}{{\text{D}}_{i}}$向C提起提取部分私钥询问请求；

④ 若i=l，C终止该预言机的模拟；

⑤ 若$i\ne l$，C首先查表${{L}_{K}}=\{i,\text{ID},{{x}_{\text{ID}}},{{D}_{\text{ID}}},\text{P}{{\text{K}}_{\text{ID}}}\}$，如果表中存在该$\text{I}{{\text{D}}_{i}}$对应的元组，则向${{A}_{I}}$返回对应的${{D}_{\text{ID}}}={{(s+{{t}_{i}})}^{-1}}P$；否则，挑战者C先以$\text{I}{{\text{D}}_{i}}$作一次${{H}_{1}}$哈希询问，并将元组$(i,\text{ID},{{Q}_{\text{ID}}}={{t}_{i}})$更新到表${{L}_{1}}$，然后向${{A}_{I}}$返回对应ID的部分私钥${{D}_{\text{ID}}}={{t}_{i}}{{)}^{-1}}P$，并将元组$\{i,\text{ID},\bot ,{{D}_{\text{ID}}},\bot \}$更新到表${{L}_{K}}$，这里“$\bot $”表示为空。

3) 秘密值询问

当${{A}_{I}}$向C以$\text{I}{{\text{D}}_{i}}$并提起询问后：

① C首先查表${{L}_{K}}$，如果该表中存在一个元组$\{i,\text{ID},{{x}_{\text{ID}}},{{D}_{\text{ID}}},\text{P}{{\text{K}}_{\text{ID}}}\}$该$\text{I}{{\text{D}}_{i}}$的公钥未被替换，那么C向${{A}_{I}}$返回该ID对应的秘密值${{x}_{\text{ID}}}$，否则输出模拟失败。

② 否则，C先以$\text{I}{{\text{D}}_{i}}$作一次${{H}_{1}}$哈希询问，并将元组$(i,\text{ID},{{Q}_{\text{ID}}}={{t}_{i}})$更新到表${{L}_{1}}$，然后再作一次部分私钥询问并随机选择一个${{x}_{\text{ID}}}\in Z_{q}^{*}$，最后向${{A}_{I}}$返回秘密值${{x}_{\text{ID}}}$并将元组$\{i,\text{ID},{{x}_{\text{ID}}},{{D}_{\text{ID}}},\text{P}{{\text{K}}_{\text{ID}}}\}$更新到表${{L}_{K}}$，元组中插入的公钥$\text{P}{{\text{K}}_{\text{ID}}}$为C成秘密值后利用公钥生成算法获得的。

4) 请求公钥询问

对于${{A}_{I}}$的每一个询问$\text{I}{{\text{D}}_{i}}$：

① C首先查表${{L}_{K}}$，如果该表中存在一个元组$\{i,\text{ID},{{x}_{\text{ID}}},{{D}_{\text{ID}}},\text{P}{{\text{K}}_{\text{ID}}}\}$，则返回该ID所对应的公钥$\text{P}{{\text{K}}_{\text{ID}}}$；

② 否则，C先以$\text{I}{{\text{D}}_{i}}$作一次${{H}_{1}}$哈希询问，并将元组$(i,\text{ID},{{Q}_{\text{ID}}}={{t}_{i}})$更新到表${{L}_{1}}$，然后执行一次秘密值询问，执行公钥生成算法为其生成一个新的公钥对返回给${{A}_{I}}$，并将新的元组$\{i,\text{ID},{{x}_{\text{ID}}},{{D}_{\text{ID}}},\text{P}{{\text{K}}_{\text{ID}}}\}$添加进该询问维护的表${{L}_{K}}$。

5) 替换公钥询问

${{A}_{I}}$向挑战者提交一个合法的元组$(\text{ID},\text{P}{{\text{{K}'}}_{\text{ID}}})$：

① C首先根据ID搜索表${{L}_{K}}$，如果表中存在对应ID的元组，则将其内容更新为$\{i,\text{ID},\bot ,{{D}_{\text{ID}}},\text{P}{{\text{{K}'}}_{\text{ID}}}\}$；

② 否则，C先以$\text{I}{{\text{D}}_{i}}$作一次${{H}_{1}}$哈希询问，并将元组$(i,\text{ID},{{Q}_{\text{ID}}}={{t}_{i}})$更新到表${{L}_{1}}$，然后再作一次部分私钥提取，并将新元组$(i,\text{ID},{{Q}_{\text{ID}}}={{t}_{i}})$插入进表${{L}_{K}}$。C并不知道敌手伪造用户公钥所用到的秘密值${{{x}'}_{\text{ID}}}$。

6) 提取私钥询问

${{A}_{I}}$就一个身份$\text{I}{{\text{D}}_{i}}$向C起提取私钥询问后：

① 若$i=l$，挑战者终止该预言机的模拟；

② 若$i\ne l$，分两种情况：

第一，挑战者查表${{L}_{K}}$，若表中存在该ID对应的元组，但是该用户的公钥已经被替换，挑战者模拟失败；否则返回该用户对应的私钥$\text{S}{{\text{K}}_{\text{ID}}}=({{x}_{\text{ID}}},{{D}_{\text{ID}}})$；

第二，若表${{L}_{K}}$中不存在该ID对应的元组，查表${{L}_{1}}$，找到该ID对应的身份哈希值${{Q}_{\text{ID}}}$，如果该ID对应元组不存在，则以该ID作一次${{H}_{1}}$询问，并将元组$(i,\text{ID},{{Q}_{\text{ID}}}={{t}_{i}})$更新到表${{L}_{1}}$，然后执行一次秘密值提取询问，将新元组$\{i,\text{ID},{{x}_{\text{ID}}},{{D}_{\text{ID}}},\bot \}$插入表${{L}_{K}}$并向${{A}_{I}}$返回提交ID私钥$\text{S}{{\text{K}}_{\text{ID}}}=({{x}_{\text{ID}}},{{D}_{\text{ID}}})$。

7） 签名询问

在预言机询问中，${{A}_{I}}$提交的询问内容为一个元组$({{M}_{i}},\text{I}{{\text{D}}_{i}},\text{P}{{\text{K}}_{\text{I}{{\text{D}}_{i}}}})$，无论该ID公钥是否被替换，C均能生成一个合法的签名(通过验证等式)：

① 任意选择两个随机数$r,t\in Z_{q}^{*}$，计算得到$R={{g}^{r}},T={{g}^{t}}$；

② 计算$U={{H}_{2}}({{M}_{i}}||R||T)$；

③ 计算$V=r{{U}^{-1}}{{D}_{\text{ID}}}-\text{P}{{\text{K}}_{A}}$，并将生成的签名$(V,R,T)$返回给${{A}_{I}}$。

8) 伪造阶段

最后，${{A}_{I}}$输出一个成功的伪造元组$({{M}^{*}},{{\sigma }^{*}}=({{V}^{*}},{{R}^{*}},{{T}^{*}}),\text{I}{{\text{D}}^{*}},\text{P}{{\text{K}}_{\text{I}{{\text{D}}^{\text{*}}}}})$，元组里的签名${{\sigma }^{\text{*}}}$是能通过验证等式的，$\text{I}{{\text{D}}^{*}}\ne \text{I}{{\text{D}}_{l}}$，若挑战者终止模拟；否则，利用文献[12]中的的攻击方法，C进行重放攻击，生成另一个伪造元组$({{M}^{*}},{{\sigma }^{*}}=({{V}^{*}},{{R}^{*}},{{T}^{*}}),\text{I}{{\text{D}}^{*}},\text{P}{{\text{K}}_{\text{I}{{\text{D}}^{*}}}})$，这里要求${{A}_{I}}$及签名${{\sigma }^{\text{*}}}$需满足：

${{R}^{\text{*}}}=e({{V}^{\text{*}}}+\text{P}{{\text{K}}_{\text{I}{{\text{D}}^{\text{*}}}}},{{U}^{*}}^{\prime }({{P}_{0}}+{{Q}_{\text{I}{{\text{D}}^{*}}}}P))$ (7)

${{R}^{\text{*}}}=e({{V}^{\text{*}}}^{\prime }+\text{P}{{\text{K}}_{\text{I}{{\text{D}}^{\text{*}}}}},{{U}^{*}}^{\prime }({{P}_{0}}+{{Q}_{\text{I}{{\text{D}}^{*}}}}P))$ (8)

最后C则通过两次伪造签名的恒等性$e({{V}^{\text{*}}}+\text{P}{{\text{K}}_{\text{I}{{\text{D}}^{\text{*}}}}},{{U}^{*}}^{\prime }({{P}_{0}}+{{Q}_{\text{I}{{\text{D}}^{*}}}}P))=e({{V}^{\text{*}}}^{'}+\text{P}{{\text{K}}_{\text{I}{{\text{D}}^{\text{*}}}}},{{U}^{*}}^{\prime }({{P}_{0}}+{{Q}_{\text{I}{{\text{D}}^{*}}}}P))$获得k-CCA困难性问题的解${{(s+{{t}_{0}})}^{-1}}P={{D}_{\text{I}{{\text{D}}^{*}}}}={{r}^{-1}}{{u}^{-1}}({{V}^{*}}+\text{P}{{\text{K}}_{\text{I}{{\text{D}}^{\text{*}}}}})$。

定理 2 无证书数字签名方案在$k-CCA$困难性假设以及随机预言机模型下，对敌手${{A}_{II}}$可以抵抗存在性伪造攻击。思路与方法同定理1。

4 无证书数字签名方案的效率分析

表 1列举了本文方案与其他无证书数字签名方案在签名以及验证阶段中计算效率和签名规模上的比较。可以看出，本文方案与其他的无证书数字签名方案相比，不但费时的双线性对运算比其他的无证书数字签名方案少，而且指数运算和计算快速的倍点运算也与其他无证书数字签名方案相当，可见本文方案具有更高的运算效率；另外，本文方案的签名规模也和其他方案大致平衡；最后，在协议的执行过程中，本文方案不需要复杂的运行费时的映射到点(map-to-point)的Hash函数。因此，本文方案是一个高效的无证书数字签名方案。

表1 4个无证书数字签名方案的效率对比
5 结论

本文提出了一个在随机预言机模型下可证明安全的无证书数字签名方案。方案仅需在系统初始化阶段预计算一次双线性对，在验证阶段计算一次双线性对，而在签名阶段不需要进行双线性对运算，因此本方案比以往一些无证书数字签名方案具有更高的计算效率和通信效率。

参考文献
[1] SHAMIR A. Identity-based cryptosystems and signature schemes[C]//Advances in Cryptology-CRYPTO'84. Berlin: Springer-Verlag, 1984.
[2] SAKAI R, OHGISHI K, KASAHARA M. Cryptosystems based on pairing[C]//Proceedings of Symposium on Cryptography and Information Security. Okinawa, Japan:[s.n.], 2000.
[3] AL-RIYAMI S, PATERSON K G. Certificateless public key cryptography[C]//Advances in Cryptology-ASIACRYPT'03. Berlin: Springer-Verlag, 2003.
[4] HUANG Xin-yi, WILLY SUSILO, YI MU, et al. On the security of a certificateless signature scheme from Asiacrypt 2003[C]//4th International Conference on Cryptology and Network Security. Berlin: Springer-Verlag, 2005.
[5] LI X, CHEN K, SUN L. Certificateless signature and proxy signature schemes from bilinear pairings[J]. Lietuvos Matematikos Rinkinys, 2005, 45(1): 76-83.
[6] JU H, KIM D, LEE D, et al. Efficient revocation of security capability in certificateless public key cryptography[C]//Knowledge-Based Intelligent Information and Engineering Systems. Berlin: Springer-Verlag, 2005.
[7] YAP W, HENG S, GOI B. An efficient certificateless signature scheme[C]//Emerging Directions in Embedded and Ubiquitous Computing, EUC Workshops 2006. Berlin: Springer-Verlag, 2006.
[8] ZHANG Zhen-feng, FENG Deng-guo. Key replacement attack on a certificateless signature scheme[EB/OL]. http:// eprint.iacr.org/2006/453.
[9] ZHANG Z, XU J, FENG D. Certificateless public-key signature: Security model and efficient construction[C]// Advances in ACNS 2006. Berlin: Springer-Verlag, 2006.
[10] HE D, CHEN J, ZHANG R. An efficient and provably-secure certificateless signature scheme without bilinear pairings[J]. International Journal of Communication Systems, 2012, 25(11): 1432-1442.
[11] HE De-biao, CHEN Yi-tao, CHEN Jian-hua. An efficient certificateless proxy signature scheme without pairing[J]. Mathematical and Computer Modelling, 2013(57): 2510-2518.