Databases Reference
In-Depth Information
Therefore, we must provide a formal result regarding the individual-level
breach probability.
Theorem 1 ([18]).
Given a pair of QIT and ST, an adversary can correctly
infer the sensitive value of any individual with probability at most
1
/l.
4.5 Comparison with Generalization
Intuitively, by releasing the QI-values directly, anatomy may allow a higher
breach probability than generalization. Nevertheless, such probability is al-
ways bounded by 1
/l
, as long as the background knowledge of an adversary
is not stronger than the level allowed by the
l
-diversity model. Next, we will
explain these observations in detail.
The derivation in Section 4.4 implicitly makes two assumptions:
•
A1: the adversary has the QI-values of the target individual (i.e., Alice);
•
A2: the adversary also knows that the individual is definitely involved in
the microdata.
In fact, usually both assumptions are satisfied in practical privacy-
attacking processes. For example, in her pioneering paper [15], Sweeney shows
how to reveal the medical record of the governor of Massachusetts from
the data released by the Group Insurance Commission, after obtaining the
governor's QI-values from public sources. The revelation is possible because
Sweeney knew in advance that the record of the governor must be present in
the microdata. Otherwise, no inference could be drawn against the governor
because the “privacy-leaking” record could as well just belong to a person
who happens to share the same QI-values as the governor.
In general, if both Assumptions A1 and A2 are true, anatomy provides
as much privacy control as generalization, that is, the privacy of a person is
breached with a probability at most 1
/l
. For instance, if an adversary is sure
that Alice has been hospitalized before, from Alice's QI-values, s/he can assert
that Alice must be described by one of tuples 5-8 in the generalized Table 3a.
Then, s/he carries out the rest of her/his probabilistic conjecture (about the
disease of Alice) in the same way as s/he would do after identifying Alice to
be in Group 2 of the anatomized Table 4a.
Now, consider the case where A1 holds, but A2 does not. Accordingly, the
overall breach probability of Alice has a Bayes form:
Pr
A
2
(Alice
qi
)
Pr
breach
(Alice
s
·
|
A
2)
(10)
where
Pr
A
2
(Alice
qi
) is the chance for Alice to be involved in the microdata,
and
Pr
breach
(Alice
s
A
2) the likelihood for the adversary to correctly guess the
disease of Alice on condition that Alice appears in the microdata. As analyzed
earlier, anatomy and generalization give the same
Pr
breach
(Alice
s
|
|
A
2), which
is simply the preach probability when both A1 and A2 are valid.
