Exercise 4.26. Let F : {0,1} {0,1} be a secure PRF, from n bit strings...

Transcribed Image Text:

Exercise 4.26. Let F : {0,1}” → {0,1}¹ be a secure PRF, from n bit strings to l<n bit strings. Define F' : {0,1}” → {0,1}¹ as: F/(m) = Fk(m) + Fk (m), i.e., concatenate the results of Fk applied to m and to the inverse of m. Present an efficient algorithm ADVF which demonstrates that F' is not a secure MAC, i.e., outputs tuple (x, t) s.t. x € {0,1}" and t = F(x). Algorithm ADVF may provide input m = {0,1}" and receive F(m), as long as x ‡ m. You can present ADVF by filling in the blanks' in the 'template' below, modifying and/or extending the template if desired, or simply write your own code if you like. ADVF : {t' = F/(_ Exercise 4.26, on page 259 of the textbook. Again, construct a distinguisher, compute P(DF%() = 1) and P(Dƒ() = 1), and show the difference between the two probabilities is large. Exercise 4.26. Let F : {0,1}” → {0,1}¹ be a secure PRF, from n bit strings to l<n bit strings. Define F' : {0,1}” → {0,1}¹ as: F/(m) = Fk(m) + Fk (m), i.e., concatenate the results of Fk applied to m and to the inverse of m. Present an efficient algorithm ADVF which demonstrates that F' is not a secure MAC, i.e., outputs tuple (x, t) s.t. x € {0,1}" and t = F(x). Algorithm ADVF may provide input m = {0,1}" and receive F(m), as long as x ‡ m. You can present ADVF by filling in the blanks' in the 'template' below, modifying and/or extending the template if desired, or simply write your own code if you like. ADVF : {t' = F/(_ Exercise 4.26, on page 259 of the textbook. Again, construct a distinguisher, compute P(DF%() = 1) and P(Dƒ() = 1), and show the difference between the two probabilities is large.