Cryptography Reference
In-Depth Information
def
=
def
=
I
(1
n
σ
1
···
σ
p
(
n
)
, where i
)
it holds
that
σ
j
=
B
(
i
,
s
j
−
1
)
and s
j
=
f
i
(
s
j
−
1
)
. That is, on input a seed
(
r
,
s
)
∈{
0
,
1
}
,
r
)
,s
0
D
(
i
,
s
)
, and for every
1
≤
j
≤
p
(
|
s
|
q
(
n
)
×
q
(
n
)
, algorithm G operates as follows, where F
(
i
,
x
)
=
f
i
(
x
):
{
0
,
1
}
Set i
←
I
(1
n
,
r
)
and s
0
←
D
(
i
,
s
)
.
Fo r j
=
1
to p
(
n
)
,
do
σ
j
←
B
(
i
,
s
j
−
1
)
and s
j
←
F
(
i
,
s
j
−
1
)
.
Output
σ
1
σ
2
···
σ
p
(
n
)
.
On input seed (
r
,
s
), algorithm
G
first uses
r
to determine a permutation
f
i
over
D
i
(i.e.,
i
r
)). Second, algorithm
G
uses
s
to determine a “starting point”
s
0
uniformly
distributed in
D
i
. The essential part of algorithm
G
is the repeated application of the
function
f
i
to the starting point
s
0
and the outputting of a hard-core predicate for
each resulting element. This part mimics Construction 3.4.2, while replacing the single
permutation
f
with the permutation
f
i
determined earlier. The expansion property of
algorithm
G
depends on the choice of the polynomial
p
(
←
I
(1
n
,
·
). Namely, the polynomial
p
(
·
) should be larger than twice the polynomial
q
(
·
).
Theorem 3.4.5:
Let
(
I
,
D
,
F
)
,B,q
(
·
)
,p
(
·
)
, and G be as in Construction 3.4.4,
and suppose that p
(
n
)
2
q
(
n
)
for all n's. Further suppose that for every i in the
range of algorithm I , the random variable D
(
i
)
is uniformly distributed over the
set D
i
. Then G is a pseudorandom generator.
>
Theorem 3.4.5 is an immediate corollary of the following proposition.
Proposition 3.4.6:
Let n and t be integers. For every i in the range of I
(1
n
)
and
every x in D
i
, define
G
i
(
x
)
=
B
(
i
,
x
)
·
B
(
i
,
f
i
(
x
))
···
B
i
,
f
t
−
1
(
x
)
i
j
+
i
(
x
)
=
f
i
(
f
i
(
x
))
for any j
≥
0
. Let
(
I
,
D
,
F
)
and B
be as in Theorem 3.4.5, with I
n
a random variable representing I
(1
n
)
and X
n
=
D
(
I
n
)
a random variable uniformly distributed in D
I
n
. Then for every polynomial
p
(
1
where f
i
(
x
)
=
x and f
·
)
, the ensembles
I
n
,
(
X
n
)
n
∈N
and
I
n
,
(
X
n
)
n
∈N
G
p
(
n
)
I
n
f
p
(
n
)
I
n
f
p
(
n
)
I
n
(
X
n
)
,
U
p
(
n
)
,
are polynomial-time-indistinguishable.
Hence the distinguishing algorithm gets, in addition to the
p
(
n
)-bit-long sequence to
be examined, the index
i
chosen by
G
(in the first step of
G
's computation) and the last
domain element (i.e.,
f
p
(
n
i
(
X
n
)) computed by
G
. Even with this extra information it is
infeasible to distinguish
G
p
(
n
)
I
n
(
X
n
)
≡
G
(
U
2
q
(
n
)
) from
U
p
(
n
)
. We note that providing the
distinguishing algorithm with
f
p
(
n
i
(
X
n
) only makes the proposition stronger and that
this stronger form is not required for proving Theorem 3.4.5. However, the stronger
form will be used in Chapter 5.
