车联网中格上基于身份的隐私保护协议

赵宗渠,王瀚博,李 英,汤永利

(河南理工大学 软件学院,河南 焦作 454000)

0 引 言

2004年国际电信联盟(ITU)发表了《The internet of things》[1]的年度报告,宣告了物联网时代即将到来。物联网的快速发展促进了车联网的产生,随着国内外智能汽车和智能交通服务的飞速发展,车载自组织网络(vehicular ad-hoc network,VANET)相关理论和技术也不断成熟,极大地提高了驾驶安全和交通效率,同时车辆通信中的身份隐私保护、信息传输正确性与及时性等需求也被广泛关注。文献[2]将VANET中的车辆命名为智能车辆,介绍了道路安全、交通管理和驾驶便利性等发展方向,并分析了智能车辆可能遭受到的隐私安全威胁。文献[3]讨论了智能车辆的敏感信息保密性和身份认证正确性的功能需求,在概念性的安全架构下,设计了使用匿名证书和公钥密码框架的安全协议,针对该协议进行了详细的威胁分析和安全性证明,但协议本质是建立在公钥基础设施(public key infrastructure,PKI)之上的,存在证书管理问题,效率会在一定程度上被限制。

目前,基于身份的签名协议成为研究重点,其解决了公钥证书管理的问题,且具有高效、灵活的特点。在VANET中车辆不希望其身份、位置等私人信息被泄露,使用与原始真实身份(identity document,ID)密切相关的假名来支持身份的匿名性是解决隐私性的优秀方法[4]。文献[5]设计了基于身份的签名协议(identity based signature,IBS),并将其用于VANET的基于身份的条件隐私保护认证协议(ID-based conditional privacy preserving authentication,ID-based CPPA)以解决传统基于PKI的CPPA协议证书开销过大的问题,但该协议是基于双线性配对的密码方案,双线性对运算有复杂的幂指数运算,计算开销往往较大。车联网环境下对通信效率要求严格,大量的双线性对运算会造成较大的时间消耗,为了避免使用双线性对运算,文献[6]提出了一种基于身份的CPPA协议,该协议是基于椭圆曲线加密算法的密码方案。文献[7]使用椭圆曲线加密算法构建了一个轻量级CPPA协议,该协议解决了私钥妥协问题,防止了权限升级攻击,然而该协议因网络管理员必须存储大量相关信息而导致存储成本很高。

现有大部分车联网上隐私保护协议的安全性都规约到传统密码原语,而传统密码算法中的幂指数运算过于繁琐,使得智能车辆有限的处理能力成为这类协议的性能瓶颈。而基于格的密码协议相关运算是在向量矩阵上的加与乘等相关运算,可以减小计算开销,且随着量子计算机的发展,RSA加密算法、椭圆曲线加密算法等传统密码体制依赖的基础数学困难问题,即大整数分解、椭圆曲线离散对数等问题,在理论上可以被量子计算机上运行的Shor算法求解[8],因此,未来这些传统密码原语协议的安全性都将受到威胁。基于格上困难问题在多项式时间内不存在已知量子求解算法,为了抵抗未来可能的量子攻击和追求更高的效率,基于格的隐私保护协议进入人们视线。

文献[9]使用一种基于格的环签名协议,其拥有较高的安全性和可追溯性,能够有效解决车联网中的隐私保护问题,但该协议使用零知识证明等复杂运算,导致效率并不优越。文献[10]结合格密码和环签名,提出了一种基于格的双重认证环签名,该协议提供身份验证,但缺乏完全匿名性。基于环签名的签名协议由于其签名密钥受用户数量影响,在用户数量庞大时,签名消耗也会相应增大,因而受到较大限制。文献[11]提出了一种新的基于格的条件隐私保护认证协议,使用基于格的数字签名来完成签名协议,但其存在签名长度过长的问题。同时,这些协议中的用户签名私钥都包含了格陷门信息,此类陷门在生成时有比较严格的规定,不但增加了协议的计算开销,而且限制了协议的应用场景。

因此,本文提出一种格上基于身份的隐私保护协议。首先,基于小整数解(small integer solution,SIS)困难问题使本协议具有抗量子攻击的特性;其次,本协议利用LPR双重加密算法[12]对车辆真实身份进行加密处理,将密文作为匿名身份,确保车辆的真实身份不会因为恶意攻击而泄露,保证车辆的隐私性;最后,基于身份的签名是轻量级认证的重要技术,拒绝采样技术的使用避免了签名协议对陷门的依赖,使本协议有更好的可行性。

1 预备知识

1.1 车联网

1.1.1 网络模型

VANET是包含车辆和路边基础设施的无线网络,典型的网络结构由车载单元(on board unit,OBU)、路侧单元(road side unit,RSU)和可信授权机构(trust authority,TA)组成,如图1所示。图1中,TA是第三方设备,它在RSU的帮助下完成所需设备的注册、车辆的验证并监控整个网络;RSU是位于路边固定的无线设备,充当TA和车辆OBU之间的中介,并将安全指令传递给范围内的车辆;OBU是固定在车辆上的存储设备,用于接收或传输相邻车辆重要信息,同时车辆内部装配有防篡改设备(tamper-proof devices,TPD),它可以记录一些隐私的数据,且不会造成泄露,具有一定抵抗攻击的能力。车联网环境下,通信模式主要分为两种,一种是路侧设备(RSU)和车载单元(OBU)间的通信(vehicle to infrastructure,V2I),另一种是单纯依靠车载单元(OBU)的车间通信(vehicle to vehicle,V2V)。虽然车联网节点拓扑结构复杂,但车辆在道路上行驶时要考虑周围车辆的跟驰关系,还要遵循交通法规和信号灯控制,因此车联网的网络节点拓扑结构也呈现相应的时空规律性,可以满足通信需求。

图1 VANET网络模型Fig.1 VANET network model

1.1.2 安全需求

在部署VANET时,必须确保消息在传输过程中不会被修改,同时需要对车辆隐私信息进行保护,但是车联网中的隐私保护是有条件的隐私保护,在特殊情况下,可信机构需要揭露恶意车辆真实身份。综上所述,为了保证车联网中的通信安全,隐私保护协议必须满足以下安全需求。

1)消息完整性验证。车联网中的任何参与者都可以验证消息是否是未经修改的合法签名,并验证发送方身份的合法性。

2)匿名性。车辆的身份对于除TA之外的所有参与者都应该是匿名的,RSU和其他车辆不能够通过分析签名消息来确定发送车辆的真实身份。

3)可追溯性。在需要时,TA能够从恶意车辆发送的信息中提取车辆的真实身份。可追溯性和匿名性结合即为条件隐私保护。

4)抵抗已知恶意攻击。基于格的隐私保护协议需要抵抗VANET中多种常见攻击,例如中间人攻击、模拟攻击、修改攻击。另外该协议不易被量子算法攻破。

1.2 短格基

定理1.1陷门生成算法

定理1.2原像采样算法

在本协议的构造中,需要一个有效的算法来提取每个用户的签名密钥S,对于用户定义的矩阵U,满足AS=U(mod(q)),使用文献[15]中的矩阵采样算法SampleMat来满足使用需求。其工作原理如下。

运行算法SamplePre(A,B,s,ui)→si∈Zm产生k个n维列向量si,输出S=[s1,…,sk]∈Zm×k。

1.3 困难问题

定义1.2决策环上容错学习问题(decision ring-learning with errors,DRLWE)。给定n,m≥1,q≥2,R上的一个概率分布χ,对于s∈Rq,随机选取a←Rq和e←χ,定义由(a,b=a·s+e)产生的分布As,χ,DRLWE问题是指判别m个样本是取自分布As,χ还是取自分布U(Rq×Rq),DRLWE问题是LWE困难问题的变体。

SIS和LWE困难问题可以用于构造哈希函数、身份认证、数字签名等密码方案,其被广泛应用在格密码领域中,且SIS困难问题和LWE困难问题及其变体可以在多项式时间内规约到最短独立向量问题(shortest independent vectors problem,SIVP),在平均情况下找到SIS问题的解和LWE问题的解与在最糟糕情况下求解SIVP问题一样困难,而SIVP困难问题在多项式时间内不存在已知量子高效求解算法,因此SIS困难问题和LWE困难问题可以构造抵抗量子算法攻击的后量子密码算法。

1.4 拒绝采样技术

2012年,文献[16]首次提出拒绝采样(rejection sampling,RS)技术,并基于拒绝采样技术提出格上首个无陷门签名方案。该技术应用于签名体制能够以确定的概率输出签名并使得输出签名的分布与签名私钥的分布相互独立,可以有效防止签名私钥泄露。关于拒绝抽样技术,有如下结论。

定理1.3令V={v∈Zm:‖v‖

2 车联网中格上基于身份的隐私保护协议

本节设计了一种车联网中格上基于身份的隐私保护协议,其数字签名方案基于SIS困难问题,使用LPR双重加密算法对车辆真实身份进行加密保护,确保了量子环境中的安全性和隐私性。该协议包括系统初始化、匿名身份和签名密钥生成、签名、验证、追溯5个阶段。在系统初始化阶段,TA为所有RSU和车辆生成并预加载系统参数;匿名身份生成和私钥提取阶段,车辆将真实身份发送给TA,TA生成匿名身份和签名密钥并分发给车辆,车辆接收到匿名身份和签名密钥后存储到防篡改设备中;签名阶段,车辆使用自身的匿名身份和私钥进行签名,通过OBU或RSU进行车辆间的通信;验证阶段,车辆检查接收消息是否通过。在特殊情况下,TA对车辆的真实身份进行揭示。

2.1 系统初始化阶段

输入安全参数后,密钥生成器(PKG)运行算法生成主密钥Msk。算法工作如下。

Setup(n):输入安全参数n;

3)输出公共参数P={A,H,H1}和系统主私钥Msk=B。

2.2 匿名身份和签名密钥生成阶段

车辆需要将真实身份ID通过安全信道发送给TA,TA先将身份ID进行加密,生成匿名身份pID来保护车辆的身份隐私,使用Msk为PKG生成签名所需的私钥Psk。最后再将匿名身份pID和私钥Psk发送给车辆,车辆将相关信息存储到TPD中防止他人获取。

TA使用LPR双重加密算法[16]来加密车辆真实身份。加密身份步骤如下。

2)随机选取e1,e2←Xn,s1←X,令iID∈{0,1}l,计算t1=as1+e1,t2=bs1+e2+q/2iID;

3)输出车辆的匿名身份pID,i=(t1,t2,Ti)。

提取私钥步骤如下。

Extract(P,Msk,pID):输入公共参数P,主密钥Msk和车辆匿名身份pID;

1)运行算法SampleMat(A,B,s,H1(pID,i)),获得签名私钥Psk,i=Si∈Zm×k;

3)输出签名密钥Psk,i=Si。

此时H1(pID,i)相当于车辆验证签名时所需的公钥Ppid,即Ppid=H1(pID,i),Ti为时间戳,TA将车辆签名所需的匿名身份(pID,i)、签名私钥Psk,i发送给车辆,车辆接收后存储到防篡改设备TPD中,防止泄露更改。

2.3 签名阶段

签名步骤如下。

Sign(μ,Psk,i,P)→(z,c)。

2)c←H(Ay,μ);

3)z←y+Sic;

签名阶段由车辆完成,车辆与车辆、车辆与RSU之间的通信按照相同形式完成。车辆在收到TA返回的签名私钥和匿名身份后,以匿名身份进行消息签名,签名需要输入公共参数P,输入签名消息μ,以及签名私钥Psk,i。车辆先在高斯分布中随机选取一个向量y,而后将A与y相乘,再与消息μ一同经过哈希运算得到向量c,然后再把私钥Si和c相乘与y相加,最后以拒绝采样的概率输出签名对(z,c)。

2.4 验证阶段

在这一阶段验证者需要检查签名的有效性,验证步骤如下。

Verify(P,μ,Ssig,pID,i)→0 or 1。

验证阶段由验证者完成,在VANET中验证者角色由RSU或接收车辆来扮演。本协议是基于身份的签名,在验证阶段只需要输入匿名身份来进行签名验证。输入匿名身份pID,i后,通过哈希函数H1来计算公钥,同时输入公共参数P、签名消息μ以及签名对(z,c)。验证通过则输出1,验证失败则输出0。

2.5 追溯阶段

此阶段由TA运行,在需要时揭露恶意车辆真实身份。车联网的安全需求是保护车辆的真实身份,但特殊情况下需要找到车辆的真实身份来维护网络中的秩序。因此需要可信第三方有能力追溯恶意车辆。TA在收到恶意签名消息以及相应参数后,使用签名的匿名身份来进行解密操作,具体步骤如下。

Trace(pID,i)→iID。

pID,i=(t1,t2,Ti),TA进行解密iID=t2-t1s。

解密过程如下。

t2-t1s=bs1+e2+⎣q/2」iID-(as1+e1)s=

ass1+es1+e2+⎣q/2」iID-as1s+e1s=

⎣q/2」iID+es1+e2+e1s

e、s都从错误分布当中选取,其本身是非常小的一个扰动。因为身份iID∈{0,1}l,所以⎣q/2」iID+es1+e2+e1s是趋近于q/2的一个向量,趋近于q/2则输出1,趋近于0则输出0,如此可以获得解密后的明文,即真实身份ID。影响本协议运行效率的主要是签名和验证两部分,追踪算法仅在出现恶意车辆违规操作等情况时才运行,因此协议效率不考虑追踪步骤的消耗。

3 协议的安全性分析

3.1 正确性证明

根据隐私保护协议的构建,可以得到

Az-H1(pID,i)c=Az-ASic=A(z-Sic)=Ay,因此有H(Az-H1(pID,i)c,μ)=H(Ay,μ)=c。

以上证明了签名验证算法的正确性。

3.2 安全性证明

3.2.1 安全模型

3.2.2 安全性证明

定理3.1不可伪造性。基于SIS问题的难度,提出的基于身份的签名协议对于随机预言模型中的自适应选择消息和身份攻击是存在不可伪造的。

通过上述证明与分析可知,签名协议不可伪造性的困难性是基于SIS困难问题的,而SIS困难问题可以规约到SIVP问题,任何多项式时间算法都无法解决SIVP问题,因此本协议在理论上可以抵抗量子算法的攻击。

定理3.2匿名性。在RLWE问题的假设下,本文方案在随机预言模型中是匿名的。

下面通过证明G0和G1游戏的不可区分来证明本方案的匿名性。

3.2.3 安全需求分析

1)消息完整性和身份认证。消息接收方需要验证发送方的合法性,并检查接收到的消息是否被修改。根据上述安全性证明可以得出结论,由于SIS问题的困难性,任何多项式时间敌手都不能伪造有效签名,因此接收方能够通过检查等式Az-H1(pID,i)c=Az-ASic=A(z-Sic)=Ay和H(Az-H1(pID,i)c,μ)=H(Ay,μ)=c来验证签名的有效性和完整性,因此所提协议满足消息完整性和身份认证的要求。

2)匿名性。在协议中,TA将车辆的真实身份加密为匿名身份,这样做的目的是提供身份匿名性并保护车辆的隐私。生成的匿名身份包含了(t1,t2,Ti),是经过LPR双重加密方案加密真实身份得来的。敌手如果想要从匿名身份中提取车辆真实身份,那么必须拥有密钥s,否则破解车辆真实身份的概率忽略不计,其困难性规约到RLWE困难问题,因此所提协议满足车联网中匿名性需求。

3)可追溯性。在VANET中,车辆使用假名互相通信。车辆的假名由TA使用ID和相应的密钥s加密生成。如果恶意车辆发送虚假信息影响交通系统,那么TA有权追踪其真实身份。车辆生成的匿名身份p′ID,i=(t1,t2,Ti)与车辆真实身份ID密切相关,TA运行Trace(pID)算法,通过计算iID=t2-t1s对匿名身份进行解密,从而提取到车辆的真实身份。因此所提协议可以满足车辆在VANET中真实身份的可追溯性。

4)抵抗已知恶意攻击。首先,根据上述分析可知,所提CPPA协议可以实现VANET中车辆之间的消息认证,从而确保通信实体的真实性,因此协议不易受到中间人攻击。其次,本协议通过等式Az-H1(p′ID,i)c=Az-ASic=A(z-Sic)=Ay、H(Az-H1(pID,i)c,μ)=H(Ay,μ)=c来检测签名(z,c)的有效性和完整性,因此所提协议可以抵抗修改攻击。然后,对于模拟攻击来说,在本协议中敌手想要成功模拟车辆,必须对消息μ′伪造有效签名(z′,c′),根据定理3.1,由于SIS问题的复杂性,协议对于随机预言模型中的自适应选择消息和身份攻击是不可伪造的,对手生成消息签名对的优势微乎其微,因此本协议可以抵抗模拟攻击。最后,根据安全性证明,协议的不可伪造性基于SIS困难问题,而SIS困难问题可以规约到SIVP问题,现在不存在多项式时间内的量子敌手可以解决SIVP问题,因此量子敌手在理论上也无法解决SIS问题,由此得出本协议可以抵抗量子算法攻击的结论。

4 协议的性能分析

4.1 理论分析

车联网环境有网络拓扑结构灵活多变、车辆设备计算能力有限等特点,导致车联网中的协议对通信效率和计算开销有着严格的限制。我国相关规定要求非安全类时延不超过100 ms。因此,V2V和V2I之间无法进行过于复杂的计算。V2V和V2I之间的通信体现在车辆的签名阶段和验证签名阶段,故协议实施的主要限制在签名和验签环节。系统初始化、匿名身份生成、私钥提取以及追溯阶段等没有严格时间限制的环节都由拥有强大计算能力的TA运行。

综上所述,本节从签名生成和签名验证所消耗的时间进行分析,考虑向量乘法运算等相对耗时较多的计算过程,而忽略了Hash运算、多项式以及矩阵的加减法等相对耗时较少的运算过程。以T1表示多项式向量乘法运算的单步平均耗时,T2表示矩阵向量乘法运算单步平均耗时,TN为零知识证明时间,N表示环成员个数。每种协议的签名和验证计算效率如表1所示。

表1 效率对比

表1中,文献[9]是格上环签名协议,在环签名协议中,用户需要使用自己的私钥和其他所有用户的公钥对消息进行签名,对于一个用户众多的环,即N很大时,计算负担是相当大的。此外文献[9]还使用了零知识证明,会额外增加计算开销。文献[10]是基于格的防止双重认证的环签名方案,除了协议性能和成员数量相关外,还需要额外的证书管理消耗。文献[11]使用基于格的数字签名实现需求,但其存在签名长度过长的问题,因此本文协议在用户众多的情况下,会在效率上优于环签名协议,且在签名长度上优于其他协议。

多项式向量乘法运算耗时约等于矩阵向量乘法的一半,即2T1≈T2,由此可以得到签名生成消耗的大小关系。本文协议是基于身份的签名,其签名生成消耗不会随着系统成员数量的变化而变化,在成员数量庞大的情况下,本文协议具有可观的效率优势。与文献[11]相比,签名的生成和验证消耗是相近的,但本文协议的签名长度更短。在考虑对比协议的通信成本时,规定所有隐私保护协议中的签名消息、成员数是相同的;同时,其他协议中系统参数设置与本文协议相同或保证同等安全等级的情况下,只需要考虑这些协议生成的签名的大小即可。参数n=128、l=128、q=1 073 479 681时,通过分析可以得到表1,本文协议在签名阶段耗时为2T2,验证签名耗时2T2,签名长度所占用的存储空间为m+k,签名大小为 3 479 Byte。

表2对协议安全属性和技术进行了对比。文献[10]是基于格的防止双重认证的环签名方案,所有的成员相对平等且没有群签名中管理员的要求,但是它需要证书管理列表CRL,需要检查签名生成过程中使用的公钥是否在CRL中,存在大量的身份管理成本。本文协议在满足车联网中各种安全需求的基础上,使用基于身份的技术,简化了身份管理成本,在协议中不再使用CRL管理,不需要检查签名生成过程中使用的公钥是否在CRL中,简化了实际使用中对公钥的管理成本。

表2 安全属性和技术对比

4.2 仿真模拟

C-V2X系列协议是我国自有核心自主知识产权的协议,其中的LTE-V2X技术能够使用现有的蜂窝网络基础设施,提供大容量的信息传输和低时延的广域通信,在车速≤500 km/h的情况下,通信距离≤1 000 m,数据传输速率为500 Mbit/s,有5G技术的加持时,传输速率可大幅提升到1 Gbit/s[18],远超欧美推行的DSRC和WI-FI技术。和本文协议密切相关的是LTE-V2X技术要求端到端非安全类时延≤100 ms,安全类时延≤20 ms,因此协议的时间消耗控制在20 ms以下才能满足标准要求。

4.2.1 仿真环境和参数设置

本文协议使用Python语言,调用Numpy库来模拟提出的签名协议。其中硬件为2 GB的内存,一个主频为2.8 GHz的双核处理器,运行系统为64位Windows7。

在本文协议中,影响效率大小的因素主要和参数n、q相关,n为协议的安全参数,协议根据安全参数的大小来确定相关格矩阵维度以及有限群的大小,一般n取2的次幂数;而q的大小也与安全水平相关,q越大安全水平越高,q一般取大素数。协议需要同时考虑到安全性和效率,安全水平越高效率会越低,因此选取不同参数来模拟仿真协议消耗用时。

4.2.2 仿真结果与分析

本文仿真模拟了LPR加密真实身份的时间消耗,结果如表3所示。从表3可知,加密用户身份的时间消耗较小,且由于这部分计算是在离线情况下进行的,不在通信阶段参与计算,因此基于RLWE的匿名化身份的操作满足车联网应用;选取n为256、q为1 073 479 681时,签名平均耗时为12.169 ms,验证签名耗时为5.669 ms,满足LTE-V2X的安全类时延(≤20 ms)要求;参数选取更大的情况下,仍满足非安全类时延(≤100 ms)要求。综上所述,本文协议满足LTE-V2X技术的指标要求,适合在车联网中实际应用。

表3 仿真结果

5 结束语

本文提出一种新的车联网中格上基于身份的隐私保护协议。首先,本文协议使用基于身份的数字签名来解决较高的身份管理成本问题。具体来说,本文协议在成员复杂度增加的情况下,签名消耗保持平稳,提高了计算效率。其次,本文协议的安全性基于SIS困难问题,通过理论证明,本文协议可以抵抗量子算法攻击;同时,根据安全性分析可知,本文协议能够抵抗伪造攻击和各种常见恶意攻击。最后,本文协议可以为VANET提供安全高效的V2I和V2V通信,且满足VANET中各种安全需求。性能分析结果表明,本文协议计算消耗更小,效率更优,可以满足我国相关行业标准,满足车联网的实际应用需求。