Cryptography Reference
In-Depth Information
Proposition 3.5.5:
Le
t f and b be as in Constr
uc
tion 3.5.4. If b is a hard-core
predicate of f , then g is a hard-core function of f.
Proof Idea:
Use the hybrid technique. The
i
th hybrid is
f
U
(1
n
,...,
f
U
(
n
n
,
b
U
(1
n
,...,
b
U
(
i
n
,
U
(
n
1
U
(
i
+
1)
1
,...,
I
nd
eed, the
n
th hybrid equals (
f
(
U
n
2
)
,
g
(
U
n
2
)), whereas the 0th hybrid equals
(
f
(
U
n
2
)
,
U
n
). Next, show how to transform an algorithm that distinguishes neigh-
boring hybrids into one predicting
b
(
U
n
) from
f
(
U
n
). Specifically, this transfor-
mation is analogous to a construction used in the proof of the “opposite direction”
for Theorem 3.3.7 and in the second proof of Theorem 3.4.1.
Conclusion.
Using either of the preceding two alternatives, we get the following:
Theorem 3.5.6:
If there exist
1-1
one-way functions, then pseudorandom gener-
ators exist as well.
The entire argument can be extended to the case in which the function
f
is polynomial-
to-1 (instead of 1-to-1). Specifically, let
f
satisfy
|
f
−
1
f
(
x
)
|
<
q
(
|
x
|
) for some poly-
nomial
q
(
) and all sufficiently long
x
's. We claim that if
f
is one-way, then (either
of the preceding alternatives yields that) pseudorandom generators exist. Proving the
latter statement using the first alternative is quite straightforward, given the exten-
sion of Proposition 3.5.3 (stated at the end of Section 3.5.1.2). For proving th
e
state-
ment using the second alternative, apply Construction 3.
5.2
to the function
f
, with
l
(
n
2
)
def
·
=
n
−
1
+
n
·
log
2
q
(
n
). This requires showing that
f
has a hard-core function
that maps
n
2
-bit strings into (
n
·
(1
+
log
2
q
(
n
)))-bit strings. Assuming that
g
is a hard-
core function of the fu
nc
tion
f
, with
|
g
(
x
)
|=
1
+
log
2
q
(
|
x
|
), we can construct such a
hard-core function for
f
. Specifically,
x
n
)
def
g
(
x
1
,...,
=
g
(
x
1
)
···
g
(
x
n
)
where
|
x
1
|=···=|
x
n
|=
n
.
3.5.2. Using Regular One-Way Functions
The validity of Proposition 3.5.3 relies heavily on the fact that if
f
is 1-1, then
f
(
U
n
)
maintains the “entropy” of
U
n
in a strong sense (i.e.,
Pr
[
f
(
U
n
)
=
α
]
≤
2
−
n
for every
α
). In this case, it is possible to shrink
f
(
U
n
) (to
n
−
l
(
n
) bits) and get almost uniform
distribution over
n
−
l
(
n
)
. As stressed earlier, the condition can be relaxed to requir-
ing that
f
be polynomial-to-1 (instead of 1-to-1). In such a case, only logarithmic loss
of “entropy” occurs, and such a loss can be compensated by an appropriate increase in
the range of the hard-core function. We stress that hard-core functions of logarithmic
length (i.e., satisfying
{
0
,
1
}
)) can be constructed for any one-way func-
tion. However, in general, the function
f
may not be polynomial-to-1, and in particular
it can map exponentially many pre-images to the same image. If that is the case, then
141
|
g
(
x
)
|=
O
(log
|
x
|
