基于无证书聚合签名的导航信息更新方案

丁晓晖，曹素珍，窦凤鸽，马佳佳，王彩芬

(1.西北师范大学 计算机科学与工程学院，甘肃 兰州 730070;2.深圳技术大学 大数据与互联网学院，广东 深圳 518118)

0 引 言

随着传感器技术与人工智能技术的快速发展，传统汽车已经与信息技术相结合，衍生出了一种更加安全智能的驾驶环境-车联网[1](Internet of vehicles，VANETs)。VANETs是智慧城市的重要组成部分，为实时路况导航信息更新提供数据支持，有效的导航信息可以帮助驾驶员更加及时准确地做出选择，从而降低交通事故的发生率，在缓解交通拥堵、安全驾驶等方面都有着极为重要的作用[2]。

为了能够完成实时的路况导航信息更新，及时有效地获取相应路段的交通状态，近年来提出了一些方案[3]，在这些方案中，车辆用户同意将自己收集到的路况信息上传给导航公司，但是这也增加了用户隐私泄露的风险。文献[4]提出的一种高效的基于区块链的车载社交网络隐私保护方案中，采取为车辆用户生成假名的方式实现隐私保护，降低了车辆用户身份隐私泄露的风险。车辆用户在注册过程中由可信中心(trusted authority，TA)为其生成假名，车辆用户使用假名进行通信可以很好地保护自己的隐私，但当其出现违法行为时，TA可以通过其假名恢复出其真实身份，实现条件隐私保护。

此外，如果无法保证车联网环境中信息的真实性，将会引发严重的通信安全问题。VANETs常采用消息签名技术来实现消息的合法性与可认证性。与此同时，通常采用聚合签名技术来降低VANETs中的通信开销，2003年Boneh等人[5]首先在欧洲密码会上提出了聚合签名的概念。聚合签名技术可以将多个用户的签名消息压缩成一个签名消息进行处理，从而提高消息的认证效率，非常适合VANETs通信环境。文献[6]提出了一种基于PKI的聚合签名方案，该方案具有良好的安全性，可抵抗多种安全攻击。但管理和维护证书会造成极大的开销，不太适用于VANETs。文献[7]基于椭圆曲线密码体制和通用的单向散列函数，提出了一种VANETs中有效的基于身份的条件隐私保护认证方案，虽解决了证书管理问题，但却存在密钥托管问题。恶意的密钥生成中心可以轻易地冒充用户进行签名，从而给系统带来严重的安全威胁。利用无证书密码体制构造签名方案[8]可以解决密钥托管问题。Al-Riyami和Paterson[9]在2003年的亚洲密码会上首次提出了无证书密码体制，在使用无证书密码体制构造签名方案时，密钥生成中心仅生成用户的部分私钥，用户随机选取一个秘密值与部分私钥一起形成自己的完整私钥，保证签名安全。文献[10-11]提出了VANETs中基于无证书的聚合签名方案，虽然这些方案适合车联网环境且满足安全需求，但文献[10-11]提出的方案涉及双线性对运算，在增加计算难度的同时也给VANETs通信环境带来了极大的通信负担。为解决该问题，文献[12-15]针对VANETs通信环境提出了一种无双线性对的无证书聚合签名方案，基于椭圆曲线离散对数困难问题构造了更为轻量的聚合签名方案，大大提高了计算效率。遗憾的是，Zhao等人[12]指出文献[14]提出的方案被不可抵抗无证书密码体制中AⅠAⅡ类敌手攻击，文献[15]提出的方案不可抵抗AⅡ类敌手攻击。此外，尽管Zhao等人[12]以及Xu等人[13]提出的方案是安全有效的，但是他们的方案都只被用于传统的车联网环境，因此，提出一个安全高效的具备导航更新功能的无证书聚合签名方案是很有必要的。

基于上述情况，该文提出了车联网中基于无证书聚合签名的导航信息更新方案。主要工作有以下几个方面：

(1)无证书密码体制既能有效解决PKI密码体制中的证书管理问题又可解决基于身份的密码体制中的密钥托管问题。因此本基于无证书密码体制，该文提出了一种适用于VANETs环境的安全高效的实时路况导航信息更新方案，在保证安全性的同时又可以有效降低VANETs环境的通信负担。

(2)通过为车辆用户生成临时假名，实现了对车辆用户信息的条件隐私保护。用户在通信过程中不用担心泄露自己的隐私，在用户有违法行为时，TA可通过假名恢复出用户的真实身份，对其进行追踪。

(3)基于椭圆曲线离散对数困难问题构造了高效安全的聚合签名方案，方案在构造过程中不涉及双线性对运算，具有轻量化的优势，更适合VANETs中快响应低延时的计算需求，能够极大缩短用户端签名时间，降低计算开销，提高应用效率。

(4)为进一步提高车辆签名的可靠性，方案中引入了审查机制，可信中心为参与任务的每一个车辆颁发信誉值，当某一个车辆公开自己的签名消息时，范围内其他符合信誉值要求的车辆会对该签名消息进行审查，若同意该签名消息，车辆会对其进行签名。若不同意该签名消息，将向可信中心举报该车辆用户。

(5)该方案实现了数据的机密性、完整性、可靠性、身份的可认证性以及不可否认性，并给出了严格的安全性证明。通过实验数值分析表明，该方案具有明显的效率优势。

1 预备知识

1.1 符号说明

主要符号说明见表1。

表1 主要符号说明

1.2 椭圆曲线

设方程y2=x3+ax+bmodp上所有的点和一个无穷远点O构成的集合称为椭圆曲线Ep(a,b)，其中，a,b,x,y都在Ep(a,b)上，p为大素数。在给定的运算下，集合中的所有点可以组成Abel群，记为G，运算法则如下：

(1)假设p是Ep(a,b)上的点，无穷远点是O，那么p+O=p；

(2)假设p是Ep(a,b)上的点，它的加法逆元是Q=-p，那么Q+p=O；

1.3 困难问题

椭圆曲线离散对数问题(elliptic curve discrete logarithm problem，ECDLP)：假定G为一个加法循环群，P作为群G的生成元，G的阶为q，Q∈GP。已知P和Q，求满足ap=Q的整数a是困难的。

2 方案的系统模型

在基于无证书聚合签名的导航信息更新方案中，导航公司将需要收集的道路路况信息任务发送给TA，TA接收到任务之后会将信息通过雾节点发送给范围内的车辆用户，在范围内的车辆用户接收到任务后，会根据任务进行相应信息的收集，收集完成后会将相应的消息签名之后广播，附近的一组满足信誉值要求的车辆会对签名消息进行审查，若认为签名合法且消息真实有效，便对该签名消息进行签名并上传给雾节点，否则将向TA举报该车辆用户。雾节点收集到各个车辆用户广播的签名消息后，会对消息签名的合法性进行认证，验证合法后会将签名消息进行聚合，然后打包发送给可信中心TA。TA接收到消息后，会对签名消息进行批量认证，若消息合法，便将消息回馈给导航公司，否则丢弃该消息，并追究相应的违法用户。系统模型如图1所示，它共由五个实体组成：

(1)导航公司：导航公司需要大量的实时信息来动态更新导航信息，然而导航公司本身是不具备这个能力的，因此它将相应的任务发放给可信中心TA，之后再根据TA反馈回来的信息完成相应的导航信息更新工作。

(2)可信中心TA：可信中心TA被认为是完全可信的，一般由政府机构担任。在该方案中，TA主要负责车辆以及雾节点的注册，同时为了保护车辆的隐私，在注册过程中会为车辆生成伪身份，但当车辆出现违法行为时，TA也可从其伪身份中获取他的真实身份，并且追究其相应的责任。此外，可信中心还负责为车辆用户生成信誉值，并负责信誉值的更新。最后，可信中心会对雾节点发送过来的聚合签名消息进行批量认证，认证通过后将其发送给导航公司。

(3)密钥生成中心(key generation center，KGC)：KGC被认为是半可信的，主要负责系统参数建立以及密钥生成。当其收到可信中心发送的车辆伪身份信息后，会执行密钥生成算法，为车辆用户生成部分私钥。

(4)雾节点：雾节点一般分布在道路两侧，用来广播TA发布的任务信息以及收集车辆用户所广播的签名消息，雾节点在TA进行注册。在收集到范围内车辆的签名消息后，它会首先验证消息的合法性，若合法雾节点会对其进行聚合，并将聚合后的消息发送给可信中心TA。

(5)车辆用户：车辆用户在接收到雾节点广播的任务后，若有符合任务要求的信息，车辆用户会将其签名之后进行广播。此外，车辆用户还需完成对附近其他车辆用户的签名消息进行审查的工作。

图1 系统模型

3 方案描述

(1)系统建立算法。

(2)雾节点注册阶段。

(3)车辆注册阶段。

车辆需要在可信中心处进行注册，为实现条件隐私保护，TA会为车辆生成一个假身份，车辆使用假身份进行通信时，不会泄露自身的真实身份信息，但当车辆出现违法行为时，TA可以通过其假身份恢复出其真实身份，并追究车辆相应的责任。设车辆的真实身份为IDi，选取当前时间为ti，使用函数f(ti)计算当前时间戳。TA为其生成假身份VIDi=h1(IDi，f(ti))。TA保存(IDi,f(ti),VIDi)，然后将VIDi发送给KGC用来生成部分私钥。此外可信中心还将为车辆生成信誉值，并负责信誉值的更新。

(4)部分私钥生成算法。

(5)用户秘密值生成算法。

(6)假名生成算法。

(7)任务发放。

导航公司将任务taski=(j,area,type,tr)发送给TA，这其中j为本次任务的编号，area为需要收集信息的大致路段，type为收集信息的类型要求，tr为对车辆用户要求的信誉阈值。TA根据要求将相应任务下发给相应路段的雾节点，雾节点接受到任务后会把任务进行广播，满足任务要求且信誉值符合规定的车辆会将收集到的消息签名之后进行广播，相应路段其他车辆在验证签名消息合法后将其重新签名发送给雾节点，雾节点会将所有的签名消息进行认证后进行聚合，并发送给TA。

(8)数据的收集及上传。

为了提高收集数据的可靠性与准确性，当一个车辆VA广播自己的签名消息后，附近的一组满足信誉值要求的车辆(V1…Vn)会首先验证VA的签名是否合法，若合法，车辆用户会验证消息m是否真实有效。如果车辆用户不同意该消息，可及时向可信中心TA进行举报，TA经过调查后若确认车辆VA违规，会扣除车辆VA以及同意消息m车辆用户的信誉值，同时增加不同意消息m车辆用户的信誉值。若车辆用户信誉值过低，可信中心则会撤销该车辆用户的身份。若车辆用户(V1…Vn)同意消息m，则对该消息进行签名，并将签名后的消息全部上传给雾节点，雾节点进行认证后将签名消息进行聚合，然后将聚合签名消息发送给可信中心进行认证。以下是数据收集与上传的具体过程：

①签名算法。

②附近车辆用户审查阶段。

当附近车辆用户(V1…Vn)接收到车辆用户广播的签名σi=(Ci,Qi)与消息mi之后，若同意消息mi真实且有效，则验证等式：

QiP=Ci+hs·Ai+hs·hai·PK+hj·PKi

是否成立。若成立，则认为VA的签名合法，其他车辆(V1…Vn)对消息mi进行签名，并广播发送给附近的雾节点。若附近车辆用户认为车辆用户VA存在违法行为，可将其向可信中心举报。可信中心在验证之后会对相应车辆用户的信誉值进行增加或扣除。

③雾节点聚合签名阶段。

雾节点在接收到n个车辆用户的签名消息后，会首先验证每个车辆用户的签名消息是否合法，对于合法的签名消息雾节点会将其进行聚合，对于违法的签名消息，雾节点会将其摒弃，并上报TA对其进行违法追踪，扣除其信誉值。首先雾节点对每一个单一的消息进行计算：

hs=h5(mi,Fi,PKi,Ai,Ci)

hj=h5(mi,Ai,Fi,Ci,PKi)

hai=h2(Ai‖PK‖f(ti))

验证等式：

QiP=Ci+hs·Ai+hs·hai·PK+hj·PKi

是否成立。若成立，则接受该签名消息，否则将其丢弃。对于验证成功的n个车辆用户{v1,v2,…,vn}的n个签名消息：

{(m1,σ1=(C1,Q1))…(mn,σn=(Cn,Qn))}；

④可信中心批量认证阶段。

可信中心接收到聚合签名后，通过以下等式进行批量验证：

若成立,则接受该消息，并将其反馈给导航公司。否则丢弃该消息，并追查违法用户。

(9)导航信息更新。

导航公司接受到可信中心发送过来的消息后，会根据消息及时地更新相应路段的导航信息，大大地缓解交通压力的同时降低事故发生率。

4 安全性分析

4.1 正确性分析

对单个签名进行正确性验证。

验证等式：

QiP=Ci+hs·Ai+hs·hai·PK+hj·PKi

是否成立，验证过程如下：

QiP=(ci+hjSKi+hsSVi)P=

ciP+hjSKiP+hsSViP=

Ci+hjPKi+hs(ai+hais)P=

Ci+hjPKi+hsaiP+hshaisP=

Ci+hjPKi+hsAi+hshaiPK

得证。

同理，可以通过对下列等式进行验证，得出聚合签名的正确性：

4.2 安全性证明

该文的聚合签名方案是基于无证书的密码体制，依据文献[16]提出的安全模型，该方案的安全性考虑两种不同的敌手，第一类普通敌手AI以及第二类超级敌手AII。

定理1：在随机预言模型中，如果在多项式时间内存在一个普通敌手AI能够以不可忽略的概率ε赢得游戏，那么一定存在一个挑战者能够以以下的优势解决ECDLP困难问题：

其中，qh2、qh3、qh4、qh5表示对应的哈希预言机查询次数，qcu表示创建用户预言机查询次数，qk表示用户的部分私钥查询次数。

证明：假设一个普通敌手AI在方案中能够以不可忽略的优势ε赢得游戏，即成功伪造目标用户VIDi的有效签名，则认为与其交互的挑战者CE能够成功解决ECDLP困难问题。CE与AI按照如下步骤进行游戏交互。

(1)初始化阶段。

挑战者CE执行算法构建系统，并令Q=PK,挑战者公开系统参数，并建立维护以下四个列表：

L1列表(VID,A,PK,Th2)

L2列表(VID,PKi,Th3)

L3列表(VID,m,Fi,SKi,A)

L4列表(VID,m,Fi,SKi,A,Th4,Th5,C,Q)

(2)预言机查询阶段。

在本阶段，第一类普通敌手与挑战者之间进行预言机交互。

h2预言机查询：

h3预言机查询：

h4预言机查询：

h5预言机查询：

普通敌手AI以(VID,m)进行询问，若在L4列表中已经存在相应元组，则返回Th5给敌手AI。若不存在，则挑战者执行用户秘密值预言机查询，以及部分私钥预言机查询。计算Th5=h5(mi,Fi,PKi,Ai,Ci)并将Th5返回给敌手AI。

用户创建预言机查询：

敌手AI以VID向挑战者进行询问，挑战者查询L3列表，若元组不存在列表中，则执行如下操作：

①当VID=VIDm时。

挑战者随机选择随机选取：

计算：

A=a·P

SK1=h3(r1‖f(ti)‖PK)

SK2=h3(r2‖f(ti)‖PK)

SK=b(SK1+SK2),PK=SK·P,SV=⊥

②当VID≠VIDm时。

挑战者随机选择随机选取：

计算：

A=a·P

A=SK·P-Th2·Q

然后将其添加到相应的列表中。若有相应的元组，则挑战者查询L1列表，若存在相应的(VID,A,Th2)，验证是否满足h2(A,Q)→Th2，若不满足，则挑战者结束本次游戏，否则返回用户信息。

用户秘密值预言机查询：

普通敌手AI以VID进行询问，挑战者查询L3列表，若在L3列表中已经存在相应元组，则返回(PK,SK)给敌手AI。

若不存在，挑战者随机选取：

计算：

SK1=h3(r1‖f(ti)‖PK)

SK2=h3(r2‖f(ti)‖PK)

SK=b(SK1+SK2)

PK=SK·P

并将(PK,SK)返回给敌手AI。

部分私钥预言机查询：

公钥预言机查询：

敌手以VID进行询问，挑战者查询L3列表，若在L3列表中已经存在相应元组，挑战者返回(A,PK)给AI，若不存在相应的元组，挑战者执行用户秘密值预言机查询以及部分私钥预言机查询。然后将(A,PK)返回给AI。

签名预言机查询：

当挑战者以(mi,Ai,Fi,VIDi)进行询问时，挑战者随机选择：

Th2i=h2(Ai‖PK‖f(ti))

并将{Ai,Th2i}加入到L1列表中。

令：

Ci=QiP-hs·Ai-hs·Th2i·PK-Th5i·PKi

将(mi,Ci,Qi,Ai)插入到L3L4中。

(3)输出阶段。

最后，敌手AI输出(VID,A,m)的一个伪造签名，此时，若VID≠VIDm，则挑战者宣布失败，否则，挑战者从签名预言机中找到如下签名消息：

(mi,σi=(Ai,Qi),Fi,Ci,PKi)

若挑战者赢得游戏，则有：

QiP=Ci+hs·Ai+hs·Th2i·PK+Th5i·PKi

(1)

敌手AI能够在多项式时间内以不同的Qi，hs，重新构造一个新的有效的签名：

即以下等式成立：

根据式(1)以及式(2)，挑战者C可以计算出：

(3)

最后，计算挑战者CE解决ECDLP困难问题的优势，若挑战者能够成功解决ECDLP问题，应同时满足以下两种情况：

E1:挑战者CE从来没有终止过游戏。

所以，挑战者取胜的概率为：

ε*=pr[E1∧E2]=pr[E1]pr[E1|E2]

(4)

这其中，pr[E1|E2]=ε。

又经过游戏过程分析计算得：

(5)

所以，由式(4)、式(5)可以得出：

显然，若挑战者CE能够以优势ε*成功伪造出一个签名，那么挑战者便可以解决ECDLP问题，然而在随机预言模型下，ECDLP问题是困难问题，也就是说敌手的优势是不存在的。即该方案可以抵抗敌手AI的伪造攻击。证明完毕。

定理2：在随机预言模型中，如果在多项式时间内存在一个超级敌手AII能够以不可忽略的概率ε赢得游戏，那么一定存在一个挑战者能够以以下的优势解决ECDLP困难问题：

其中，qh2、qh3、qh4、qh5表示对应的哈希预言机查询次数，qcu表示创建用户预言机查询次数，qb表示用户的部分私钥查询次数，qm表示用户秘密值查询次数。

经证明，该方案能够抵抗超级敌手AII的伪造攻击，方案安全，证明过程与定理1类似，篇幅限制，在此不再赘述。

5 性能分析

5.1 方案性能对比

符号说明如表2所示。

表2 符号说明

表3 各方案主要性能对比

如表3所示，将方案所满足的主要性能同竞争方案做分析比对，结果表明，文献[17]提出的方案不满足无双线性对且不能抵抗AI类敌手攻击。文献[15]采用椭圆曲线构造了更轻量的密码方案，但其却不能抵抗恶意的KGC攻击。文献[11]提出的无证书聚合签名方案虽满足安全性要求，但其却有着极大的计算开销，在VANETs环境中会造成极大的通信负担。文中方案在满足所有的安全性要求的同时采用椭圆曲线构造了更为轻量的无证书聚合签名方案，更适用于VANETs通信环境。

5.2 方案计算开销对比

如表4所示，文献[11]提出的无证书聚合签名方案在签名算法部分的总计算开销为5Tbm+3Tba+4Th，在验证算法部分的总计算开销为4Tbp+2Tbm+Tba+4Th，在聚合签名算法部分的总开销为4Tbp+7nTbm+nTba+4nTh。同理可得文献[17]以及文献[15]所提出方案的总计算开销。

表4 方案计算开销

在文中方案中，签名算法的总计算开销为Tem+2Th，验证算法的总计算开销为5Tem+3Tea+3Th，聚合签名算法的总开销为(3n+2)Tem+3nTea+3nTh。可以看出，由于采用椭圆曲线构造了无证书聚合签名方案，避免了复杂的双线性对运算，使得文中方案在计算开销方面较文献[11，17]提出的无证书聚合签名方案有较大优势。

为了更清楚地对比方案的计算效率，在配备Intel Core i5-7500处理器，3.0 GHz主频，以及8 GB的内存环境下进行了一个模拟实验。结果如图2、图3所示，将该文提出的方案同文献[11,15,17]等的方案进行计算效率对比。

结果表明，该文提出的方案在签名算法以及验证算法方面的计算效率较文献[11,17]提出的方案有明显优势，与文献[15]基本相当。但文献[15]提出的方案不能抵抗AII类敌手攻击，因此安全性不如文中方案。此外文中方案采用了聚合签名技术，进一步降低了计算开销，使其可以满足通信计算开销极大的VANETs环境。

图2 签名算法消耗时间

图3 验证算法消耗时间

6 结束语

针对VANETs中路况导航信息更新中的安全隐私问题，提出了一种基于无证书密码体制具有条件隐私保护以及审查机制的无证书聚合签名方案，并通过严格的安全性证明表述了方案的安全性。通过生成临时假名，实现车辆用户的条件隐私保护。方案的构造过程中未使用双线性对运算，并使用聚合签名技术使得方案的计算开销大大降低。通过与其他方案的性能分析对比表明，该方案在安全性及计算效率上有明显优势，适用于VANETs应用环境。