Understanding the privacy-efficiency trade-off in location based queries

Mobile devices with global positioning capabilities (e.g., GPS) allow users to ask queries relative to their present location. Since certain queries may be privacy-sensitive, it is important to protect the identity of the users who send requests for Location-based Services (LBS). Instead of reporting the exact user location to the LBS provider, existing privacy-preserving techniques either perturb or encrypt the location data. Current LBS privacy solutions fall into several categories, based on the type of location transformation they employ, and the system architecture they rely on. This position paper introduces a taxonomy of LBS privacy solutions, and discusses the privacy-efficiency trade-offs achieved by various techniques. It also identifies several open problems, and proposes some interesting directions for future research.