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
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 }
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
→{ 0 , 1 }
Search WWH ::

Custom Search