Skip to main content
Engineering LibreTexts

15.5: Exercises

  • Page ID
    7415
  • \( \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.

    • Was this article helpful?