Databases Reference
In-Depth Information
m
1
≤
c
(
m
l
+
m
l
+1
+
...
+
m
o
)
for some constant
c
. We say that
g
satisfies recursive (
c, l
)-diversity for
R
,
denoted r-div
c,l
(
g, R
), if for every
r
∈
R
,
r
's equivalence class satisfies recursive
(
c, l
)-diversity.
Example 10.
The anonymized table in Fig. 1 satisfies recursive (1,2)-diversity.
Recursive (
c, l
)-diversity has two immediate implications.
First, it enables owners to drop assumption
A4
, thus extending applica-
bility of the guarantee to tables with duplicate sensitive values. Indeed, it is
easy to check that under assumptions
A1
,
A2
and
A3
,(
c, l
)-diversity im-
poses an upper bound of
c
1+
c
on the attacker's a posteriori and a priori belief,
and hence on the belief revision that
S
r
holds. Recursive (
c, l
)-diversity thus
provides defense even when assumption
A4
is violated.
Second, recursive (
c, l
)-diversity allows to relax assumption
A3
to accom-
modate defense against background attacks. [16] shows that this guarantee
implies that regardless of which (at most)
l
1 sensitive values are pruned
from
r
's equivalence class as being unassociated to
r
[
ID
] (according to back-
ground information), the frequency of each remaining sensitive value in the
pruned equivalence class is at most
−
c
1+
c
. This is the upper bound on the a
posteriori belief about secret
S
r
.
[17] discusses additional refinements of (
c, l
)-diversity, relaxing the defini-
tion to allow for the disclosure of attributes for certain individuals with less
stringent privacy concerns. The authors also show that l-diversity is a prac-
tical notion, not only because it defends against more realistic attacks than
k-anonymity, but also because finding an optimal l-diverse generalization of a
table can be done no less eciently than finding an optimal k-anonymization.
Machanavajjhala et al. show how to exploit the structural similarity of the two
privacy notions to easily adapt to l-diversity the state-of-the-art techniques
developed for k-anonymity, such as the Incognito algorithm [12].
In the remainder of this section, we connect l-diversity to the
GBP
model.
Relationship to the GBP Model.
The insight that when assumption
A4
does not hold K-anonymity provides no guarantees, is also reflected in the
GBP
model. Specifically, in the pathological case when all tuples in
r
's equiv-
alence class share the same sensitive value, the posterior probability of
S
r
is
given by
∧A
g
(
R
)] =
mult(
r
[
S
]
,
[
r
]
g
)
|
P
u
[
S
r
|V
(
R
)
=1
[
r
]
g
|
so from (5) we obtain that the only guarantee possible for
S
r
is
mult(
r
[
S
]
,R
)
|
BFBR
R
{
S
r
(
V
,
A
g
,
1
−
)
.
u
}
,
R
|
This is a trivial guarantee, satisfied by any anonymization, including those in
which the secret
S
r
is completely exposed.
