Skip to main content
Library homepage
 
Loading table of contents menu...
Engineering LibreTexts

5.6: Exercise

  • Page ID
    86459
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\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]{\| #1 \|}\) \( \newcommand{\inner}[2]{\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]{\| #1 \|}\) \( \newcommand{\inner}[2]{\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)

    image

    (c)

    image

    (d)

    image

    (e)

    image

    \(/ / 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:
    image
    \(\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.

    • Was this article helpful?