# Exercises

- Page ID
- 7345

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.