# Exercises

- Page ID
- 7415

15.1: Prove __Claim 15.3__

15.2: Show that a 2-message key-agreement protocol exists if and only if CPA-secure public-key encryption exists.

In other words, show how to construct a CPA-secure encryption scheme from any 2- message KA protocol, and vice-versa. Prove the security of your constructions.

15.3: (a). Suppose you are given an ElGamal encryption of an unknown plaintext *M* ∈ ?. Show how to construct a different ciphertext that also decrypts to the same *M*.

(b). Suppose you are given two ElGamal encryptions, of unknown plaintexts *M*_{1},*M*_{2} ∈ ?. Show how to construct a ciphertext that decrypts to their product *M*_{1} · *M*_{2}.

15.4: Suppose you obtain two ElGamal ciphertexts (*B*_{1},*C*_{1}), (*B*_{2},*C*_{2}) that encrypt unknown plaintexts *M*_{1} and *M*_{2}. Suppose you also know the public key *A* and cyclic group generator *g*.

(a). What information can you infer about *M*_{1} and *M*_{2} if you observe that *B*_{1} = *B*_{2}?

(b). What information can you infer about *M*_{1} and *M*_{2} if you observe that *B*_{1} = g · *B*_{2}?

(c). What information can you infer about *M*_{1} and *M*_{2} if you observe that *B*_{1} = (*B*_{2})^{2}?