Cryptography Reference
In-Depth Information
Proposition
3.3.8:
Let
G
be
a
pseudorandom
generator
with
expansion
factor l
(
n
)
=
2
n. Then the function
f
:
{
0
,
1
}
∗
→{
0
,
1
}
∗
defined by letting
y
)
def
f
(
x
,
=
G
(
x
)
, for every
|
x
|=|
y
|
is a strongly one-way function.
Proof:
Clearly,
f
is polynomial-time-computable. It is left to show that each
probabilistic polynomial-time algorithm can invert
f
with only negligible success
probability. We use a reducibility argument. Suppose, on the contrary, that
A
is a
probabilistic polynomial-time algorithm that for infinitely many
n
's inverts
f
on
f
(
U
2
n
) with success probability at least
1
poly(
n
)
. We shall construct a probabilistic
polynomial-time algorithm
D
that distinguishes
U
2
n
and
G
(
U
n
) on these
n
's,
reaching a contradiction.
The distinguisher
D
uses the inverting algorithm
A
as a subroutine. On input
α
∈{
0
,
1
}
∗
, algorithm
D
uses
A
in order to try to get a pre-image of
α
under
f
.
Algorithm
D
then checks whether or not the string it obtained from
A
is indeed
a pre-image and halts outputting 1 in case it is (otherwise it outputs 0). Namely,
algorithm
D
computes
β
←
A
(
α
) and outputs 1 if
f
(
β
)
=
α
, and 0 otherwise
(i.e.,
D
(
α
)
=
1iff
f
(
A
(
α
))
=
α
).
By our hypothesis, for some polynomial
p
(
·
) and infinitely many
n
's,
1
p
(
n
)
By
f
's construction, the random variable
f
(
U
2
n
) equals
G
(
U
n
), and therefore
Pr
Pr
[
f
(
A
(
f
(
U
2
n
)))
=
f
(
U
2
n
)]
>
1
p
(
n
)
. On the other hand, by
f
's construction, at most 2
n
different 2
n
-bit-long strings (i.e., those in the support
of
G
(
U
n
)) have pre-images under
f
. Hence,
=
=
Pr
=
G
(
U
n
)]
>
[
D
(
G
(
U
n
))
1]
[
f
(
A
(
G
(
U
n
)))
Pr
[
D
(
U
2
n
)
=
1]
=
Pr
[
f
(
A
(
U
2
n
))
=
U
2
n
]
≤
2
−
n
. It follows that for infinitely many
n
's,
1
p
(
n
)
−
1
2
n
>
1
2
p
(
n
)
Pr
[
D
(
G
(
U
n
))
=
1]
−
Pr
[
D
(
U
2
n
)
=
1]
>
which contradicts the pseudorandomness of
G
.
3.4. Constructions Based on One-Way Permutations
In this section we present constructions of pseudorandom generators based on one-way
permutations. The first construction has a more abstract flavor, as it uses a single length-
preserving 1-1 one-way function (i.e., a single one-way permutation). The second
construction utilizes the same underlying ideas to present pseudorandom generators
based on collections of one-way permutations.
3.4.1. Construction Based on a Single Permutation
We provide two alternative presentations of the same pseudorandom generator. In
the first presentation, we provide a pseudorandom generator expanding
n
-bit-long
seeds into (
n
+
1)-bit-long strings, which combined with Construction 3.3.2 yields a
