# 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}}$$

## Exercises

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:

 $$\mathcal{A}$$ $$x:=\operatorname{\text {QERY}}()$$ for all $$s^{\prime} \in\{0,1\}^{\lambda}:$$ $$\quad$$ if $$G\left(s^{\prime}\right)=x$$ then return 1 return 0

(a) 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?

(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.2. Let $$G:\{0,1\}^{\lambda} \rightarrow\{0,1\}^{\lambda+\ell}$$ be an injective $$P R G$$, and consider the following distinguisher:

 $$\mathcal{A}$$ $$x:=\operatorname{QUERY}()$$ $$s^{\prime} \leftarrow\{0,1\}^{\lambda}$$ return $$G\left(s^{\prime}\right) \stackrel{?}{=} x$$

What is the advantage of $$\mathcal{A}$$ in distinguishing $$\mathcal{L}_{\mathrm{prg}-\mathrm{real}}^{G}$$ from $$\mathcal{L}_{\mathrm{prg}-\mathrm{rand}}^{G} ?$$ 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:

 $$\mathcal{A}$$ $$x:=\operatorname{\text {QERY}}()$$ return $$x \stackrel{?}{\in} S$$

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?

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:

$$\mathrm{~ s ә ุ n ว ә х ә ~ K . x . x q ! ~ ә Ч 7 ~ แ ә}$$ $$\mathrm{~ 5 ~ j o ~ s ә п . I ว d o . d ~ ә x R ~ ә}$$ $$\mathrm{~ I s ~ o f ~ s ә п п ा q e q o . I d ~ z u ә .}$$ $$\mathrm{~ s ~ o f ~ s o l t ! l q u q e i d ~ q u e i o f}$$

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?

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

5.7. Prove that if $$G$$ is a secure $$P R G$$, then so is the function $$H(s)=G(\bar{s})$$.

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$$

(a) (c) (d) (e) $$/ / H:\{\odot, 1\}^{2 \lambda} \rightarrow\{0,1\}^{3 \lambda}$$
$$\frac{H\left(s_{L} \| s_{R}\right):}{x:=G\left(s_{L}\right)}$$
$$y:=G\left(s_{R}\right)$$
$$\operatorname{return} x \oplus y$$

$$/ / H:\{0,1\}^{2 \lambda} \rightarrow\{0,1\}^{6 \lambda}$$
$$x:=G\left(s_{L}\right)$$
$$y:=G\left(s_{R}\right)$$
$$y:=G\left(s_{R}\right)$$
$$\operatorname{return} x \|_{y}$$

(g) $$\frac{H\left(s_{L} \| s_{R}\right)}{x:=G\left(s_{L}\right)}$$

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)
$$\frac{H\left(s_{L} \| s_{R}\right):}{y:=G\left(s_{R}\right)}$$
return $$s_{L} \| y$$

$$/ / H:\{\theta, 1\}^{2 \lambda} \rightarrow\{\theta, 1\}^{4 \lambda}$$

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}) ?$$
$$/ / H:\{0,1\}^{2 \lambda} \rightarrow\{0,1\}^{3 \lambda}$$
(b)
$$\frac{H\left(s_{L} \| s_{R}\right):}{\operatorname{return} G\left(s_{L}\right)}$$

$$\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

Hint: $$\mathrm{~ - 5 ~ ड ़ ् प 7 ~ \ u t s n ~ प ว प}$$ 2 7! 7е4t әno.Id$$2 \mathrm{~ . r e [ n}$$ $$\mathrm{~ ว प 7 ~ ' ә s E כ ~ s ̦ प 7 ~ u I ~ '}$$

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:

$$\mathcal{L}_{\text {which-prg }}^{G_{1}}$$
QUERY ()$$:$$
$$s \leftarrow\{0,1\}^{\lambda}$$
return $$G_{1}(s)$$

\mid

 $$\mathcal{L}_{\text {which-prg }}^{G_{2}}$$ QUERY(): $$s \leftarrow\{0,1\}^{\lambda}$$ return $$G_{2}(s)$$

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.

5.12. Let $$G_{1}$$ and $$G_{2}$$ be deterministic functions, each accepting inputs of length $$\lambda$$ and producing outputs of length $$3 \lambda$$

(a) 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$$.

(b) 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?

$$\star 5.13$$. Prove that if $$P R G s$$ exist, then $$P \neq N P$$.

Hint:

$$\mathrm{~ D U d ~ ә ұ в р т р и е о ~ К L r e ~ y ә е н ұ е ~ о ұ ~ К . r e s .}$$ $$07 \mathrm{dN}=\mathrm{~ d ~ f R प ~ u o n d u u n s s e ~ [ n f r a m o d ~ ә Ч}$$

5.14. (a) 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: $\frac{G(s):}{\text { return } s \| f(s)}$ (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 $\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.

5.15. Let $$s_{0}, s_{1}, \ldots$$ and $$t_{1}, t_{2}, \ldots$$ be defined as in the symmetric ratchet (Construction 5.9).

(a) Prove that if $$G$$ is a secure PRG then the following two libraries are indistinguishable, for any polynomial-time algorithm $$\mathcal{A}$$ :

|l|
$$\frac{\text { TEST }():}{s_{n-1}} \leftarrow\{0,1\}^{\lambda}$$
$$s_{n} \| t_{n}:=G\left(s_{n-1}\right)$$
$$\tilde{t}=\mathcal{A}\left(s_{n}\right)$$
$$\operatorname{return} \tilde{t} \stackrel{?}{=} t_{n}$$

\mid

 $$\mathcal{L}_{\text {right }}$$ $$\frac{\operatorname{TeST}():}{s_{n} \leftarrow\{0,1\}^{\lambda}}$$ $$\tilde{t}=\mathcal{A}\left(s_{n}\right)$$ $$t_{n} \leftarrow\{0,1\}^{\lambda}$$ return $$\tilde{t} \stackrel{?}{=} t_{n}$$

(b) What is $$\operatorname{Pr}\left[\right.$$ TEST outputs true] in $$\mathcal{L}_{\text {right }}$$ ?

(c) 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. (d) 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: $$\mathrm{~ ( ว ) ~ ๆ т в ् ~ f o ~ К . r е}$$

5.6: Exercise is shared under a not declared license and was authored, remixed, and/or curated by LibreTexts.