# Cryp

1815 words 8 pages
Homework 5
4.2 Consider a "CCA-type" extension of the deﬁnition of secure message authentication codes where the adversary is provided with both a Mac and Vrfy oracle. (a) Provide a formal deﬁnition and explain why such a notion may make sense. (b) Show that when the Mac scheme is deterministic, your deﬁnition is equivalent to Definition 4.2. (c) Show that when the Mac scheme may be probabilistic, the deﬁnitions are not equivalent. (That is, show that there exists a probabilistic scheme that is secure by Deﬁnition 4.2 but not by your deﬁnition.) Consideration The message authentication experiment Mac-forge, Π(n):

1. A random key k ← {0, 1}n is chosen. 2. The adversary is given oracle access to Mack (·) and Vrfyk (·, ·) and outputs a
…show more content…
. , t d ), output (r, ⊕d=1 t i ) What is the advantage of this i modiﬁcation? (This is a more challenging modiﬁcation to prove.) The book has concluded that Construction 4.5 completely relies on the pseudorandom function to yield existentially unforgeability, i.e., Pr Mac-forge

= 1 = Pr D Fk (·) (1n ) = 1 .

Said ﬁxed-length MAC scheme should also achieve existentially unforgeability. That being said, no PPT adversary can successfully tell the corresponding tag for any speciﬁc message with signiﬁcant probability. This is exactly how a pseudorandom function works. So using any ﬁxedlength MAC or a pseudorandom function are equivalent. For the second modiﬁcation think of rewriting the statements in the second case of the proof on the book. Remember that we have two messages m = m . If there exists a j such that b j = b j = 1, then m and m should be of the same length. In this case the message content of one of the blocks must be different (or m = m ); let i denote the index of the different block. This means that the function f n was never applied to a block with content (r, {0, 1}, i , m i ) during Mac-forge, with Π, and so a d v can succeed in guessing t i with probability at most 2−n . If there does not exist such j , that means m and m are of different length. In this case, the function f n was never applied to the block with content (r, 1, d , m d ) (where d donates the number of blocks of m ). As above, this means that can succeed with probability at most 2−n