An Alternative Approach to k-Anonymity for Location-Based Services

Users of location-based services (LBSs) may have serious privacy concerns when using these technologies since their location can be utilized by adversaries to infer privacy-sensitive information about them. In this work, we analyze the mainstream anonymity solutions proposed for LBSs based on k-anonymity, and point out that these do not follow the safe assumptions as per the original definition of k-anonymity. We propose an alternative anonymity property, LBS (k,T)-anonymity, that ensures anonymity of a user's query against an attacker who knows about the issuance of the user query within a time window. We evaluate the vulnerability of the approaches in the literature to this type of attack that we believe is very basic and important, and assess the performance of our proposed algorithm for achieving LBS (k,T)-anonymity in terms of providing optimal solution.