5.6: Exercise

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).