Privacy Protection through Anonymity in Location-based Services - Database Security: Applications and Trends - page 506

be formally evaluated if it is clearly identified which part of a request can act as
a so-called quasi-identifier . A quasi-identifier [17] is data that can be used by
an attacker to identify the actual issuer of the request, through some external
knowledge that we call context and that is assumed to be possibly reachable by
the attacker. Clearly, what is a quasi-identifier in requests changes depending
on the applicative context C .
A typical context assumed in almost all LBS privacy research, exemplified
by [9, 8], is given in Example 2 below.

Example 2. Consider a location based yellow pages service and the following
context C st , in which the attacker can obtain at most the following knowledge:
1. the location of each user;
2. the fact that the STData field of the requests forwarded by the LTS always
contains the location of the issuer of the original request.
Suppose that Alice issues a request asking for the closest shop where she
can find some specialty items. Assume LTS wants to protect Alice's privacy
by not revealing that the request issuer is Alice. The LTS now receives the
request and deletes the information that could directly lead to Alice's identity
(her name, for example). Moreover, the exact location of Alice is generalized
into an area. Then, the resulting generalized request r is forwarded to the
SP.

If an attacker obtains r , he first uses the location knowledge (assumption
1) to restrict the set of possible issuers to the users whose location is in the
region specified in r . Suppose this set has only one person, who must be Alice
due to assumption 2. In this case, the LTS has failed to provide privacy under
this context. The LTS obviously has to enlarge the area a bit further to obtain
r so the area of r covers the locations of three users: Alice, Bob and Carl. In
this case, r provides 3-anonymity. Further enlarging the area in the requests
generally provides k -anonymity with a greater k value.

Context C st may seem too excessive because it assumes that an attacker
knows the location of all users. However, if an attacker can possibly know
the location of one user (not too outrageous an assumption), we are forced
to assume the worst case, namely he knows the location of all users. This
assumption may be relaxed by saying that the attacker can only know the
locations of some users in some particular areas. But this is outside the scope
of this paper.
Given a context C , the attacker aims to infer, from a generalized request,
the identity of the user that issued it. We model a specific attack as the
likelihood of associating a specific identity to a generalized request.

Definition 2. An attack exploiting context C is a function Att C : R × I →

+ .

R

A special case of Definition 2 is the one in which the attacker can identify,
from the generalized request, a set of candidate issuers, each one having the