Modeling privacy approaches for location based services

Locationbased services (LBS) use geospatial data of mobile device to provide information in real time. A key concern in using these services is the need to reveal the user's exact location, which may allow an adversary to infer private information about the user. To address the privacy concerns of LBS users, a number of security approaches have been proposed based on the concept of k-anonymity. The central idea in location k-anonymity is to find a set of k-1 users close to the actual user, such that the locations of these k users are indistinguishable from one another, thus protecting the identity of the user. A number of performance parameters like success rate, amount of privacy achieved are used to measure the performance of the k-anonymity approaches. However, there is no formal model to compare the different k-anonymity approaches. Moreover, these proposals also make the implicit, unrealistic assumption that the k−1 users are readily available. Thus they ignore the turnaround time to process a user request, which is crucial for a real-time application like LBS. In this work, we model the k-anonymity approaches using queuing theory to compute the average sojourn time of users and queue length of the system. To demonstrate that queuing theory can be used to model all k-anonymity approaches, we quantitatively compare three different k-anonymity approaches with varying degree of complexity - top-up, bottom-down and bulk processing. The proposed analytical model is further validated with experimental results.