Cryptography Reference
In-Depth Information
Let
d
k
(
n
) denote the probability that
D
outputs 1 on input taken from the hybrid
H
n
(i.e.,
d
k
(
n
)
def
[
D
(
H
n
)
1]). Recall that
H
n
equals
G
(
U
n
), whereas
H
p
(
n
)
=
Pr
=
n
equals
U
p
(
n
)
. Hence,
d
0
(
n
)
1],
d
p
(
n
)
(
n
)
=
Pr
[
D
(
G
(
U
n
))
=
=
Pr
[
D
(
U
p
(
n
)
)
=
1], and
d
0
(
n
)
d
p
(
n
)
(
n
)
(
n
)
=|
−
|
. Combining these facts with Claim 3.3.3.2, we get
[
D
(
G
1
(
U
n
))
=
1]
−
Pr
[
D
(
U
n
+
1
)
=
1]
|
|
Pr
p
(
n
)
−
1
d
k
(
n
)
p
(
n
)
−
1
d
k
+
1
(
n
)
1
p
(
n
)
·
=
−
k
=
0
k
=
0
d
0
(
n
)
−
d
p
(
n
)
(
n
)
p
(
n
)
=
=
(
n
)
p
(
n
)
1
q
(
n
)
Recall that by our (contradiction) hypothesis,
(
n
)
>
for infinitely many
n
's.
Contradiction to the pseudorandomness of
G
1
follows.
3.3.3.
∗
Variable-Output Pseudorandom Generators
Pseudorandom generators, as defined earlier (i.e., in Definition 3.3.1), provide a pre-
determined amount of expansion. That is, once the generator is fixed and the seed is
fixed, the length of the pseudorandom sequence that the generator provides is also
determined. A more flexible definition, provided next, allows one to produce a pseudo-
random sequence “on the fly.” That is, for any fixed seed, an infinite sequence is being
defined such that the following two conditions hold:
1.
One can produce any prefix of this sequence in time polynomial in the seed and the
length of the prefix.
2.
For a uniformly chosen
n
-bit-long seed, any poly(
n
)-bit prefix of corresponding output
sequence is pseudorandom.
In other words:
Definition 3.3.4 (Variable-Output Pseudorandom Generator): A variable-
output pseudorandom generator
is a deterministic polynomial-time algorithm
G satisfying the following two conditions:
}
∗
and t
1
t
)
1.
Variable output:
For all s
∈{
0
,
1
∈ N
, it holds that
|
G
(
s
,
|=
t and
1
t
+
1
)
.
2.
Pseudorandomness:
For every polynomial p, the ensemble
,
1
t
)
is a prefix of G
(
s
,
G
(
s
1
p
(
n
)
)
{
G
(
U
n
,
}
n
∈N
is
pseudorandom.
By a minor modification of Construction 3.3.2, we have the following:
Theorem 3.3.5:
If pseudorandom generators exist, then there exists a variable-
output pseudorandom generator.
