Cryptography Reference
In-Depth Information
Y
W
(space of func-
Definition 7.2
Let
be a random variable with values in
W
→
Y
=
v
(
=
tions
) which is conditionally independent of W given V
, i.e.,
P
γ
and W
=
w
|
V
=
v)
=
P
(
=
γ
|
V
=
v)
P
(
W
=
w
|
V
=
v).
is an
α>
0
average
uniformizer for Eve's distribution iff
E
(
H
)
≥
log
2
|
Y
|−
α
,
(7.26)
where
H
=
H
(
z
)
=
H
((
z
))
.
average uniformizer, the bound is on the mutual information
averaged over the set
If
is an
α
:
I
(
Y,
V
)
=
I
(
Y
)
−
H
(
Y
|
V
)
=
log
2
|
Y
|−
E
(
H
)
≤
α.
(7.27)
Uniformizers are produced stochastically. Notice that by the conditional
stochastic independence assumption,
z
can be assumed to vary independently
of
with the law
P
Eve
.
Proposition 7.1
w
∈
W
α
β>
Suppose
is an
average uniformizer. Then for every
0
,
outside a set of probability
β
(ω)
β
ω
is a
strong uniformizer for
.
PROOF.
Note that for any
γ
:
W
→
Y
,H
γ
is at most log
2
|
Y
|
. Thus log
2
|
Y
|−
H
is a nonnegative random variable. Applying Chebychev's inequality to
log
2
|
Y
|−
β>
H
, it follows that for every
0,
1
β
P
(
log
2
|
Y
|−
β
≥
H
)
≤
E
(
log
2
|
Y
|−
H
)
1
β
(
=
log
2
|
Y
|−
E
(
H
))
1
β
α.
≤
x
∈
The random variable
is strongly universal
2
iff for all
x
=
X
,
1
|
Y
|
.
x
)
}≤
P
{
z
:
(
z
)(
x
)
=
(
z
)(
(7.28)
The following is the main result of Ref. [12]:
Proposition 7.2
(BBCM Privacy Amplification).
Suppose
is a
univer-
W
→
Y
sal
2
family of mappings
conditionally independent of W. Then
is a
2
log
2
|
Y
|−
R
(
X
)
ln 2
average uniformizer for X.
7.3.2 Practical Results
We will refer to the inequality that provides the upper bound on the average
value of the mutual information as the
average privacy amplification bound
,or
APA, and we will refer to the inequality that provides the upper bound on the
actual, or pointwise mutual information as the
pointwise privacy amplifcation
bound
,orPPA.
