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
}