Location privacy attacks based on distance and density information

Proximity services alert users about the presence of other users or moving objects based on their distance. Distance preserving transformations are among the techniques that may be used to avoid revealing the actual position of users while still effectively providing these services. Some of the proposed transformations have been shown to actually guarantee location privacy with the assumption that users are uniformly distributed in the considered geographical region, which is unrealistic assumption when the region extends to a county, a state or a country. In this paper we describe a location privacy attack that, only using partial information about the distances between users and public knowledge on the average density of population, can discover the approximate position of users on a map, independently on the fake or hidden position assigned to them by a privacy preserving algorithm. We implement this attack with an algorithm and we experimentally evaluate it showing that it is practically feasible and that partial distance information like the one exchanged in common friend-finder services can be sufficient to violate users' privacy