Show that any two-round key exchange protocol satisfying Def. 10.1 can be converted into a CPA-secure public
Question:
Show that any two-round key exchange protocol satisfying Def. 10.1 can be converted into a CPA-secure public key encryption scheme. (ii) (15 pts) Consider the following public-key encryption scheme. The public key is (G, q, g, h = g x ), and the private key is x (generated the same way as in the El Gamal encryption scheme). In order to encrypt a bit b, the sender does the following:
• If b=0, choose uniform y ∈ Zq and compute c1 = g y and c2 = h y . Set the ciphertext to be (c1, c2).
• If b = 1, choose independent and uniform y, z ∈ Zq, and compute c1 = g y and c2 = g z . Set the ciphertext to be (c1, c2).
(a) Show that it is possible to decrypt efficiently, given knowledge of x.
(b) Prove that this encryption scheme is CPA secure if the decisional Diffie-Hellman problem is hard relative to the group G.