On the difficulty of achieving Differential Privacy in practice: user-level guarantees in aggregate location data
Florimond Houssiau, Luc Rocher, Yves-Alexandre de Montjoye · Nature Communications · 2022
Using Bassolas et al.’s attack model on a real-world mobility dataset, we show the empirical risk to be higher than the 16% bound as soon as the victim took more than three unique trips over any week ( p 3 ( u ) = 70.5%). Figure 1 reports the accuracy of the membership attack, p k ( u ), the likelihood that an attacker can test if u is in the aggregated data knowing k trips from their trajectory. The average number of trips per user in Bassolas et al.’s dataset is not reported but, looking at the Google Maps Timeline of one of us, the 39 trips taken over a typical week with 32 of them being unique would give an attacker a 95.4% certainty that he is in the dataset. Empirical accuracy of a membership attack (dots) and theoretical upper bound (solid line) as a function of the number of unique trips taken by a user. Reported upper bound (dashed line) and empirical accuracy of the attack on one of the authors’ data (triangle). From a differential privacy standpoint, the guarantees given by the authors ( ε = 0.66) protect single trips taken by a victim. A conservative estimate of the total privacy loss for any user in the dataset for 1 week, obtained through a straightforward application of the composition theorem, would be ε = 46.2 and δ = 2.1 × 10 (see “Methods”). Standard values of ε range from “ as little as 0.01 to as much as 7 ” in the literature , with higher values providing exponentially weaker guarantees. This privacy loss would furthermore grow linearly with the number of weeks of data released; for the 1 year of data released here, the ε budget could be as much as 52 times higher. We believe that behavioral data have a great potential for good, especially in research, and that data should be used a lot more than they are currently. However, in the pursuit of this laudable goal, we have allowed weak de-identification methods relying on unrealistic assumptions to be used to anonymize data behind closed doors. The guarantees given by these methods were incorrect in practice, leading numerous datasets to be re-identified and eroding public trust . The standard attack model considered by the authors is very strong and probably not realistic in a setup where aggregated data is shared with trusted researchers. However, as we are moving away from de-identification and towards modern privacy engineering solutions such as Differential Privacy, it is crucial for us as a community to learn from previous mistakes. The inherent risks and limitations of data sharing have to be clearly communicated and the guarantees we give data subjects correct and transparent. The future and broad availability of data for research are at stake. The guarantees given by Bassolas et al. rely on the assumption that each user does not contribute more than one trip to the dataset. The analyses performed in the paper strongly suggest that users contribute more than one trip to the dataset. Indeed, the final dataset used by Bassolas et al. contains connections, origin-destination trip counts, with at least 100 trips each. The dataset contains for instance 46,333 connections for Atlanta (population 5 M). Assuming that each user reports exactly one trip, at least 4.6 M people from Atlanta should contribute to the dataset to get the number of connections reported in the dataset. Given that only 67% of US mobile phone users use Google Maps as their main navigation app , we find this unlikely, thereby strongly suggesting that some users contributed more than one trip to the dataset. Regarding unique trips, the authors later confirmed that each user contributes a list of their unique weekly trips to the weekly aggregate. If the same trip (A → B) is made several times in a week, it is only counted once. In the case of one of the authors having made 39 trips in a given week, this results in him contributing 32 unique trips to the weekly aggregate while 7 of them would be discarded. Note that here unique refers to trips that are unique for a given user during a given week. We use a longitudinal mobility dataset extracted from CDR data. Each individual trajectory contains points with time and approximate location (antennas). We segment trajectories using a winner-takes-all approach, selecting the most used location for every hour, and define a trip as a movement from one location to a distinct one in the consecutive hour. We follow the procedure described by Bassolas et al. to aggregate anonymized trips: computing the origin-destination count matrix for unique trips, add zero mean Laplacian noise with scale 1/ ε to each entry, and discard all (noisy) counts lower than 100. We then use the attack model the authors rely on to compute the 16% increase over a random guess: the standard membership inference attack with perfect knowledge. In this model, the strong attacker has access to all the records in the dataset, except the victim’s, and auxiliary information about the victim. More specifically, for k between 0 and 70, we select one user u with exactly k trips. The attacker performs a membership attack to test whether the anonymized data D ′ they received is D (the anonymized trajectories with u included) or D (without u included). We compute the local origin-destination matrix A ( u ) for the user u and, by linearity of the noise addition, compute the normalized matrix A ( D ′) - A ( D ) generated from either no user or u . We perform a likelihood-ratio test to distinguish whether the normalized matrix was sampled from a Laplacian distribution L (0, 1/ ε) or L ( A ( u ), 1/ ε ). We repeat this procedure 10,000 times for all values of k between 0 and 70 and report the mean in Fig. 1 . The theoretical bound reported by Bassolas et al. is obtained by bounding the posterior probability of an attacker trying to infer whether a user is in the dataset, π ( y ). Formally, let D* be the tested dataset, D the dataset with the user u , and D the data without u . If the attacker’s prior holds no information (e.g., when P [ D* = D ] = 0.5), we then have for all y (and for M an ε-DP mechanism ): which then implies π ( y ) ≤ e /(1 + e ). To estimate the privacy loss for any user in 1 week of data, we assume conservative bounds: each user contributes only once to each count and makes no more than 70 unique trips per week (10 per day). Let n trips be the maximum number of unique trips that any user could contribute to the data, then the L 1 sensitivity of the count matrix is n t rips . Adding Lap(1/ ε ) noise and low-count filtering implies ( n trips × ε , 2.1 × 10 )-differential privacy by a straightforward application of simple composition bounds . Similarly, the privacy loss for a year of data can be estimated as the sum of the privacy losses for every week. A reasonable estimate of the total loss of the data release would thus be 52 times the privacy loss for a week, ε total = 52 × n trips × ε = 2402.4. Note that, while better bounds can be obtained, they require larger values of δ . In this specific case, acceptable values of ε would require prohibitively large values of δ rendering the guarantees meaningless in practice.