Achieving guaranteed anonymity in time-series location data

Collaborative sensing networks anonymously aggregate location-tagged sensing information from a large number of users to monitor environments. However, sharing anonymous location-tagged sensing information from users raises serious privacy concern. Rendering the location traces anonymous before sharing them with application service providers or third parties often allows an adversary to follow anonymous location updates because a time-series of anonymous location data exhibit a spatio-temporal correlation between successive updates. Prior privacy techniques for location data such as spatial cloaking techniques based on k-anonymity and best-effort algorithms do not meet both data quality and privacy requirements at the same time. This raises the problem of guaranteed anonymity in a dataset of location traces while maintaining high data accuracy and integrity.;To overcome these challenges, we develop a novel privacy metric, called Time-To-Confusion to characterize the privacy implication of anonymous location traces and propose two different privacy-preserving techniques that achieve both the guaranteed location privacy of all users and high data quality. The Time-To-Confusion effectively captures how long an adversary can follow an anonymous user at a specified level of confidence, given system parameters such as location accuracy, sampling frequency, and user density. Two different privacy mechanisms are designed with and without a trustworthy location privacy server in a time series of location updates. In the first solution, we propose an uncertainty-aware path cloaking algorithm in a trustworthy privacy server that determines the release of user location updates based on tracking uncertainty and maximum allowable tracking time. Our second solution does not require users to trust the centralized privacy server. Instead, we propose the novel concept of virtual trip lines where vehicles update their location and sensing information. This concept enables temporal cloaking in a distributed architecture where no single entity accesses all of identity, location, and timestamp information, yet incurring only a slight degradation of service quality. We evaluate two proposed algorithms with a case study of automotive traffic monitoring applications. We show that our proposed solutions effectively suppress worst case tracking bounds and home identification rates, while achieving significant data accuracy improvements.