Cryptography Reference
In-Depth Information
Clearly,
r
:
must be upper-bounded by a polynomial. Definition 3.6.4 is ob-
tained as a special case (of Definition 3.6.9) by letting the functions
d
and
r
equal
the function
N → N
, where
r
(
n
)is
computable in poly(
n
) time from
n
, we can construct general pseudorandom functions
using any pseudorandom generator. Specifically:
. Similarly to Construction 3.6.5, for any
d
,
r
:
N → N
Construction 3.6.10:
Let G, G
0
, and G
1
be as in Construction 3.6.5. Let
d
,
r
:
N → N
, and let G
be a deterministic algorithm mapping n-bit-long in-
puts into r
(
n
)
-bit outputs. Then for every s
∈{
0
,
1
}
n
, we define a function f
s
:
{
0
,
1
}
d
(
n
)
→{
0
,
1
}
r
(
n
)
such that for every
σ
1
,...,σ
d
(
n
)
∈{
0
,
1
}
,
f
s
σ
1
σ
2
···
σ
d
(
n
)
def
=
G
G
σ
d
(
n
)
···
G
σ
2
G
σ
1
(
s
)
···
Construction 3.6.5 is regained from Construction 3.6.10 by letting
d
(
n
)
=
n
and using the identity function in the role of
G
. By extending the proof of
Theorem 3.6.6, we obtain the following:
=
r
(
n
)
Theorem 3.6.11:
Let G, G
, and the f
s
's be as in Construction 3.6.10, and sup-
pose that G is a pseudorandom generator. Further suppose that G
is polynomial-
time-computable and that the ensemble
G
(
U
n
)
{
}
n
∈N
is pseudorandom,
8
as de-
fined in Definition 3.2.8. Then
f
s
}
s
∈{
0
,
1
}
∗
is an efficiently computable ensemble
of generalized pseudorandom functions.
{
Proof:
In case
G
is the identity transformation (and
r
(
n
)
=
n
), the proof is almost
identical to the proof of Theorem 3.6.6. To deal with the general case, we use a
hybrid argument. Specifically, we use a
single
intermediate
hybrid
(i.e., a single
hybrid of the function ensemble
{
f
s
}
and a truly random function): For every
n
,
we consider the (random) function
g
:
{
0
,
1
}
d
(
n
)
→{
0
,
1
}
r
(
n
)
defined by letting
=
G
(
h
(
x
)), where
h
is uniformly selected among all functions mapping
d
(
n
)-bit-long strings to
n
-bit strings. The theorem follows by showing that this
hybrid ensemble is indistinguishable from both the uniform function ensemble
and the function ensemble of Construction 3.6.10.
In the following, we denote by
H
n
(resp.,
H
n
) a random variable uniformly dis-
tributed over the set of all functions mapping
d
(
n
)-bit-long strings to
r
(
n
)-bit-long
(resp.,
n
-bit-long) strings. Recall that the hybrid distribution, denoted
G
◦
g
(
x
)
H
n
,is
obtained by functional composition of the fixed function
G
and the random func-
tion distribution
H
n
. As usual,
F
n
denotes a random variable uniformly distributed
over the multi-set
{
f
s
}
s
∈{
0
,
1
}
n
.
Claim 3.6.11.1:
For every probabilistic polynomial-time oracle machine
M
,
every polynomial
p
(
·
), and all sufficiently large
n
's,
Pr
M
G
◦
H
n
(1
n
)
1
M
H
n
(1
n
)
1
<
1
p
(
n
)
−
Pr
=
=
8
In case
r
(
n
)
n
(for all
n
's), what we require is that
G
be a pseudorandom generator. But otherwise this
cannot be required, since
G
is not expanding. Still, the other features of a pseudorandom generator (i.e., efficient
computability and pseudorandomness of the output) are always required here.
>
