# 7.4: 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 $$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: 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$$. 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: Figure $$\PageIndex{1}$$: Copy and Paste Caption here. (Copyright; author via source)

(a) Give the decryption algorithm for this scheme.

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