# 15.5: Exercises


##### Exercise $$15.1$$

Prove Claim 15.3.

##### Exercise $$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.

##### Exercise $$15.3$$

(a) Suppose you are given an ElGamal encryption of an unknown plaintext $$M \in \mathbb{G}$$. 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} \in \mathbb{G}$$. Show how to construct a ciphertext that decrypts to their product $$M_{1} \cdot M_{2}$$.

##### Exercise $$15.4$$

Suppose you obtain two ElGamal ciphertexts $$\left(B_{1}, C_{1}\right),\left(B_{2}, C_{2}\right)$$ 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 \cdot B_{2}$$ ?

(c) $$\star$$ What information can you infer about $$M_{1}$$ and $$M_{2}$$ if you observe that $$B_{1}=\left(B_{2}\right)^{2}$$ ?

This page titled 15.5: Exercises is shared under a CC BY-NC-SA 4.0 license and was authored, remixed, and/or curated by Mike Rosulek (Open Oregon State) .