Exercises

5.1: Let $$G$$ : $$\{0,1\}^{\lambda} \rightarrow \{0,1\}^{\lambda + \ell}$$. Define $$im(G) = \{y \in \{0,1\}^{\lambda + \ell} \mid \exists s : G(s) = y\}$$, the set of possible outputs of $$G$$. For simplicity, assume that $$G$$ is injective (i.e., 1-to-1).

(a). What is $$|im(G)|$$, as a function of $$\lambda$$ and $$\ell$$?

(b). A string $$y$$ is chosen randomly from $$\{0,1\}^{\lambda + \ell}$$. What is the probability that $$y \in im(G)$$, expressed as a function of $$\lambda$$ and $$\ell$$?

5.2: Let $$G : \{0,1\}^{\lambda} \rightarrow \{0,1\}^{\lambda + \ell}$$ be an injective PRG. Consider the following distinguisher:

$\mathscr{A}\\x:=\text{QUERY()}\\\text{for\space all}\space s^{\prime}\in\{0,1\}^{\lambda}:\\\text{if}\space G(s^{\prime})=x\space\text{then\space return 1}\\text{return}\space 0\nonumber$

(a). What is the advantage of $$?$$ in distinguishing $$\mathscr{L}^G_{\text{prg-real}}$$ and $$\mathscr{L}^G_{\text{prg-rand}}$$? Is it negligible?

(b). Does this contradict the fact that $$G$$ is a PRG? Why or why not?

(c). What happens to the advantage if $$G$$ is not injective?

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

$\mathscr{A}\\x:=\text{QUERY()}\\s^{\prime}\space\leftarrow\{0,1\}^{\lambda}\\\text{return}\space G(s^{\prime})\stackrel{?}{=}x\nonumber$

What is the advantage of ? in distinguishing $$\mathscr{L}^G_{\text{prg-real}}$$ from $$\mathscr{L}^G_{\text{prg-rand}}$$?

Hint: When computing $$Pr[? \diamondsuit \mathscr{L}^G_{\text{prg-rand}}$$ outputs 1], separate the probabilities based on whether $$x \in im(G)$$ or not. ($$im(G)$$ is defined in a previous problem)

5.4: 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:

$\mathscr{A}\\x:=\text{QUERY()}\\\text{return}\space x\stackrel{?}{\in}S\nonumber$

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

5.5: Show that the scheme from Section 5.2 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 \{0,1\}^{2\lambda}$$ where $$s_1 \in im(G)$$, and $$s_2 \notin im(G)$$. 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 independent of the random choices made when executing the scheme.

5.6: (a). Let $$?$$ be any function. Show that the following function $$G$$ is not a secure PRF (even if ? is a secure PRG!). Describe a successful distinguisher and explicitly compute its advantage:

$\underline{G(s):}\\\text{return}\space\parallel f(s)\nonumber$

(b).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,

$\underset{s\leftarrow\{0,1\}^{\lambda}}{\operatorname{Pr}}[V(G(s))=s]\text { is non-negligible. }\nonumber$

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.

5.7: In the “PRG feedback” construction $$H$$ in Section 5.4, there are two calls to $$G$$. The security proof applies the PRG security rule to both of them, starting with the first. 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 must it be in the order that was presented?

5.8: 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 PRG.

5.9: Let $$G : \{0,1\}^{\lambda} \rightarrow \{0,1\}^{3\lambda}$$ be a 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.

$\text { (a) } \left| \begin{array}{l}{\underline{H(s)}\\ {x} :=G(s)} \\ {y :=G(s)} \\ {y :=\text { first } \lambda \text { bits of } x} \\ {z :=\text { last } \lambda \text { bits of } x} \\ {\text { return } G(y)\|G(z)}\end{array}\right.\nonumber$

$\text { (b) } \left| \begin{array}{c}{\underline{H(s):}\\{x} :=G(s)} \\ {y :=\text { first } 2 \lambda \text { bits of } x} \\ {\text { return } y}\end{array}\right.\nonumber$

$\text { (c) } \left| \begin{array}{l}{\underline{H(s):}\\{x} :=G(s)} \\ {y :=G(s)} \\ {\text { return } x\|y}\end{array}\right.\nonumber$

$\text { (d) } \left| \begin{array}{c}{\underline{H(s):}\\{x} :=G(s)} \\ {y :=G\left(0^{\lambda}\right)} \\ {\text { return } x\|y}\end{array}\right.\nonumber$

$\text { (e) } \left| \begin{array}{c}{\underline{H(s):}\\{x} :=G(s)} \\ {y :=G\left(0^{\lambda}\right)} \\ {\text { return } x \oplus y}\end{array}\right.\nonumber$

$\text{(f)}\left|\begin{array}{l}{/ / H :\{0,1\}^{2 \lambda} \rightarrow\{0,1\}^{3 \lambda}} \\ {\underline{H(s) :}\\{x :=G\left(s_{\text { left }}\right)}} \\ {y :=G\left(s_{\text { right }}\right)} \\ {\text { return } x \oplus y}\end{array}\right.\nonumber$

$\text{(g)}\left|\begin{array}{l}{/ / H :\{0,1\}^{2 \lambda} \rightarrow\{0,1\}^{6 \lambda}} \\ {\underline{H(s):}\\{x :=G\left(s_{\text { left }}\right)}} \\ {y :=G\left(s_{\text { right }}\right)} \\ {\text { return } x\|y}\end{array}\right.\nonumber$

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

$\text{(a)}\left|\begin{array}{l}{/ / H :\{0,1\}^{2 \lambda} \rightarrow\{0,1\}^{3 \lambda}} \\ {\underline{H(s)}\\{\text { return } G\left(s_{\text { left }}\right)}}\end{array}\right.\nonumber$

Note that H includes half of its input directly in the output. How do you reconcile this fact with the conclusion of Exercise 5.6(b)?

$\text{(b)}\left|\begin{array}{l}{/ / H :\{0,1\}^{2 \lambda} \rightarrow\{0,1\}^{3 \lambda}} \\ {\underline{H(s)}\\{\text { return } G\left(s_{\text { left }}\right)}}\end{array}\right.\nonumber$

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 $$\mathscr{L}^{G_1}_{\text{which-prg}}$$ and $$\mathscr{L}^{G_2}_{\text{which-prg}}$$ as follows:

Prove that if $$G_1$$ and $$G_2$$ are both secure PRGs, then $$\mathscr{L}^{G_1}_{\text{which-prg}} ≋ \mathscr{L}^{G_2}_{\text{which-prg}}$$ — that is, it is infeasible to distinguish which PRG was used simply by receiving output samples.

5.12: Prove that if PRGs exist, thenP $$\not=$$ NP

Hint: $$\{y | \exists s : G(s) = y\} \in \text{NP}$$

Note: This implies that $$\mathscr{L}^{G}_{\text{prg-real}} \not\equiv \equiv \mathscr{L}^G_{\text{prg-rand}} \text{for all} G$$. That is, there can be no PRG that is secure against computationally unbounded distinguishers.