Homework 5
4.2 Consider a "CCA-type" extension of the definition of secure message authentication codes where the adversary is provided with both a Mac and Vrfy oracle. (a) Provide a formal definition and explain why such a notion may make sense. (b) Show that when the Mac scheme is deterministic, your definition is equivalent to Definition 4.2. (c) Show that when the Mac scheme may be probabilistic, the definitions are not equivalent. (That is, show that there exists a probabilistic scheme that is secure by Definition 4.2 but not by your definition.) 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 modification? (This is a more challenging modification 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 fixed-length MAC scheme should also achieve existentially unforgeability. That being said, no PPT adversary can successfully tell the corresponding tag for any specific message with significant probability. This is exactly how a pseudorandom function works. So using any fixedlength MAC or a pseudorandom function are equivalent. For the second modification 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