Only answer part a Exercise 1. Pseudorandom Functions [40 points] Let Fk {0,1} {0, 1} be a

Only answer part a  

Transcribed Image Text:

Exercise 1. Pseudorandom Functions [40 points] Let Fk {0,1}" {0, 1}" be a pseudorandom function. For each of the functions below you will have to show that it is NOT a PRF,i.e., give an attack and a justification for why your attacker/distinguisher can distinguish whether it is talking to a pseudorandom function or a truly random function with probability 1/2 + p(n) where p(n) is a non-negligible value. a. (20 points) Show that F(x) = Fk(0||x)||Fk(x||1), where || denotes string con- catenation, is NOT a PRF. b. (20 points) Show that F(x) = F(x) Fk() is NOT a PRF. The bar notation, x, denotes inversion of the string, i.e. if x = 01101, then x = 10010. Exercise 1. Pseudorandom Functions [40 points] Let Fk {0,1}" {0, 1}" be a pseudorandom function. For each of the functions below you will have to show that it is NOT a PRF,i.e., give an attack and a justification for why your attacker/distinguisher can distinguish whether it is talking to a pseudorandom function or a truly random function with probability 1/2 + p(n) where p(n) is a non-negligible value. a. (20 points) Show that F(x) = Fk(0||x)||Fk(x||1), where || denotes string con- catenation, is NOT a PRF. b. (20 points) Show that F(x) = F(x) Fk() is NOT a PRF. The bar notation, x, denotes inversion of the string, i.e. if x = 01101, then x = 10010.