15.5: Exercises

$$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$ $$\newcommand{\vecd}[1]{\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]{\| #1 \|}$$ $$\newcommand{\inner}[2]{\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]{\| #1 \|}$$ $$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

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 M1,M2 ∈ ?. Show how to construct a ciphertext that decrypts to their product M1 · M2.

15.4: Suppose you obtain two ElGamal ciphertexts (B1,C1), (B2,C2) that encrypt unknown plaintexts M1 and M2. Suppose you also know the public key A and cyclic group generator g.

(a). What information can you infer about M1 and M2 if you observe that B1 = B2?

(b). What information can you infer about M1 and M2 if you observe that B1 = g · B2?

(c). What information can you infer about M1 and M2 if you observe that B1 = (B2)2?

15.5: Exercises is shared under a CC BY-NC-SA 4.0 license and was authored, remixed, and/or curated by Mike Rosulek.