Cryptography Reference
In-Depth Information
Then, letting
U
1
be independent of
U
n
(where
U
1
represents the choice of
σ
in
Step 1 of algorithm
A
), we have
Pr
[
A
(
f
(
U
n
))
=
b
(
U
n
)]
=
Pr
[
D
(
f
(
U
n
)
·
U
1
)
=
1&
U
1
=
b
(
U
n
)]
+
Pr
[
D
(
f
(
U
n
)
·
U
1
)
=
0&1
−
U
1
=
b
(
U
n
)]
=
Pr
[
D
(
f
(
U
n
)
·
b
(
U
n
))
=
1&
U
1
=
b
(
U
n
)]
+
Pr
[
D
(
f
(
U
n
)
·
b
(
U
n
))
=
0&
U
1
=
b
(
U
n
)]
1
2
·
Pr
1
2
·
=
[
D
(
f
(
U
n
)
·
b
(
U
n
))
=
1]
+
(1
−
Pr
[
D
(
f
(
U
n
)
·
b
(
U
n
))
=
1])
1
2
+
1
2
·
(
Pr
[
D
(
f
(
U
n
)
·
b
(
U
n
))
=
1]
−
Pr
=
[
D
(
f
(
U
n
)
·
b
(
U
n
))
=
1])
1
2
+
1
2
p
(
n
)
>
where the inequality is due to Eq. (3.12.) But this contradicts the theorem's
hypothesis by which
b
is a hard-core of
f
.
3.4.1.2. An Alternative Presentation
Combining Theorems 3.3.3 and 3.4.1, we obtain, for any polynomial stretch function
p
,
a pseudorandom generator stretching
n
-bit-long seeds into
p
(
n
)-bit-long pseudorandom
sequences. Unfolding this combination we get the following construction:
Construction 3.4.2:
Let f
:
{
0
,
1
}
∗
→{
0
,
1
}
∗
be a
1-1
length-preserving and
polynomial-time-computable function. Let b
:
{
0
,
1
}
∗
→{
0
,
1
}
be a polynomial-
time-computable predicate, and let p
(
·
)
be an arbitrary polynomial satisfying
p
(
n
)
>
n. Define G
(
s
)
=
σ
1
···
σ
p
(
|
s
|
)
, where s
0
def
=
s, and for every
1
≤
j
≤
p
(
|
s
|
)
it holds that
σ
j
=
b
(
s
j
−
1
)
and s
j
=
f
(
s
j
−
1
)
. That is,
Let s
0
=
s and n
=|
s
|
.
Fo r j
=
1
to p
(
n
)
,
do
σ
j
←
b
(
s
j
−
1
)
and s
j
←
f
(
s
j
−
1
)
.
Output
σ
1
σ
2
···
σ
p
(
n
)
.
The construction is depicted in Figure 3.4. Note that
σ
j
is easily computed from
s
j
−
1
,but
if
b
is a hard-core of
f
, then
σ
j
=
b
(
s
j
−
1
) is “hard to approximate” from
s
j
=
f
(
s
j
−
1
).
The pseudorandomness property of algorithm
G
depends on the fact that
G
does not
output the intermediate
s
j
's. (By examining the following proof, the reader can easily
verify that outputting the last element, namely,
s
p
(
n
)
, does not hurt the pseudorandom-
ness property; cf. Proposition 3.4.6.)
