Privacy Preservation For Continuous Query In Location Based Services

With the popularity of mobile devices such as smart-phones and tablets, location based services have become an integral part of humans’ daily life. The main concerns are the leakages of both users’ location and query contents to adversaries. Current privacy preserving solutions are focusing on temporal and spatial cloaking based methods to protect users’ location privacy. However, these solutions are vulnerable when subjected to continuous query environments. Further, if users are constrained by road network environments, an adversary can follow their trajectory with ease. In this Dissertation, a way of dealing with continuous query privacy in both two dimensional Euclidean space set-up(Cartesian Plane) and road network environment is presented.The first solution involves query linking privacy preservation for continuous LBS queries in an Euclidean space set-up. A cloud-based architecture that provides two functions; anonymity and authenticated privacy preservation function is proposed. A novel privacy preserving algorithm named Authenticated Velocity-Distance based Dynamic Cloaking Algorithm(AVD-DCA) is designed that preserves privacy for users based on their security profiles and similarity in their velocities. Further, to minimize the size of the cloaking area, a Minimum Spanning Tree based cloaking mechanism is employed.The second solution is geared towards solving problems of continuous queries in constrained road network environments. A solution of preserving privacy for continuous LBS queries in road networks is proposed where a centralized architecture in form of honest-but-curious model is used to provide anonymity for users as they use LBS services. A mix zone approach is used where two algorithms are designed. The first algorithm, Optimal Mixing Load Sub-graph(OMLS) finds an optimal placement of mix zones and creates three levels of abstraction to anonymize users, while the second algorithm, Semantically Based Graph Abstraction(SBGA) uses the three levels to abstract users in order to achieve their chosen and desired privacy level.The third solution proposes to optimize placement of mix zones to preserve privacy for users’ trajectory for continuous LBS queries in road networks. Two algorithms are designed. The first algorithm, Abstraction Graph(AG), selects a sample of mix zones that satisfy the user desired privacy level under the acceptable service availability condition. The second algorithm, Optimized Decision Graph(ODG), utilizes the generated graph to find an optimal solution for the placement of mix zones through decomposition, chunking and replacement strategies. An analysis is done on the capability of these algorithms to withstand attacks prone to mix zones such as timing attacks, transitions attacks and continuous query timing and transitions attacks.Finally, experiments are carried out to test efficiency and performance of our proposed algorithms. In the first experiment, the results show that AVD-DCA preserves privacy for users as well as achieving desired Quality of Service(QoS). In the second and third experiments, the results show that the proposed Algorithms preserve privacy for users based on their privacy and service availability conditions.