安全高效的无双线性对的无证书签名方案

胡冰洁，周彦伟，杨 波，张 晶

(1.陕西师范大学 计算机科学学院，陕西 西安710062；2.密码科学技术国家重点实验室，北京100878；3.西安高新一中 初中部东区初级中学，陕西 西安710075)

2003年，Al-Riyaml等[1]提出了无证书公钥密码机制的新密码学原理.在该机制中，用户的私钥由密钥生成中心（Key Generation Center,KGC）和用户共同生成.由于该机制可同时解决传统公钥密码机制和基于身份密码机制的固有问题，即证书管理和密钥托管，得到大量关注，并在知识产权保护、电子政务、网络购物等方面应用广泛.

2004年，文献[2]提出无证书签名方案，引起学者的广泛关注，随后大量的无证书签名方案[3-15]相继被提出.2006年，文献[3]基于双线性对运算提出一个无证书签名方案，但是该方案无法抵抗第一类敌手的公钥替换攻击.为对此安全缺陷进行改进.2008年，文献[4]提出一个改进方案，在该方案中，用户部分私钥由短签名方案生成，并直接和用户选取的秘密值产生签名的私钥，虽然该方案在安全性方面优于文献[3]，但是在计算效率方面，该方案仍基于双线性对运算构造，使得方案的计算效率和实用性较低.2010年，文献[5]在不使用双线性对运算的前提下，设计了一个具有强安全性的无证书签名方案，但是该方案使用了大量的指数运算，在一定程度上降低了方案的计算效率.2012年，文献[6]提出一个无双线性对的无证书签名方案，并在随机预言机模型下基于椭圆曲线离散对数问题对方案的不可伪造性进行了证明.然而文献[7]指出该方案存在安全缺陷，即无法抵抗第一类敌手的公钥替换攻击；并针对此安全缺陷提出了一个改进方案，遗憾的是，该方案仍无法抵抗敌手的公钥替换攻击，使得该方案无法满足实际应用环境对签名机制高安全性的要求.2014年，文献[8]采用改变传统无证书算法顺序的方式对文献[7]的方案进行改进，以KGC公告板形式公开用户公钥，从而进一步对KGC的行为进行约束，然而该方案仍无法抵抗第一类敌手的公钥替换攻击.2016年，文献[9]通过将签名阶段选取的随机数与消息相关的哈希函数值进行绑定的方法对文献[8]的方案进行改进，提出9个相关的改进方案，并在随机预言机模型下基于椭圆曲线离散对数问题对效率最优方案的不可伪造性进行证明，该方案依然存在安全缺陷，即无法抵抗第一类敌手的公钥替换攻击.2018年，文献[10-14]分别提出了无证书签名方案，文献[10]的方案不能抵抗第一类敌手的公钥替换攻击；虽然文献[11-12]所提出的方案是安全的，但是在签名阶段和验证阶段均使用了大量的点乘运算，在一定程度上影响了方案的计算效率和实用性；文献[13-14]在方案的设计中使用了复杂的双线性对运算，并且无法抵抗第一类敌手的公钥替换攻击.2019年，文献[15]基于物联网的实际应用环境提出了一个强不可伪造的无证书签名方案，虽然该方案是安全的，但是其在签名、验证阶段均使用了双线性对运算，使得方案的计算效率较低.

安全性分析表明文献[3,6-10]的方案存在安全缺陷，即不能抵抗第一类敌手的公钥替换攻击，未满足实际应用环境对签名机制强安全性的要求.文献[4,15]在构造方案时使用了复杂的双线性对运算，使得方案的计算效率较低.另外，文献[9]的方案不能抵抗敌手的公钥替换攻击，原因在于未考虑到在用户密钥生成算法中加强用户公钥元素间的联系.

因此，为设计一个同时满足强安全性和高计算效率的无证书签名方案，本文采用不使用双线性对运算的思路，在用户密钥生成算法中，通过哈希函数加强用户公钥元素间联系的方法，设计了一个安全高效的无证书签名方案，并在随机预言机模型下基于椭圆曲线离散对数问题对方案的不可伪造性进行证明，同时对方案的无密钥托管性、不可否认性以及前后向安全性进行分析和说明.经安全分析可知，本文方案在安全性方面，相较于文献[9]有较大的提升，即本文方案对两类敌手可同时具有不可伪造性；经效率分析可知，相比于文献[4,15]，本文方案在签名和验证阶段均未使用双线性对运算.因此，与现有部分方案相比，本文方案满足现实应用环境下对签名机制的强安全性和高计算效率的要求，更适合用于宽带受限的网络环境中.

1 基础知识

1.2 无证书签名方案及安全模型文献[6]详细的介绍了无证书签名方案的基础结构，同时定义了无证书签名方案的安全模型.在该模型中，攻击者被划分为两类敌手：敌手A1（恶意的用户，即第一类敌手）可替换用户公钥但不知道系统的主密钥；敌手A2（恶意的KGC，即第二类敌手）知道系统的主密钥但是不可替换用户公钥.

不可伪造性的具体定义详见文献[6].

1.3 分叉引理在方案的安全性证明中，若挑战者C利用敌手A的一次成功伪造无法解决困难问题，则考虑使用分叉引理，以得到A的另一个成功伪造.分叉引理的实质为A输出关于消息m的两个有效签名的概率至少等于A在随机预言机H所维持的询问-应答列表中找到一个分叉的概率.

2 无证书签名方案

3 安全性证明

参考文献[9]，我们在随机预言机模型下基于椭圆曲线离散对数问题对方案的安全性和不可伪造性进行证明.

4 现有无证书签名方案的安全性分析

经安全性分析得知，文献[6-9]的方案不能抵抗敌手的公钥替换攻击原因在于：未考虑到在用户密钥生成算法中加强用户公钥元素间的联系，或在签名阶段未将选取的随机数与消息进行关联.以文献[9]的方案（方案1）为例，在此章节证明使用本文方案可解决其安全缺陷，使其达到其所声称的安全性，即满足不可伪造性.

文献[9]详细介绍了其方案的各个算法，此处不再进行赘述.

文献[9]在生成用户密钥时未受到用户的约束，使得敌手A1可进行公钥替换攻击.而本文方案在设计用户密钥生成算法时通过哈希函数加强用户各公钥元素间的关联程度.使用本文方案，敌手A1无法对文献[9]的签名过程进行伪造，解决了其方案的安全缺陷.

5 性能及效率分析

本节对方案的性能（无密钥托管性、不可否认性、前后向安全性）以及效率进行分析和说明.

5.1 性能分析（1）无密钥托管性 在本文方案中，由于用户的私钥Ski=(xi,di) 是由KGC生成的部分私钥di和用户选取的秘密值xi共同组成，所以，如果KGC想要掌握用户的完整私钥Ski=(xi,di) 以伪造签名和解密密文，必须获得xi，但xi是用户随机选取的，所以KGC无法获得.另外，如果KGC想通过其掌握的部分公钥信息Xi求解xi， 因为Xi=xi·P，则意味着KGC要求解椭圆曲线离散对数困难问题.

因此，本文方案具有无密钥托管性.

（2）不可否认性 由安全性证明可知，本文所提方案对具有不同能力的两种敌手而言，同时满足不可伪造性.接收方将信息签名 σ=(T,S)，消息mi和发送者身份Di的公钥对Pki=(Xi,Ri)送给验证者，验证者在不需要获得发送者和其的私钥信息的前提下，仅需要进行简单的计算即可确定发送者的身份.通过这种方法，可有效避免发送者的否认行为.验证者所做计算如下：

由表1可知，文献[9-10,13-14]存在安全缺陷，其中文献[14]完全是不安全，文献[9-10,13]无法抵抗第一类敌手的公钥替换攻击，并且文献[13-14]在验证阶段均使用了复杂的双线性对运算，导致其计算效率较低；虽然文献[11-12,15]对第一类敌手和第二类敌手而言均具有不可伪造性，但是其在计算效率方面仍有待提高.具体来说，文献[11-12]在签名和验证阶段均使用了多个点乘运算，文献[15]在签名阶段使用了大量的指数运算，在验证阶段使用了多个双线性对运算.而本文方案在构造过程中采用了不使用双线性对运算的思路，对两类敌手可同时满足不可伪造性，并且在签名阶段中仅使用了3个点乘运算，在验证阶段中仅使用了4个点乘运算.因此，与现有部分方案相比，本文方案具有更强的安全性和更高的计算效率.

表1 效率分析表Tab.1 The tableof efficiency analysis

6 结束语

本文分析现有的无证书签名方案，发现部分方案存在以下情况：部分方案在构造方案时采用了双线性对运算[13-15]，由于双线性对运算的计算量开销较大，导致方案的计算效率和实用性低下；部分不采用双线性对运算构造的方案[11-12]在签名、验证过程中大量使用点乘运算，在一定程度上，使得方案的计算效率和实用性降低；另外，部分方案[9]存在安全缺陷，即无法抵抗第一类敌手的公钥替换攻击，经安全性分析得知，造成此安全缺陷的原因为在密钥生成过程中忽略公钥各元素间的联系或在签名阶段中未将所选取的随机数与消息进行关联.针对此情况，本文设计了一个安全高效的无双线性对的无证书签名方案，并在随机预言机模型下基于椭圆曲线离散对数问题对方案的不可伪造性进行证明，同时对方案的无密钥托管性、不可否认性以及前后向安全性进行分析和说明.经安全分析可知，本文方案可解决现有部分方案的安全缺陷，使其达到其所声称的安全性，即满足不可伪造性.另外，本文方案在计算效率方面均具有较大的提升，即满足实际应用环境对签名机制强安全性、高计算效率的要求.在传统密码学基础原语的研究中，往往会忽略了由于泄露与通信双方相关的秘密状态信息而对其安全性所造成的影响,如何在泄露的现实环境中依然保持无双线性对的无证书签名方案的高机密性值得进一步研究[18].