The Geo-indistinguishability For Differential Privacy With LBS

With global positioning capabilities of mobile devices allow users to retrieval their related points of interest (POI) at their nearby locations. In order to protect the privacy of users, it is very important that the exact location coordinates of users don't expose to un-trusted third party so that provide location based services, since the information of user's location can be associated with the sensitive details about lifestyle, political or religious affiliation, health and other personal information etc. Differential privacy regardless of any background knowledge owned by the attackers.Because it is built on a solid mathematical foundation,it has carried on the strict definition for privacy protection and provides a quantitative assessment method and also greatly enhances the reliability of privacy protection processing,thus widely be studied by scholars in recent years.The geo-indistinguishability,as a new extension of the model,has a very high academic frontier.First,this paper studies the optimization of trade-offs between geo-indistinguishability and quality losses, namely given a threshold value and a prior to design a spanner graph algorithm that proposed by shokri, so that only take into account the regional boundaries of POIs rather than each pair of location constraints,and then we propose a method to reduce the number of constraints of the linear program effectively from cubic to quadratic to minimum quality of service losses, so as to achieve better privacy protection.Second, this paper studies the effectiveness of geo-indistinguishability in practice when running the optimal mechanism, that is,the ability to protect the users'POIs. We improve this extract POIs'algorithm by setting the parameters and simulate experiments in two databases.For each user's mobile trajectories,we identify its POIs through space-time clustering algorithm, and regard it as the real POIs, then obfuscate trajectories in the optimal mechanism, and think of it as the attackers' collected information, and use the same cluster algorithm in obfuscated trajectories and infer the new POIs.Finally,this paper sets up a set of metrics to measure the ability to protect the user's POIs. These metrics are:attackers can infer the number of real POIs (inferred accuracy),the physical distance between real POIs and obfuscated ones (actual distance),the similarity between neighbourhood surrounding real POIs and obfuscated ones (semantic similarity), and make comparisons respectively.Result shows that the method has obvious advantages in terms of running time or accuracy to ensure the trade-offs between services and quality losses.