Private queries and trajectory anonymization: A dual perspective on location privacy

The emergence of mobile devices with Internet connectivity (e.g., Wi-Fi) and global positioning capabilities (e.g., GPS) have triggered the widespread development of location-based applications. For instance, users are able to ask queries about points of interest in their proximity. Furthermore, users can act as mobile sensors to monitor traffic flow, or levels of air pollution. However, such applications require users to disclose their locations, which raises serious privacy concerns. With knowledge of user locations, a malicious attacker can infer sensitive information, such as alternative lifestyles or political affiliations. Preserving location privacy is an essential requirement towards the successful deployment of location-based services (LBS). Currently, two main LBS use scenarios exist: in the first one, users send location-based queries to an un-trusted server, and the privacy objective is to protect the location of the querying user. In the second setting, a trusted entity, such as a telephone company, gathers large amounts of location data (i.e., trajectory traces) and wishes to publish them for data mining (e.g., alleviating traffic congestion). In this case, it is crucial to prevent an adversary from associating trajectories to user identities. In this survey paper, we give an overview of the state-of-the-art in location privacy protection from the dual perspective of query privacy and trajectory anonymization. We review the most prominent design choices and technical solutions, and highlight their relative strengths and weaknesses.