基于网格标识匹配的位置隐私保护方法

张少波 刘 琴 王国军



基于网格标识匹配的位置隐私保护方法

张少波①③刘 琴②王国军*①④

①(中南大学信息科学与工程学院 长沙 410083)②(湖南大学信息科学与工程学院 长沙 410082)③(湖南科技大学计算机科学与工程学院 湘潭 411201)④(广州大学计算机科学与教育软件学院 广州 510006)

在基于位置的服务中，基于可信第三方模型是当前位置隐私保护中的主要模型，但该模型存在一定的隐私泄露风险。该文提出一种基于网格标识匹配(GIM)的位置隐私保护方法，用户首先将查询区域划分为网格，并结合保序对称加密和K匿名技术，在匿名器形成K匿名，然后利用网格标识匹配返回查询结果给用户。在查询的过程中，匿名器并不知道用户的具体位置，加强了该模型中用户位置的隐私保护。同时中间匿名器仅进行简单的比较和匹配，有效缓解了匿名器的性能瓶颈问题。安全分析表明该方法能有效保护用户的位置隐私；并且通过实验验证该方法能有效减小匿名器的处理时间开销。

位置隐私；网格标识匹配；保序对称加密；K匿名

1 引言

随着无线通信技术、智能终端设备和定位技术的发展，基于位置的服务(Location Based Service, LBS)发展迅速并获得广泛关注[1,2]。在LBS中，用户通过带有定位功能的设备可以获得当前位置，并向位置服务器发送查询，以获取用户位置附近的兴趣点(Points Of Interests, POIs)，例如寻找距离当前位置最近的宾馆、影院和加油站等，然而人们在享用LBS带来便利的同时，也面临着敏感信息泄露的风险[3]。根据用户发送的LBS查询，攻击者可能分析出特定用户的敏感信息，如家庭住址、生活习惯、健康状况以及社会关系等[4]。同时位置服务提供商(Location Services Provider, LSP)也可能将用户的隐私信息泄露给第三方，这将给用户带来严重的安全隐私风险。因此，目前基于位置服务的位置隐私保护问题已引起学者的广泛关注，并迫切需要解决。

为减少隐私泄露的风险，国内外已提出一些位置隐私保护方法，采用的基本结构主要分为两类[5]：基于点对点的结构和基于可信第三方(Fully- Trusted Third Party, TTP)的中心服务器结构。在基于点对点的结构中，用户之间通过协作的方式形成K匿名域[6,7]或使用混淆的方式[8]向LBS发送查询，使LSP不知道用户的精确位置。在基于可信第三方的中心服务器结构中，引入了一个可信匿名器，作为移动用户和LSP之间的中间体。该结构中用户首先将查询请求发送给匿名器，然后匿名器将用户的服务请求按用户的隐私需求形成一个包括个用户的匿名域，并将它发送给LSP进行查询，得到查询结果集后再返回给匿名器，最后可信匿名器根据用户需求对候选结果集进行求精，并将精确结果返回给用户。但基于可信第三方的中心服务器结构存在两个问题：(1)匿名器知道用户的精确位置，如果它被攻击者攻破，将会带来严重的安全威胁。(2) 匿名器承担着匿名、求精等繁重的计算任务，容易成为该结构中的性能瓶颈。

针对TTP结构存在的两个缺陷，文献[12]提出通过自定义动态网格系统，使中间第三方不知道用户的具体位置，达到保护用户位置隐私的目的。但如果用户指定的查询区域只有一个用户，LBS服务器就会很容易指出真实的用户，暴露用户的位置隐私。针对该方法存在的缺陷，本文提出基于网格标识匹配(Grid Identifier Matching, GIM)的位置隐私保护方法，结合保序对称加密(Order-Preserving Symmetric Encryption, OPSE)和K匿名技术，用户首先对查询面积进行网格划分，并将能确定各用户查询区域的坐标用保序对称加密算法加密，然后发送到中间匿名器形成K匿名域，匿名器并不知道用户的具体位置，且它不需要完全可信，加强了对用户位置的隐私保护。同时在查询的过程中，中间匿名器仅进行简单的比较和匹配，有效缓解了匿名器的性能瓶颈问题。

2 系统模型和相关定义

2.1 系统模型

如图1所示为基于GIM的位置隐私保护模型图，系统主要由用户、匿名器和LBS服务器3类实体组成，具体工作过程为：(1)用户发送查询时，首先指定一个查询面积进行网格划分，并寻找用户附近个其它用户，各用户按查询范围在网格结构上确定各自的查询区域，然后用OPSE对各确定网格查询区域的坐标进行加密，发送给匿名器；同时用户将自己指定的查询区域内的网格单元标识进行Hash并加密发送给匿名器；(2)匿名器比较用OPSE加密后的坐标大小，并根据比较结果形成包含个用户查询区域的匿名域，然后将该匿名域发送给LSB服务器进行查询；(3)LBS服务器查询匿名域内的POIs，并将各POIs的位置以及对应的网格单元标识进行Hash并加密后返回给匿名器；(4)匿名器将各POIs位置所在的加密网格单元标识与用户需要查询区域的加密网格单元标识进行匹配，如果相等，则将该网格单元标识对应的POIs发送给用户。该方法的优点是匿名器并不知道用户的精确位置，同时它只进行简单的比较和匹配操作，加强了对用户位置的隐私保护，同时也有效缓解了匿名器的性能瓶颈问题。

图1 基于GIM的位置隐私保护模型

2.2 保序加密

2.3 安全模型

在位置隐私保护的研究方面，目前比较典型的攻击模型主要分为两种[16]：强攻击者攻击模型和弱攻击者攻击模型。

(1)强攻击者攻击模型： 在强攻击者攻击模型中，攻击者能监视整个系统中特定用户的行为记录，本方法中的匿名器和LSP都可能成为潜在的强攻击者。因为LBS服务器管理所有用户的LBS查询数据，LSP因利益关系，可能会泄露LBS服务器中敏感信息给第三方。匿名器在用户和LBS服务器之间进行匿名和转发信息，也可能会对用户进行行为分析，并造成信息泄露。

(2)弱攻击者攻击模型： 在弱攻击者攻击模型中，攻击者具有很少关于用户的背景知识，攻击者通过使用背景知识或其它攻击手段，试图知道其它用户更多的个人信息。本方法中，攻击者可能试图窃听用户与LBS服务器之间的通信信道，分析传输过程中的数据，甚至篡改查询结果发送给用户进行攻击。

3 基于网格标识匹配的位置隐私保护方法

3.1 用户加密查询

本文假定用户的查询是范围查询，例如在市区环境下用户查询自己周围1 km范围内的餐馆、酒店或电影院等。用户在发送查询前，首先通过带有定位功能的设备获得自己的当前位置，然后根据自己的查询半径，指定一个包含用户查询范围的方形查询面积。该查询面积可由左下角坐标和右上角坐标确定，再将该查询面积划分为大小相等的网格。因此，用户指定的查询面积网格结构可表示为

(2)

(4)

(5)

为使匿名器形成K匿名，用户根据K近邻算法[17]寻找到用户附近兴趣点相同的个其它用户，它们都是可信的。然后每个用户在网格结构上分别形成半径为的圆形查询范围，并分别确定自己的查询区域。

(7)

(9)

3.2 位置坐标比较

(11)

3.3 服务器查询

LBS服务器收到匿名器转发的查询请求消息后，首先使用LBS服务器私钥解密中的。然后根据中,和恢复用户指定的查询面积网格结构，并获得用户需要查询的兴趣点以及对称加密密钥集。同时LBS服务器用OPSE中的解密算法以及密钥，解密查询区域中的两个坐标，可以在网格结构上确定K匿名域。最后LBS服务器根据查询匿名域的POIs，共得到个POIs。如果第个POI的位置为，则它所在的网格单元标识为。

(13)

(14)

(16)

(17)

3.4 网格标识匹配

3.5 用户求精结果

4 安全性分析

本节主要分析GIM位置隐私保护模型分别抵制强攻击者和弱攻击者的攻击，本模型中将LSP和匿名器作为强攻击者，窃听者为弱攻击者。具体分析如下。

4.1抵制LSP的攻击

挑战：LSP管理所有用户的查询数据，LSP作为强攻击者想从这些数据中推断出一些用户敏感信息，从而揭露用户的精确位置。如果LSP可以确定地知道查询内容所对应用户的精确位置，那么LSP将赢得这个游戏。

定理1 GIM位置隐私保护方法能抵制LSP的推断攻击。

证明 本方案中，用户发送的查询经匿名器转发给LSP的查询请求为,中包括匿名域，兴趣点类型，密钥集以及网格结构，从这些信息中，LSP不能获得用户的精确位置。因为在查询过程中，LBS服务器根据,查询中的每个网格的POIs，然后返回给匿名器，而LSP仅知道该用户的，但它并不能与具体的用户关联。而且该匿名区域至少包括个用户，LSP能猜到是某个用户的概率最多只有。因此，LSP通过这些数据不能得到用户的精确位置。

证毕

4.2 抵制匿名器的攻击

挑战：匿名器在用户和LBS服务器之间，负责对用户进行K匿名，同时对查询请求、查询结果等信息的进行转发，它作为强攻击者想从这些数据中能推断出一些用户的敏感信息，从而揭露用户的精确位置。如果匿名器可以确定地知道查询内容所对应用户的精确位置，那么匿名器将赢得这个游戏。

定理2 GIM位置隐私保护方法能抵制匿名器的推断攻击。

证毕

4.3 抵制窃听者的攻击

挑战：弱攻击者通过侦听不安全的无线信道，试图从这些数据中能推断出一些用户的敏感信息，从而揭露用户的精确位置，甚至攻击者有意篡改用户的查询结果。如果弱攻击者知道用户的精确位置或能成功篡改用户的查询结果，那么弱攻击者将赢得这个游戏。

村级诊所作为新型农村合作医疗的前沿阵地，乡村医生直接决定着新农合供给的质量，这就要求当地政府实施积极的乡村医生队伍建设政策，其中包括提高乡村医生专业素质，坚持持证上岗原则；不断引进专业院校大学生来到村级诊所工作，制定一系列的鼓励政策；提升乡村医生的工作环境，提高其工资待遇水平；加强医疗设备的供给，保障最基本的医疗卫生服务等。

定理3 GIM位置隐私保护方法能抵制侦听者的攻击。

证明 在用户发送给LBS服务器的查询请求消息,中，,,和都是通过对称加密,和非对称加密进行加密的，攻击者没有密钥，不能解密这些参数，从而得不到有用的信息。在用户查询结果返回给用户的,中，中网格单元标识的哈希值加密后的,POIs的位置加密后的以及完整性验证函数都是通过对称加密函数进行加密的，同样攻击者得不到密钥，也得不到有用的信息。如果攻击者在结果返回的过程中，试图篡改POIs的位置，或加入一些假POIs的位置发送给用户，使用户得到错误的查询结果。GIM方案在LBS服务器端引入消息完整性验证机制，，用户得到POIs的位置后，先用验证值是否相等，如果不相等，则说明该查询结果的完整性被破坏，用户丢弃该查询结果并进行重新查询。因此，弱攻击者既不能得到用户的精确位置，也不能破坏查询结果的完整性。

证毕

5 实验及结果分析

本节主要通过实验验证GIM方案在相关参数变化下，用户每次查询时，对平均计算时间和平均通信开销的影响；同时在匿名器的平均计算时间以及平均通信开销上，与TTP[10], ELPP[5]方法进行仿真实验比较。实验采用由Brinkhoff移动对象生成器[18]，并利用德国奥尔登堡市交通网络图作为输入生成10000个移动用户，如图2所示。实验随机选取某时刻的移动对象Tom作为实验对象，Tom寻找到邻近的其它2和3个用户的位置分布情况如图3所示。实验参数设置如表1所示。实验的硬件环境为：Intel(R)Core(TM)i5-4590CPU@3.30 GHz3.30 GHz, 4.00 GB内存，操作系统为Microsoft Windows 7，采用MyEclipse开发平台，以Java编程语言实现。

图2 生成10000个移动用户                 图3移动用户Tom找到的邻近用户

表1实验参数设置

5.1 参数变化对GIM性能的影响

图4 网格单元粒度及查询范围半径变化对性能的影响

图5 网格单元粒度及匿名度变化对性能的影响

5.2 匿名器性能对比

图6 匿名器性能对比

由图6(b)可知，在匿名器通信开销上，TTP和ELPP相对于GIM有一定优势。因为在用户发送查询请求消息给匿名器的过程中，TTP中发送的是用户的精确位置，ELPP中发送的是经过转换的位置信息，而GIM方法发送的是个能确定用户指定查询区域的坐标加密集、加密网格单元标识集和用户端生成的对称密钥集等信息。同时在匿名器返回结果消息给用户的过程中，TTP和ELPP方法中匿名器返回的是精确结果，而GIM方法返回的候选结果集，在用户端需耗费一定的开销对结果集求精。因此，在匿名器的通信开销上，GIM方法有一定的劣势，但它能更好保护用户的位置隐私。

6 结束语

基于位置服务的快速发展，位置隐私问题已成为当前隐私保护方向的一个研究热点。针对TTP结构模型存在的缺陷，本文提出一种基于网格标识匹配的位置隐私保护方法。该方法利用网格思想，结合保序对称加密和K匿名技术，加强用户的位置隐私保护，且匿名器不清楚用户的具体位置。安全分析表明该方法能抵制LSP、匿名器和窃听者的隐私攻击。同时通过实验验证该方法在匿名器上具有较低的查询计算开销，有效缓解了匿名器的性能瓶颈问题。当然该方法也有待改进的地方，例如查询结果集的求精和寻找其它个用户由用户端完成，增加了用户端的计算开销，因此在下一步工作中，我们尝试在匿名器上通过用户历史记录形成K匿名，在适当增加匿名器开销的情况下，减少用户端的开销。

[1] LU Rongxing, LIN Xiaodong, LIANG Xiaohui,A dynamic privacypreserving key management scheme for location-based services in vanets[J]., 2012, 13(1): 127-139. doi: 10.1109/TITS.2011.2164068.

[2] YU Rong, KANG Jiawen, HUANG Xumin,MixGroup: accumulative pseudonym exchanging for location privacy enhancement in vehicular social networks[J]., 2016, 13(1): 93-105. doi: 10.1109/TDSC.2015.2399291.

[3] NIU Ben, LI Qinghua, ZHU Xiaoyan,Enhancing privacy through caching in location-based services[C]. 2015 IEEE Conference on Computer Communication(INFOCOM), Hong Kong, China, 2015: 1017-1025. doi: 10.1109/ INFOCOM.2015.7218474

[4] 张学军, 桂小林, 伍忠东. 位置服务隐私保护研究综述[J]. 软件学报, 2015, 26(9): 2373-2395. doi: 10.13328/j.cnki.jos. 004857.

ZHANG Xuejun, GUI Xiaolin, and WU Zhongdong. Privacy preservation for location-based services: a survey[J]., 2015, 26(9): 2373-2395. doi: 10.13328/j.cnki.jos. 004857.

[5] PENG Tao, LIU Qin, and WANG Guojun. Enhanced location privacy preserving scheme in location-based services [J]., 2014: 1-12. doi: 10.1109/JSYST. 2014.2354235.

[6] SHOKRI R, THEODORAKOPOULOS G, PAPADIMITRATOS P,Hiding in the mobile crowd: location privacy through collaboration[J]., 2014, 11(3): 266-279. doi: 10.1109/TDSC.2013.57.

[7] CHOW C Y, MOKBEL M F, and LIU X. Spatial cloaking for anonymous location-based services in mobile peer-to-peer environments[J]., 2011, 15(2): 351-380. doi: 10.1007/s10707-009-0099-y.

[8] ARDAGNA C A, CREMONINI M, VIMERCATI S D C,An obfuscation-based approach for protecting location privacy[J].,2011, 8(1): 13-27. doi: 10.1109/TDSC.2009.25.

[9] 彭志宇, 李善平. 移动环境下LBS位置隐私保护[J]. 电子与信息学报, 2011, 33(5): 1211-1216. doi: 10.3724/SP.J.1146. 2010.01050.

PENG Zhiyu and LI Shanping. Protecting location privacy in location-based services in mobile environments[J].&2011, 33(5): 1211-1216. doi: 10.3724/SP.J.1146. 2010.01050.

[10] GEDIK B and LIU L. Protecting location privacy with personalized k-anonymous: architecture and algorithms[J]., 2008, 7(1): 1-18. doi: 10.1109/TMC.2007.1062.

[11] 周长利, 马春光, 杨松涛. 路网环境下保护LBS位置隐私的连续KNN查询方法[J]. 计算机研究与发展, 2015, 52(11): 2628-2644. doi: 10.7544/issn1000-1239.2015.20140523.

ZHOU Changli, Ma Chunguang, and YANG Songtao. Location privacy-preserving method for LBS continuous KNN query in road networks[J]., 2015, 52(11): 2628-2644. doi: 10.7544/ issn1000-1239.2015.20140523.

[12] SCHLEGEL R, CHOW C Y, HUANG Q,User-defined privacy grid system for continuous location-based services[J]., 2015, 14(10): 2158-2172. doi: 10.1109/TMC.2015.2388488.

[13] AGRAWAL R, KIERNAN J, SRIKANT R,Order preserving encryption for numeric data[C]. Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data, Paris, France, 2004: 563-574.

[14] POPA R A, LI F H, and ZELDOVICH N. An ideal-security protocol for order-preserving encoding[C]. 2013 IEEE Symposium on Security and Privacy (SP), Berkeley, California, 2013: 463-477. doi: 10.1109/SP.2013.38.

[15] AHMADIAN M, PAYA A, and MARINESCU D C. Security of applications involving multiple organizations and order preserving encryption in hybrid cloudenvironments[C]. 2014 IEEE International Parallel & Distributed Processing Symposium Workshops (IPDPSW), Phoenix, Azerbaijan, 2014: 894-903. doi: 10.1109/IPDPSW.2014.102.

[16] GAO Sheng, MA Jianfeng, SHI Weisong,TrPF: a trajectory privacy-preserving framework for participatory sensing[J]., 2013, 8(6): 874-887. doi: 10.1109/TIFS.2013. 2252618.

[17] MCNAMES J. A fast nearest-neighbor algorithm based on a principal axis search tree[J].2001, 23(9): 964-976. doi: 10.1109/34.955110.

[18] BRINKHOFF T. Generating traffic data[J]., 2003, 26(2): 19-25.

The Method of Location Privacy Protection Based on Grid Identifier Matching

ZHANG Shaobo①③LIU Qin②WANG Guojun①④

①(School of Information Science and Engineering, Central South University, Changsha 410083, China)②(College of Computer Science and Electronic Engineering, Hunan University, Changsha 410082,China)③(School of Computer Science and Engineering, Hunan University of Science and Technology, Xiangtan 411201, China)④(School of Computer Science and Educational Software, Guangzhou University, Guangzhou 510006, China)

The model based on fully-trusted third party is a major model for location privacy protection in location-based services, but the model has some risk of exposing privacy. In this paper, a location privacy protection method based on Grid Identifier Matching (GIM) is proposed. In this method the user first divides the query area into grid and combines the order-preserving symmetric encryption and K-anonymity mechanism. Then, the K-anonymity paradigm is formed in anonymizer. Finally, the query results are returned to users by utilizing GIM. In the query process, the anonymizer dose not have any knowlegdge about a user’s real location, which can enhance the user’s location privacy. Meanwhile, the anonymizer only does simple comparison and matching operations, which relieves effectively is performance bottleneck of the anonymizer. Security analysis shows that the proposed approach can effectively protect the user’s location privacy. Experimental evaluations show that the proposed approach can decrease processing time overhead of the anonymizer.

Location privacy; Grid Identifier Matching (GIM); Order-preserving symmetric encryption; K- anonymity

TP393

A

1009-5896(2016)09-2173-07

10.11999/JEIT160350

2016-04-12；

2016-07-18；

2016-08-09

国家自然科学基金(61472451, 61272151, 61402161)，中南大学中央高校基本科研业务费专项资金(2016zzts058)

The National Natural Science Foundation of China (61472451, 61272151, 61402161), The Fundamental Research Funds for the Central Universities of Central South University (2016zzts058)

王国军 csgjwang@csu.edu.cn

张少波： 男，1979年生，讲师，博士生，研究方向为隐私保护和云计算安全.

刘 琴： 女，1982年生，助理教授，博士，研究方向为隐私保护、云计算和大数据.

王国军： 男，1970年生，教授，博士生导师，研究方向为系统安全、隐私保护、可信计算和大数据安全.