Databases Reference
In-Depth Information
Example 6.
Consider the database from Example 1. Suppose that the owner
exports the projection of the
PDA
relation on its doctor attribute:
V
(
d
):
PDA
(
p, d, a
). Since neither patients nor ailments are exported, this
publishing is seemingly safe. However, an attacker can still learn from it some
(small amount of) information about the secret. Indeed, if the published list
of doctors is empty, then the actual database relation must be empty as well,
so no patient can suffer from any ailment. An attacker whose belief assigns
non-zero probability to a possible secret containing at least one ailing patient
will therefore revise this belief a posteriori. If however there is even one doctor
in the published list, then there is a non-zero probability of a certain patient
suffering from some disease. An attacker who is a priori certain that there
are no ailing patients must revise his belief as well. Clearly, at least these two
attackers have learned something about the secret upon observing the list of
doctors, and the idealized guarantee NBR
D
P,S
−
is violated. At the same time,
ruling out this publishing amounts to asking the owner to release no data
whatsoever, even if she avoids the attributes involved in the secret.
No further belief revision (NFBR
D
P,S
).
Since the guarantees NDE
and NSE
S
are too weak, and the ideal guarantee NBR
P,S
is too strong, we
consider a more pragmatic guarantee: it assumes that the owner is willing
to live with the current level in attacker's belief as induced by the already
published data
(
D
), but wants to make sure that publishing any further
data will not lead to further belief revision. Formally, denoting with
V
N
the
new publishing function which the owner contemplates, a breach occurs when
P
δ
[
s
(
D
)] is the belief of
the attacker described by distribution
δ
that
s
is the secret, provided that
both
|V
(
D
)]
=
P
δ
[
s
|V
(
D
)
∧N
(
D
)]. Here,
P
δ
[
s
|V
(
D
)
∧N
V
(
D
)and
N
(
D
) are published:
=
D
∈
[
D
]
V
∩
[
D
]
N
,S
(
D
)=
s
δ
(
D
)
P
δ
[
s|V
(
D
)
∧N
(
D
)] =
P
δ
[
s
(
D
)]
P
δ
[
V
(
D
)
∧N
(
D
)]
∧V
(
D
)
∧N
D
∈
[
D
]
V
∩
[
D
]
N
δ
(
D
)
.
(3)
The associated guarantee is the following:
NFBR
D
P,S
(
N
,
V
):=
∀
s
∀
(
δ
∈P
)
P
δ
[
s
|V
(
D
)] =
P
δ
[
s
|V
(
D
)
∧N
(
D
)]
.
Example 7.
Assume that on the schema from Example 1, the owner has
already published
=(
V
p
,V
a
) where
V
p
,V
a
are the views from Exam-
ple 2. The owner is currently contemplating the publishing of the two
new views
V
N
=(
V
PD
,V
DA
) from Example 4. Suppose that
V
p
(
D
)=
{
. From this
observation, any attacker can reverse-engineer the set of possible databases.
This includes, among others, the database
D
1
=
(John),(Jane),(Jack)
}
,and
V
a
(
D
)=
{
(pneumonia),(flu),(cold)
}
{
(John,doc
1
,pneumonia),
(Jane,doc
2
,flu), (Jack,doc
3
,cold)
}
, yielding the secret
s
1
=
S
(
D
1
)=
{
(John,
pneumonia), (Jane,flu), (Jack,cold)
. Given an attacker described by some
distribution
δ
, assume that his a priori belief that
s
1
is the secret is non-zero
}
