# 5.6: Exercise

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

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

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

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

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