15.5: Exercises
- Page ID
- 86476
Prove Claim 15.3.
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.
(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}\).
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}\) ?