Information Technology Reference
In-Depth Information
Fig. 5.1
Illustration of a general anonymity model: each user specifies its anonymity set for person-
alized location privacy by defining an anonymity range, e.g., a disk centered at the user's location.
User 1 and 2 are out of user 3's anonymity range and thus are not in user 3's anonymity set (rep-
resented by no direct edge from user 1 or 2 to user 3); user 1 and 3 are within user 2's anonymity
range and thus are in user 2's anonymity set (represented by directed edges from user 1 and 3 to
user 2)
5.2
System Model
We consider a mobile network where users obtain their locations via mobile de-
vicesthat are capable of localization (e.g., by GPS or wireless access points based
localization). Users send their locations to a LBS provider for a certain LBS (e.g.,
location-based navigation or recommendation), and the LBS provider feedbacks the
desired results to the users based on their reported locations. To protect privacy, each
user uses a pseudonym as its identity for the LBS.
As in [
1
,
4
,
5
], we assume that the LBS provider is untrusted, i.e., it may leak users'
location traces to an adversary. For example, the adversary may steal the location
data by hacking into the LBS system. The adversary aims to learn the real identity
of a user by linking and analyzing the locations visited by the user's pseudonym. We
also assume that users are honest-but-curious such that each user honestly follows
the protocols with others (which will be discussed in Sect.
5.5.3
), but is curious about
others' private information. We further assume that the adversary may collude with a
limited number of users to gain useful information for inferring a user's real identity.
The use of pseudonym allows short-term reference to a user (e.g., one pseudonym
can be used for the navigation of an entire trip between two locations), which is
useful for many LBSs and does not disclose private information. However, long-
term linking among a user's locations should be prevented, as it may reveal sufficient
information for inferring the user's real identity [
6
,
7
,
8
]. Although a user may hide
explicit linking among its locations by changing its pseudonym, the adversary can
still link different pseudonyms of the user by exploiting spatial-temporal correlation
in its locations. For example, consider a user that visits location
l
1
with pseudonym
Alice at time
t
1
, and then visits location
l
2
that is close to location
l
1
with pseudonym
Bob at time
t
2
. If the adversary observes from the location traces that no other user
changes its pseudonym between time
t
1
and
t
2
, or there exists such a user but it
does not visit any location close to location
l
1
or
l
2
, then the adversary can infer that
pseudonym Alice and Bob must refer to the same user, since only the same user can
visit both location
l
1
and
l
2
within the limited period between time
t
1
and
t
2
.
