Exercise 3. Proving CPA Encryption [20 points] Let F: {0, 1}" x {0,1}" + {0, 1}" be a secure PRP (key, input and output size are all n bits). Consider the following encryption scheme: Gen(1") : Output a key k of size n bits selected uniformly at random from {0,1}" Enc(k, m) : Pick r uniformly at random from {0,1}" Set a = Fk(r om) em Return c= r, a > 1. Write down the decryption algorithm. 2. Prove that the scheme is CPA secure by giving a security reduction. Exercise 3. Proving CPA Encryption [20 points] Let F: {0, 1}" x {0,1}" + {0, 1}" be a secure PRP (key, input and output size are all n bits). Consider the following encryption scheme: Gen(1") : Output a key k of size n bits selected uniformly at random from {0,1}" Enc(k, m) : Pick r uniformly at random from {0,1}" Set a = Fk(r om) em Return c= r, a > 1. Write down the decryption algorithm. 2. Prove that the scheme is CPA secure by giving a security reduction