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= F#(r om) om Return c= 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= F#(r om) om Return c= 1. Write down the decryption algorithm. 2. Prove that the scheme is CPA secure by giving a security reduction