Databases Reference
In-Depth Information
δ
(
D
)
.
P
δ
[
s
]:=
(1)
s
=
S
(
D
)
δ
also induces the probability
P
δ
[
V
(
D
)] that the published data is
V
(
D
):
δ
(
D
)
.
P
δ
[
V
(
D
)] :=
D
∈
[
D
]
V
The actual release of the published data causes a revision of the attacker's
belief about the probability of
s
being the actual secret. We call this the
a
posteriori
probability, and it is the conditional probability
P
δ
[
s
|V
(
D
)]:
=
D
∈
[
D
]
V
,
S
(
D
)=
s
δ
(
D
)
(
D
)] =
P
δ
[
s
∧V
(
D
)]
P
δ
[
s
|V
D
∈
[
D
]
V
δ
(
D
)
.
(2)
P
δ
[
V
(
D
)]
Classes of attackers.
For all privacy guarantees we consider next, we
conservatively assume that the attacker is able to reverse-engineer the pos-
sible databases and secrets from the published data. Attackers are therefore
distinguished from each other exclusively by their belief about the likelihood of
databases, as induced by the external knowledge they possess. Consequently,
in the following we characterize an attacker by the probability distribution
δ
he associates on all databases. A class of attackers we wish to defend against
is then described by a family
P
of probability distributions.
2.2 Privacy Guarantees
Privacy guarantees rule out privacy breaches. We list below several alternative
guarantees that generalize guarantees considered in the literature. Each one
is determined by the definition of what constitutes a “breach”.
Extent-Dependent Guarantees.
We start with a class of guarantees
which depend on the extent of actual database
D
. Each of them take as
argument a publishing function
V
and hold if and only if publishing
V
(
D
)
does not breach privacy.
No complete database exposure (NDE
D
).
The worst case of breach
consists in complete exposure of the actual database
D
.Thatis,thebreachis
defined as the case when the only possible database is
D
:[
D
]
V
=
. In this
case, an attacker who successfully reverse-engineers the possible databases
retrieves the actual database and can then compute
any
secret function
{
D
}
S
on
it. The guarantee of no database exposure, denoted NDE
D
(
V
), requires at
least two possible databases:
NDE
D
(
V
):=
|
[
D
]
V
|≥
2
.
Example 4.
Assume that in the setting of Example 1, the hospital publishes
a view revealing which doctors every patient sees:
V
PD
(
p, d
):
PDA
(
p, d, a
)
.
An additional view is published as well, listing which ailments every doctor is
−
