Cryptography Reference
In-Depth Information
2.
Construct a real scheme by replacing the random function by a pseudorandom func-
tion. Namely, the legitimate users will share a random/secret seed specifying such a
pseudorandom function, whereas the adversaries will not know the seed. As before, the
adversaries can, at most, obtain (from the legitimate users) the values of the function
at arguments of their choice. Finally, conclude that the real scheme (as presented here)
is secure (since otherwise one could distinguish a pseudorandom function from a truly
random one).
We stress that this methodology can be applied only if the legitimate users can share
random/secret information not known to the adversary (e.g., as is the case in private-key
encryption schemes).
7
3.6.4.
∗
Generalizations
We present generalizations of the notion of a pseudorandom function, first to the case
where the function is not length-preserving, and then to the case where the function
is defined over the set of all strings. These generalizations offer greater flexibility in
using pseudorandom functions in applications.
3.6.4.1. Functions That Are Not Length-Preserving
Departing from Definition 3.6.4, we present the following generalization of the notion
of a pseudorandom function ensemble.
Definition 3.6.9 (Pseudorandom Function Ensembles, Generalization):
Let
d
,
r
:
N → N
. We say that
f
s
:
r
(
|
s
|
)
s
∈{
0
,
1
}
∗
d
(
|
s
|
)
{
0
,
1
}
→{
0
,
1
}
is an
efficiently computable generalized pseudorandom function ensemble
(generalized pseudorandom function)
if the following two conditions hold:
1.
Efficient evaluation:
There exists a polynomial-time algorithm that on input s and
x
d
(
|
s
|
)
returns f
s
(
x
)
.
2.
Pseudorandomness:
For every probabilistic polynomial-time oracle machine M ,
every polynomial p
(
∈{
0
,
1
}
·
)
, and all sufficiently large n's,
Pr
M
F
n
(1
n
)
1
M
H
n
(1
n
)
1
<
1
p
(
n
)
=
− Pr
=
where F
n
is a random variable uniformly distributed over the multi-set
n
,
and H
n
is uniformly distributed among all functions mapping d
(
n
)
-bit-long strings
to r
(
n
)
-bit-long strings.
{
f
s
}
s
∈{
0
,
1
}
7
In contrast, the
Random Oracle Methodology
refers to a situation in which the adversary is also given the
description of the function, which replaces the random oracle to which it has
direct
access (as discussed in
footnote 6 ). We warn that, in contrast to the methodology presented here, the Random Oracle Methodology is a
heuristic. See further discussion in Section 3.8.2.
