Exercise 2. CPA Encryption [20 points] In this question you will break CPA security of two encryption schemes (the first build with PRGs and the second build with PRFs). 1. State the CPA security game. Consider the following encryption scheme: Let G() : {0,1} {0,1} be a secure PRG. Gen (1) Output a key k of size n bits selected uniformly at random from {0,1}n Enc(k, m) : c = m + G(k) + 1|2n| (where 1n is a string of all 1's of size n) Dec(k, c) m = c +G(k) + 1|2n| Show that the above construction is not CPA-secure. 1. Describe an adversary that can break CPA security of above construction. 2. Explicitly state the probability of success of this adversary. Now consider another construction: Let F be a fixed-length PRF. Gen (1) k{0,1}n : Enc(k, m) F(On) + m Dec(k, c) Fk (0) + c Show that the above construction is not CPA-secure. 1. Describe an adversary that can break CPA security of the above construction. 2. Explicitly state the probability of success of this adversary.