Fundamental limits of location privacy using anonymization

摘要

In [1]–[3], the concept of perfect location privacy is defined and sufficient conditions for achieving it were obtained when anonymization is used. In this paper, necessary conditions for perfect privacy are obtained. Specifically, we prove that the previous sufficient bounds are tight, and thus we obtain the threshold for achieving perfect location privacy using anonymization. First, we assume that a user's current location is independent from her past locations. Using this i.i.d model, we show that if the adversary collects more than equation anonymous observations, then the adversary can successfully recover the users' locations with high probability. Here, n is the number of users in the network and r is the number of all possible locations that users can go to. Next, we model users' movements using Markov chains to better model real-world movement patterns. We show similar results if the adversary collects more than equation observations, where |E| is the number of edges in the user's Markov chain model.