Cryptography Reference
In-Depth Information
h
)(
q
)). Thus, when given oracle access to
H
n
, machine
M
emulates an execution of
M
G
◦
H
n
(1
n
).
2.
On the other hand, when given oracle access to
f
s
, machine
M
emulates an
execution of
M
f
s
(1
n
) (the reason being that, in this case,
M
responds to query
q
(made by
M
) with
G
(
f
s
(
q
))
M
) with
G
(
h
(
q
))
(
G
◦
=
n
,
when given oracle access to
f
s
, machine
M
emulates an execution of
M
F
n
(1
n
).
=
f
s
(
q
)). Thus, for uniformly selected
s
∈{
0
,
1
}
Thus, if
M
violates the statement of the claim, then
M
violates the pseudoran-
domness of
{
f
s
}
, which contradicts what we have already established.
Combining Claims 3.6.11.1 and 3.6.11.2, the theorem follows.
Comment.
One major component of the proof of Theorem 3.6.11 is proving the fol-
lowing proposition:
}
|
s
|
}
s
∈{
0
,
1
}
∗
be a generalized pseudorandom function ensem-
ble, and let G
be as in the theorem's hypothesis. Then the generalized function ensemble
{
f
s
:
d
(
|
s
|
)
Let
{
{
0
,
1
}
→{
0
,
1
}
s
∈{
0
,
1
}
∗
, defined by f
s
(
x
)
def
d
(
|
s
|
)
r
(
|
s
|
)
G
(
f
s
(
x
))
, is pseudorandom.
f
s
:
{
0
,
1
}
→{
0
,
1
}
=
The proof of Claim 3.6.11.2 actually establishes this proposition and then applies it to
{
f
s
}
s
∈{
0
,
1
}
∗
as defined in Eq. (3.16).
3.6.4.2. Functions Defined on All Strings
Thus far we have considered only function ensembles in which each function is finite
(i.e., maps a finite domain to a finite range). Using such functions requires a priori
knowledge of an upper bound on the length of the inputs to which the function is
to be applied. (Shorter inputs can always be encoded as inputs of some longer and
predetermined length.) However, it is preferable not to require such a priori knowledge
of the upper bound (e.g., since such a requirement may rule out some applications).
It is thus useful to have a more flexible notion of a pseudorandom-function ensemble,
allowing application of individual functions to inputs of varying lengths not known a
priori. Such ensembles are defined and constructed next.
Definition 3.6.12 (Pseudorandom Function Ensembles with Unbounded
Inputs):
Let r
:
N → N
. We say that
}
∗
→{
r
(
|
s
|
)
{
f
s
:
{
0
,
1
0
,
1
}
}
s
∈{
0
,
1
}
∗
is an
efficiently computable unbounded-input pseudorandom function en-
semble
(unbounded-input pseudorandom function)
if the following two conditions
hold:
1.
Efficient evaluation:
There exists a polynomial-time algorithm that on input s and
x
}
∗
returns f
s
(
x
)
.
∈{
0
,
1
