Abstract
An important motivation for research in location privacy has been to protect against user profiling, i.e., inferring a user's political affiliation, wealth level, sexual preferences, religious beliefs, and other sensitive attributes. Existing approaches focus on distorting or suppressing individual locations, but we argue that, for directly protecting against profiling, it is more appropriate to focus on the frequency with which various locations are visited - in other words, the histogram of a user's locations. We introduce and explore a new privacy notion, namely, on-the-fly privacy for location histograms, in which a mobile user repeatedly submits obfuscated locations to a Location-Based Service aiming for the resulting histogram to resemble a target profile or differ from it. For example, she may want to avoid looking wealthy or to resemble a health-conscious person. We describe how to design concrete privacy mechanisms that operate under different assumptions on, e.g., the user's mobility, including provably optimal mechanisms. We use a mobility dataset with 1083 users to illustrate how these mechanisms achieve privacy while minimizing the quality loss caused by the location obfuscation, in the context of two types of Location-Based Services: nearest-PoI, and geofence.