基于路网环分布的隐私保护近邻查询方法  

Location Privacy Preserving Nearest Neighbor Query Method Based on Circle Distribution on Road Networks

作　　者：倪巍伟[1,2] 冯志刚 闫冬 NI Wei-Wei;FENG Zhi-Gang;YAN-Dong(Department of Computer Science and Engineering,Southeast University,Nanjing 211189;Key Laboratory of Computer Network and Information Integration in Southeast University,Ministry of Education,Nanjing 211189)

机构地区：[1]东南大学计算机科学与工程学院,南京211189 [2]东南大学计算机网络和信息集成教育部重点实验室,南京211189

出　　处：《计算机学报》2020年第8期1385-1396,共12页Chinese Journal of Computers

基　　金：国家自然科学基金(61772131,61370077)资助.

摘　　要：位置服务在方便人们生活的同时,也带来了隐私安全问题,路网环境对移动对象运动模式的限制使得位置隐私保护问题更为复杂.基于空间混淆的现有路网隐私保护近邻查询方法存在对重放攻击的抵御能力较弱,位置泛化与查询处理效率低,以及处理效率与位置保护安全强度不可调节,难以支持个性化隐私保护查询的不足.针对上述问题,引入路网环分布概念并设计生成给定路网环分布的算法,在匿名服务器端离线生成路网环分布;通过设置基于路网环分布的子网扩张结束条件,提升所提隐匿环机制对重放攻击的抵御能力;借助子网扩张结束条件调控隐匿环子网规模实现对隐匿环生成效率、近邻查询效率与位置隐私保护强度的调节.进一步,结合隐匿环的组成结构,提出可以有效降低搜索起始边规模的剪枝方法,提升基于隐匿环的近邻POI查询效率.理论分析和实验结果表明,所提方法能有效抵御重放攻击,提升位置泛化处理与近邻查询处理的时效,在此基础上能够兼顾对查询发起者位置信息保护效果、位置泛化处理与近邻查询时效的调节.Location-based services(LBS)facilitate our daily life,nevertheless,they also bring privacy protection problem.The location and identity of the query initiator may be exploited by the attacker based on special query modes and other query related information.The limitation of mobile object’s motion mode on road network makes location privacy protection more complex in face of location based nearest neighbor query.Road network spatial cloaking is the representative technology to realize location privacy protection in road network environment.Namely,location of the query initiator,as well as the query content,are expanded to a road subnet satisfying specific privacy protection constraints in an anonymous way,usually done on trusted third party servers.The trusted anonymous server submits the subnet instead of query initiator’s real location to LBS server.The LBS server receives the subnet to finish the network expansion search and returns the candidate query results to the query initiator.Existing methods have the following shortcomings.They can not effectively resist replay attacks,there is a risk of location privacy leakage,and the anonymizing cost at the trusted third party is high.Besides,query methods lack attention to the internal relationship of each section in the anonymized subnet,and perform indifferent processing on the boundary nodes of the anonymized subnet,which results in waste of computing resources.Query processing method lacks the regulation mechanism to anonymization performance,query efficiency and privacy preserving intensity,which is difficult to meet the personalized query needs of queriers.Concerning aforementioned problems,the solution of PNQCD algorithm is proposed,which realizes privacy-preserving k nearest neighbor querying on road networks leveraging cloaking circle-based cloaking technology.It adopts the idea of circle based road subnet,called cloaking circle,to act as anonymized road subnet.The concept of circle probability distribution of the road network is introduced,and its gene

关 键 词：位置隐私保护 隐匿环 路网环分布 偏好调控 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]