Databases Reference
In-Depth Information
work attacker classes considered
[8] all
P
a
;
secret-focused
P
S
[19, 20] independent-tuple
P
it
[16, 17] l-pruning
P
u
⊂LP⊂
P
S
P
it
⊂P
a
LP
[23, 24] uniform distribution
P
u
=
{u}
Fig. 2.
Classes of attackers considered by privacy guarantees in various works
k-Anonymous Views.
An intriguing idea introduced by Jajodia et al
in [25] is to apply the notion of k-anonymity to view-based publishing. The
setting is similar to generalization-based publishing: we have a single table
R
with identity attributes
ID
and sensitive attributes
S
. The owner publishes
data from
R
via views expressed as conjunctive queries. It is assumed that re-
leasing all identifiers
Π
ID
(
R
) and all sensitive attributes
Π
S
(
R
) is acceptable
to the owner, but releasing the
association
between them is not.
Aview
V
is said to satisfy
k
-anonymity if for every identifier
id
∈
Π
ID
(
R
),
there are
k
distinct possible databases
{
R
1
,...,R
k
}⊆
[
R
]
V
, each associating
id
with a distinct sensitive value
s
1
,...,s
k
.
This guarantee can be connected to the
GBP
model as follows. Say that
an attacker is
uniform secret-focused
if he is described by a distribution on
databases which is generated by a uniform distribution on secrets. Given secret
S
, there is only one such uniform secret-focused distribution,
δ
S
. Then view
V
's k-anonymity implies
,V,
1
BFBR
R
{δ
S
r
},S
r
(
V
k
)
.
r
∈
R
are the views (considered a priori known to the attacker)
Π
ID
(
R
)and
Π
S
(
R
), and
V
where
S
r
is the secret association for tuple
r
, as defined in Section 4.1.
5 View-Based Versus Generalization-Based Publishing
The formalization of various privacy guarantees in terms of the
GBP
model
allows us to qualitatively compare view-based and generalization-based pri-
vacy guarantees.
Abstracting from the different expressive powers of the publishing func-
tions
(views versus generalizations), the fundamental difference be-
tween these guarantees remains the class of probability distributions used to
model attackers.
The guarantee in [8] is the most conservative one, considering all types
of attackers (with the drawback of high complexity for deciding the extent-
dependent guarantees, and undecidability in the extent-independent case).
V
and
N
