1.  (65  points)   Let F be a length-preserving PRF. For each of the following constructions, determine whether or not it is necessarily a PRF (don’t worry about whether or not the function is length preserving, it’s ok if it’s not). Prove your answers.

(a)  Fk(1)(x): If k = 0n  output 1n , else output Fk (x).

(b)  Fk(2)(x) = Fk (0||x)||Fk (1||x).

(c)  Fk(3)(x) = Fk (0||x)||Fk (x||1).

(d)  Fk(4)1 llk2 (x) = Fk1 (x) (where the key is parsed into two equal length parts k1 , k2 ).   (e)  Fk(5)(x1 ||x2 ) = Fk (x1 ) (where the input is parsed into two equal length parts x1 , x2 ).

Note: We omitted the length of inputs and outputs, but if it helps you understand how the functions are defined, note that for k ∈ {0, 1}n  we have Fk(1)   : {0, 1}n  → {0, 1}n , Fk(2)  : {0, 1}n-1  → {0, 1}2n , Fk(3)  : {0, 1}n-1  → {0, 1}2n , Fk(4)  : {0, 1}n/2  → {0, 1}n/2 , Fk(5)  : {0, 1}2n  → {0, 1}n .  Also note that in this problem you are not asked to differentiate between the case where the function can never be a PRF vs the case where it may or may not be:  in both these cases it is not necessarily a PRF, and you should answer no.

2.  (13  points)   Suppose you’re given a candidate block-cipher F which is length preserving, efficiently computable and invertible, and which satisfies the following property:  For all keys k ∈ {0, 1}n  and for any two inputs x, x/  ∈ {0, 1}n  that differ on exactly one bit, Fk (x) and Fk (x/ ) differ on 4 bits.

Determine whether (i) F must be a good block-cipher (if any good block-ciphers exist); (ii) F cannot a good block-cipher; or (iii) F may or may not be a good block-cipher (if any good block-ciphers exist). Prove your answer.

Note:  For the above, you can identify  “good block-cipher” with  “strong PRP”. You can think of F as defined for all n (and for simplicity we assumed length preserving, namely key length and block length are the same).

3.  (26 points)  Let F be a length preserving PRF. For each of the following MAC constructions, determine whether (i) it must be secure, (ii) can never be secure, or (iii) may or may not be secure (that is, if there exists any PRF, then there’s a PRF that makes the construction a secure MAC, and a PRF that makes the construction an insecure MAC). Prove your answers.

Here, “secure MAC” refers to the definition we gave in class (existential unforgeability against adaptive chosen message attack). The constructions below are all efficient and satisfy correctness (you don’t need to prove this part).