Cryptography Reference
In-Depth Information
decision whether
f
is random or pseudorandom. In Exp
F,D
,akey
k
is randomly
chosen from
K
to fix a function
f
k
∈
F
, and the distinguisher
D
with oracle
access to
f
k
returns bit
b
. Again, this bit is
D
's decision whether
f
k
is random
or pseudorandom. Each experiment has a certain probability of returning 1. The
probabilities are taken over all random choices made in the experiments (i.e., in the
first experiment, the probability is taken over all choices of
f
and all internal random
choices of
D
f
, whereas in the second experiment, the probability is taken over all
choices of
k
and all internal random choices of
D
f
k
). To qualify a distinguisher
D
(with regard to its ability to distinguish between a random function and a PRF),
one looks at the difference between the two probabilities. Note that if
D
is a good
distinguisher, then it returns 1 more often in one experiment than in the other.
Consequently, the
prf-advantage
of
D
for
F
can be defined as followed:
Adv
prf
F,D
=Pr[Exp
F,D
=1]
−
Pr[Exp
Rand,D
=1]
It goes without saying that different distinguishers may have different prf-
advantages. For example, one distinguisher may achieve a greater prf-advantage
than another simply by asking more or more intelligent questions or by using a
better strategy to process the replies. Also, it is reasonable to assume that the more
input-output examples that can be observed, the better the ability to tell the two
types of functions apart. Consequently, the quality of a function family
F
must also
be measured as a function of the resources allowed to a distinguisher. For any given
resource limitation, we may be interested in the prf-advantage achieved by the best
(i.e., most intelligent) distinguisher (among all distinguishers that are restricted to
the given resource limitations). We associate to
F
a prf-advantage that on input of
any values of the resource parameters returns the maximum prf-advantage that an
adversary restricted to these resources is able to obtain. Consequently, for any given
t
,
q
,and
µ
,wedefinethe
prf-advantage
of
F
as
Adv
prf
F
Adv
prf
F,D
(
t, q, µ
)=max
D
{
}
where the maximum is taken over all
D
having time complexity
t
and making at
most
q
oracle queries, the sum of the lengths of these queries being at most
µ
bits.
The main reason for using the prf-advantage of
F
as a measure for the quality of
F
is that it does not specify anything about the kinds of strategies that can be used
by a distinguisher. In fact, it can do anything as long as it stays within the specified
resource bounds.
So far, we have only assigned a prf-advantage to a function family
F
.Wehave
neither specified the requirements for
F
to be a PRF family, nor have we said what
