Cryptography Reference
In-Depth Information
That is,
h
maps to some small set (of density
1 times the den-
sity of the set (i.e.,
h
maps a relatively large probability mass to this set). Our first goal
is to prove that for some constant
c
) a probability mass
T
+
3
3
c
·
k
)-expanding. In
0, at most
4
of the
h
's are (
c
·
k
δ
,
δ
>
2
3
other words, only
4
of the functions map to some set of density
δ
a probability mass of
3
c
·
k
3
3
c
·
k
≈
3
.
We start with a related question. We say that
α
∈{
0
,
1
}
more than (
c
·
k
δ
·
δ
+
1)
2
k
is
t -overweighted
by the func-
2
−
k
. A function
h
S
n
is called (
t
tion
h
if
Pr
[
h
(
X
n
)
=
α
]
≥
(
t
+
1)
·
∈
,ρ
)
-overweighting
k
of cardinality
ρ
2
k
if there exists a set
R
⊂{
0
,
1
}
such that each
α
∈
R
is
t
-overweighted
by
h
. (Clearly, if
h
is (
t
,ρ
)-overweighting, then it is also (
t
,ρ
)-expanding, but the con-
1
t
2
verse is not necessarily true.) We first show that at most a
fraction of the
h
's are
ρ
(
t
,ρ
)-overweighting. The proof is in two steps:
2
−
k
for every
x
. Using Lemma 3.5.1, it follows that each
1.
Recall that
Pr
[
X
n
=
x
]
≤
k
is
t
-overweighted by at most a
t
−
2
α
∈{
0
,
1
}
fraction of the
h
's.
2.
Consider a bipartite graph having (
t
)-overweighting functions on one side and
k
-bit-long strings on the other side such that (
h
,ρ
,α
∈
S
n
×{
,
}
k
)
0
1
is an edge in
this graph if and only if
α
is
t
-overweighted by
h
. In this graph, each of the
(
t
,ρ
)-overweighting functions has degree at least
ρ
·
2
k
, whereas each image
α
has degree at most
t
−
2
S
n
|
·|
. Thus, the number of (
t
,ρ
)-overweighting functions
2
k
·
(
t
−
2
·|
S
n
|
)
1
t
2
S
n
|
is at most
=
ρ
·|
.
ρ
·
2
k
We now relate the expansion and overweighting properties, showing that upper bounds
on the number of overweighting functions yield upper bounds on the number of expanding
functions (which is the non-trivial direction). Specifically, we prove the following:
Subclaim
:For
T
≥
4, if
h
is (
T
,
)-expanding, then there exists an integer
i
∈{
1
,...,
2
i
−
3
k
+
2
}
such that
h
is (
T
·
,
2
i
+
1
)-overweighting.
k
·
2
k
·
The subclaim is proved as follows: Let
R
be a set of cardinality
such that
Pr
[
h
(
X
n
)
∈
R
]
≥
(
T
+
1)
·
.For
i
=
1
,...,
k
+
3, let
R
i
⊆
R
denote the subset of points
in
R
that are (2
i
−
3
·
T
)-overweighted by
h
. (Indeed,
R
k
+
3
=∅
.) Suppose, contrary to the
k
·
2
i
+
1
2
k
claim, that
|
R
i
|
<
·
for every
i
∈{
1
,...,
k
+
2
}
. Then for
T
≥
4 and
k
≥
1,
h
(
X
n
)
R
i
+
1
)
k
+
2
Pr
[
h
(
X
n
)
∈
R
]
=
Pr
[
h
(
X
n
)
∈
(
R
\
R
1
)]
+
Pr
∈
(
R
i
\
i
=
1
T
4
+
1
k
+
2
2
(
i
+
1)
−
3
·
T
+
1
·
|
R
i
\
R
i
+
1
|
2
k
≤
·
+
i
=
1
T
4
+
1
k
+
2
k
·
2
i
+
1
(2
i
−
2
<
·
+
·
T
+
1)
·
i
=
1
≤
(
T
+
1)
·
which contradicts the hypothesis regarding
R
.
Using this subclaim (for any
T
≥
>
0), the fraction of the
h
's that are (
T
,
4 and
)-
expanding is bounded above by
k
1
128
k
T
2
k
·
2
i
+
1
<
·
(
T
·
2
i
−
3
)
2
·
i
=
1
