Cryptography Reference
In-Depth Information
3 Preliminaries
A message authentication scheme consists of a signing algorithm
S
and a verify-
ing algorithm
. The signing algorithm might be probabilistic, while the verifying
one is usually not. Associated with the scheme are parameters
and
N
describing
the length of the shared key and the resulting authentication tag, respectively.
On input an
-bit key
K
and a message
M
, algorithm
V
outputs an
N
-bit string
τ
called the authentication tag, or the MAC of
M
. On input an
-bit key
K
,
a message
M
,andan
N
-bit tag
τ
, algorithm
S
outputs a bit, with 1 standing
for accept and 0 for reject. We ask for a basic validity condition, namely that
authentic tags are accepted with probability one. That is, if
τ
=
V
S
(
K, M
), it
must be the case that
(
K, M, τ
) = 1 for any
K
,
M
,and
τ
.
In general, an adversary in a message authentication scheme is a probabilistic
algorithm
V
A
, which is given oracle access to the signing and verifying algorithms
S
(
K,
·
)and
V
(
K,
·
,
·
) for a random but hidden choice of
K
.
A
can query
S
to
generate a tag for a plaintext of its choice and ask the verifier
V
to verify that
τ
is a valid tag for the plaintext. Formally,
A
's attack on the scheme is described
by the following experiment:
1. A random string of length
is selected as the shared secret.
2. Suppose
makes a signing query on a message
M
. Then the oracle computes
an authentication tag
τ
=
A
may be
probabilistic, this step requires making the necessary underlying choice of a
random string for
S
(
K, M
) and returns it to
A
. (Since
S
S
, anew for each signing query.)
3. Suppose
A
makes a verify query (
M, τ
). The oracle returns the decision
d
=
V
(
K, M, τ
)to
A
.
The adversary's attack is a (
q
s
,q
v
)-attack if during the course of the attack
A
makes no more than
q
s
signing queries and no more than
q
v
verify queries. The
outcome of running the experiment in the presence of an adversary is used to
define security. As in [5], we say that the MAC algorithm is weakly unforgeable
against chosen-message attacks (WUF-CMA) if
A
cannot make a verify query
(
M, τ
) which is accepted for an
M
that has not been queried to the signing
oracle
S
. We say that the MAC algorithm is strongly unforgeable against chosen-
message attacks (SUF-CMA) if
A
cannot make a verify query (
M, τ
)whichis
accepted regardless of whether or not
M
is
new
,aslongasthetaghasnotbeen
attached to the message by the signing oracle.
As in fast MACs, the proposed
E
-MAC is based on universal hash-function
families. A family of hash functions
H
is specified by a finite set of keys
K
.Each
key
k
∈K
defines a member of the family
H
k
∈H
. As opposed to thinking
of
H
as a set of functions from
A
to
B
, it can be viewed as a single function
H
B
, whose first argument is usually written as a subscript. A
random element
h
:
K×
A
→
∈H
is determined by selecting a
k
∈K
uniformly at random
and setting
h
=
H
k
.
There has been a number of different definitions of universal hash families
(see, e.g., [13, 26, 36, 37, 44, 47, 49]). We give below a formal definition of one
class of universal hash families called
-almost universal [9].
Search WWH ::
Custom Search