Cryptography Reference
In-Depth Information
n
(where
k
is chosen uniformly at random on input 1
n
).
•
←{
,
}
Gen
:
k
0
1
•
(
,
)
:=
F
k
(
)
Mac
:
Mac
k
m
m
.
1f
F
k
(
m
)
=
t
•
Ve r
:
Ve r
(
k
,
m
,
t
)
:=
0 otherwise
.
In contrast with the case of encryption schemes, where an encryption algorithm
that is a deterministic function of the key and the message makes the scheme auto-
matically insecure, we have that
I
F
has a deterministic
Mac
algorithm and is, nev-
ertheless, UF-CMA secure:
Theorem 5.1
If F is a pseudo-random function, then
I
F
is a UF-CMA secure MAC.
Proof
The intuitive idea behind the proof is that forging a tag on a new message
requires the adversary to guess the value of the pseudo-random functionwhen applied
to that message. If the function were purely random then all the possible tag values
would be equally likely and, since we are applying the function to messages of
length
n
and
F
is length-preserving, there are 2
n
of these values, so the probability
of guessing the correct one would be 2
−
n
and hence negligible (since it decreases
exponentially). If
F
is pseudo-random instead of random, then a PPT algorithm can
distinguish it from a random function only with negligible probability and, because
of this, the adversary will have negligible advantage in the CMA authentication
unforgeability experiment. Thus the proof will follow the pattern established in the
proof of Theorem 4.1, namely, we will first show that the ideal MAC scheme based
on a random function is UF-CMA secure and then we will deduce from this fact that
I
F
is also UF-CMA secure.
Let us call, for simplicity,
I
=
I
F
and let
i
I
be the ideal MAC that is similar
n
instead of
F
.Asin
the proof of Theorem 4.1, this idealized scheme is not efficient and hence is not a
MAC in the strict sense but, for the purposes of this proof, this fact is irrelevant.
The adversary
n
to
I
but uses a truly random function
f
:{
0
,
1
}
→{
0
,
1
}
can query the oracle about the value of
f
on several messages
and then it has to guess the value
f
A
for a different message
m
. Since
f
is a
random function with 2
n
possible values, the probability that
(
m
)
A
guesses correctly or,
in other words, the advantage of
A
in the authentication unforgeability experiment
is
Adv
uf-cma
2
−
n
.
Next, in order to bound the advantage
Adv
uf-cma
A,
i
I
(
n
)
=
A
,
I
(
n
)
we construct a distinguisher
as a subroutine, tries to determine whether a given function
f
is
equal to some
F
k
for a randomly chosen key or is randomly chosen in
D
that, using
A
n
n
)
{
0
,
1
}
(
{
0
,
1
}
(see Definition 4.2) and we use the distinguisher advantage
Adv
prf
D
F
(
n
)
to obtain the
,
required bound.
D
runs as follows:
On input 1
n
,
D
is given oracle access to a function
f
n
n
which
•
:{
0
,
1
}
→{
0
,
1
}
n
or a random function.
is either
f
:=
F
k
for
k
←{
0
,
1
}
queries the oracle in the
Mac
uf-cma
on input 1
n
andwhen
•
A
A
A,I
(
)
D
runs
experiment
on a message
m
i
,
D
queries its own oracle
f
and returns the oracle's answer,
t
i
n
=
f
(
m
i
)
to
A
.
