During Week 2 we built a PKE scheme which was secure assuming the DDH assumption. In this exercise, we will use the Lemma to build a PKE scheme for single bit messages from the CDH assumption. Recall that if you can solve CDH then you can solve DDH but it's not clear that the only way to solve DDH is to first solve CDH. This means that when you assume DDH you're also implicitly assuming CDH, and so a PKE assuming only CDH is an improvement. Here is the scheme: - Gen(): Choose a prime p, a generator gZp, and a random exponent x$, output (pk, sk )= (gx,x). - Enc(msg, pk): Parse msg {0,1} and pk=gxZp (we will use that every element of Zp can be parsed as a string in {0,1}log(p)). Draw y$, and r{0,1}log(p), and output ct=(gy,r,gxy,rmsg), where gxy,r is the string inner product, and gxy is computed as (gx)y. - Dec(ct, sk): Parse ct =(gy,r,L) where gyZp,r{0,1}log(p) and L{0,1}; also parse sk =x. Output Lgxy,r{0,1}, where gxy is computed as (gy)x. Problem 5. Do both of the following. (a) Prove correctness. (b) Show how to use an adversary which breaks the semantic security of the above scheme to complete the following "inner product prediction" challenge for CDH with probability 1/2+ for non-negligible >0 : given (p,g,gx,gy,r) return gxy,r. It can be shown (using the same argument that is used to prove the Lemma) that an adversary who completes this challenge with probability 1/2+ for non-negligible >0 can be used to design an adversary to solve CDH with non-negligible probability (you do not have to noow thic)