4
$\begingroup$

Given a polynomial time deterministic algorithm $G_1:\{0,1\}^n \rightarrow \{0,1\}^{n+1}$, consider the function $G:\{0,1\}^n \rightarrow \{0,1\}^{p(n)}$ constructed as follows:

  1. Let $s \in \{0,1\}^n$ be the input seed and denote $s =s_0$.
  2. For every $i = 1,\ldots,p(n)$, compute $(s_i,\sigma_i) = G_1(s_{i-1})$.
  3. Output $(\sigma_1,\ldots,\sigma_{p(n)})$.

Now, we know that if $G_1$ is a pseudorandom generator, then $G$ is also a pseudorandom generator - i.e. in order for the construction of $G$ to yield a pseudorandom generator it is sufficient for $G_1$ to be a pseudorandom generator.

My question is as follows: Is it also necessary that $G_1$ is a pseudo-random generator? In other words, is it true that $G$ is a pseudorandom generator if and only if $G_1$ is a pseudorandom generator - i.e. is it possible to prove that if $G_1$ is not a pseudorandom generator, then $G$ is not a pseudorandom generator?

More generally, if the above is not true, given $G_1$, is there any way to construct a deterministic poly-time algorithm $G:\{0,1\}^n \rightarrow \{0,1\}^{2n}$ such that $G$ is a pseudorandom generator if and only if $G_1$ is a pseudorandom generator?

Or, if this is not possible, given a permutation $f:\{0,1\}^n \rightarrow \{0,1\}^n$, is it possible to construct a deterministic polynomial time algorithm $G:\{0,1\}^n \rightarrow \{0,1\}^{2n}$ such that $G$ is a pseudorandom generator if and only if $f$ is a one-way permutation?


For context: I am working through each step of the classical construction of pseudorandom functions from one-way functions:

OWF $\rightarrow$ hard-core predicate $\rightarrow$ $n+1$ PRG $\rightarrow$ $2n$ PRG $\rightarrow$ PRF

we know that if $f$ is a one-way permutation, then this construction yields a pseudorandom function. I would like to understand whether it is necessary that $f$ is a one-way function for this construction to work - i.e. if I am given an inversion adversary for $f$, can I construct an adversary for the pseudorandom function given by the above construction? More generally, given a permutation $f$, I would like to construct a function which is pseudorandom, if and only if $f$ is a one-way permutation, and I was curious whether the typical construction of pseudorandom functions has this property.

$\endgroup$
  • 1
    $\begingroup$ Imagine a $G$ that ignores the first bit of its input and outputs a constant bit (say 0) as the first bit of its output. $\endgroup$ – Maeher Nov 6 '19 at 9:45
  • $\begingroup$ A $G_1$ that is. $\endgroup$ – Maeher Nov 6 '19 at 9:52
  • $\begingroup$ Your construction does not quite work yet. Your $G'_1$ would need two bit stretch, I think, to get the correct parameters. If I'll have time later I'll write a proper answer. $\endgroup$ – Maeher Nov 6 '19 at 10:30
  • $\begingroup$ Thanks! I added some additional edits detailing the underlying question of whether, given a permutation, it is possible to construct a length doubling generator which is pseudorandom if and only if the permutation is one way. $\endgroup$ – Ryan Nov 6 '19 at 10:40
  • $\begingroup$ @Maeher after thinking more about your suggestion for a counter example to necessity, and looking again at the construction I imagined from your suggestion, I see how my interpretation of your suggestion was wrong (and I can't see how to fix it) and so I removed it from the post for now. If you could provide more details that would be great! $\endgroup$ – Ryan Nov 6 '19 at 16:27
1
$\begingroup$

It is not necessary, that $G_1$ is a PRG.

Let $G_2: \{0,1\}^{n-1} \rightarrow \{0,1\}^n$ be a PRG, define $G_1: \{0,1\}^n \rightarrow \{0,1\}^{n+1}$ as \begin{align*} G_1(s_1||\ldots||s_n) := 1||G_2(s_2||\ldots||s_n). \end{align*} and consider the distinguisher $\mathcal{D}_1$, which returns the first bit $w_1$, when given the $n+1$ bit string $w := w_1||\ldots||w_{n+1}$ as input.

For $s_1 \leftarrow \{0,1\}^n$ and $r_1 \leftarrow \{0,1\}^{n+1}$ we have \begin{align*} \Big|\text{Pr}[\mathcal{D}_1(G_1(s_1))=1] - \text{Pr}[\mathcal{D}_1(r_1)=1]\Big| = \Big|1 - \frac{1}{2}\Big| = \frac{1}{2} > \mathsf{negl}(n), \end{align*} which implies that $G_1$ is not a PRG.

Nevertheless, we can still prove, that $G$ is a PRG, by using a slight modification of Katz' and Lindell's proof for theorem 6.20 in "Introduction to Modern Cryptography". (I assume you are familiar with it, since you are using the exact same notation.)

We construct a distinguisher $\mathcal{D}_2$ for $G_2$ using another distinguisher $\mathcal{D}$ for $G$, with \begin{align*} \Big|\text{Pr}[\mathcal{D}(G(s))=1] - \text{Pr}[\mathcal{D}(r)=1]\Big| =: \epsilon(n). \end{align*}

Let $\mathcal{D}_2$ behave as follows, when given a $w := w_1 || \ldots || w_n \in \{0,1\}^n$ as input.

  1. $i \leftarrow \{0, \ldots, p(n) - 1\}$
  2. $r \leftarrow \{0,1\}^i$
  3. $p := G(1||w)$
  4. Construct a bit-string $w'$ as the concatenation of $r$, $w_{n}$ and the first $p(n) - i - 1$ bits of $p$.
  5. Output $\mathcal{D}(w')$

You can easiliy verifiy the following two statements:

  • If $i = 0$ and $w = G_2(s_2)$ for $s_2 \in \{0,1\}^{n-1}$, then $w' = G(s)$ for $s = b||s_2$ and $b \in \{0,1\}$.
  • If $i = p(n) -1$ and $w = r_2 \leftarrow \{0,1\}^n$, then $w' \leftarrow \{0,1\}^{p(n)}$.

Using the same argument as Katz and Lindell, we obtain \begin{align*} \mathsf{negl}(n) \geq \frac{\epsilon(n)}{p(n)} && \Longrightarrow && \mathsf{negl}(n) \geq \epsilon(n), \end{align*} which means, that $G$ is a PRG.

Similar arguments apply to your other two questions.

$\endgroup$
  • $\begingroup$ This definitely answers the original question. However, I still wonder what the minimum necessary requirement is for constructing a length doubling PRG? Given your construction, one could ask if it is necessary that $G_2$ is a PRG. My intuition would just be to iterate the above construction and answer "no" - but then eventually I would end up at the necessity of an $\{0,1\}\rightarrow \{0,1\}^2$ PRG. This seems strange though, as it would imply that for any $n$ the only necessary requirement for generating $p(n)$ pseudorandom strings is an $\{0,1\}\rightarrow \{0,1\}^2$ PRG? $\endgroup$ – Ryan Nov 7 '19 at 14:05
  • $\begingroup$ You would not end up at the necessity of an $\{0,1\} \rightarrow \{0,1\}^2$ PRG, because the proof would fail, as soon as you would reach an input length of $\mathcal{O}(\mathsf{poly}(\log(n)))$, since the proof only works for polynomial length-expansion. (Expanding from $\mathcal{O}(\mathsf{poly}(\log(n)))$ to $p(n)$ is exponential.) $\endgroup$ – kawowski Nov 7 '19 at 20:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.