Cryptography Reference
In-Depth Information
n be integers, S
n
be a hashing family, and b and
Lemma 3.5.1:
Let m
<
δ
be two
b
−
m
2
. Suppose that X
n
is a random variable
reals such that m
≤
b
≤
n and
δ
≥
2
−
distributed over
{
0
,
1
}
n
such that for every x , it holds that
Pr
[
X
n
=
x
]
≤
2
−
b
. Then
for every
α
∈{
0
,
1
}
m
and for all but at most a
2
−
(
b
−
m
)
δ
−
2
fraction of the h's in
S
n
, it holds that
Pr
[
h
(
X
n
)
=
α
]
∈
(1
±
δ
)
·
2
−
m
The average value of
], when averaging over all
h
's, equals 2
−
m
. Hence the
lemma upper-bounds the fraction of
h
's that deviate from the average value. Specifi-
cally, a function
h
not satisfying
Pr
[
h
(
X
n
)
=
α
α
and the random variable
X
n
). The lemma asserts that the fraction of bad functions
is at most 2
−
(
b
−
m
)
Pr
[
h
(
X
n
)
=
α
]
∈
(1
±
δ
)
·
2
−
m
is called
bad
(for
def
=
b
−
m
δ
−
2
. Typically we shall use
δ
2
−
1 (making the deviation
from average equal the fraction of bad
h
's). Another useful choice is
3
1 (which
yields an even smaller fraction of bad
h
's, yet here non-badness implies only that
Pr
δ
≥
[
h
(
X
n
)
=
α
]
≤
(1
+
δ
)
·
2
−
m
, since
Pr
[
h
(
X
n
)
=
α
]
≥
0 always holds).
Proof:
Fix an arbitrary random variable
X
n
satisfying the conditions of the lemma
and an arbitrary
def
=
Pr
α
∈{
0
,
1
}
m
. Denote
w
x
[
X
n
=
x
]. For every
h
,wehave
x
w
x
ζ
x
(
h
)
Pr
[
h
(
X
n
)
=
α
]
=
ζ
x
(
h
) equals 1 if
h
(
x
)
=
α
where
, and 0 otherwise. Hence, we are interested in the
probability, taken over all possible choices of
h
, that
−
x
w
x
ζ
x
(
h
)
|
2
−
m
|
>δ
2
−
m
.
Looking at the
ζ
x
's as random variables defined over the random variable
H
n
,it
is left to show that
x
w
x
ζ
x
>δ
·
2
−
m
2
−
(
b
−
m
)
δ
2
−
m
Pr
−
<
2
This is proved by applying Chebyshev's inequality, using the following facts:
2
−
m
1.
The
ζ
x
's are pairwise independent, and
Var
(
ζ
x
)
<
(since
ζ
x
=
1 with proba-
bility 2
−
m
, and
ζ
x
=
0 otherwise).
(by the hypothesis), and
x
w
x
=
w
x
≤
2
−
b
2.
1.
Namely,
>δ
·
2
−
m
x
w
x
ζ
x
(
δ
·
2
−
m
)
2
x
w
x
ζ
x
≤
Var
2
−
m
Pr
−
x
w
x
·
Var
(
ζ
x
)
=
δ
2
·
2
−
2
m
2
−
m
2
−
b
δ
<
·
2
−
2
m
2
The lemma follows.
