Databases Reference
In-Depth Information
strongly dependent on the number of users joining the anonymity service and,
in particular, on the number of users physically co-located in the same mix
zone at the same time.
Bettini et. al. [5] propose a framework able to evaluate the risk of sensitive
location-based information dissemination and introduce a technique aimed at
supporting
k
-anonymity [8, 9]. The concept of
k
-anonymity captures a tradi-
tional requirement of statistical agencies stating that released data must be
indistinguishably related to no less than a certain number (
k
) of users. Tradi-
tionally,
k
-anonymity is based on the definition of a
quasi-identifier
that is a
set of attributes exploitable for linking data to identifiers. The
k
-anonymity
requirement states that each release of data must guarantee that every com-
bination of values of quasi-identifiers can be indistinctly linkable to at least
k
individuals. The proposal in [5] puts forward the idea that the geo-localized
history of the requests submitted by a user can be considered as a quasi-
identifier that can be used to discover sensitive information about that user.
For instance, a user tracked during working days is likely to commute from her
house to the workplace in a specific time frame in the morning and to come
back in another specific time frame in the evening. This information could be
used to identify the user. Consequently, the service provider gathering both
user requests for services and personal history of locations (i.e., a sequence of
user location updates) should never be able to link a subset of requests to a
single user. To make this possible, there must exist
k
users having a personal
history of locations consistent with the set of requests that have been issued.
This solution is highly dependent on the availability of
k
indistinguishable
histories of locations: the worst case happens when a given user has a unique
history, which make her always identifiable.
Also other proposals [6, 20] rely on the concept of
k
-anonymity by re-
quiring that a user should be indistinguishable from other
k
1usersina
given spatial area or temporal interval. Gruteser and Grunwald [6] propose a
middleware architecture and an adaptive algorithm to adjust location infor-
mation resolution, in spatial or temporal dimensions, to comply with specified
anonymity requirements. To this purpose, the authors introduce the concepts
of
spatial
and
temporal cloaking
used to transform the location of a user to a
different location that satisfies the required level of anonymity. Spatial cloak-
ing guarantees
k
-anonymity by applying an adaptive quad-tree algorithm that
decreases the spatial resolution to an area that contains
k
indistinguishable
users. Temporal cloaking, which is orthogonal to the spatial cloaking, pro-
vides spatial coordinates with higher accuracy but it reduces the accuracy in
time. The key feature of the adaptive cloaking algorithm is that the required
level of anonymity can be achieved for any location. Mokbel et al. [20] present
a framework, named
Casper
, that changes traditional location-based servers
and query processors to provide the users with anonymous services. Users can
define their privacy preferences through two parameters:
k
, meaning that the
user wants to be indistinguishable among other
k
entities; and
A
min
repre-
senting the minimal area that the user is willing to release. The core of the
−
