Cryptography Reference
In-Depth Information
implements the function) is not able to tell whether it is a random function or a PRF.
To make this idea more precise (in a mathematically strong sense), we consider an
experiment. Let
F
:
K
Y
be a PRF family that is publicly known. Imagine an
adversary who is locked up in a room with a computer system connected to another
computer system located somewhere outside the room (and out of sight). The outside
computer system implements a function
g
:
X
×
X
→
→
Y
that is either a random function
or an instance of
F
(and hence a PRF).
If
g
is a random function, then it is drawn at random from
Rand
X→Y
•
(i.e.,
r
←
Rand
X→Y
).
g
•
If
g
is a PRF, then it is drawn at random from the PRF family
F
, namely
g
r
←
r
←
F
. More specifically, a key
k
is chosen according to
k
K
and
g
is
then set to the instance
f
k
of the PRF family
F
.
In this setting, the adversary's job is to decide whether
g
is a random function
or an instance of the PRF family
F
. He or she can adaptively choose input values
x
Y
. If the PRF family
F
is good (bad), then the probability that the adversary can make a correct decision is
only negligibly (nonnegligibly) better than 1
/
2. Hence, the quality of a PRF family
can be measured by the difficulty of telling its instances apart from true random
functions.
To further formalize this idea, we must again make use of a
distinguisher
.
This time, however, the distinguisher is a PPT algorithm that has oracle access to
some function and that makes a decision whether this function is random or pseudo-
random. In the rest of this chapter, we use the term
D
g
to refer to a distinguisher
D
with oracle access to function
g
(be it a random function or an instance of a PRF
family). In either case, the output of
D
g
∈
X
and observe the corresponding output values
f
(
x
)
∈
is one bit. We then consider the following
two experiments:
1) Experiment Exp
Rand,D
f
r
←
Rand
X→Y
D
f
output
b
b
←
2) Experiment Exp
F,D
k
r
←
K
D
f
k
output
b
b
←
In Exp
Rand,D
, a (random) function
f
is randomly chosen from
Rand
X→Y
and the distinguisher
D
with oracle access to
f
returns bit
b
. This bit, in turn, is
D
's
