Research On Location Privacy Protection Based On Spatial K-anonymity

In recent years, mobile devices enabled with GPS and Internet access have becomeextremely common. People use these devices to obtain information easily through locationbased services (LBS). Although these services are very popular, their usage can also raisesevere privacy concerns because LBS provides customized information based on a user’sgeographic location. For example, an adversary may infer sensitive information fromprecise user positions (such as hospital). Therefore, mechanisms for protecting locationprivacy are mandatory when using LBSs. Available location privacy approaches differwith respect to the protected information and the considered attacker model. Most of themimplement the concept of k-anonymity to protect the user’s privacy. These methodsusually rely on the use of trusted third parties (TTP) such as anonymous servers.This thesis assess the applicability and effectiveness of location privacy approachessystematically firstly. A classification of possible attacks that try to reveal the protectedinformation introduced. It analyzes existing approaches with respect to their protectiongoals and their ability to resists the introduced attacks. Then it implements researches onsome key issues such as location privacy protection, general queries in Euclidean spaceand road network condition based on user-anonymizer-LBS framework. The completeresearch is outlined below:Firstly, a general framework for implementing reciprocal algorithms using anyexisting spatial index (such as R*-trees and Quad-trees) on the user locations is proposed.Moreover, since employing general-purpose spatial indices, the proposed system is notlimited to anonymization, but supports conventional spatial queries as well. At the sametime, an adjusted median splits method is provided, aimed on effectiveness and efficiency.And a spatial k-anonymity algorithm based on locality-sensitive hashing partition isproposed. The algorithm is shown to preserve both locality and moderate computationcomplexity. It can also be used as splits method.Secondly, a general model for privacy-aware mobile services over road networks(StarGCloaking) is proposed. StarGCloaking has three distinct features: it supports road-network-specific, personalized privacy and quality of service (QoS) requirements ona per request basis; it strikes a balance between the attack resilience of the performedprotection and the processing cost of the anonymous query; it scales to support a largenumber of mobile users with varying service requirements, through a star-graph basedprivatization model, powered by multi-folded optimizations in implementation.Thirdly, an HSGCloaking algorithm to protect users’ privacy in road network isproposed. It orders the nodes of a star network by using Hilbert order to meet thereciprocity condition of every user. The cloaking framework supports k-nearest neighbor(k-NN) and range queries by presenting two query processing algorithms.Finally, the correctness and validity of the above algorithms are proved by thetheoretical analysis and experimental verification.