Protecting location privacy from untrusted wireless service providers

Access to mobile wireless networks has become critical for day-to-day life. However, it also inherently requires that a user's geographic location is continuously tracked by the service provider. It is challenging to maintain location privacy, especially from the provider itself. To do so, a user can switch through a series of identifiers, and even go offline between each one, though it sacrifices utility. This strategy can make it difficult for an adversary to perform location profiling and trajectory linking attacks that match observed behavior to a known user. In this paper, we model and quantify the trade-off between utility and location privacy. We quantify the privacy available to a community of users that are provided wireless service by an untrusted provider. We first formalize two important user traits that derive from their geographic behavior: predictability and mixing, which underpin the attainable privacy and utility against both profiling and trajectory linking attacks. Second, we study the prevalence of these traits in two real-world datasets with user mobility. Finally, we simulate and evaluate the efficacy of a model protocol, which we call Zipphone, in a real-world community of hundreds of users protecting themselves from their ISP. We demonstrate that users can improve their privacy by up to 45% by abstaining minimally (e.g., by sacrificing at most 5% of their uptime). We discuss how a privacy-preserving protocol similar to our model can be deployed in a modern cellular network.