Inference attacks and defenses in continuous location sharing with local differential privacy

Local differential privacy (LDP) has recently emerged as a commonly used privacy standard. With the growing popularity of LDP, recent works started applying LDP to location data collection and privacy-preserving usage of location-based services (LBS). However, in many practical applications of location data sharing and LBS usage, the user must continuously share his/her location with the data collector (e.g., LBS provider). Although the privacy of each individual location is protected with LDP, correlations between the user's consecutive locations can be exploited to infer the user's true locations. Following this idea, in this thesis we propose novel inference attacks against continuous location sharing under LDP. We develop attacks in two categories: statistical attacks based on Bayesian adversary formulation for stationary users and Hidden Markov Model (HMM) based attacks for mobile users. We also propose two extensions for our HMM-based attacks (informed and chain attacks), which enable the attacker to incorporate aggregate population statistics or use multiple iterations of HMM construction to improve attack effectiveness. We adapt and apply our attacks to four popular LDP protocols (GRR, RAPPOR, OUE, OLH), three datasets, and varying privacy levels. Experiment results show that our attacks are highly effective, which highlights the privacy risks of using LDP in continuous location sharing. Furthermore, results show that the attacks are better suited for the types of users they were designed for, i.e., statistical attacks achieve higher effectiveness than HMM-based attacks in case of stationary users, whereas HMM-based attacks achieve higher effectiveness in case of mobile users. Although our HMM-based attacks are effective on bitvector-based LDP protocols (such as RAPPOR and OUE), we observe that they suffer from efficiency problems, i.e., high memory usage and execution time. These hinder the scalability of our attacks, especially when grid sizes are large or when the attacker aims to achieve precise location inference. We therefore propose heuristic methods to improve the time and memory-efficiency of our attacks by removing states with low occurrence probability from the attack HMMs. We experimentally show that our improvements can reduce the memory and time costs of the attacks by more than an order of magnitude, while maintaining similar effectiveness compared to their original versions. Finally, we propose three defense strategies against our attacks: Memoization, Replay, and Replication. In memoization, each user stores a perturbed version of their original value, which is perturbed for a second time before being reported to the data collector. In replay, each user maintains a cache of previous locations and their perturbed counterparts. When a certain location is repeated, the user replays the old perturbed version rather than performing a fresh perturbation. In replication, each user replicates their previously reported value if their current location is similar to their previous location. We evaluate the three defenses using the same experiment setup containing four LDP protocols, three datasets, varying privacy levels, and mobile and stationary users. Results show that our defenses are successful in reducing attack effectiveness. We critically analyze the success, efficiency, and utility aspects of the three defenses under varying conditions, and provide recommendations regarding when to use which defense.