Return to 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?

Update: As Maeher has pointed out (if I understand correctly), let's consider some pseudorandom $G_1':\{0,1\}^n \rightarrow \{0,1\}^n$, and a generator $G_1:\{0,1\}^n \rightarrow \{0,1\}^{n+1}$ defined via

\begin{equation} G_1(s) = (0,G_1'(s^{[2:n+1]})), \end{equation} where $s^{[2:n+1]}$ is the last $n$ bits of $s \in \{0,1\}^{n+1}$. Then, $G_1$ is not pseudorandom (a distinguisher just outputs 1 if the first bit it receives is 0), but $G$ as constructed above is a pseudorandom generator. If all these claims are correct, then $G_1$ provides an explicit example showing that it is not necessary for $G_1$ to be pseudorandom for $G$ to be pseudorandom.

In light of this example (and given the context below), I am still very interested in the more general questions above - i.e. Do there exist constructions of length doubling generators which are pseudorandom if and only if the underlying primitive is secure?

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.

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.

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?

Update: As Maeher has pointed out (if I understand correctly), let's consider some pseudorandom $G_1':\{0,1\}^n \rightarrow \{0,1\}^n$, and a generator $G_1:\{0,1\}^n \rightarrow \{0,1\}^{n+1}$ defined via

\begin{equation} G_1(s) = (0,G_1'(s^{[2:n+1]})), \end{equation} where $s^{[2:n+1]}$ is the last $n$ bits of $s \in \{0,1\}^{n+1}$. Then, $G_1$ is not pseudorandom (a distinguisher just outputs 1 if the first bit it receives is 0), but $G$ as constructed above is a pseudorandom generator. If all these claims are correct, then $G_1$ provides an explicit example showing that it is not necessary for $G_1$ to be pseudorandom for $G$ to be pseudorandom.

In light of this example (and given the context below), I am still very interested in the more general question stated above...

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.

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?

Update: As Maeher has pointed out (if I understand correctly), let's consider some pseudorandom $G_1':\{0,1\}^n \rightarrow \{0,1\}^n$, and a generator $G_1:\{0,1\}^n \rightarrow \{0,1\}^{n+1}$ defined via

\begin{equation} G_1(s) = (0,G_1'(s^{[2:n+1]})), \end{equation} where $s^{[2:n+1]}$ is the last $n$ bits of $s \in \{0,1\}^{n+1}$. Then, $G_1$ is not pseudorandom (a distinguisher just outputs 1 if the first bit it receives is 0), but $G$ as constructed above is a pseudorandom generator. If all these claims are correct, then $G_1$ provides an explicit example showing that it is not necessary for $G_1$ to be pseudorandom for $G$ to be pseudorandom.

In light of this example (and given the context below), I am still very interested in the more general questions above - i.e. Do there exist constructions of length doubling generators which are pseudorandom if and only if the underlying primitive is secure?

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.

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?

Update: As Maeher has pointed out (if I understand correctly), let's consider some pseudorandom $G_1':\{0,1\}^n \rightarrow \{0,1\}^n$, and a generator $G_1:\{0,1\}^n \rightarrow \{0,1\}^{n+1}$ defined via

\begin{equation} G_1(s) = (0,G_1'(s^{[2:n+1]})), \end{equation} where $s^{[2:n+1]}$ is the last $n$ bits of $s \in \{0,1\}^{n+1}$. Then, $G_1$ is not pseudorandom (a distinguisher just outputs 1 if the first bit it receives is 0), but $G$ as constructed above is a pseudorandom generator. If all these claims are correct, then $G_1$ provides an explicit example showing that it is not necessary for $G_1$ to be pseudorandom for $G$ to be pseudorandom.

In light of the above (and given the context below), I still have the following underlying question:

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.

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?

Update: As Maeher has pointed out (if I understand correctly), let's consider some pseudorandom $G_1':\{0,1\}^n \rightarrow \{0,1\}^n$, and a generator $G_1:\{0,1\}^n \rightarrow \{0,1\}^{n+1}$ defined via

\begin{equation} G_1(s) = (0,G_1'(s^{[2:n+1]})), \end{equation} where $s^{[2:n+1]}$ is the last $n$ bits of $s \in \{0,1\}^{n+1}$. Then, $G_1$ is not pseudorandom (a distinguisher just outputs 1 if the first bit it receives is 0), but $G$ as constructed above is a pseudorandom generator. If all these claims are correct, then $G_1$ provides an explicit example showing that it is not necessary for $G_1$ to be pseudorandom for $G$ to be pseudorandom.

In light of this example (and given the context below), I am still very interested in the more general question stated above...

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.