E-MACs: Towards More Secure and More Efficient Constructions of Secure Channels - Information Security and Cryptology-ICISC 2010 - page 298

4.2 Description

Instantiation. Fix an encryption primitive that is semantically secure. Based

on a security parameter N , legitimate users agree on an N -bit long prime integer
p .Let K =( k 1 ,k 2 ,...,k B ), for k i 's drawn uniformly and independently from
Z p , be the shared secret key that will be used for message authentication. As in
typical universal hash functions, depending on the values of N and B ,thekey
can be long. One way to generate such a key is via a pseudorandom generator,
e.g., [10, 28]. In such a case, only the seed of the pseudorandom generator is
required to be distributed to the legitimate parties. As in symmetric-key cryp-
tographic systems, the shared secret is distributed to the legitimate users via a
secure channel. With the knowledge of the shared secret, legitimate users can
exchange subsequent messages, over insecure channels, in an authenticated and
confidential way. (Observe that the encryption key K E in our setup is indepen-
dent of the authentication key K .) Only the shared keys are assumed to be
secret; all other parameters such as N , B ,and p are publicly known.

E

Authentication. Without loss of generality, we assume the message can be
divided into B -1 blocks of length N -bits, that is M = m 1 || m B− 1 .(We

overload m i to denote both the binary string in the i th block and the integer
representation of the i th block as an element of Z p ; the distinction between the
two representations will be omitted when it is clear from the context.) For ev-
ery message M to be encrypted and authenticated, the sender draws an integer
r uniformly at random from

m 2 || ... ||

Z p anew for each message (this r represents the

coin tosses of ). We emphasize that r must be independent of all r 's gener-

ated to authenticate other messages. The sender encrypts M

S

|| r and transmits

the resulting ciphertext c = ” denotes

the concatenation operation), along with the the N -bit long tag of message M
computed as:

E ( M || r ) to the receiver (the symbol “ ||

B− 1

τ = k i m i + k B r mod p, (1)

i =1

where m i denotes the i th block of message M .

Remark 1. A misconception about universal hash-function families is that the
authentication key needs to be as long as the longest message to be authenti-
cated. Obviously, if this was true, universal hashing will be impractical for most
applications. In the literature, there exist standard techniques to hash arbitrary-
length messages using a fixed-length key. The first such technique was proposed
by Wegman and Carter in [50], and later refined by Halevi and Krawczyk in [26].
The work of Black et al. [9] provides a different generic algorithm to transform
any hash function that is -AU on equal-length messages, h , to a hash function
that is -AU on arbitrary-length messages, h ∗ . However, for a lack of space and
for a better continuity of the main ideas of the paper, we omit going into the
details of such techniques. (Interested readers may refer to [9, 26, 50] for more