Location privacy: going beyond K-anonymity, cloaking and anonymizers

With many location-based services, it is implicitly assumed that the location server receives actual users locations to respond to their spatial queries. Consequently, information customized to their locations, such as nearest points of interest can be provided. However, there is a major privacy concern over sharing such sensitive information with potentially malicious servers, jeopardizing users' private information. The anonymity- and cloaking-based approaches proposed to address this problem cannot provide stringent privacy guarantees without incurring costly computation and communication overhead. Furthermore, they require a trusted intermediate anonymizer to protect user locations during query processing. This paper proposes a fundamental approach based on private information retrieval to process range and K-nearest neighbor queries, the prevalent queries used in many location-based services, with stronger privacy guarantees compared to those of the cloaking and anonymity approaches. We performed extensive experiments on both real-world and synthetic datasets to confirm the effectiveness of our approaches.