Cryptography Reference
In-Depth Information
In carrying out privacy amplification, we must shorten the key by the
number of bits of information that have potentially been leaked to the eaves-
dropper [7]. Having taken that into account, we denote by
g
the additional
number of bits by which the key length will be further shortened to assure
sufficient secrecy, i.e., the additional bit subtraction amount, and we refer to
g
as the
privacy amplification subtraction parameter
. With this definition of
g
, Ben-
nett et al. [12] show as a corollary of Prop. 7.2 that the set of Carter-Wegman
hash functions is a 2
−
g
/
ln 2 average uniformizer. We thus have for the APA
bound on
I
, the average value of the mutual information, the inequality
2
−
g
ln 2
.
I
≡
I
(
Y,
V
)
≤
(7.29)
In the case of the APA, the quantity
g
plays a dual role: in addition to represent-
ing the number of additional subtraction bits, for the APA case
g
also directly
determines the upper bound on the average of the mutual information.
In the case of PPA we again employ the symbol
g
to denote the number
of subtraction bits, as above for APA, but the upper bound on the pointwise
mutual information is now given in terms of a different quantity
g
, which
we refer to as the
pointwise bound parameter
. Also in the case of the PPA we
need the parameter
g
, which we refer to as the
pointwise probability parameter
,
in terms of which we may define the failure probability
P
f
. This definition
is motivated by Prop. 7.1, from which we find that the Carter-Wegman hash
functions are 2
−
g
/
ln 2 strong uniformizers except on a set of probability
2
−
g
ln 2
.
2
−
g
ln 2
P
f
≤
(7.30)
We therefore define the pointwise probability parameter as
g
≡
g
.
g
−
(7.31)
Thus the quantities
g
,
g
and
g
are not all independent, and are constrained
by Equation (7.31). In terms of these parameters we have for the PPA bound
on
I
, the actual value of the mutual information, the inequality
2
−
g
ln 2
=
2
−
(
g
−
g
)
ln 2
I
≡
I
(
Y, V
)
≤
(7.32)
where the associated failure probability
P
f
is bounded by
2
−
g
P
f
≤
.
(7.33)
The failure probability is not even a defined quantity in the APA case, but
it plays a crucial role in the PPA case. Thus the bound on the pointwise
mutual information is directly determined by the value of the parameter
g
,
with respect to which one finds a tradeoff between
g
, the number of additional
compression bits by which the key is shortened, and
g
, the negative logarithm
of the corresponding failure probability.
