Cryptography Reference
In-Depth Information
which may be identified with the single function
h
:
K
×
A
→
B
given by
h
(
k
,
x
)
=
h
k
(
x
)
. Thus we may define:
Definition 5.7
Let
h
={
h
k
:
A
→
B
}
k
∈
K
be a keyed hash function and
ε
a positive
real number. Then
h
is
ε
-
almost universal
if, for any
x
=
y
in
A
,Pr
(
h
k
(
x
)
=
h
k
(
y
))
≤
ε
, where
k
is randomly chosen in
K
.
Remarks 5.3
1. We will see later that in cryptography, fixed hash functions (which do not depend
on a key) are often used. However, to study them from the complexity-theoretic
point of view we have to look at keyed hash functions.
2. Observe that, if
I
=
(
Gen
,
Mac
,
Ve r
)
is a MAC with deterministic tag gener-
Mac
k
(
−
)
}
k
∈
K
is a keyed hash function with
which the MAC is often identified.
The idea behind the use of universal hash functions for message authentication
is to apply the hash function to the message and then to process the output obtained
by means of a pseudo-random function. Almost
ation algorithm, then the family
{
-universality was generalized by
Krawczyk [122] as follows (we may assume here, without loss of generality, that the
hash function maps binary strings to binary strings):
ε
Definition 5.8
Let
h
={
h
k
}
K
be a keyed hash function and
ε>
0. We say that
h
is
ε
-
almost Xor universal
if, for any
x
=
y
and any
a
, we have that Pr
(
h
k
(
x
)
⊕
h
k
(
y
)
=
a
)
≤
ε
for
k
randomly chosen.
-almost Xor universal hash function
h
may be used to construct a MAC
(calledUMAC) by defining the
Mac
algorithmas follows. Consider a pseudo-random
function
An
ε
{
f
k
}
K
and, for a message
m
, define:
Mac
k
(
m
)
=
h
k
(
m
)
⊕
f
k
(
r
),
where
r
is a nonce that must not be repeated over all tags computed with the key
k
.
Then Krawczyk proved that this MAC is secure in the sense that the probability of
success of a single forgery attempt in a chosen-message attack is no greater that
ε
.
5.5.1 GCM
We are going to exhibit an
-almost Xor universal hash function and to build a Maple
implementation of aMACbased on this function following the ideas explained above.
Actually, the construction is a little more complicated because the MAC is, in fact,
a scheme for authenticated encryption called GCM (an acronym for
Galois Counter
ε
