Research On Location Privacy Protection Method Based On SpaceTwist

In recent years,the rapid development of spatial positioning technology and mobile communication technology has promoted the emergence of many software which providing location-based services(LBS).However,many studies have shown that LBS services may expose users’ private information,for example,attackers can infer users’ sensitive private information through their location information.A wide range of research work has been carried out on the security issues in LBS services.Common location privacy protection technologies include encryption-based technologies,fake location-based technology,anonymous area-based technology,and technologies based on users’ collaboration.Among them,encryption-based technology is the most secure,but less practical.The technology based on fake locations is simple to implement,but its security cannot be guaranteed.Both the anonymous area-based technology and the user collaboration-based technology can guarantee a certain degree of security,but the anonymous area-based technology often needs to introduce a trusted third party(TTP),and the service quality of the user collaboration-based technology is greatly affected by the user density distribution.In order to solve the k-nearest neighbor query problem in location privacy protection,the SpaceTwist scheme proposes that the user selects a false location as an anchor,and then implements an accurate k-nearest neighbor query through the incremental nearest neighbor algorithm without exposing the real location information.Unfortunately,the SpaceTwist scheme cannot guarantee the security of K-anonymity,nor does it solve the problem of anchor selection.This thesis will analyze and optimize the SpaceTwist scheme based on the above location privacy protection technologies.The main contents are as follows:1.Through the discussion of the main algorithm of the SpaceTwist scheme,named the incremental neighbor query algorithm(INN),analyze the security protection degree of the SpaceTwist scheme.The expression of the attack area Ωwhich formed by the possible position of the user in special case as well as the attack algorithm in general cases is given,and the influence of each parameter value in the INN algorithm on the security of the SpaceTwist scheme is further discussed.2.In order to optimize the efficiency of POI query,a SpaceTwist solution that can realize efficient query is proposed in combination with the R tree.The server will pre-construct the R tree to store the POI spatial data,and call the branch and bound(BAB)algorithm through the depth-first traversal of the R tree,the specific k-nearest neighbor results can be completed.This thesis conducts simulation experiments on synthetic datasets of different scales.Compared to the normal SpaceTwist scheme based on the common index method,this method has higher query efficiency and shorter query response time,besides the larger the scale of POI data,the greater its advantages.3.To solve the problem that the SpaceTwist scheme cannot achieve K-anonymity and unsolved anchor point selection,we propose a framework,called LKINN(lightweight K-anonymity incremental nearest neighbor),which can accomplish K-anonymity for INN algorithm with lightweight computational cost.LKINN is based on a hybrid location privacy protection architecture while it has lax security assumptions for all components in the architecture.Simulation results show that LKINN is enough safe to protect normal users’ location privacy from semi-trusted users,besides LKINN achieves less response time and lower communication.