一个基于区块链的车载网无证书签名方案

周楠，杜红珍

（宝鸡文理学院数学与信息科学学院，陕西宝鸡 721013）

车载自组网（Vehicle Ad hoc Network，VANET）简称车载网，不仅能为车辆用户提供安全性服务，还可提供娱乐等增值类服务，在智能交通中发挥着重要作用。

近年来，基于区块链技术独有的优良特性，已经有不少研究者尝试将区块链技术运用到VANET中。如文献[1]在加密过程用到了区块链中的Merkle树结构。文献[2]使用了区块链技术中的分布式技术存储数据，以实现车辆的隐私及交通信息的完整性。文献[3]则用到了区块链技术的不可篡改性和可扩展性等。

无证书公钥密码体制（Certificateless Public Key Crypotography，CLPKC）摒弃了基于传统公钥基础设施[4-5]和基于身份[6-7]的证书管理和密钥托管的弊端。已有的无证书签名方案[8-11]大都涉及双线性对的大量使用，存在成本高、效率低等问题，甚至有些方案[12-14]不满足最基本的安全性需求。

基于上述研究，文中基于区块链技术提出了一个适用于VANET 的无证书签名方案，并进行了严格的安全性分析和性能分析。结果表明，在随机预言机模型下，文中方案可证明是安全的，且满足车载网的安全和隐私相关需求。

1.1 VANET系统模型

文中对传统VANET 系统模型进行了改进。在新的系统模型中，可信机构为密钥生成中心（Key Generation Center，KGC）。引入不同结构的Merkle 树分别作为区块链BC-1 和区块链BC-2 链接，在VANET 系统中用于存储不同的数据。其中，BC-1用于存储车辆用户生成的伪身份和对应的未撤销的参数，BC-2 用于存储验证后被撤销的伪身份。基于区块链的车载网系统模型如图1 所示。

图1 基于区块链的车载网系统模型

1.2 数学难题

双线性对、CDH 问题及ECDL问题详见文献[13]。

2.1 系统建立算法

输入安全参数k，(G1,+)和(G2,·)是两个q阶循环群，P为G1群生成元，双线性对e:G1×G1→G2。KGC随机取，计算系统公钥：

选取五个安全哈希函数，分别定义如下：

最后，秘密保存主密钥s，公布系统参数：

2.2 部分私钥生成算法

给定用户Vi的真实身份RIDi，KGC 计算θi=s-1H0(RIDi)，将(RIDi,H0(RIDi))作为Vi的数据存储以便追踪。随机选取，计算hi=H1(RIDi,Ppub)，ωi=λiH0(RIDi)，xi=s-1+hiλi。通过安全信道将部分私钥PSKi=(xi,θi,ωi)发送给车辆用户Vi。

2.3 用户密钥生成算法

接收到部分私钥PSKi后，Vi先验证从KGC 接收到的部分私钥是否满足等式若等式成立，则接收部分私钥，否则请求重新发送部分私钥。随机取秘密值，用户私钥为SKi=(xi,yi)，计算Xi=xiPpub2和Yi=yiPpub2，将PKi=(Xi,Yi)作为自身公钥。

2.4 伪身份生成算法

2.5 签名算法

对待签名消息Mi，Vi随机选取zi∈Zq*，计算Zi=ziPpub2。在时间段ti内，Vi计算ji=H2(Mi,PIDi,PKi,ti,Zi)，ηi=H3(Mi,PIDi,Ppub,ti,Zi)，Γi=H4(Mi,PIDi,PKi,Ppub,Zi)，δi=(zi+ηixi)Ppub1+jiyiΓi。

(Zi,δi)即为ti时间段内伪身份PIDi的用户在消息Mi上的签名。Vi将消息/签名数组(Mi,(Zi,δi))及PIDi,ti广播到RSU。

2.6 验证算法

RSU 接收到(Mi,PIDi,Zi,δi,ti)后，先检查时间戳ti是否有效，若有效，可搜索区块链BC-1 和BC-2 以获得伪身份PIDi，确保收到的PIDi存在于BC-1，而非BC-2，这表示已将PIDi分配给Vi，并且尚未撤销。

1）单个签名验证

接收到Vi的数组(Mi,(Zi,δi)) 及PIDi,ti后，RSU进行哈希运算得ji、ηi和Γi。验证e(δi,Ppub2)=e((Zi+ηiXi),Ppub1)·e(Γi,jiYi)是否成立，若成立，则接受签名(Zi,δi)；
否则，RSU 将拒绝这个签名。

2）批量签名验证

接收到不同车辆用户(V1,V2,…,Vn)的消息签名组(M1,PID1,Z1,δ1,t1),(M2,PID2,Z2,δ2,t2),…,(Mn,PIDn,Zn,δn,tn) 后，RSU 验 证 等 式是否成立；
若成立，则接受Mi上签名(Zi,δi)(i=1,2,…,n)，否则拒绝签名。

2.7 追踪算法

若某用户Vi发生违法犯罪行为，KGC 可追踪其真实身份，撤销其伪身份PIDi并存储在区块链BC-2 中。KGC 用s搜索满足e(PIDi,sTi)=e(H0(RIDi),P+PIDi) 的信息(RIDi,Ti)，KGC 在数据库中找到H0(RIDi)，使e(PIDi,sTi)=e(H0(RIDi),P+PIDi) 成立，即揭露了Vi的真实身份PIDi。最终，撤销Vi伪身份并将其存储在区块链BC-2 中。

无证书签名安全模型见文献[13]。

3.1 可证明安全

定理1 在随机预言机模型下，假设敌手A1在多项式时间t内，最多进行qHi(i=0,1,2,3,4) 次哈希询问，qk次部分私钥询问，qs次私钥询问，qp次公钥询问，qps次伪身份询问，qsig次签名询问，以不可忽略的优势ε赢得Game1，则存在一多项式算法C 在内，以不可忽略的优势解决CDH 难题，其中，tm表示在群G1中进行一次点乘运算所需的时间。

证明：输入某CDH 的任意实例，令P∈G1,X=aP,Y=bP,C 与A1进行Game1 中的交互，利用A1作为子程序计算出abP。C 需维护列表L0、L1、L2、L3、L4、Lk用于记录A1在Game1 进行的询问，初始状态记录为空。

1）C 运行系统建立算法，令Ppub1=X，发送params={q,P,G1,G2,e,Ppub,H0,H1,H2,H3,H4}给A1。C选择索引1 ≤j≤qH0，qH0表示对预言机H0进行的最大询问次数。

2）A1与C 进行一下交互询问。

H0询问：C 维护列表L0=(RIDi,di)。若存在相应记录，则返还记录值；
否则，随机选取di∈G1添加到表L0，并返还di给A1。

H1询问：C 维护表L1=(RIDi,Ppub,ei)。若存在相应记录，则返还记录值；
否则，随机选取添加到表L1，并返还ei给A1。

H2询问：C 维护L2=(Mi,PIDi,PKi,ti,Zi,fi)。若存在相应记录，则返还记录值；
否则随机取添加到表L2，并返还fi给A1。

H3询问：C 维护L3=(Mi,PIDi,Ppub,ti,Zi,gi)。若存在相应记录，则返还记录值；
否则随机取添加到表L3，并返还gi给A1。

H4询问：C 维护L4=(Mi,PIDi,PKi,Ppub,Zi,ki)。若有相应记录，则返还记录值；
否则，随机取ki∈G1添加到表L4，并返还ki给A1。

部分私钥询问：C 维护列表Lk=(RIDiPSKi,SKi,PKi,PIDi) 。当i≠j时，若有相应记录，则返还记录值；
否则，C 查询表L0和L1，随机取,ωi∈G1，计算θi=xidi-ωiei，添加元组PSKi=(xi,θi,ωi)到列表Lk中，并返还PSKi给A1；
当i=j时，终止程序。

伪身份询问：C 维护Lk=(RIDi,PSKi,SKi,PKi,PIDi)。若存在相应记录，则返还记录值；
否则，C 随机取计算，添加PIDi到Lk，返还PIDi。

公钥询问：C 维护Lk=(RIDi,PSKi,SKi,PKi,PIDi) 。若存在相应记录，则返还记录值；
否则，C 进行部分私钥查询获得xi，随机取yi∈Z*q，计算Xi=xiPpub2,Yi=yiPpub2，添加PKi=(Xi,Yi)到Lk，返还(Xi,Yi)给A1。

私钥询问：C 维护Lk=(RIDi,PSKi,SKi,PKi,PIDi)。当i≠j时，若存在相应记录，则返还记录值；
否则，C进行公钥查询生成公私钥对(SKi,PKi)，添加(RIDi,PSKi,SKi,PKi,PIDi) 到Lk，返还(xi,yi)；
当i=j时，终止程序。

替换公钥询问：A1选择新公钥，并发送。C 查看Lk是否存在记录PKi，若存在，令，SKi=⊥；
否则，添加(RIDi,PSKi,,⊥,PIDi)到Lk。

签名询问：C 由公钥询问得(SKi,PKi) 。当i≠j时，C 随机取，计算Zi=ziPpub2，fi=H2(Mi,PIDi,PKi,ti,Zi)，gi=H3(Mi,PIDi,Ppub,ti,Zi)，ki=H4(Mi,PIDi,PKi,Ppub,Zi)，δi=(zi+gixi)Ppub1+fiyiki，返还(Zi,δi)。

3）A1输出一个在消息上的伪造签名。若，则C 终止程序；
否则，由分叉引理[14]C 和A1选择不同哈希函数H3进行与上述相同的模拟交互过程，得到另外一个有效签名。于是有：

A1在此Game1 中获胜，当且仅当以下事件同时发生。

E1：是在消息上生成的有效签名；

E2：A1没有查询过的部分私钥；

E3：A1没有查询过的签名。

由P(E1)=ε，知，C 利用A1解决CDH 难题的优势为。

定理2 在随机预言机模型下，假设敌手A2能在多项式时间t内，最多进行qHi(i=0,1,2,3,4)次哈希询问，qs次私钥询问，qps次伪身份询问，qp次公钥询问，qsig次签名询问，以不可忽略的优势ε赢得Game2，则存在一个多项式算法C，在多项式时间内，能以不可忽略的优势解决CDH 难题，其中，tm表示在群G1中进行一次点乘运算所需的时间。

证明：输入某CDH 的任意实例，令P∈G1,X=aP,Y=bP，C 与A2进行Game2 中的交互，利用A2作为子程序计算出abP。C 需要维护表L0、L1、L2、L3、L4、Lk，用于记录A2在Game2 中的询问，初始状态记录为空。

1）C 运行系统建立算法，令Ppub1=sP，将主密钥s和params={q,P,G1,G2,e,Ppub,H0,H1,H2,H3,H4) 发送给A2。

2）A2与C 进行一下交互询问。

由于H0、H1、H2、H3伪身份询问和签名询问与定理1 中类似，不再赘述。

H4询问：C 维护L4=(Mi,PIDi,PKi,Ppub,Zi,ki)。若存在相应记录，则返还记录值；
否则，随机取，令ki=τiY=τi(bP)，并添加到L4，返还ki给A2。

私钥询问：C 维护Lk=(RIDi,PSKi,SKi,PKi,PIDi)。当i≠j时，若存在相应记录，则返还记录值；
否则，C 随机取，计算Yi=yiPpub2，将SKi=(xi,yi)，PKi=(Xi,Yi) 添加到Lk中，返还(xi,yi) ；
当i=j时，终止程序。

公钥询问：C 维护Lk=(RIDi,PSKi,SKi,PKi,PIDi)。当i≠j时，若存在相应记录，则返还记录值；
否则，C随机取，计算Yi=yiPpub2，添加SKi、PKi到Lk，返还(Xi,Yi)；
当i=j时，令Yi=yiX，添加(RIDi,PSKi,⊥,PKi,PIDi)到Lk，返还(Xi,Yi)给A2。

3）A2输出一个在消息上的伪造签名。若，则C 终止程序；
否则，。计算出。由CDH 的难解性可知方案在A2攻击下是安全的。

与定理1 类似，可得C 利用A2解决CDH 难题的优势为。

3.2 安全及隐私需求分析

3.2.1 认证性及消息完整性

由定理1 和定理2 可知，方案满足签名的认证性及消息完整性需求。

3.2.2 匿名性

因PIDi=γiθi=γis-1H0(RIDi)，Vi的伪身份PIDi由s和随机数γi生成，仅KGC 和Vi知道s。又因γi是随机选取的，即便敌手获得Vi伪身份PIDi，也无法求得θi。且敌手还须从H0(RIDi)计算出RIDi，基于哈希函数的单向性，方案可提供匿名性保护。

3.2.3 可追踪性

若某车辆发生违法犯罪行为，KGC 使用密钥s搜索使e(PIDi,sTi)=e(H0(RIDi),P+PIDi)成立的(RIDi,Ti)。基于区块链的特性，在区块链BC-1 中可以获得(PIDi,Ti)。此外，KGC 可在数据库中找到满足等式e(PIDi,sTi)=e(H0(RIDi),P+PIDi)的H0(RIDi)，也就揭露了Vi的真实身份RIDi。KGC 随之撤销Vi的伪身份PIDi，并存储在区块链BC-2 中。最终，KGC 查出违法犯罪车辆用户Vi的真实身份RIDi。

文中主要从安全性和计算量两个方面对方案进行性能分析。

在安全性方面，考虑方案能否提供认证性和消息完整性，为车辆用户提供匿名性保护及抵抗两类敌手的攻击，文献[14-16]方案未涉及双线性对运算，故不作比较。安全性分析如表1 所示。

表1 安全性分析

由表1 可知，文献[9]不满足可追踪性；
文献[12]方案无法抵抗敌手A2；
文献[13]方案不能抵抗敌手A1和A2；
而文中方案满足所有安全及隐私需求。

在计算量方面，文中采用文献[13]中的实验结果，方案涉及运算分别用Tbp、Tsm、Tpa表示运行一次双线性对运算、一个群上标量乘运算和一个点加运算所需时间，运算所需基础执行时间如表2 所示。

表2 基础执行时间

如表3 所示，相比于文献[9]和[12]方案，文中方案在签名和验证方面都具有一定优势，签名阶段耗时减少了1.349 4 ms，验证阶段由于减少了双线性对和群上标量乘运算的使用，使得耗时分别减少了7.906 8 ms 和1.345 ms，方案总耗时分别减少了9.256 2 ms 和2.694 4 ms，且总耗时最短，仅为26.419 2 ms。另外，虽然在计算量方面，文中方案不及文献[13]方案，但考虑到签名方案安全的重要性，文中方案能在保证安全性的前提下，一定程度上减少了签名方案的计算量和耗时，因此，与同类方案比具有一定优势。

表3 计算复杂度对比

针对车载网存在的不安全、成本高和效率低等问题，文中引入区块链技术对传统车载网系统进行了改进，并基于此模型构造了一个安全的适用于车载网的无证书签名方案，在随机预言机模型下严格证明了方案的不可伪造性。性能分析结果表明，文中方案与同类型方案相比，在安全性和计算量上具有一定的优势，适用于车载网的实际应用。