# 15.5: Exercises

$$\newcommand{\vecs}{\overset { \rightharpoonup} {\mathbf{#1}} }$$ $$\newcommand{\vecd}{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$$$\newcommand{\AA}{\unicode[.8,0]{x212B}}$$

##### 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) .