Necessary conditions for construction of $n$ to $p(n)$ pseudorandom generators from $n$ to $n+1$ generators?

Question

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.

Answer 1

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.