Cryptography Reference
In-Depth Information
Theorem 2.5.6 and Proposition 3.5.3 and using a logarithmic length function, we get
very close to constructing a pseudorandom generator. In particular, for every polyno-
mial
p
(
), using
l
(
n
)
def
3 log
2
p
(
n
), we can construct a deterministic polynomial-time
algorithm expanding
O
(
n
)-bit-long seeds into (
O
(
n
)
·
=
1)-bit-long strings such that no
polynomial-time algorithm can distinguish the output strings from uniformly chosen
ones with probability greater than
+
1
p
(
n
)
(except for finitely many
n
's). Yet this does not
imply that the output is pseudorandom (i.e., that the distinguishing gap is smaller than
any
polynomial fraction). An additional idea is needed (because we cannot use
l
(
·
)
larger than any logarithmic function). In the sequel, we shall present two alternative
ways of obtaining a pseudorandom generator from Construction 3.5.2.
The First Alternative.
As a prelude to the actual construction, we use Construc-
tion 3.3.2 (in Section 3.3.2) in order to increase the expansion factors for the algo-
rithms arising from Construction 3.5.2. In particular, for every
i
, we construct a
deterministic polynomial-time algorithm, denoted
G
i
, expanding
n
-bit-long seeds into
n
3
-bit-long strings such that no polynomial-time algorithm can distinguish the output
strings from uniformly chosen ones with probability greater than
∈ N
1
n
i
(except for finitely
many
n
's). Denote these algorithms by
G
1
,
G
2
,...
. We now construct a pseudorandom
generator
G
by letting
G
(
s
)
def
G
m
(
|
s
|
)
s
m
(
|
s
|
)
where
⊕
de
notes bit-by-bit XOR of strings,
s
1
s
2
···
s
m
(
|
s
|
)
=
s
,
|
s
i
|=
|
s
|
m
(
=
G
1
(
s
1
)
⊕
G
2
(
s
2
)
⊕···⊕
±
1, and
|
s
|
√
n
.
4
)
m
(
n
)
def
(
|
s
|
2
. The pseudorandomness of
G
follows
by a reducibility argument. Specifically, if for some
i
and infinitely many
n
's, some
polynomial-time algorithm can distinguish
G
(
U
n
) from
U
n
2
with probability greater
than
=
Clearly,
|
G
(
s
)
|≈
m
(
|
s
|
)
)
3
=|
s
|
3
1
n
2
i
/
3
, then we can distinguish
G
i
(
U
n
/
m
(
n
)
) from
U
(
n
/
m
(
n
))
3
(in polynomial time) with
probability greater than
1
n
2
i
/
3
1
=
(
n
/
m
(
n
))
i
, in contradiction to the hypothesis regarding
G
i
.
The Second Alternative.
Here we apply Construction 3.5.2 to the function
f
defined by
f
(
x
1
,...,
x
n
)
def
=
f
(
x
1
)
···
f
(
x
n
)
w
here
n
. The benefit in applying Construction 3.5.2 to the function
f
is that we can use
l
(
n
2
)
def
|
x
1
|=···=|
x
n
|=
1, and hence Proposi
tio
n 3.5.3 indicates that
G
is a
pseudorandom generator. All that is left is to show that
f
has a hard-core function that
maps
n
2
-bit strings into
n
-bit strings. Assuming that
b
is a
h
ard-core predicate of the
function
f
, we can construct such a hard-core function for
f
. Specifically:
=
n
−
Construction 3.5.4:
Let f
:
{
0
,
1
}
∗
→{
0
,
1
}
∗
and b
:
{
0
,
1
}
∗
→{
0
,
1
}
. Define
f
(
x
1
,...,
x
n
)
def
=
f
(
x
1
)
···
f
(
x
n
)
g
(
x
1
,...,
x
n
)
def
=
b
(
x
1
)
···
b
(
x
n
)
where
|
x
1
|=···=|
x
n
|=
n.
4
The choice of the function
m
:
N → N
is rather arbitrary; any unbounded function
m
:
N → N
satisfying
m
(
n
)
<
n
2
/
3
will do.
