Cryptography Reference
In-Depth Information
identically to the
J
-bit-long prefix of
G
(
U
n
). Next, we use the following ad-
ditional observations:
The event
A
(1
t
G
(
U
n
))
next
A
(
G
(
U
n
)) is independent of
J
. Thus,
,
=
[
A
(1
t
G
(
U
n
))
next
A
(
G
(
U
n
)) &
J
L
A
(
G
(
U
n
))]
Pr
,
=
=
L
A
(
G
(
U
n
))]
[
A
(1
t
G
(
U
n
))
next
A
(
G
(
U
n
))]
= Pr
[
J
=
· Pr
,
=
We can assume, without loss of generality, that
A
never reads its entire input
(because the success probability of an arbitrary
A
can be easily met by a modified
A
that does not read its last input bit; see Exercise 20). It follows that
L
A
(
G
(
U
n
))
∈
L
A
(
G
(
U
n
))]
1
t
.
Combining all the preceding with Eq. (3.13) (and
t
=
p
(
n
)), we get
{
0
,...,
t
−
1
}
, and so
Pr
[
J
=
=
1
t
·
Pr
t
−
1
t
·
1
2
[
A
(
f
(
U
n
))
=
b
(
U
n
)]
=
[
A
(1
t
,
G
(
U
n
))
=
next
A
(
G
(
U
n
))]
+
Pr
1
2
+
1
1
p
(
n
)
·
1
p
(
n
)
1
p
(
n
)
1
2
≥
+
−
·
1
p
(
n
)
·
p
(
n
)
for infinitely many
n
's, in contradiction to the hypothesis that
b
is a hard-core
of
f
.
1
2
+
=
3.4.2. Construction Based on Collections of Permutations
We now apply the ideas underlying Construction 3.4.2 in order to present constructions
of pseudorandom generators based on collections of one-way permutations. The fol-
lowing generic construction is readily instantiated using popular candidate collections
of one-way permutations; see details following the abstract presentation.
3.4.2.1. An Abstract Presentation
Let (
I
F
) be a triplet of algorithms defining a collection of one-way permutations
(see Section 2.4.2) such that
D
(
i
) is uniformly distributed over the domain of
f
i
for
every
i
in the range of
I
. Let
q
be a polynomial bounding the number of coins used by
algorithms
I
and
D
(as a function of the input length).
1
For
r
,
D
,
q
(
n
)
, let us denote
∈{
0
,
1
}
by
I
(1
n
n
the output of algorithm
I
on input 1
n
and coin tosses
r
. Likewise,
D
(
i
,
s
) denotes the output of algorithm
D
on input
i
and coin tosses
s
∈{
0
,
1
}
,
r
)
∈{
0
,
1
}
q
(
n
)
.We
remind the reader that Theorem 2.5.2 (existence of hard-core predicates) applies also
to collections of one-way permutations.
Construction 3.4.4:
Let
(
I
F
)
be a triplet of algorithms defining a collection
of one-way permutations, and let B be a hard-core predicate for this collection. Let
p
(
,
D
,
·
)
be an arbitrary polynomial. For n
∈ N
and r
,
s
∈{
0
,
1
}
q
(
n
)
, define G
(
r
,
s
)
=
1
In many cases, the polynomial
q
is actually linear. In fact, one can modify any collection of one-way
permutations so that
q
(
n
)
=
n
; see Exercise 19 in Chapter 2.
