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}}\)
\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)
\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)
\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vectorC}[1]{\textbf{#1}} \)
\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)
\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)
\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)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:
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.
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).
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?
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\).
Let \(F\) be a secure PRP with blocklength blen \(=\lambda\). Consider the following randomized encryption scheme:
(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.
Let \(F\) be a secure PRP with blocklength blen \(=\lambda\). Show the the following scheme has pseudorandom ciphertexts:
Hint:
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.
Hint:
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}\) :
(a) Describe the corresponding decryption algorithm.
(b) Prove that the scheme satisfies CPA$ security.
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:
Suppose \(F\) is a secure PRP with blocklength \(\lambda\). Give the decryption algorithm for the following scheme and prove that it satisfies CPA$ security:
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.
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.
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:
Show that an encryption scheme \(\Sigma\) has CPA security if and only if the following two libraries are indistinguishable:
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!
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).