# 5.6: Exercise

$$\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}$$
##### Exercise $$5.1$$

Let $$G:\{0,1\}^{\lambda} \rightarrow\{0,1\}^{\lambda+\ell}$$ be an injective (i.e., 1-to-1) PRG. Consider the following distinguisher:

1. What is the advantage of $$\mathcal{A}$$ in distinguishing $$\mathcal{L}_{\mathrm{prg}-\mathrm{real}}^{G}$$ and $$\mathcal{L}_{\mathrm{prg}-\mathrm{rand}}^{G}$$ ? Is it negligible?
2. Does this contradict the fact that $$G$$ is a PRG? Why or why not?
3. What happens to the advantage if $$G$$ is not injective?
##### Exercise $$5.2$$

Let $$G:\{0,1\}^{\lambda} \rightarrow\{0,1\}^{\lambda+\ell}$$ be an injective $$P R G$$, and consider the following distinguisher:

What is the advantage of $$\mathcal{A}$$ in distinguishing $$\mathcal{L}_{\mathrm{prg}-\mathrm{real}}^{G}$$ from $$\mathcal{L}_{\mathrm{prg}-\mathrm{rand}}^{G} ?$$

Hint:

When computing $$\textrm{Pr}\left [ \mathcal{A} \diamond \mathcal{L}_{\mathrm{prg}-\mathrm{rand}}^{G}\text{ output 1}\right]$$, separate the probabilities based on whether $$x$$ is a possible output of $$G$$ or not.

##### Exercise $$5.3$$

For any PRG $$G:\{0,1\}^{\lambda} \rightarrow\{0,1\}^{\lambda+\ell}$$ there will be many strings in $$\{0,1\}^{\lambda+\ell}$$ that are impossible to get as output of $$G$$. Let $$S$$ be any such set of impossible $$G$$-outputs, and consider the following adversary that has $$S$$ hard-coded:

What is the advantage of $$\mathcal{A}$$ in distinguishing $$\mathcal{L}_{\text {prg-real }}^{G}$$ from $$\mathcal{L}_{\text {prg-rand }}^{G}$$ ? Why does an adversary like this one not automatically break every PRG?

##### Exercise $$5.4$$

Show that the scheme from Section $$5.3$$ does not have perfect one-time secrecy, by showing that there must exist two messages $$m_{1}$$ and $$m_{2}$$ whose ciphertext distributions differ.

Hint:

There must exist strings $$s_{1},s_{2}\in \left \{ {\color{Red} 0,1} \right \}^{\lambda +\ell}$$ where $$s_{1}\in \textrm{im}\left ( G \right )$$, and $$s_{2} \notin \textrm{im}\left ( G \right )$$. Use these two strings to find two messages $$m_1$$ and $$m_2$$ whose ciphertext distributions assign different probabilities to $$s_1$$ and $$s_2$$. Note that it is legitimate for an attacker to “know” $$s_1$$ and $$s_2$$, as these are properties of $$G$$ alone, and do not depend on the random choices made “at runtime” — when the library executes the encryption algorithms.

##### Exercise $$5.5$$

The proof of Claim $$5.5$$ applies the PRG security rule to both of the calls to $$G$$, starting with the first one. Describe what happens when you try to apply the PRG security of $$G$$ to these two calls in the opposite order. Does the proof still work, or does it work only in the order that was presented?

##### Exercise $$5.6$$

Let $$\ell^{\prime}>\ell>0$$. Extend the "PRG feedback" construction to transform any PRG of stretch $$\ell$$ into a PRG of stretch $$\ell^{\prime}$$. Formally define the new PRG and prove its security using the security of the underlying $$P R G$$.

##### Exercise $$5.7$$

Prove that if $$G$$ is a secure $$P R G$$, then so is the function $$H(s)=G(\bar{s})$$.

##### Exercise $$5.8$$

Let $$G:\{\theta, 1\}^{\lambda} \rightarrow\{0,1\}^{3 \lambda}$$ be a secure length-tripling PRG. For each function below, state whether it is also a secure PRG. If the function is a secure PRG, give a proof. If not, then describe a successful distinguisher and explicitly compute its advantage. When we write $$a\|b\| c:=G(s)$$, each of $$a, b, c$$ have length $$\lambda$$.

##### Exercise $$5.9$$

Let $$G:\{0,1\}^{\lambda} \rightarrow\{0,1\}^{3 \lambda}$$ be a secure length-tripling PRG. Prove that each of the following functions is also a secure PRG:

(a)

Note that $$H$$ includes half of its input directly in the output. How do you reconcile this fact with the conclusion of Exercise $$5.14(\mathrm{~b}) ?$$

(b)

##### Exercise $$\star 5.10$$

Let $$G$$ be a secure length-doubling PRG. One of the following constructions is a secure PRG and one is not. Which is which? Give a security proof for one and an attack for the other.

Hint:

Usually when something is insecure, it’s insecure for $$any$$ choice of building block. In this case, the attack only works for certain $$G$$. Basically, you will need to construct a particular $$G$$, prove that it's a secure PRG, and then prove that $$H_1/H_2$$ is not secure when using $$G$$.

##### Exercise $$5.11$$

A frequently asked question in cryptography forums is whether it’s possible to determine which PRG implementation was used by looking at output samples.

Let $$G_{1}$$ and $$G_{2}$$ be two PRGs with matching input/output lengths. Define two libraries $$\mathcal{L}_{\text {which-prg }}^{G_{1}}$$ and $$\mathcal{L}_{\text {which-prg }}^{G_{2}}$$ as follows:

Prove that if $$G_{1}$$ and $$G_{2}$$ are both secure PRGs, then $$\mathcal{L}_{\text {which-prg }}^{G_{1}} \approx \mathcal{L}_{\text {which-prg }}^{G_{2}}-$$ that is, it is infeasible to distinguish which PRG was used simply by receiving output samples.

##### Exercise $$5.12$$

Let $$G_{1}$$ and $$G_{2}$$ be deterministic functions, each accepting inputs of length $$\lambda$$ and producing outputs of length $$3 \lambda$$

1. Define the function $$H\left(s_{1} \| s_{2}\right)=G_{1}\left(s_{1}\right) \oplus G_{2}\left(s_{2}\right)$$. Prove that if either of $$G_{1}$$ or $$G_{2}$$ (or both) is a secure PRG, then so is $$H$$.
2. What can you say about the simpler construction $$H(s)=G_{1}(s) \oplus G_{2}(s)$$, when one of $$G_{1}, G_{2}$$ is a secure PRG?
##### Exercise $$\star 5.13$$

Prove that if $$P R G s$$ exist, then $$P \neq N P$$.

​​​​​​​Hint:

$$\left \{ y \,|\,\exists \left ( s \right )=y \right \}\in \textrm{NP}$$. Prove the contrapositive! Use the powerful assumption that $$P= N P$$ to construct an effcient adversary to attack any candidate PRG.

##### Exercise $$5.14$$
1. Let $$f$$ be any function. Show that the following function $$G$$ is not a secure PRG, no matter what $$f$$ is. Describe a successful distinguisher and explicitly compute its advantage:
2. Let $$G:\{0,1\}^{\lambda} \rightarrow\{0,1\}^{\lambda+\ell}$$ be a candidate PRG. Suppose there is a polynomial-time algorithm $$V$$ with the property that it inverts $$G$$ with non-negligible probability. That is $\operatorname{Pr}_{s \leftarrow\{0,1\}^{\lambda}}[V(G(s))=s] \text { is non-negligible. }$ Show that if an algorithm $$V$$ exists with this property, then $$G$$ is not a secure PRG. In other words, construct a distinguisher contradicting the PRG-security of $$G$$ and show that it achieves non-negligible distinguishing advantage.

Note: Don’t assume anything about the output of $$V$$ other than the property shown above. In particular, $$V$$ might very frequently output the "wrong" thing.

##### Exercise $$5.15$$

Let $$s_{0}, s_{1}, \ldots$$ and $$t_{1}, t_{2}, \ldots$$ be defined as in the symmetric ratchet (Construction 5.9).

1. Prove that if $$G$$ is a secure PRG then the following two libraries are indistinguishable, for any polynomial-time algorithm $$\mathcal{A}$$ :
2. What is $$\operatorname{Pr}\left[\right.$$ TEST outputs true] in $$\mathcal{L}_{\text {right }}$$ ?
3. Prove that for any polynomial-time algorithm $$\mathcal{A}, \operatorname{Pr}\left[\mathcal{A}\left(s_{n}\right)=t_{n}\right]$$ is negligible, where $$s_{n}, t_{n}$$ are generated as in the symmetric ratchet construction.
4. Prove that for any polynomial-time algorithm $$\mathcal{A}, \operatorname{Pr}\left[\mathcal{A}\left(s_{n}\right)=s_{n-1}\right]$$ is negligible. In other words, "turning the ratchet backwards" is a hard problem.
​​​​​​​Hint:

The proof should be a few lines, a direct corollary of part (c).

This page titled 5.6: Exercise is shared under a CC BY-NC-SA 4.0 license and was authored, remixed, and/or curated by Mike Rosulek (Open Oregon State) .