Location-Privacy Preserving Partial Nearby Friends Querying in Urban Areas

Abstract

This work studies the location-privacy preserving proximity querying in the context of proximity based services (PBSs), a special kind of location-based services (LBSs). The users register with the trusted PBS provider and specify their own personalized location privacy profile to be enforced against the curious friends (other registered users). Due to the urban area constraint, the user mobility is only on the city road network which is modeled as a weighted directed graph. The users share their own precise locations with the PBS provider and also query the nearby friends, the metric of which is defined on the shortest path on the graph. The proposed location privacy model ensures the location anonymity of the friends on the graph. To this end, two anonymity models, called weak location k-anonymity and strong location k-anonymity, are introduced to protect against the identified consecutive attack scenarios. The attack scenarios model the belief of the attacker (the query issuer) on the whereabouts of the friends. The PBS provider simulates the belief of each attacker on every users' whereabouts and suppresses some friends from the query result to ensure the location anonymity of each and every user at all times. Effective and efficient algorithms, needing no cryptographic protocols, have been developed to provide weak/strong location k-anonymity. An extensive experimental evaluation, mainly addressing the issues of privacy/utility tradeoff and runtime efficiency, on two real graphs with a simulated mobility is presented.