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

a cryptographic point of view, it is safe to assume that no information about the
r 's will be revealed.
This shows how -MACs can take advantage of the E & A structure to improve

authentication eciency and satisfy their secrecy requirement. All that is needed
is to generate a random string, append it to the encrypted plaintext message, and
use it to encrypt the authentication tag. Therefore, as claimed earlier, no post-
processing of the compressed image is required and the secrecy requirement of
E

E

-MACs can be achieved, without expensive computational effort. This result is
not surprising. In fact, it supports the main motive behind this work, namely the
intuition that post-processing the compressed image by a cryptographic function
can be replaced by computations performed by the encryption algorithm (i.e.,
post-processing is redundant in such compositions).

We will now state the main theorem regarding the probability of successful
forgery against the proposed

E -MAC.

Theorem 2. Let Σ denotes the proposed be an adversary

making a ( q s ,q v ) -attack on Σ . Given the semantic security of the underlying
encryption scheme,

E -MAC and let A

A 's advantage of successful forgery is at most

⎧
⎨

q v
p

if q s =0

Adv Σ
A

= (3)

⎩

q v
p −

if q s > 0 .

1

Proof. From the proof of Lemma 3 (equation (16)), the tag is uniformly dis-
tributed over

Z p . Hence, if the adversary makes no signing queries, the proba-
bility of forging a valid tag is 1 /p .
Assume that the adversary has queried the signing oracle S ( K, · )for q s times

and recorded ( M 1 ,τ 1 ) , , ( M q s ,τ q s ). By Theorem 1, given the semantic security

of the encryption algorithm, no information about the

···

E -MAC's secret key is

revealed by the observed τ i 's.
Now, consider calling the query

( K, M ,τ ), where M and τ are any message-
tag pair of the adversary's choice. We aim to bound the probability of successful
forgery for an M that has not been queried to the signing oracle; that is, M

V

= M i

for any i =1 , ,q s . We break the proof into two cases: queried tag and unqueried

tag. For ease of notations, r i will be denoted as the B th block of the i th message,
that is, r i = m i B .

···

Queried tag ( M ,τ = τ q ): Assume that τ = τ q for a q .This

case represents the event that a collision in the hashing operation occurs. Then,
V

∈{ 1 , ··· ,q s }

( k, M ,τ ) = 1 if and only if the following holds:

B B

?
≡

k m τ ≡

τ q ≡ k m mod p, (4)

=1 =1