Skip to main content
Engineering LibreTexts

7.4: Exercises

  • Page ID
    7379
  • \( \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}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

    Exercise \(7.1\)

    Let \(\sum\) be an encryption scheme, and suppose there is a program \(\mathcal{A}\) that recovers the key from a chosen plaintext attack. More precisely, \(\operatorname{Pr}[\mathcal{A} \diamond \mathcal{L}\) outputs \(k]\) is non-negligible, where \(\mathcal{L}\) is defined as:

    fig-ch01_patchfile_01.jpg
    Figure \(\PageIndex{1}\): Copy and Paste Caption here. (Copyright; author via source)

    Prove that if such an \(\mathcal{A}\) exists, then \(\Sigma\) does not have CPA security. Use \(\mathcal{A}\) as a subroutine in a distinguisher that violates the CPA security definition.

    In other words, CPA security implies that it should be hard to determine the key from seeing encryptions of chosen plaintexts.

    Exercise \(7.2\)

    Let \(\Sigma\) be an encryption scheme with CPA$ security. Let \(\Sigma^{\prime}\) be the encryption scheme defined by:

    \[\Sigma^{\prime} \cdot \operatorname{Enc}(k, m)=00 \| \Sigma . \operatorname{Enc}(k, m)\]

    The decryption algorithm in \(\Sigma^{\prime}\) simply throws away the first two bits of the ciphertext and then calls \(\sum\). Dec.

    (a) Does \(\Sigma^{\prime}\) have CPA$ security? Prove or disprove (if disproving, show a distinguisher and calculate its advantage).

    (b) Does \(\Sigma^{\prime}\) have CPA security? Prove or disprove (if disproving, show a distinguisher and calculate its advantage).

    Exercise \(7.3\)

    Suppose a user is using Construction \(7.4\) and an adversary observes two ciphertexts that have the same \(r\) value.

    (a) What exactly does the adversary learn about the plaintexts in this case?

    (b) How do you reconcile this with the fact that in the proof of Claim \(7.5\) there is a hybrid where \(r\) values are never repeated?

    Exercise \(7.4\)

    Construction \(7.4\) is a randomized encryption scheme, but we could also consider defining it as a nonce-based scheme, interpreting \(r\) as the nonce: \(\operatorname{Enc}(k, r, m)=(r, F(k, r) \oplus m)\). Formally prove that it is secure as a deterministic, nonce-based scheme. In other words, show that the following two libraries are indistinguishable, where \(\Sigma\) refers to Construction \(7.4\).

    fig-ch01_patchfile_01.jpg
    Figure \(\PageIndex{1}\): Copy and Paste Caption here. (Copyright; author via source)
    Exercise \(7.5\)

    Let \(F\) be a secure PRP with blocklength blen \(=\lambda\). Consider the following randomized encryption scheme:

    fig-ch01_patchfile_01.jpg
    Figure \(\PageIndex{1}\): Copy and Paste Caption here. (Copyright; author via source)

    (a) Give the decryption algorithm for this scheme.

    (b) Prove that the scheme has CPA$ security.

    (c) Suppose that we interpret this scheme as a nonce-based scheme, where \(v\) is the nonce. Show that the scheme does not have nonce-based CPA security. The libraries for this definition are given in the previous problem.

    Note: Even in the standard CPA libraries, \(v\) is given to the adversary and it is unlikely to repeat. However, in the nonce-based libraries the adversary can choose \(v\), and this is what leads to problems.

    Exercise \(7.6\)

    Let \(F\) be a secure PRP with blocklength blen \(=\lambda\). Show the the following scheme has pseudorandom ciphertexts:

    fig-ch01_patchfile_01.jpg
    Figure \(\PageIndex{1}\): Copy and Paste Caption here. (Copyright; author via source)

    Hint:

    Exercise \(7.7\)

    Let \(F\) be a secure PRP with blocklength blen \(=\lambda\). Below are several encryption schemes, each with \(\mathcal{K}=\mathcal{M}=\{0,1\}^{\lambda}\) and \(C=\left(\{0,1\}^{\lambda}\right)^{2}\). For each one:

    • Give the corresponding Dec algorithm.
    • State whether the scheme has CPA security. (Assume KeyGen samples the key uniformly from \(\{0,1\}^{\lambda}\).) If so, then give a security proof. If not, then describe a successful adversary and compute its distinguishing bias.
    fig-ch01_patchfile_01.jpg
    Figure \(\PageIndex{1}\): Copy and Paste Caption here. (Copyright; author via source)

    Hint:

    Exercise \(7.8\)

    Suppose \(F\) is a secure PRP with blocklength \(n+\lambda\). Below is the encryption algorithm for a scheme that supports plaintext space \(\mathcal{M}=\{0,1\}^{n}\) :

    fig-ch01_patchfile_01.jpg
    Figure \(\PageIndex{1}\): Copy and Paste Caption here. (Copyright; author via source)

    (a) Describe the corresponding decryption algorithm.

    (b) Prove that the scheme satisfies CPA$ security.

    Exercise \(\star 7.9\)

    Suppose \(F\) is a secure PRP with blocklength \(\lambda\). Give the decryption algorithm for the following scheme and prove that it does not have CPA security:

    fig-ch01_patchfile_01.jpg
    Figure \(\PageIndex{1}\): Copy and Paste Caption here. (Copyright; author via source)
    Exercise \(\star 7.10\)

    Suppose \(F\) is a secure PRP with blocklength \(\lambda\). Give the decryption algorithm for the following scheme and prove that it satisfies CPA$ security:

    fig-ch01_patchfile_01.jpg
    Figure \(\PageIndex{1}\): Copy and Paste Caption here. (Copyright; author via source)

    Hint:

    Note: If \(r=0^{\lambda}\) then the scheme reduces to Exercise \(7.7\) (f). So it is important that \(r\) is secret and random.

    Exercise \(7.11\)

    Let \(\Sigma\) be an encryption scheme with plaintext space \(\mathcal{M}=\{0,1\}^{n}\) and ciphertext space \(C=\{0,1\}^{n}\). Prove that \(\Sigma\) cannot have CPA security.

    Conclude that direct application of a PRP to the plaintext is not a good choice for an encryption scheme.

    Exercise \(\star 7.12\)

    In all of the CPA-secure encryption schemes that we’ll ever see, ciphertexts are at least \(\lambda\) bits longer than plaintexts. This problem shows that such ciphertext expansion is essentially unavoidable for CPA security.

    Let \(\sum\) be an encryption scheme with plaintext space \(\mathcal{M}=\{0,1\}^{n}\) and ciphertext space \(C=\{0,1\}^{n+\ell}\). Show that there exists a distinguisher that distinguishes the two CPA libraries with advantage \(\Omega\left(1 / 2^{\ell}\right)\)

    Hint:

    Exercise \(7.13\)

    Show that an encryption scheme \(\Sigma\) has CPA security if and only if the following two libraries are indistinguishable:

    fig-ch01_patchfile_01.jpg
    Figure \(\PageIndex{1}\): Copy and Paste Caption here. (Copyright; author via source)

    In plain language: if these libraries are indistinguishable, then encryptions of chosen plaintexts are indistinguishable from encryptions of random plaintexts. You must prove both directions!

    Exercise \(7.14\)

    Let \(\Sigma_{1}\) and \(\Sigma_{2}\) be encryption schemes with \(\Sigma_{1} \cdot \mathcal{M}=\Sigma_{2} \cdot \mathcal{M}=\{0,1\}^{n}\).

    Consider the following approach for encrypting plaintext \(m \in\{0,1\}^{n}\) : First, secret-share \(m\) using any 2-out-of-2 secret-sharing scheme. Then encrypt one share under \(\Sigma_{1}\) and the other share under \(\Sigma_{2}\). Release both ciphertexts.

    (a) Formally describe the algorithms of this encryption method.

    (b) Prove that the scheme has CPA security if at least one of \(\left\{\Sigma_{1}, \Sigma_{2}\right\}\) has CPA security. In other words, it is not necessary that both \(\Sigma_{1}\) and \(\Sigma_{2}\) are secure. This involves proving two cases (assuming \(\Sigma_{1}\) is secure, and assuming \(\Sigma_{2}\) is secure).


    This page titled 7.4: 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) via source content that was edited to the style and standards of the LibreTexts platform; a detailed edit history is available upon request.