Databases Reference
In-Depth Information
it would be generalized to
r
. However, if the attacker knows that
i
2
always
issues requests with
k
3, then he knows that if the issuer of
r
were
i
2
,the
request would have been generalized to a request
r
different from
r
, because
the spatio-temporal region of
r
should include at least 3 users. Hence the
attacker would identify
i
1
as the issuer of
r
.
≥
A straightforward solution to extend
C
I
-safe algorithms to these cases
is the following: when a request
r
needs to be generalized with degree of
anonymity
k
, the anonymity set is computed considering only the users that
can possibly issue a request requiring that degree of anonymity. Clearly, the
solution is viable only if a limited set of
k
values is available and a large number
of users using each value exists. If this is not the case, more sophisticated
strategies need to be devised to obtain
C
I
-safe generalization algorithms, and,
to our knowledge, this is still an open research issue.
Anonymity in the dynamic case
The techniques presented in Section 3 to provide anonymity in the static,
single-issuer case do not guarantee user's privacy in the dynamic, single-issuer
case. Example 4 shows that the generalization of each request in a trace, using
a
C
I
-safe algorithm, is not sucient to guarantee user's anonymity.
Example 4.
User
i
1
issues a request
r
with
k
=3.TheLTSusesa
C
I
-safe
algorithm to generalize
r
into a request
r
whose spatio-temporal region in-
cludes only users
i
1
,
i
2
and
i
3
. Afterwards,
i
1
issues a new request
r
1
with
k
= 3. The LTS generalizes it into a request
r
1
whose spatio-temporal region
includes only users
i
1
,
i
4
and
i
5
. Suppose the attacker is able to link requests
r
and
r
1
, i.e. he is able to understand that the two requests have been issued
by the same user. The attacker can observe that neither
i
2
nor
i
3
canbethe
issuer of
r
1
, because they are not in the spatio-temporal region of
r
1
; Conse-
quently, they cannot be the issuers of
r
either. Analogously, considering the
spatio-temporal region in
r
, he can derive that
i
4
and
i
5
cannot be the issuers
of the two request. Therefore, the attacker can identify
i
1
as the issuer of
r
and
r
1
.
The problem of anonymity in the dynamic, single-issuer case has been
investigated in [4]. The notion of
k
-anonymity along a trace of requests is
called
historical k-anonymity
. Some preliminary definitions are necessary to
formally define it. It is reasonable to assume that the LTS not only stores in
its database the set of requests issued by each user, but also stores for each
user the sequence of her location updates. This sequence is called
Personal
History of Locations
(PHL). More formally, the PHL of user
u
is a sequence
of 3D points (
,for
i
=1
,...,m
,
represents the position of
u
(in two-dimensional space) at the time instant
t
i
.
APHL(
x
1
,y
1
,t
1
,...,
x
m
,y
m
,t
m
), where
x
i
,y
i
) is defined to be
LT-consistent
with
a set of requests
r
1
,...,r
n
issued to a SP if for each request
r
i
there exists an
x
1
,y
1
,t
1
,...,
x
m
,y
m
,t
m
