————————————
基金项目：国家自然科学基金资助项目(61173188)。
作者简介：郭松矗(1989－)，男，硕士研究生，主研方向：网络与信息安全；崔 杰，讲师、博士。 收稿日期：2013-03-07 修回日期：2013-06-04 E-mail ：guosongchu@126
面向车载自组网的高效位置隐私保护查询方案
郭松矗，崔 杰
(安徽大学计算机智能与信号处理教育部重点实验室，合肥 230039)
摘 要：随着车载自组网应用对安全性要求的提高，用户和服务提供商对各自私有信息保密性的要求也越来越高。针对现有查询方案无法同时保护车辆身份、位置及服务提供商数据隐私的问题，利用私有信息检索技术，提出一种高效的位置服务查询方案。采用匿名认证的方法进行车辆间的相互认证与车辆及路边的认证。在此基础上，使用安全硬件对数据库的数据进行混淆处理，通过代理重加密完成车辆对数据库服务数据的检索，从而实现车辆和数据库双方的隐私保护。分析结果表明，该方案可实现车辆身份匿名查询，能够保护车辆位置隐私和服务提供商的数据库信息，且只需两轮通信，具有较高的通信效率。 关键词：车载自组网；基于位置服务；代理重加密；双线性映射；匿名认证
Efficient Location Privacy Preserving Query Scheme
Oriented to V ANETs
GUO Song-chu, CUI Jie
(Key Laboratory of Intelligent Computing & Signal Processing, Ministry of Education, Anhui University, Hefei 230039, China) 【Abstract 】With the enhanced security requirements of the Vehicular Ad Hoc Networks(V ANETs) applications, vehicles and service providers have a high demand on their privacy information. The traditional privacy preserving query schemes of mobile devices cannot both protect the privacy information of the vehicle and the service provider database. This paper proposes an efficient location service query scheme by using the Private Information Retrieval(PIR) technology. Vehicles verify other vehicles and roadside base station by anonymous authentication. Meanwhile, the data of the service provider database is confused by the secure coprocessor, and the query service is implemented by the Proxy Re-cryptography(PRC) algorithm. The scheme can protect the privacy information of both vehicle and service provider database. Analysis shows that this scheme not only achieves the vehicle’s anonymous query, but also protects both the location privacy of vehicles and the data privacy of service provider databases. Moreover, the communication cost is only twice, and has the high efficiency of communication.
【Key words 】Vehicular Ad Hoc Networks(V ANETs); Location-based Services(LBS); Proxy Re-cryptography(PRC); bilinear mapping groups; anonymous authentication
DOI: 10.3969/j.issn.1000-3428.2014.06.022
计 算 机 工 程 Computer Engineering 第40卷 第6期 V ol.40 No.6 2014年6月
June 2014
·安全技术· 文章编号：1000-3428(2014)06-0099-05 文献标识码：A
中图分类号：TP309
1 概述
车载自组网(Vehicular Ad Hoc Networks, VANETs)是移动自组织网络(Mobile Ad Hoc Networks, MANETs)的一种。它主要由固定在车辆上的无线通信设备(On-board Unit, OBU)、路边的通信(Road Side Units, RSU)和一个可信的管理中心(Trusted Authority, TA)以及服务提供商(Service Providers, SP)组成。通过车辆之间、车辆与路边之间驾驶信息(如车辆的行驶状态和道路信息等)的交换来保证车辆的安全驾驶，是智能交通系统[1]中的一个重要组成部分。近年来，车载网络、车载网络安全问题取得了广泛深入的研究[2-3]，成为了目前移动网络和移动网络安全方面的研究热点之一。
在MANETs 中，用户从服务提供商查询服务数据的同时，希望能够保护自己的隐私信息不被数据库得到，同时服务提供商也担心自己数据库数据的泄露，因此对用户和数据库双方都进行隐私保护的查询方案的需求越来越迫切。而在VANETs 中，车辆位置是关系到用户安全隐私的敏感信息。如移动中的车辆A ，其身份标识ID A 、位置标识为(X A ,Y A )，在行进的过程中，车辆A 想要得到SP 数据库中关于它的位置(X A ,Y A )关联的服务d A (如车辆A 附近的道路交通情况、车辆A 附近的银行或宾馆等)，出于自身安全的考
虑，车辆A 不想泄露自己的身份ID A 和它的位置(X A ,Y A )，
而SP 数据库也不想泄露除d A 外的其他服务信息。
针对移动环境下保护用户隐私信息的查询研究近年取得了大量的成果。文献[4]提出一种使用公钥基础设施PKI
100 计 算 机 工 程 2014年6月15日
和匿名路由(Anonymity Router, AR)的方案，文中在用户和位置服务提供者(Location-based Services Server, LS)之间引入了一个AR ，如果攻击者同时获得了AR 和LS 的公私钥或者AR 和LS 协作就能获得用户的隐私数据。文献[5]提出车辆在查询前联合多个附近的车辆，模糊化自己的位置信息从而达到匿名
查询的目的，但是要达到实用的效果，需要有合适的车辆密度，不适于车流量稀疏的高速公路等。文献[6]提出了使用多次虚假位置信息查询，间接得到目的查询位置信息的方案，然而多次重复查询产生很高的通信代价。文献[7]提出了一种把网络划分成多个簇的方法，但是当网络的拓扑结构变化很快时将产生很大的簇成员添加、撤销代价。文献[8]提出了基于茫然传输的方案，实现付费信息的查询，能有效地保护用户的真实身份信息，但SP 可以获得用户的查询内容。文献[9]提出了在真实查询中加入虚假查询信息的方法，能有效地保护实际查询信息的安全性，但连续多次查询增大了通信开销。
本文利用私有信息检索的方法，提出一个位置服务查询新方案。私有信息检索是安全多方计算研究的一个重要分支，旨在保护用户查询数据库时的查询隐私(如用户在查询专利数据库等时，不想让数据库知道他所查询的内容)。基于安全硬件的私有信息检索是私有信息检索研究中广泛使用的一种方法。安全硬件(如IBM4758)通常装备在服务器上，拥有独立于服务器的内存和处理器，同时也能阻止外界对它内存的访问，是安全可信的。文献[10]首次提出了含有安全硬件的私有信息检索，之后使用安全硬件的私有信息检索取得了蓬勃的发展[11-12]。由于车载网络中车辆节点的计算能力有限和基于安全硬件的私有信息检索有着较低的计算、通信复杂度，因此本文采用了基于安全硬件的私有信息检索方法来设计方案。
2 预备知识
本节将给出位置隐私保护查询方案的模型、问题描述及新方案相关的基础知识。
2.1 系统模型和问题定义 2.1.1 系统模型
本文位置隐私保护查询方案的系统模型如图1所示。
图1 系统模型
本文的模型图在参考文献[8]的基础上引入了安全硬件
SC 。各参与方的功能介绍如下：
TA ：可信的车辆管理中心。它布置了位于道路两侧的RSU 和装备在车辆上的OBU ，同时TA 拥有OBU 的真实身份ID OBU 。
OBU ：车辆上的通信设备。它可以使用专用短程通信技术(Dedicated Short Range Communication, DS
RC)与其他的OBU 或RSU 进行通信。它拥有自己的真实身份OBU ID 和自己的位置OBU OBU (,)x y [9]。
RSU ：是TA 构建于路边的。它可以使用DSRC 和OBU 进行通信，也可以使用有线设备接入Internet ；RSU 是TA 的下级，可以对OBU 进行身份认证，向OBU 提供接入Internet 的功能。
SP ：位置服务提供商。SP 数据库中存储了若干条记 录，每条记录的格式是<；位置, 服务>记为<(x i ,y i ),d i >，SP 的存储模型如表1所示。其中，(x i ,y i )表示位置。([1,])i d i N ∈表示有关位置(,)i i x y 的服务信息。
表1 SP 数据库的存储模型
位置 服务 (x 1,y 1)
d 1 (x 2,y 2) d 2 … … (x N ,y N )
d N
SC [11]：安全协处理器。是架构于SP 上的安全硬件。安全协处理器用来实现OBU 和SP 之间的交互操作。安全协处理器不会泄露用户隐私给任何人，可以防止任何外源包括宿主服务器访问它的内存空间，并且能安全地使用密码学工具。
2.1.2 问题定义
本文方案可以在满足下面安全需求的前提下根据输入得到相应的输出：
输入 OBU 的真实身份信息OBU ID 和它的位置OBU (,x
OBU )y ，TA 提供共有安全参数，SP 的数据库111{((,),),x y d
222((,),),,((,),)}N N N x y d x y d L
输出 OBU 得到SP 数据库中OBU OBU (,)x y 对应服务d i 安全需求：对于车辆身份，只有TA 能得到OBU 的真实身份信息OBU ID 。对于车辆位置OBU OBU (,)x y ，任何参与方都不能得到OBU 的位置OBU OBU (,)x y 。对于数据库数据，假设数据库中OBU OBU (,)x y 对应的服务为d i ，则SP 数
据库中服务j d j i
≠（）是保密的。 2.2 相关的预备知识 2.2.1 双线性映射
双线性映射[13]的定义是：假设存在2个有限的乘法G 和GT ，它们的阶为一个大素数q ，G 的一个生成元为g ，那么存在一个双线性映射e ：G×G →GT ，其中，e 满足下面的性质：
(1)双线性性：对于任意的,a b Zq ∈，有：
()
,(,)a b ab e g g e g g = (1)
第40卷 第6期 101
郭松矗，崔 杰：面向车载自组网的高效位置隐私保护查询方案 (2)非退化性：若g 是G 的一个生成元，则(),e g g 是GT 的一个生成元。
(3)可计算性：对于任意的,a b Zq ∈，则存在有效的算法去计算()
a b e g ,g 。
那么e 就是一个双线性映射，G 是一个双线性。 2.2.2 代理重加密
代理重加密使用一个半可信的代理者，它可以把使用Alice 公钥加密的密文转换成使用另外一个参与方Bob 公钥对相同明文加密的密文。半可信是指代理者会在加密的过程中严格按照协议的约定执行，但可
能会保存计算过程中的中间信息。在代理的过程中，半可信的代理者不会获得明文的任何信息及Alice 和Bob 的私钥的任何信息。
一个代理重加密主要包括下面5个算法，即KeyGen 、ReKeyGen 、
Enc 、ReEnc 和Dec ，分别是产生密钥、产生重加密密钥、
加密、重加密和解密。
代理重加密形式化定义[14]如下： (1)Alice 调用KeyGen 得到 (,)A A SK PK ，Bob 调用
KeyGen 得到(,)B B SK PK 。
(2)输入Alice 的私钥A SK 、
Bob 的私钥B SK ，重加密密钥产生算法ReKeyGen 输出重加密密钥A B SK →，半可信的第三方保存A B SK →。
(3)Alice 计算(,)A C Enc PK m =，代理者计算’C =
(,)A B ReEnc PK C →，则Bob 可以使用自己的私钥B SK 计
算'(,')B m Dec SK C =，并且’m m =。
3 VANETs 下的位置隐私保护查询方案
3.1 方案描述
该方案主要包括2个阶段：
(1)初始化阶段，主要包括各个参与方密钥的生成、SP 对数据库的散列、加密和SC 对数据库的置换。
(2)查询阶段，主要包括RSU 对接入车辆OBU 的验证
阶段和OBU 的位置服务查询阶段。
3.2 系统的初始化阶段
3.2.1 各参与方密钥的生成
(1)TA 产生双线映射(,,,,)T q g G G e ，g 是G 的生成元。同时，TA 选择一个散列函数h ()。TA 公布h ()和(,,,,)T q g G G e 。
(2)TA 选择SK TA =s (s ∈Zq )作为其私钥，并计算s TA PK g =作为其公钥。
(3)OBU 假名的生成： 1)OBU →TA ：O B U ID ，TA 使用TA SK 对OBU ID 签名得到：OBU ()TA SK SIG ID
TA →OBU ：OBU ()TA SK SIG ID
2)OBU 选择SK OUB =u ()q u Z ∈作为其私钥，并计算PK OUB =g u 作为其公钥。
3)OBU →TA ：ID ′=h (ID OBU //r i )，其中，i r 是一个随机数。TA 对ID'签名生成(')TA SK SIG ID
4)TA →OBU ：()TA SK SIG ID'。 5)OBU 重复步骤c 得到：
{}(,,))
(TA TA ''
SK l SK k SIG
ID SIG ID L 。
(4)SP 选择()SP q SK v v Z =∈作为其私钥，并计算其公
钥v
SP PK g =作为其公钥。SP 选择随机数q r Z ∈，计算r
vr SP R PK g ==，并公布R 。
3.2.2 数据库的加密、散列和SC 对数据库的置换
数据库的处理过程如图2所示。
(1)SP 对数据库中的记录进行散列和加密。对(,)i i x y 计算h (x i //y i )，对i d 使用r 计算()(,)r i i E d e g g d =⋅。 (2)SC 对数据库进行随机的置换，置换中SC 保存到h (x i //y i )([1,])i N ∈对应的新位置i n ，即 SC 保存到
111222{((),),((),),,((),)}N N N h x y n h x y n h x y n L ，其中，
12(,,,)N n n n L 是(1,2,,)N L 的一个置换。
图2 数据库散列和SC 对数据库加密和置换
3.3 查询阶段
此阶段的模型如图3所示，OBU 先使用假名与RSU 认证，然后OBU 发送OBU OBU (,)x y 的散列结果OBU OBU (//)h x y 给SC ，SC 查：
111222{((//),),((//),),,((//),)}N N N h x y n h x y n h x y n L 得到OBU OBU (//)h x y 所对应的位置信息n i ，从数据库中获得n i 所对应的()i E d ，之后SC 产生对应的重加密密钥和重加密结果，并把重加密的结果返回给OBU ，OBU 解密得到
102 计 算 机 工 程 2014年6月15日
相应的i d 。
图3 查询阶段的模型
3.3.1 身份认证
身份认证步骤如下： (1)OBU →RSU ：SIG
()()()
12[,,,]TA TA TA '''SK SK SK k i
SIG SIG ID SIG ID SIG ID =L 其中，[1,]i k ∈。
(2)RUS 计算()TA PK V =VER SIG
IF V =TRUE
THEN 转到步骤(3)。 ELSE 转到步骤(4)。
(3)RSU 和OBU 之间通过Diffie-Hellman 密钥协商协议协商一个会话密钥Key 进行通信，以后的通信使用Key 进行加密。
(4)OBU 所提交的身份不合法，则RSU 向其他的RSU 和TA 通报该OBU 的欺诈信息。
3.3.2 OUB 的位置服务查询阶段
在OBU 在线查询阶段，所执行的步骤如下：
(1)OBU 、SC 、SP 服务器协作产生重加密密钥 sp obu SK →，SC 保存它。
1)SP 选择q t Z ∈，计算T =SK SP t·mod q ，SP →SC ：t ，SP →OBU ：T 。
2)OBU T ′=T /SK OBU =SK SP ×t /SK OBU mod q ，OBU →SC ：T'。
3)SC 计算：SP OBU /'/ mod SK t T u v q →==。
(2)OBU ：C =E Key (OBU OBU (,)h x y )，OBU →RSU ：C 。 (3)RSU ：OBU OBU (,)h x y =D Key (C )。 RSU →SC ：OBU OBU (,)h x y 。
(4)SC 查询得到OBU OBU (,)h x y 对应的i n 。
1)IF i n 对应的 ()i E d 在SC 关于()i E d 的cache 中 2)THEN
SC →OBU ：()i E d 、SP OBU SK R R →=′。
3)ELSE
SC 从SP 读取K ’个()j E d (其中包括i n 对应的()i E d ，另外的K ’–1个随机选择)放入自己的cache 中。
SC →OBU ：()i E d 、SP OBU SK R R →=′。
(5)OBU 计算'1/()/(,)u i E d e R g 得到i d 。
4 方案性能分析
4.1 正确性证明
定理1 OUB 能获得正确的i d 。
证明：OBU 计算'
1/()/(,)u
i E d e R g ，其中，
() (,)r i i E d e g g d =⋅；SP OBU SK R R →=′；SP r vr
R PK g ==；SK SP–OBU =u /v mod q ，带入后，则：
'1/1/()/(,)[(,)]/[(,)]u r vru /v u i i E d e R g e g g d e g g =⋅ 根据式(1)：
'1/()/(,)[(,)]/[(,)]u r r i i i E d e R g e g g d e g g d =⋅= (2)
所以OUB 可以得到正确的d i 。
4.2 安全性分析
定理2 OBU 同时能保证自己ID 的隐私性和查询信息OBU OBU (,)x y 隐私性。
证明：认证时OBU 可以随机的从()
{1,TA 'SK SIG SIG ID =
()2,,TA 'SK SIG ID L ()}TA 'SK k
SIG ID 中选择一个进行认
证。RSU 不能获得OBU 的OBU ID ，从而能保证OBU 身份信息的隐私行。因为SC 作为安全硬件，不会泄露用户隐
私给任何人，并可以防止任何外源包括宿主服务器访问它的内存空间，而且能安全地保持和使用密码学工具，所以SP 不能从SC 中获得它所接收和存储的任何信息。当查询的()i E d 在SC 的cache 里SC 可以直接返回给OBU ，SP 完全不能获得OBU 所提交的(x OBU , y OBU )。当要查询的 E (d i )不在SC 的cache 里时，在SP 看来，SC 随机地从数据 库中读取了K 条记录，但它也不能确定OBU 所查询的OBU OBU (,)x y 。
定理3 通过协议的执行SP 仅返回了d i 的重加密结果，能有效保证SP 数据的安全性。
证明：协议执行结束后，SP 仅返回d i 的重加密结果，没有泄露SP 数据库的任何额外信息。由于d i 的解密需要使用OBU 的私钥SK OUB ，因此SP 所返回的信息也仅有发送请求的OBU 才能解密，所以协议能保证SP 数据库内容的安全性。
4.3 效率分析
定理4 在OBU 的查询阶段协议的通信复杂度是O (1)。 证明：在线查询的时候OBU 首先通过1轮的通信生成重加密密钥SP OBU SK →。随后OBU 向SC 提交要查询的 (x OBU , y OBU )，SC 完成查询后向OBU 返回()i E d 以及R'，然后OBU 通过计算可以得到d i 。因此，在整个查询的阶段OBU 只需要2轮的通信就可以获得相应的查询结果。 4.4 方案对比
现有各种方案的对比如表2所示。通过对比本文的方案在保护车辆的身份信息、车辆位置信息和数据库隐私保护方面优于其他的方案。
第40卷第6期 103 郭松矗，崔杰：面向车载自组网的高效位置隐私保护查询方案
表2 方案对比
方案匿名性查询条件隐私SP隐私优缺点通信代价文献[4]方案√ × √不能防止AR和SP合谋O(1)
文献[6]方案√√ ×
多次的查询通信代价较高O(n) 文献[8]方案√ × ×
SP不知道身份但知道查询信息O(1) 文献[9]方案√√ ×
虚假查询泄露数据信息并增加通信O(n) 本文方案√√√能保护身份、查询信息和数据库O(1)
5 结束语
本文采用双线性映射和代理重加密技术，并借鉴基于安全硬件的私有信息检索，提出一种在车载网络中保护用户位置隐私的位置服务查询方案。该方案既可以保证OBU 身份和位置的保密性，也可以保证SP数据库内容的隐私性。下一步的研究是设计更高效的位置隐私保护查询方案。
参考文献
[1] Drane C R, Rizos C. Positioning Systems in Intelligent
Transportation Systems[M]. Boston, USA: [s. n.], 1997.
[2] 常促宇, 向勇, 史美林. 车载自组网的现状与发展[J].
通信学报, 2007, 28(11): 116-126.
[3] 吴静, 刘衍珩, 王健, 等. 车载自组网的可信认证与信
任评估框架[J]. 通信学报, 2009, 30(10): 107-113.
[4] McDiarmid A, Irvine J. Achieving Anonymous Location-based
高速查询Services[C]//Proc. of Vehicular Technology Conference.
Los Angeles, USA: IEEE Press, 2004: 1-6.
[5] Mokbel M F, Chow C Y, Aref W G. The New Casper: Query
Processing for Location Services Without Compromising Privacy[C]//Proc. of International Conference on Very Large Data Bases. Seoul, Korea: VLDB Endowment, 2006: 763-774.
[6] Yiu Man-Lung. Spacetwist: Managing the Trade-offs Among
Location Privacy, Query Performance, and Query Accuracy in
Mobile Services[C]//Proc. of International Conference on Data Engineering. Cancun, Mexico: IEEE Press, 2008: 366-375. [7]Giudici F. CAESAR: An Urban Location Service for
V ANETs[J]. ACM SIGMOBILE Mobile Computing and Communications Review, 2007, 11(2): 45-46.
[8] Chim T W, Yiu S M, Hui L C K, et al. OPQ: OT-based Private
Querying in V ANETs[J]. IEEE Transactions on Intelligent Transportation Systems, 2011, 12(4): 1413-1422.
[9] Lin Yao, Liu Chi, Liu Guangya, et al. Location Anonymity
Based on Fake Queries in Continuous Location-based Services[C]//Proc. of International Conference on Availability, Reliability and Security. Prague, Czech Republic: IEEE Press, 2012: 85-93.
[10] Smith S W, Safford D. Practical Server Privacy with Secure
Coprocessors[J]. IBM Systems Journal, 2001, 40(3): 683-695.
[11] Iliev A, Smith S. Private Information Storage with Logarith-
micspace Secure Hardware[M]. [S. 1.]: Springer, 2004.
[12] 花常琪, 仲红, 石润华, 等. 基于加密数据库的高效安全
HW-PIR方案[J]. 计算机工程, 2012, 38(20): 97-100.
[13] Barreto P S L M, Kim H Y. Efficient Algorithms for Pairing-
based Cryptosystems[M]. Berlin, Germany: Springer, 2002. [14] 邵俊. 代理重加密的研究[D]. 上海: 上海交通大学, 2007.
编辑索书志
发布评论