Cryptography Reference
In-Depth Information
Definition 1.
Let
H
=
{
h
:
A
→
B
}
be a family of hash functions and let
≥
0
be a real number.
H
is said to be
-almost universal, denoted
-AU, if for all
distinct
M, M
∈
A
, we have that
Pr
h←H
[
h
(
M
)=
h
(
M
)]
is said to be
-almost universal on equal-length strings if for all distinct, equal-length strings
M, M
∈
≤
.
H
A
, we have that
Pr
h←H
[
h
(
M
)=
h
(
M
)]
≤
.
4
The Proposed
E
-MAC
4.1 Overview
Semantic security (or equivalently indistinguishability under chosen plaintext
attacks (IND-CPA) [24]) is the only assumption we make on the underlying
encryption algorithm. In fact, secure deterministic encryption algorithms suces
for our construction. However, since semantic security is a basic requirement in
most applications, we will assume the use of a semantically secure encryption.
As in fast MACs in the literature, the proposed
-MAC utilizes universal hash-
function families in the Wegman-Carter style [13, 49]. However, as opposed to
universal hash functions based MACs, we will show that
E
-MACs can be secure
without any post computation on the compressed image. (Recall that universal
hash functions based MACs have two rounds of computations: 1. message com-
pression using universal hash functions and, 2. output transformation, which in
most practical applications a pseudorandom function applied to the compressed
image [9, 27].) That is, as will be shown in the remaining of this section, the
structure of the authenticated encryption system can be utilized to eliminate the
need to employ pseudorandom function families. Thus, improving the speed of
the MAC and reducing the required amount of shared key information (the key
needed to identify the pseudorandom function).
Before we proceed with the detailed description of the proposed
E
E
-MAC, we
emphasize that the proposed universal hash family used for the implementation
of the proposed
-MAC is not the only possible solution. In fact, any
-almost-
Δ
-
universal (
-A
Δ
U) hash family, such as the
MMH
family of Halevi and Krawczyk
[26] and the
NH
family of Black
et al.
[9], will satisfy the security requirements
detailed in Section 5. (The
-A
Δ
U is a stronger notion than
-AU given in
Definition 1; interested readers may refer to [26] for a formal definition of
-
A
Δ
U hash families.)
Furthermore, different assumptions about the underlying encryption algo-
rithm may lead to different constructions of
E
-MACs. That is, whether the en-
cryption is a stream cipher, cipher block chaining (CBC) mode block cipher,
electronic code book (ECB) mode block cipher, etc., can have an impact on the
design and performance of the composition. We only show here how the seman-
tic security of the underlying encryption algorithm can be utilized to improve
the eciency and security of message authentication. Further improvements in
E
E
-MACs performance using specific modes of operations is left for a continuing
research in this direction.
Search WWH ::
Custom Search