Cryptography Reference
In-Depth Information
existence of one-way functions is a necessary condition to the existence
of pseudorandom generators. That is:
Theorem 3.4.
(85):
Pseudorandom generators exist if and only if one-
way functions exist.
The necessary condition is easy to establish. Given a pseudorandom
generator
G
that stretches by a factor of two, consider the func-
tion
f
(
x
)=
G
(
x
) (or, to obtain a length preserving-function, let
f
(
x, y
)=
G
(
x
), where
|x|
=
|y|
). An algorithm that inverts
f
with
non-negligible success probability (on the distribution
f
(
U
n
)=
G
(
U
n
))
yields a distinguisher of
U
2
n
}
n∈
N
,becausetheprob-
ability that
U
2
n
is an image of
f
is negligible.
{
G
(
U
n
)
}
n∈
N
from
{
3.3
Pseudorandom functions
Pseudorandom generators provide a way to eciently generate long
pseudorandom sequences from short random seeds. Pseudorandom
functions, introduced and constructed by Goldreich, Goldwasser and
Micali (68), are even more powerful: they provide ecient direct access
to bits of a huge pseudorandom sequence (which is not feasible to
scan bit-by-bit). More precisely, a
pseudorandom function
is an ecient
(deterministic) algorithm that given an
n
-bit
seed
,
s
,andan
n
-bit
argu-
ment
,
x
, returns an
n
-bit string, denoted
f
s
(
x
), so that it is infeasible
to distinguish the values of
f
s
, for a uniformly chosen
s
n
,from
∈{
0
,
1
}
n
.Thatis,
the (feasible) testing procedure is given oracle access to the function
(but not its explicit description), and cannot distinguish the case it is
given oracle access to a pseudorandom function from the case it is given
oracle access to a truly random function.
One key feature of the above definition is that pseudorandom func-
tions can be generated and shared by merely generating and sharing
their seed; that is, a “random looking” function
f
s
:
{
0
,
1
}
n
the values of a truly random function
F
:
{
0
,
1
}
→{
0
,
1
}
n
,
is determined by its
n
-bit seed
s
. Parties wishing to share a “random
n
→{
0
,
1
}