Databases Reference
In-Depth Information
[8] therefore considers attackers whose background knowledge enables
them to form an opinion that discriminates among possible
secrets
, but who
cannot (or do not care to) distinguish among the possible
databases
witness-
ing any given secret. In this survey we call such attackers
secret-focused
, and,
given a secret
P
S
the set of distributions describing secret-
focused attackers with respect to
S
, we denote with
.
P
S
is defined as follows. Given a distribution
δ
S
on possible secrets, we
say that
δ
S
induces a distribution
δ
on possible databases if
δ
satisfies both
of the following conditions:
S
•
for every
s
and every
D
such that
s
=
S
(
D
), we have
s
=
S
(
D
)
δ
(
D
)=
δ
S
(
s
);
•
all witnesses of the secret are equi-probable according to
δ
:
∀
δ
(
D
1
)=
δ
(
D
2
)
.
Observing that
δ
is uniquely determined by
δ
S
,wehavethat
D
1
,D
2
S
(
D
1
)=
S
(
D
2
)
⇒
P
S
is the set of
distributions on databases induced by all unrestricted distributions on secrets.
Note that
P
S
still allows for attackers with arbitrary capacity to discriminate
among the secrets, as we start from arbitrary distributions on secrets.
[8] studies the setting in which the already published views
V
, the secret
S
are specified by unions of conjunctive queries with
inequalities UCQ
=
. The constraints in
, and the new view
N
C
are equivalent to containment state-
ments between UCQ
=
queries. Such constraints extend classical embedded
dependencies [1] with disjunction and inequalities, and can express such com-
mon integrity constraints as keys and foreign keys, functional, inclusion and
join dependencies [1], cardinality constraints, and beyond.
For the extent-dependent guarantees, [8] shows that NFBR
D
P
a
,S
)
is
Π
2
-complete in the combined size of the queries and database, while
NFBR
D
P
S
,
(
V
,
N
) is in PSPACE. These results hold even when the attacker
knows that
D
satisfies a set
(
V
,
N
S
is
weakly acyclic
[9,
10]. In addition, both extent-independent guarantees NFBR
P
a
,S
(
C
of constraints, as long as
C
V
,
N
)and
NFBR
P
S
,S
(
V
,
N
) are undecidable [8], even in the absence of constraints
(
).
These results should be viewed in light of the fact that in generalization-
based publishing (discussed in Section 4), deciding whether an anonymization
is optimal is NP-complete in the size of the database.
While the above results render the proposed privacy guarantees impracti-
cal in the current form, the study in [8] is a first step toward identifying restric-
tions leading to tractability on the views, secret and constraints. Moreover, the
study proves that changing the class of attacker distributions yields a novel
privacy guarantee, which is qualitatively different from the version in [19, 20],
as witnessed by the different complexity and decidability bounds. Finally, the
contrast between the various classes of attackers considered in [19, 20] and [8]
shows the diculty of striking the right balance between the strength of the
guarantee and the feasibility of checking it.
C
=
∅
