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
:
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