Cryptography Reference
In-Depth Information
query the function being examined at various points, depending possibly on previous
answers obtained, and yet cannot tell whether the answers were supplied by a function
taken from the pseudorandom ensemble (of functions) or by one from the uniform
ensemble (of functions). Indeed, to formalize the notion of pseudorandom functions,
we need to consider ensembles of functions. For the sake of simplicity, we shall consider
ensembles of length-preserving functions, and in the following the reader is encouraged
to further simplify the discussion by setting
(
n
)
=
n
. Generalizations are discussed in
Section 3.6.4.
Definition 3.6.1 (Function Ensembles):
Let
:
N → N
(
e.g.,
(
n
)
=
n
)
.An
F
n
}
n
∈N
of random variables such
that the random variable F
n
assumes values in the set of functions mapping
(
n
)
-bit-long strings to
(
n
)
-bit-long strings. The
uniform
-
bit function en-
semble,
denoted H
={
H
n
}
n
∈N
, has H
n
uniformly distributed over the set of all
functions mapping
(
n
)
-bit-long strings to
(
n
)
-bit-long strings.
-
bit function ensemble
is a sequence F
={
To formalize the notion of pseudorandom functions, we use (probabilistic
polynomial-time)
oracle machines
(see Section 1.3.5). We stress that our use of the
term “oracle machine” is almost identical to the standard usage. One minor deviation is
that the oracle machines we consider have a length-preserving function as oracle, rather
than a Boolean function (as is more standard in complexity theory). Furthermore, we
assume that on input 1
n
, the oracle machine makes queries of only length
(
n
). These
conventions are not really essential (they merely simplify the exposition a little). We let
M
f
denote the execution of the oracle machine
M
when given access to the oracle
f
.
Definition 3.6.2 (Pseudorandom Function Ensembles):
An
-bit function
ensemble F
={
F
n
}
n
∈N
is called
pseudorandom
if for every probabilistic poly-
nomial-time oracle machine M , every polynomial p
(
·
)
, and all sufficiently large
n's,
Pr
1
<
M
F
n
(1
n
)
1
−
Pr
M
H
n
(1
n
)
1
p
(
n
)
=
=
where H
={
H
n
}
n
∈N
is the uniform
-bit function ensemble.
Using techniques similar to those presented in the proof of Proposition 3.2.3 (in
Section 3.2.2), we can demonstrate the existence of pseudorandom function ensembles
that are not statistically close to the uniform one. However, to be of practical use, we
require that the pseudorandom functions can be efficiently computed. That is, functions
in the ensemble should have succinct representations that support both selecting them
and evaluating them. These aspects are captured by the following definition, in which
I
is an algorithm selecting representations of functions (which are associated to the
functions themselves by the mapping
φ
).
Definition 3.6.3 (Efficiently Computable Function Ensembles):
An
-bit func-
tion ensemble F
={
F
n
}
n
∈N
is called
efficiently computable
if the following two
conditions hold:
