Cryptography Reference
In-Depth Information
3.5.1.2. The Basic Construction
Using any 1-1 one-way function and any hashing family, we can take a major step
toward constructing a pseudorandom generator.
Construction 3.5.2:
Let f
:
{
0
,
1
}
∗
→{
0
,
1
}
∗
be a function satisfying
|
f
(
x
)
|=
p
(
|
x
|
)
for some polynomial p
(
·
)
and all x 's. For any integer function l
:
N → N
,
let g
:
{
0
,
1
}
∗
→{
0
,
1
}
∗
be a function satisfying
|
g
(
x
)
|=
l
(
|
x
|
)
+
1
, and let S
n
−
l
(
n
)
p
(
n
)
S
n
−
l
(
n
)
p
(
n
)
be a hashing family. For every x
∈{
0
,
1
}
n
and h
∈
, define
G
(
x
,
h
)
def
=
(
h
(
f
(
x
))
,
h
,
g
(
x
))
Clearly,
|
G
(
x
,
h
)
|=
(
|
x
|−
l
(
|
x
|
))
+|
h
|+
(
l
(
|
x
|
)
+
1)
=|
x
|+|
h
|+
1. Thus,
G
satis-
fies the expanding requirement. The next proposition provides an upper bound on the
distinguishability between the output of
G
and a uniform ensemble (alas, this upper
bound is negligible only if
l
:
N → N
is super-logarithmic).
Proposition 3.5.3:
Let f , l, g, and G be as before. Suppose that f is
1-1
and
that g is a hard-core function of f . Then for every probabilistic polynomial-time
algorithm A, every positive polynomial p
(
·
)
, and all sufficiently large n's,
1
p
(
n
)
l
(
n
)
3
2
−
|
Pr
[
A
(
G
(
U
n
,
U
k
))
=
1]
−
Pr
[
A
(
U
n
+
k
+
1
)
=
1]
|
<
2
·
+
where k is the length of the representation of the hashing functions in S
n
−
l
(
n
)
.
p
(
n
)
Recall that by Exercises 22 and 23 we can use
k
=
O
(
n
). In particular, the forego-
ing proposition holds for functions
l
(
) of the form
l
(
n
)
def
0isa
constant. For such functions
l
, every one-way function (can be easily modified into
a function that) has a hard-core
g
as required in the proposition's hypothesis (see
Section 2.5.3). Hence, we get very close to constructing a pseudorandom generator
(see later).
·
=
c
log
2
n
, where
c
>
Proof Sketch:
Let
H
n
−
l
(
n
)
p
(
n
)
denote a random variable uniformly distributed over
S
n
−
l
(
n
)
. We first note that
p
(
n
)
≡
H
n
−
l
(
n
)
p
(
n
)
g
(
U
n
)
H
n
−
l
(
n
)
p
(
n
)
G
(
U
n
+
k
)
(
f
(
U
n
))
,
,
U
n
+
k
+
1
≡
U
n
−
l
(
n
)
,
U
l
(
n
)
+
1
H
n
−
l
(
n
)
p
(
n
)
,
We consider the hybrid distribution (
H
n
−
l
(
n
)
p
(
n
)
(
f
(
U
n
))
,
H
n
−
l
(
n
)
,
U
l
(
n
)
+
1
). The
p
(
n
)
proposition is a direct consequence of the following two claims.
Claim 3.5.3.1:
The ensembles
H
n
−
l
(
n
)
p
(
n
)
,
g
(
U
n
)
n
∈N
(
f
(
U
n
))
,
H
n
−
l
(
n
)
p
(
n
)
