Databases Reference
In-Depth Information
(a) Microdata
(b) A voter registration list
Table 1.
Illustration of linking attacks for privacy inferencing
hint about
who
is the owner of each tuple. This naive approach fails, because
an adversary may combine
T
with certain additional information, to recover
the owner of a tuple. For instance, imagine that a neighbor of Sarah knows
the age 28 of Sarah, and that Sarah has been hospitalized before, and thus,
must have a record in
T
. Since this neighbor has all the non-sensitive values of
Sarah, s/he easily finds out that the last-but-one tuple in
T
belongs to Sarah.
In this way, the neighbor has successfully “linked” Sarah to her sensitive value
pneumonia
.
The above process exemplifies a type of privacy inferences called
linking
attacks
, where an adversary accurately infers the sensitive value of a victim,
via the victim's non-sensitive values. Since the non-sensitive attributes may be
utilized to pinpoint the tuple owned by a person, they are commonly referred
to as the
quasi-identifier
(QI) attributes. Linking attacks were first identified
as a real threat by Sweeney [15]. In particular, she shows that when the QI
attributes are
date-of-birth
,
gender
,and
Zipcode
, 87% of the Americans have a
unique combination of the values on those attributes. Furthermore, leveraging
a dataset released by a real publisher (the publication was done in the same
way as described earlier for Table 1a), Sweeney convinces the community
about the seriousness of linking attacks, by correctly extracting the medical
history of an ex-governor of Massachusetts.
In reality, the QI-values of an individual may be acquired by an adversary
through several channels. Knowing the victim is an obvious channel, as in our
earlier example where the adversary is the neighbor of Sarah. Alternatively,
an adversary may also obtain the QI-values from an
external database
,which
can be completely separate from
T
, and its accessibility to the public cannot
be controlled by the publisher of
T
. For instance, a worker in the government
may have access to the voter registration list in Table 1b, which includes all
the QI-attributes in the microdata of Table 1a, together with peoples' names.
Note that an external database, most likely, does not include exactly the same
