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,
(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
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 }   Search WWH ::

Custom Search