Databases Reference
In-Depth Information
In contrast, it is easily verified that, even after dropping assumption
A4
,
recursive (
c, l
)-diversity guarantees that
mult(
r
[
S
]
,
[
r
]
g
)
|
mult(
r
[
S
]
,R
)
|
c
1+
c
≤
≤
R
|
[
r
]
g
|
c
1+
c
. Plugging this
which implies that the further belief revision is bounded by
bound into (5), we obtain
c
1+
c
)
.
r-div
c,l
(
g
)
BFBR
R
⇒
{u},S
r
(
V
,
A
g
,
r
∈
R
A remarkable fact about recursive (
c, l
)-diversity is that it represents the
first anonymity flavor that looks beyond the uninformed attacker described
by the uniform probability distribution. The class of attackers it considers can
be described by the following family of probability distributions. We say that
a probability distribution
δ
is
l-pruning
if it satisfies both conditions below:
R
, there is a set
V
r
of sensitive values occurring in [
r
]
g
, such
•
for every
r
∈
that
-
|
V
r
|
<l
and
for every database
R
,
δ
(
R
) = 0 if and only if there are
r
∈
-
R
and
such that
R
contains the association of
r
[
ID
] with
v
;
v
∈
V
r
•
all databases with non-zero probability are equi-probable.
Intuitively,
V
r
is the set of alternatives which the attacker rules out as unas-
sociated to
r
[
ID
]. Denoting with
LP
all l-pruning distributions given by
R
and
g
,wehave
c
1+
c
)
.
r-div
c,l
(
g
)
BFBR
R
⇒
LP,S
r
(
V
,
A
g
,
r
∈
R
Since
is generated by all possible choices of
V
r
, the guarantee defends
against all attackers able to rule out at most
l
LP
1 alternatives, no matter which
these alternatives are, as dictated by the various attackers' backgrounds.
We conclude this section with a few remarks.
−
4.3 Additional Remarks on Anonymization Techniques
Complexity of Finding Optimal Anonymizations.
Clearly one extreme
way to ensure k-anonymity is to generalize tuples into a single equivalence
class. This would of course minimize the utility of the released data. [18]
studies the problem of finding the k-anonymization which incurs the least
amount of data loss due to generalization (for various metric for data loss),
showing that the problem of optimal k-anonymization is NP-complete. Sev-
eral follow-up papers propose practical k-anonymization algorithms based on
approximations and heuristics [12, 3, 7, 4]. While Machanavajjhala et al. do
