(a) Let K1 = {0, 1}n+1. Construct a new PRF F1, defined over (K1, X , Y), with the following property: the PRF F1 is secure; however, if the adversary learns the last bit of the key then the PRF is no longer secure. This shows that leaking even a single bit of the secret key can completely destroy the PRF security property.

Hint: Let k1 = k k b where k 2 {0, 1}n and b 2 {0, 1}. Set F1(k1, x) to be the same as F(k, x) for all x 6= 0n. Define F1(k1, 0n) so that F1 is a secure PRF, but becomes easily distinguishable from a random function if the last bit of the secret key k1 is known to the adversary.

(b) Construct a new PRF F2, defined over (K K, X , Y), that remains secure if the attacker learns any single bit of the key. Your function F2 may only call F once