轻量级K匿名增量近邻查询位置隐私保护算法

Location privacy protection method based on lightweight K-anonymity incremental nearest neighbor algorithm

基于位置的服务为人们生活带来便利的同时可能暴露用户的位置隐私。在k近邻查询问题中,构造K匿名区来保护用户位置隐私的方法具有一定的安全性,但会带来较大的通信开销。SpaceTwist方案使用锚点代替真实位置进行k近邻查询,实现简单且通信开销小,不过其无法保证K匿名安全,也没有给出锚点的具体选取方法。为克服SpaceTwist的缺点,一些方案通过引入可信匿名服务器或者使用用户协作的方式计算用户的K匿名组,进而加强算法的查询结束条件以实现K匿名安全;一些方案结合地图中兴趣点的大致分布,提出锚点的优选方法,进一步减小了平均通信开销。基于完善SpaceTwist的考虑,提出轻量级K匿名增量近邻(LKINN,lightweight K-anonymity incremental nearest neighbor)查询位置隐私保护算法,借助凸包这一数学工具计算K匿名组的关键点集合,并在此基础上给出一种锚点的选择方法,能够以更低的响应时间和通信代价实现K匿名安全。此外,LKINN基于混合式位置隐私保护架构,对系统中的所有成员都只做半可信的安全性假设,与现有的一些研究成果相比,降低了安全性假设要求。仿真实验结果表明,LKINN能够防止半可信用户对正常用户位置隐私的窃取,保护地图中正常用户的位置隐私,并且与一些现有方案相比,LKINN拥有更短的查询响应时间以及更小的通信开销。

The use of location-based service brings convenience to people's daily lives,but it also raises concerns about users' location privacy.In the k-nearest neighbor query problem,constructing K-anonymizing spatial regions is a method used to protects users' location privacy,but it results in a large waste of communication overhead.The SpaceTwist scheme is an alternative method that uses an anchor point instead of the real location to complete the k-nearest neighbor query,which is simple to implement and has less waste of communication overhead.However,it cannot guarantee K-anonymous security,and the specific selection method of the anchor point is not provided.To address these shortcomings in SpaceTwist,some schemes calculate the user's K-anonymity group by introducing a trusted anonymous server or using the way of user collaboration,and then enhance the end condition of the query algorithm to achieve K-anonymity security.Other schemes propose the anchor point optimization method based on the approximate distribution of interest points,which can further reduce the average communication overhead.A lightweight K-anonymity incremental nearest neighbor(LKINN) location privacy protection algorithm was proposed to improve SpaceTwist.LKINN used convex hull mathematical tool to calculate the key points of K-anonymity group,and proposed an anchor selection method based on it,achieving K-anonymity security with low computational and communication costs.LKINN was based on a hybrid location privacy protection architecture,making only semi-trusted security assumptions for all members of the system,which had lax security assumptions compared to some existing research schemes.Simulation results show that LKINN can prevent semi-trusted users from stealing the location privacy of normal users and has smaller query response time and communication overhead compare to some existing schemes.