Cryptography Reference
In-Depth Information
1.
Efficient indexing:
There exists a probabilistic polynomial-time algorithm I and
a mapping from strings to functions,
(
I
(1
n
))
and F
n
are identically
φ
, such that
φ
distributed.
We denote by f
i
the function assigned to the string i (i.e., f
i
def
=
φ
(
i
)
).
2.
Efficient evaluation:
There exists a polynomial-time algorithm V
such that
,
=
f
i
(
x
)
for every i in the range of I
(1
n
)
and x
∈{
,
}
(
n
)
.
V
(
i
x
)
0
1
In particular, functions in an efficiently computable function ensemble have relatively
succinct representations (i.e., of polynomial (in
n
) rather than exponential (in
n
) length).
It follows that efficiently computable function ensembles can have only exponentially
many functions (out of the double-exponentially many possible functions, assuming
(
n
)
=
n
).
Another point worth stressing is that efficiently computable pseudorandom functions
can be efficiently evaluated at given points
provided that the function description is given
as well
. However, if the function (or its description) is
not
known, then the value of the
function at a given point cannot be approximated, even in a very liberal sense and even
if the values of the function at other points are given.
Terminology.
In the rest of this topic we consider only efficiently computable pseudo-
random function ensembles. Hence, whenever we talk of pseudorandom functions, we
actually mean functions chosen at random from an efficiently computable pseudoran-
dom function ensemble.
Observe that, without loss of generality, the sequence of coin tosses used by the in-
dexing algorithm in Definition 3.6.3 can serve as the function's description. Combining
this observation with Definition 3.6.2, we obtain the following alternative definition of
efficiently computable pseudorandom functions:
Definition 3.6.4 (Efficiently Computable Pseudorandom Function Ensem-
bles, Alternative Formulation):
An
efficiently computable pseudorandom
function ensemble
(pseudorandom function)
is a set of finite functions
f
s
:
{
0
,
1
}
(
|
s
|
)
→{
0
,
1
}
(
|
s
|
)
s
∈{
0
,
1
}
∗
where
:
N → N
and the following two conditions hold:
1.
Efficient evaluation:
There exists a polynomial-time algorithm that on input s and
x
}
(
|
s
|
)
returns f
s
(
x
)
.
2.
Pseudorandomness:
The function ensemble F
∈{
0
,
1
={
F
n
}
n
∈N
, defined so that F
n
is
uniformly distributed over the multi-set
{
f
s
}
s
∈{
0
,
1
}
n
, is pseudorandom.
We comment that more general notions of pseudorandom functions can be defined and
constructed analogously; see Section 3.6.4.
3.6.2. Construction
Using any pseudorandom generator, we can construct a pseudorandom function en-
semble (for
(
n
)
=
n
) that is efficiently computable.
150
