Unraveling an old cloak: k-anonymity for location privacy

By Reza Shokri, Carmela Troncoso, Claudia Díaz, Julien Freudiger, Jean-Pierre Hubaux. 2010

153 citations recorded by the source corpus.

There is a rich collection of literature that aims at protecting the privacy of users querying location-based services. One of the most popular location privacy techniques consists in cloaking users' locations such that k users appear as potential senders of a query, thus achieving k-anonymity. This paper analyzes the effectiveness of k-anonymity approaches for protecting location privacy in the presence of various types of adversaries. The unraveling of the scheme unfolds the inconsistency between its components, mainly the cloaking mechanism and the k-anonymity metric. We show that constructing cloaking regions based on the users' locations does not reliably relate to location privacy, and argue that this technique may even be detrimental to users' location privacy. The uncovered flaws imply that existing k-anonymity scheme is a tattered cloak for protecting location privacy.

Subfields: Artificial Intelligence

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

Citations in the corpus

Knock Knock, Who's There? Membership Inference on Aggregate Location Data (2017, background): “Previous location privacy research taking into account traces or profiles of single users [7, 12, 16, 24, 28, 37] does not apply to our problem, which focuses on aggregate location statistics.”
Anonymization of location data does not work: a large-scale measurement study (2011, background): “More recent work has shown that k-anonymity fails to provide strong privacy protection [23] which led to the introduction of l-diversity [20] and t-closeness [15].”
Differentially Private Filtering (2012, background): “ [4], [27]. However, in the absence of a quantitative deﬁnition of privacy and a clear model of the adversary capabilities, it is common that proposed techniques are later argued to be deﬁcient [28], [29]. The temporal cloaking scheme proposed in [4] for example aggregates the speed measurements of ”
What Does The Crowd Say About You? Evaluating Aggregation-based Location Privacy (2017, background): “, based on k-anonymity, as they have already been shown to be ineffective [43].”
Technical Privacy Metrics (2015, background): “In addition, k-anonymous data releases do not oer protection across multiple releases of the same data set [Xiao and Tao 2007], or when sensitive data, such as location data, are semantically close [Shokri et al. 2010b]. Despite this criticism, k-anonymity is still widely used today, and is routinel”
Quantifying Location Privacy: The Case of Sporadic Location Exposure (2011, background): “As it is shown in [19,20] these interesting approaches still lack an appropriate evaluation mechanism and metric that we provide in this paper.”