Differential private POI queries via Johnson-Lindenstrauss transform

The growing popularity of location-based services is giving untrusted servers relatively free reign to collect huge amounts of location information from mobile users. This information can reveal far more than just a user's locations but other sensitive information, such as the user's interests or daily routines, which raises strong privacy concerns. Differential privacy is a well-acknowledged privacy notion that has become an important standard for the preservation of privacy. Unfortunately, existing privacy preservation methods based on differential privacy protect user location privacy at the cost of utility, aspects of which have to be sacrificed to ensure that privacy is maintained. To solve this problem, we present a new privacy framework that includes a semi-trusted third party. Under our privacy framework, both the server and the third party only hold a part of the user's location information. Neither the server nor the third party knows the exact location of the user. In addition, the proposed perturbation method based on the Johnson Lindenstrauss transform satisfies the differential privacy. Two popular point of interest queries, -NN and Range, are used to evaluate the method on two real-world data sets. Extensive comparisons against two representative differential privacy-based methods show that the proposed method not only provides a strict privacy guarantee but also significantly improves performance.