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

4.3 Open problems
The techniques presented in Section 3 can guarantee anonymity in the static,
single-issuer case. In this section we discuss three relevant open problems that
are mostly related to the extension of these techniques to different cases.
Homogeneity attack.
Example 1 in Section 2 shows that, in the multiple-issuer case, a homogeneity
attack is possible in LBS, and hence anonymity can be insucient to guarantee
user privacy. A technical solution proposed to contrast the homogeneity attack
in the area of DB is called l-diversity [14]. Intuitively, a set of tuples in a DB
table is l -diverse if the tuples contain at least l different values of private
information.
A preliminary investigation on the extension of the l -diversity concept in
the area of LBS has appeared [2]. Intuitively, the l -diversity property holds for
a generalized request r if the attacker can infer at least l different values of
private information from the requests issued by the users in the anonymity set
of r . Further research is needed, for example, to formally characterize a) how
the parameters k and l affect the probability distribution in the anonymity
set, b) under which conditions close values in private information can really be
considered different (e.g., location areas), and c) how the homogeneity attack
changes in the dynamic case.
Personalization of the degree of anonymity.
In our discussion we never considered issues related to the personalization of
defense parameters, as for example, the degree of anonymity k to be enforced
by the LTS. Some approaches (e.g. [16]) actually explicitly allow different
users to specify different values of k . A natural question is if the proposed
techniques can be applied and can be considered safe even in this case. Once
again, to answer this question it is essential to consider which knowledge an
attacker may obtain. The degree of anonymity k desired by each user at the
time of a request is not assumed to be known by the attacker in contexts C st
and C ist , hence algorithms that are safe for these contexts remain safe even
when the LTS admits different values of k .
However, it may be reasonable to consider contexts in which the attacker
may obtain information about k . In the multiple-issuer case, the attacker
may use, for example, data mining techniques. Example 3 shows that, in
these contexts, C I -safe algorithms need to be extended in order to provide an
effective defense.
Example 3. User i 1 issues a request r asking the LTS a degree of anonymity
k = 2. Using a C I -safe algorithm, the LTS generalizes r to the request r
that has a spatio-temporal region containing only users i 1 and i 2 . Since the
generalization algorithm is C I -safe, if r were issued by i 2 with k = 2, then