无双线性对的无证书签名方案的研究

刘高军　吴迪

摘要：分析指出目前已知无证书签名方案的不足，提出一种无需双线性对运算的无证书签名方案，在随机预言机模型下证明了方案的不可伪造性，其安全性基于离散对数困难假设，并对比分析了与已知其它无证书签名方案的安全性和性能。

关键词：无证书公钥密码体制；无证书签名；无双线性对

中图分类号：TP309.7 文献标识码：A 文章编号：1007-9416（2017）04-0092-03

1 引言

Shamir提出的基于身份的公钥密码体制，简化了基于证书的公钥密码体制中的证书撤销以及密钥管理问题，目前已提出了很多基于该体制的签名方案，但密钥托管仍旧是其固有的缺陷。2003年，Al-Riyami和Paterson首次提出了无证书公钥密码体制，该体制克服了基于身份的公钥密码体制中的密钥托管问题，也避免了证书密码学中证书存储和管理的问题。对于无证书公钥密码体制的研究成为了密码学的热点。

2005年，二人又提出了無证书签名方案，但较为严谨的形式化安全证明并未给出。Huang等人 指出了上述方案具有缺陷，可能遭受密钥替换攻击，并提出了另外的方案和一个全新的安全模型，但此安全模型也不完善，因为不能完全抵抗掉类型I攻击者的攻击。Zhang等人改进了上述安全模型，另外给出了一个高效的签名方案，后续又发表了一种无证书签名方案新的构造方法[2]，并把运用新构造方法实现的方案与其它学者提出的方法进行了对比，整体性能较好。文献[2]中提到若把预运算考虑进去，其签名算法比其它方案效率高。即使考虑预运算，签名验证算法中也会用到双线性对。在有限域中，对比标量乘运算和指数运算，双线性对运算比它们更为耗时，根据文献[1]中指出的，运行一次双线性对运算的时间至少是在椭圆曲线上进行标量乘运算耗费时间的21倍，因此，一个无证书签名方案如果不需要进行双线性对运算，那它将会具有较低的计算复杂度和更高的运算效率。评判一个签名方案是否安全可信的标准为：在较强的安全模型下，即使是基于弱的困难性假设，如果能够证明是安全的，不可伪造的，那么该方案就是安全可信的。

本文中的签名方案将DL困难问题替换为BDH困难问题，无论是签名阶段还是验证阶段，算法中均消除了双线性对运算，其安全性基于离散对数困难假设。

2 无证书签名方案通用算法及其安全模型

2.1 无证书签名方案通用算法

无证书签名方案中会牵扯到三位参与者：密钥生成中心，签名者，验证者。无证书签名方案主要有以下算法构成：

（1）参数初始化算法。

输入：安全参数；

输出：系统公开参数，系统主密钥；

密钥生成中心公开系统公开参数，需要保密系统主密钥。

（2）部分私钥和秘密值生成算法。

输入：签名者身份ID，系统公开参数，系统主密钥；

输出：身份ID签名者的部分私钥，秘密值；

密钥生成中心通过安全的信道把和秘密值返还给签名者。

（3）私钥和公钥生成算法。

输入：签名者身份ID，系统公开参数，部分私钥，秘密值；

输出：签名者的公钥，私钥。

（4）签名算法。

输入：系统公开参数，消息，签名者身份ID，公钥，私钥；

输出：签名。

（5）验证签名算法。

输入：系统公开参数，签名，消息，签名者身份ID，公钥；

输出：1或者0。

如果验证通过，输出1，否则输出0。

2.2 安全模型

无证书公钥密码体制中具有两种不同类型的攻击者A和B。根据Huang等人发表的论文中定义的攻击者类型，无证书签名方案中常常会面临两种类型的攻击。

A：攻击者能够查到签名者的公钥，或者能够替换掉签名者的公钥，但系统主密钥是保密的。

B：攻击者能够获取到系统主密钥，但签名者的公钥是保密的，也不能够替换掉签名者的公钥。

定义2.1 在A类型的攻击者的攻击下，如果在概率多项式的时间内，攻击者在如下的攻击步骤中没有获得不可忽略的优势，则该无证书签名方案在适应性选择消息攻击下，具有不可伪造性。

（1）攻击者输入安全参数，运行初始化参数算法，获得系统公开参数publicParams，系统主密钥是保密的。

（2）攻击阶段，攻击者操作如下：

Hash查询：任意输入的hash值都可以查询到。

部分私钥查询：任意选择签名者的身份ID，通过部分私钥和秘密值生成算法，查询到部分私钥。

公钥/私钥查询：任意选择签名者的身份ID，通过私钥和公钥生成算法，查询到对应的公钥/私钥对。

签名者公钥替换：任意选择签名者身份ID，选择一个新公钥进行替换。

签名查询：任意选择签名者身份ID和明文，对该签名者进行公钥/私钥查询，计算对应的签名。

（3）签名伪造：伪造对应身份ID签名者的四元组签名（明文，签名，身份ID，公钥）。

由以上可知，若攻击者想获得胜利，当且仅当：1）伪造的签名是身份ID签名者利用公钥/私钥对消息的一个合法有效签名。2）攻击者没有进行过身份为ID的签名者的部分私钥查询。3）攻击者没有进行过身份ID签名者对消息的签名查询。

定义2.2 在B类型的攻击者的攻击下，如果在概率多项式的时间内，攻击者在如下的攻击步骤中没有获得不可忽略的优势，则该无证书签名方案在适应性选择消息攻击下，具有不可伪造性。

（1）攻击者输入安全参数，运行初始化参数算法，获得系统公开参数publicParams和系统主密钥。

（2）查询阶段，攻击者执行的操作同定义2.1中的第二步骤。

（3）簽名伪造：伪造对应身份ID签名者的四元组签名（明文，签名，身份id，公钥）。

由以上可知，若攻击者想获得胜利，当且仅当：1）伪造的签名是身份id签名者利用公钥/私钥对消息的一个合法有效签名。2）攻击者没有进行过身份为id的签名者的秘密值，也没有替换掉签名者的公钥。3）攻击者没有进行过身份id签名者对消息的签名查询。

定义2.3 如果在上述攻击下，攻击者在概率多项式时间内无法获得胜利，那么这个无证书签名方案在适应性选择消息攻击下就是安全的，存在不可伪造性。

3 无双线性对签名方案

3.1 参数初始化

首先根据安全参数，生成两个满足的素数p、q，之后密钥生成中心随机选择系统主密钥，需保密系统主密钥Z。

公开系统参数，其中参数，为选择的安全Hash函数：，，参数，参数P是椭圆曲线上循环群中任意一阶为q的生成元。

3.2 签名者密钥生成

根据给出的签名者身份，密钥生成中心随机选择参数，计算签名者的部分私钥和部分公钥，并通过安全的渠道返回给签名者。其中，。签名者可以通过计算是否成立来判断密钥生成中心分配给自己的部分私钥是否有效。

签名者随机选择作为其秘密值，生成对应的私钥，公钥，其中，。

3.3 签名操作

签名者A随机选择a，生成签名，将消息和发送给验证者B，其中，，，。

3.4 签名验证操作

当收到签名和后，验证者B将提交至密钥生成中心，通过计算

是否成立来公开验证签名者的身份，其中，若此等式成立，则输出1，否则输出0。

4 安全性证明（证明参考文献[6]中的方法）

定理4.1在ROM中，若存在一个A类型的攻击者能在概率多项式的时间内以绝对优势在定义2.1中的攻击过程中获胜，即说明在多项式受限制时间内能够以（假设Hash查询最多进行次，i=1，2）的优势解决离散对数困难问题。

假设W可以解决离散对数难题，预设其困难问题的输入为，计算出v是W的目标。最初，W需要设置，并维持以下初始值为空的列表用于记录查询结果：，查询列表，，部分私钥查询列表，私钥查询列表，公钥查询列表，签名列表和验证签名查询列表。

其中为攻击者。攻击开始后，W首先发送给。

，查询：列表的格式为，列表的格式为，针对列表，对进行查询，并把查询结果发送给W，若已在列表中存在，则把相应的值返回给。若不存在，则W需在中随机选择，并将结果加入列表中。针对列表，对进行查询，并把查询结果发送给W，若已在列表中存在，则把相应的值返回给。若不存在，则W随机选择c，当c=0时，在中随机选择并返回给，并把结果加入列表中；当c=1时，返回给。

部分私钥提取查询：列表的格式为（ID，D，R），如果在列表中存在，则返回给。否则，W在中随机选择D，，将结果加入列表，中，将（R，D）返回给，其中。

私钥/公钥提取查询：列表的格式为（ID，D，x），如果在列表中存在，则返回给。否则，W进行部分五月提取查询得到参数D，在中随机选择x，把结果加入列表中。列表的格式为（ID，R，X），如果在列表中存在，则返回给。否则，W进行部分私钥提取查询和私钥提取查询，将结果加入列表中，并返回（R，X）给，其中X=xP；若列表和中不存在，则进行查询，若c=1，W在中随机选择r，x，将结果连同c加入列表中，并返回（R，X），其中R=rP，X=xP。若c=0，查询列表，获得（R，D），W在中随机选择x，把结果加入列表，中，并返回（R，X）。

公钥替换/签名查询：由于知道签名者的身份ID，可以把原来的x替换为，把对应的公钥R替换为。针对签名，W先进行公钥提取查询，若c=1，则放弃，否则进行私钥提起查询，在中随机选a，把消息返回给，其中T=aP，X=xP，，，，，。

校验签名查询：W先在列表查询：（1）若c存在且等于0，则在列表中查询，若成立，输出1，表示通过验证，否则终止。其中，。（2）若c存在且等于1，则进行查询，若在查询中存在，输出1，表示通过验证，否则终止。（3）如果公钥提取查询为空，那么进行查询，若在查询中存在，输出1，表示通过验证，否则终止。

经过若干次数查询后，在中随机选择a，，输出对m的有效伪造签名，其中T=aP，，。若伪造签名成功，W会得到，否则，W就没有解决离散对数困难问题。如果对进行过部分私钥或私钥查询，则W就会攻击失败，它不作这种查询的概率至少是；如果对进行查询，则W就会攻击失败，它不做这种查询的概率大于。因此，W解决DL困难问题的优势至少是。

定理4.2在ROM中，若存在一个A类型的攻击者能在概率多项式的时间内以绝对优势在定义2.2中的攻击过程中获胜，即说明在多项式受限制时间内能够以（假设Hash查询最多进行次，i=1，2）的优势解决离散对数困难问题。

假设W可以解决离散对数难题，给定一个随机的DL困难问题实例（p，q，P，aP），则 W的目标是计算出a。为攻击者且知道系统主密钥z，但不能进行公钥替换攻击，其它条件及目标均同定理1中给定的。攻击开始后，W发送给。

可以进行定理3.1中的除校验签名之外的所有查询。

校验签名查询： W先在列表查询：（1）若存在且c=0，则在列表中查询，若成立，输出1，表示通过验证，否则终止模拟，其中。（2） 若存在且c=1，则进行查询，若查询存在结果，输出1，表示通过验证，否则终止。（3）如果进行公钥提取查询结果为空，就进行查询，如果查询存在结果，输出1，表示通过验证，否则终止。

经过若干次数查询后，在中随机选择a，，输出对m的有效伪造签名，其中T=aP，，。若伪造签名成功，W会得到，否则，W就没有解决离散对数困难问题。若对进行过部分私钥或私钥查询，则W失败，它不作这种查询的概率至少是；若对进行查询，则W失败，它不做这种查询的概率大于。因此，W解决DL困难问题的优势至少是。

5 效率分析

若用P表示一个双线性对运算，S表示群中的一次标量乘运算，H表示一次哈希运算，E表示群中的指数运算，表示中一个点的长度，表示群中一个点的长度，群本文签名长度为，公钥长度为，签名和验证的运算总量为3S+2H。文献[8]中方案1的签名长度为，公钥长度为，计算总量为5P+3H+1S。方案2中的签名长度为，公钥长度为，计算总量为3P+7S+3E+1H。文献[3]中签名长度为，公钥长度为，计算总量是2P+2S+6E。文献[6]中签名长度为，公钥长度为，计算总量是4P+2S+2E+1H。

对比得知，尽管文献[4]中方案1的签名长度和公钥长度均小于本方案，但是其计算量高于本方案。文献[4]中方案2和文献[3]的签名长度与本方案相当，文献[2]的签名程度比本方案短，但它们的计算量仍旧高于本方案。显然就签名的计算效率来说，效率明显高于文献[2-4]中的方案。

6 结语

本文简单介绍了已知的无证书签名方案，并分析了它们的缺点，根据无证书签名方案的通用算法，提出了无需双线性对运算的签名方案。本方案在随机预言机模型下证明了其不可伪造性，其安全性是基于离散对数困难假设的，并且无论是在签名阶段还是验证簽名阶段，均没有用到双线性对运算，与其它签名方案相比具有更低的计算复杂度和更好的计算效率的优点，但仍有不足，签名长度和公钥长度较长，不利于在网络中传输，因此仍旧有深入研究的必要。

参考文献

[1]Chen L，Cheng Z，and Smart N P. Identity-based key agreement protocols from Pairings[J]. Int.J.Inf.Secur，2007，6（4）：213-241.

[2] 张磊，张福泰.一类无证书签名方案的构造方法[J].计算机学报，2009，（05）：940-945.

[3]Zhang L，Zhang F，and Zhang F. New efficient certificateless signature//Proceedings of the EUC workshops 2007，Lecture Notes in Computer Science 4809.Taipei，Taiwan：Springer-Verlag，2007：692-703.

[4]Huang X，Mu Y，Susilo W，Wong D，and Wu W.certificateless signature revisited//Proceedings of the ACISP 2007，Lecture Notes in Computer Science 4586.Townsville，Australia：Springer-Verlag，2007：308-322.

[5]Huang，Q.Wong，D.S. Generic certificateless encryption in the standard model.In： MiyaajiA.Kikuchi，H.Rannenberg，K.（eds.） Advances in Information and Computer Security（IWSEC 2007）.LNCS.vol.4752.pp.278-291.Springer，Heidelberg（2007）.