涂晓斌，艾美珍，2，左黎明，2，易传佳，2，周 晓，邓国健

（华东交通大学1. 理学院； 2. 系统工程与密码学研究所； 3. 信息工程学院，江西 南昌330013）

1976 年，传统公钥密码体制被Diffie 和Hellman[1]首次提出，该密码体制中公钥需依赖可信证书机构（certificate authority， CA） 与用户身份关联， 但CA 的管理增加了系统维护成本。 基于身份的密码体制在1984 年被Shamir[2]提出，解决了公钥与用户的关联问题，却带来了密钥托管问题[3]。Al-Riyami 和Paterson[4]在2003 年提出了无证书密码体制，不仅克服了公钥密码体制中的CA 证书管理问题，还解决了基于身份的密码体制的密钥托管问题。 由此，无证书密码体制被广泛应用于数字签名[5]中，成为了当前国内外专家的研究热点[6-8]。 2015 年，汤永利等人[9]提出了一类无证书签名方案，且通过形式化的安全证明表明该方案具有较高安全性。2017 年，周彦伟等人[10]提出了一个高效安全的无证书签名方案，实验表明该方案具有较高的计算效率。 2018 年，吴涛等人[11]指出Huang 等人[12]所提出的无证书方案不能抵抗第二类敌手的攻击，并给出了改进方案。 本文针对于无证书签名方案中公钥与持有者之间没有认证关系，提出了一种基于密钥捆绑的无证书签名方案，通过对用户自选参数和公钥进行密钥捆绑，可有效防止公钥替换攻击，阻断针对无证书签名的第一类攻击者，另一方面该方案中的部分私钥可以通过所申请的部分私钥授权码广播吊销，可以阻断密钥泄露后带来的进一步安全问题。

1 基础知识

1.1 安全性假设

定义1 双线性对[13]（bilinear pairing，BP）

若G1为q 阶加法循环群，G2为q 阶乘法循环群，映射e：G1×G1→G2称为双线性对映射则满足以下3 条性质：

1） 双线性性：e（aP，bQ）ab，其中P，Q∈G1， a，b∈Zq；

2） 非退化性：存在P，Q∈G1，使得e（P，Q）≠1；

3） 可计算性：任给P，Q∈G1，e（P，Q）是可以被计算的。

定义2 逆计算性Diffie-Hellman 问题（inverse computational diffie-hellman problem，Inv-CDH）

1.2 改进后的无证书数字签名定义

由于在传统无证书签名方案中， 用户公钥与用户身份缺乏认证关系, 使得该签名方案容易遭受恶意攻击。 文献[14]提出基于双重的无证书短签名方案，实现了用户身份与秘密值的绑定，避免了恶意用户的公钥替换攻击，但该方案所提出的双重的设置较为复杂，在实际应用中部署较为繁琐。 本文提出了基于密钥捆绑的无证书签名方案，该方案由七个算法组成，其定义如图1 所示。

图1 改进的无证书签名定义Fig.1 Improved certificate-free signature definition

2 基于密钥捆绑的无证书签名方案构造

方案由7 个算法组成，具体描述如下：

1） 系统建立：给定安全参数k，选择阶都为素数q＞2k的加法循环群G1和乘法循环群G2，设P 是G1的生成元，选择双线性对e：G1×G1→G2，选择安全抗碰撞哈希函数：H1：｛0，1｝*→Zq*，H2：｛0，1｝*→Zq*。KGC 任选一个随机数s∈Zq*作为系统主密钥，秘密保存s，计算ypub=sP∈G1作为系统公钥，公布系统参数：params=｛k，G1，G2，e，q，P，ypub，H1，H2｝。

2） 秘密值建立：签名用户user 随机选择秘密值x∈Zq*，计算并公开用户部分公钥y=xP∈G1。

3） 部分私钥提取：签名用户user 身份为ID∈（0，1）*，KGC 随机选择v，w∈Zq*，计算V＝vP，W＝wP，Q＝H1（ID，ypub，y，V，W），计算私钥d=s-1（w+vQ） ，其中V，W 作为用户user 申请部分私钥的授权识别码，可用于广播吊销泄露的部分私钥，最后KGC 通过安全信道发送（d，V，W）给用户。 部分私钥合理性可以通过等式e（dP，ypub）=e（W+QV，P）验证。

4） 私钥建立：签名用户user 的私钥为（x，d）。

5） 公钥建立（密钥捆绑）：签名用户user 计算：U＝xypub，并将用户公钥（y，U，V，W）公开，其中参数U 用于对KGC 和用户进行密钥捆绑，防止公钥替换，任何人可以用e（U，P）＝e（ypub，y）来验证有效性。

6） 签名：签名用户user 对消息m∈（0，1）*签名,得到签名S 的步骤如下：

①计算h=H2（m，ypub，y，U，V，W）；

7） 签名验证：签名验证者验证签名σ=（m，S），步骤如下：

①计算Q=H1（ID，ypub，y，V，W），这个可以预计算后一直使用；

②计算h=H2（m，ypub，y，U，V，W）；

③当e（S，U＋hypub）=e（W+QV，P）成立，则签名验证成功，否则签名验证失败。

方案的正确性证明如下

3 安全性证明

在无证书签名方案中，其安全模型所讨论的敌手[15]主要分为以下两类：

1） 第一类敌手A（模拟不诚实的用户）：不知道系统主密钥和用户部分私钥，但可以替换用户公钥。

2） 第二类敌手A2（模拟恶意但被动的KGC）：掌握了系统主密钥和用户部分私钥，但不能替换用户公钥。

关于两类敌手的安全游戏模型的形式化描述详见文献[16]，限于篇幅，本文不再赘述。 由于本方案在用户公钥建立时进行了密钥捆绑，用户与用户公钥之间存在关联且可公开验证，可以避免了第一类敌手的公钥替换攻击。 因此本文针对掌握系统主密钥和部分私钥的第二类敌手攻击，给出随机预言机下的安全性证明。

定理 在随机预言机模型下，针对第二类敌手A2，在适应性选择消息攻击下本文所提出的无证书签名方案是存在性不可伪造的。

引理 假设A2在概率多项式时间t 内以不可忽略的概率ε 攻破了本文方案， 记qx，qH1，qH2，qE，qpk，qS分别为敌手A2做秘密值询问，H1询问，H2询问，部分私钥解析询问，公钥询问以及签名询问的次数；记tx，tH1，tH2，tE，tpk，tS分别为敌手A2做秘密值询问，H1询问，H2询问、部分私钥解析询问，公钥询问以及签名询问的一次所需的时间，则存在概率多项式时间算法C，在时间t′内以不可忽略的优势ε′解决Inv-CDH 问题。 其中

记列表Lx，LH1，LH2，LE，Lpk，LS为A2的秘密值询问，H1询问，H2询问，部分私钥解析询问，公钥询问以及签名询问的跟踪记录。 A2询问过程如下：

1） 秘密值询问：当A2对IDi进行秘密值询问时，查找由数组（IDi，xIDi，yIDi）构成的列表Lx是否存在IDi的记录，若存在则将查找的值返回给A2，否则：①若IDi≠ID*，则C 随机选取xIDi∈Zq*，计算yIDi=xIDiP∈G1，并将值xIDi发送给A2，且将数组（IDi，xIDi，yIDi）记录到Lx中；②若IDi＝ID*，则令aP∈G1为用户部分公钥yIDi，并将“⊥”返回给A2，同时将数组（IDi，⊥，yIDi）记录到Lx中，其中“⊥”表示为空。

2） H1询问：当A2对IDi进行H1询问时，查找由数组（IDi，vIDi，wIDi，VIDi，WIDi，QIDi）构成的列表LH1是否存在IDi的记录，若存在则向A2返回对应的值，否则：C 随机选取vIDi，wIDi∈Zq*，计算VIDi＝vIDiP，WIDi＝wIDiP，选取QIDi∈Zq*作为H1（IDi，ypub，yIDi，VIDi，WIDi）的值，将值返回给A2，同时将数组（IDi，vIDi，wIDi，VIDi，WIDi，QIDi）记录到LH1中。

3） 部分私钥询问：当A2对IDi进行部分私钥询问时，C 检查由数组（IDi，QIDi，vIDi，wIDi，dIDi）构成的列表LE中是否存在IDi的记录，若存在则将值返回给A2，否则：C 查找出LH1中IDi的记录，计算dIDi=s-1（wIDi＋vIDiQIDi）， 并将dIDi发送给A2，同时将（IDi，QIDi，vIDi，wIDi，dIDi）记录到LE中。

4） 公钥询问：当A2对IDi进行公钥询问时，C 检查由数组（IDi，yIDi，UIDi，VIDi，WIDi）构成的列表Lpk中是否存在IDi的记录，若存在则将值返回值A2，否则：C 查找出IDi在Lx以及LH1中IDi的记录，若IDi≠ID*，则计算UIDi=xIDiypub，否则计算UIDi=xIDiypub=yIDis，将（yIDi，UIDi，VIDi，WIDi）返回给A2，并将（IDi，yIDi，UIDi，VIDi，WIDi）记录到Lpk中。

5） H2询问：当A2对（IDi，mj）进行H2询问时，查找由数组（IDi，mj，hj）构成的列表LH2是否存在（IDi，mj）的记录，若存在则向A2返回对应的值，否则C 查找列表Lpk中IDi的记录，若IDi≠ID*，随机选取hj∈Zq*作为H2（mj，ypub，yIDi，UIDi，VIDi，WIDi）的值，并将hj返回给A2，同时将（IDi，mj，hj）记录到列表LH2中，否则，将给定的实例中的b∈Zq*作为H2（mj，ypub，yIDi，UIDi，VIDi，WIDi）的值，并将b 返回给A2，同时将数组（IDi，mj，b）记录到LH2中。

最后，A2停止询问，输出一个有效签名σ。若签名σ=（m*，S*）是挑战身份ID*的，则C 通过查询所维护的列表Lx，LH1，LH2，LE，Lpk，LS，提取与ID*的相关记录数组，其中：yID*=aP，h=b 为关于m*的H2询问值。

以下为解决Inv-CDH 困难问题的优势：

1） A2对哈希函数H1，H2询问的应答在Zq*中是均匀分布的。

C 解决Inv-CDH 困难问题的优势的下界估计为

而C 所需的多项式时间上界估计为

综上所述，存在概率多项式时间算法，在时间内以不可忽略的优势解决Inv-CDH 问题，这与Inv-CDH问题困难性矛盾。因此在随机预言机模型下，针对第二类敌手，在适应性选择消息攻击下本文所提出的无证书签名方案是存在性不可伪造的。

4 效率分析

4.1 性能比较

表1 为本文方案性能比较分析，其中，M 代表倍乘运算，E 代表指数运算，P 代表双线性对运算。

由表1 可知，在签名阶段本方案仅使用了1 次的倍乘运算，而文献[4]方案使用了1 次双线对运算和3次倍乘运算，文献[6]方案使用了3 次倍乘运算，文献[7]方案使用了1 次倍乘运算，文献[11]方案使用了3 次指数运算和1 次倍乘运算。 本方案在签名阶段的计算量与文献[7]方案相近，较低于文献[4，6，11]方案；在签名验证阶段本方案使用了1 次双线对运算和1 次倍乘运算。文献[4]方案使用了4 次双线对运算和1 次指数运算，文献[6]方案使用了2 次双线对运算和1 次倍乘运算，文献[7]方案使用了1 次双线对运算和2 次指数运算以及1 次倍乘运算，文献[11]方案使用了3 次双线对运算，通过对比可知，在此阶段本文方案计算量较低于文献[4，6，7，11]方案。 综上，本方案计算复杂度较低，在性能效率方面略优于其他方案。

4.2 运行效率比较

在64 位windows7 操作系统、Intel（R） Core（TM） i3-4150 CPU @ 3.50 GHz 的CPU 和DDR3 1 600 MHz 16 G 的内存以及华硕B85M-V5 PLUS 主板的运行环境下， 结合斯坦福大学开发的PBC （Pairing-Based Cryptography）库，实现本文方案和文献[4，6，7，10]方案，并比较各个方案在经过100 次运行后的平均耗时，其实验结果如表2 所示。 由表2 可知，本文方案在签名阶段的平均耗时为0.011 s，在验证阶段平均耗时为0.030 s，方案的平均总耗时为0.098 s。 在方案的平均总耗时上，本文方案与文献[4]方案相比，减少了约50.5%，与文献[6]方案相比，减少了约28.5%，与文献[7]方案相比，减少了约10.1%,与文献[11]方案相比，减少了约45.6%，由此可知，本文提出的签名方案具有较高的运行效率。

表1 方案效率分析与比较Tab.1 Analysis and comparison of scheme efficiency

表2 方案运行100 次平均耗时比较Tab.2 The average time-consuming comparison of scheme running 100 times s

5 结束语

本文提出了一种基于双线对的无证书签名方案，并在随机预言机的模型下，基于Inv-CDH 困难问题给出了方案的安全性证明。与传统的无证书签名方案对比，本文方案实现了公钥与持有者之间的捆绑认知，防止了公钥替换攻击。 通过对比分析可知，本方案具有较高的计算效率。