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

afield,foran r drawn uniformly at random from Z p , the resulting ( k B r mod p )

is uniformly distributed over Z p . Consequently, for any plaintext message M ,

since the tag is a result of adding ( k B r mod p )to( i k i m i mod p ), and since
( k B r mod p ) is uniformly distributed over

Z p , the resulting tag is uniformly

Z p . That is, for any fixed value τ ∈ Z p , the probability that the

distributed over

tag will take this specific value is given by:

= τ )= 1 Pr( τ

p .

(16)

Combining Bayes' theorem [25] with equations (15) and (16) yields:

= τ )= Pr(

τ = τ | M = M )Pr( M = M )

Pr( M = M | τ =Pr( M = M ) . (17)

Pr( τ = τ )

Equation (17) implies that the tag τ gives no information about the plaintext
M since τ is statistically independent of M . Similarly, one can show that the
tag is independent of the secret key.
Now, let τ 1 through τ represent the tags for messages M 1 through M ,re-
spectively. Further, let r 1 through r be the coin tosses of the signing algorithm
S for the authentication of messages M 1 through M , respectively. Recall that

r i 's are mutually independent and uniformly distributed over Z p . Then, for any

possible values of the messages M 1 through M with arbitrary joint probability
mass function, and all possible values of τ 1 through τ ,weget:

Pr( τ 1 = τ 1 , ··· , τ = τ )= Pr( τ 1 = τ 1 , ··· , τ = τ | M 1 = M 1 , ··· , M = M )

M 1 ,··· ,M

Pr( M 1 = M 1 , ··· , M = M )

Pr

B− 1 B− 1

k i m 1 i ) k − B , ··· , r =( τ − k i m i ) k − 1

= r 1 =( τ 1 −

B

M 1 ,··· ,M i =1 i =1

Pr( M 1 = M 1 , ··· , M = M ) (18)

Pr ··· Pr

B− 1 B− 1

k i m 1 i ) k − 1 k i m i ) k − 1 = r 1 =( τ 1 − r =( τ −

B B

M 1 ,··· ,M i =1 i =1

Pr( M 1 = M 1 , ··· , M = M ) (19)

1
p ···

1
p

= Pr( M 1 = M 1 , ··· , M = M ) (20)

M 1 ,··· ,M

=Pr( τ 1 = τ 1 ) ··· Pr( τ = τ ) , (21)

denotes the i th block of the j th where m j i message M j . Equation (19) holds

due to the independence of the r i 's; equation (20) holds due to the uniform

distribution of the r i 's; and equation (21) holds due to the uniform distribution

of the τ i 's. Therefore, authentication tags are mutually independent, and the

lemma follows.