5.6: Exercise
 Page ID
 86459
Let \(G:\{0,1\}^{\lambda} \rightarrow\{0,1\}^{\lambda+\ell}\) be an injective (i.e., 1to1) PRG. Consider the following distinguisher:
 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?
 Does this contradict the fact that \(G\) is a PRG? Why or why not?
 What happens to the advantage if \(G\) is not injective?
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.
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\) hardcoded:
What is the advantage of \(\mathcal{A}\) in distinguishing \(\mathcal{L}_{\text {prgreal }}^{G}\) from \(\mathcal{L}_{\text {prgrand }}^{G}\) ? Why does an adversary like this one not automatically break every PRG?
Show that the scheme from Section \(5.3\) does not have perfect onetime 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.
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?
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\).
Prove that if \(G\) is a secure \(P R G\), then so is the function \(H(s)=G(\bar{s})\).
Let \(G:\{\theta, 1\}^{\lambda} \rightarrow\{0,1\}^{3 \lambda}\) be a secure lengthtripling 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\).
Let \(G:\{0,1\}^{\lambda} \rightarrow\{0,1\}^{3 \lambda}\) be a secure lengthtripling 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)
Let \(G\) be a secure lengthdoubling 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\).
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 {whichprg }}^{G_{1}}\) and \(\mathcal{L}_{\text {whichprg }}^{G_{2}}\) as follows:
Prove that if \(G_{1}\) and \(G_{2}\) are both secure PRGs, then \(\mathcal{L}_{\text {whichprg }}^{G_{1}} \approx \mathcal{L}_{\text {whichprg }}^{G_{2}}\) that is, it is infeasible to distinguish which PRG was used simply by receiving output samples.
Let \(G_{1}\) and \(G_{2}\) be deterministic functions, each accepting inputs of length \(\lambda\) and producing outputs of length \(3 \lambda\)
 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\).
 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?
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.
 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:
 Let \(G:\{0,1\}^{\lambda} \rightarrow\{0,1\}^{\lambda+\ell}\) be a candidate PRG. Suppose there is a polynomialtime algorithm \(V\) with the property that it inverts \(G\) with nonnegligible probability. That is \[\operatorname{Pr}_{s \leftarrow\{0,1\}^{\lambda}}[V(G(s))=s] \text { is nonnegligible. }\] 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 PRGsecurity of \(G\) and show that it achieves nonnegligible 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.
Let \(s_{0}, s_{1}, \ldots\) and \(t_{1}, t_{2}, \ldots\) be defined as in the symmetric ratchet (Construction 5.9).
 Prove that if \(G\) is a secure PRG then the following two libraries are indistinguishable, for any polynomialtime algorithm \(\mathcal{A}\) :
 What is \(\operatorname{Pr}\left[\right.\) TEST outputs true] in \(\mathcal{L}_{\text {right }}\) ?
 Prove that for any polynomialtime 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.
 Prove that for any polynomialtime algorithm \(\mathcal{A}, \operatorname{Pr}\left[\mathcal{A}\left(s_{n}\right)=s_{n1}\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).