# Prove there is PRG that is not necessarily one-to-one

We assume that there is at least one PRG .Now prove there is a PRG like $G:\{0,1\}^{n} \rightarrow \{0,1\}^{l(n)}$ such that it is not necessarily one-to-one.

• Remove one bit of the output? Apr 12, 2015 at 11:17
• Dear Aleph I think you mean we assume that $G_{1}:\{0,1\}^{n} \rightarrow \{0,1\}^{l(n)}$ is a PRG then we construct $G_{2}:\{0,1\}^{n} \rightarrow \{0,1\}^{l(n)-1}$ such that for $0 \leqslant i \leqslant l(n)-1$ the $i$th bit from output of $G_{2}$ is equal to the $i$th bit from output of$G_{1}$ . is my imagination about your idea true? Apr 12, 2015 at 11:36
• @ebad: no, that idea doesn't work: why would you expect that $G_2(x) = G_2(y)$ for some $x \ne y$? Apr 13, 2015 at 14:10
• What does this have to do with PRGs? From that definition, it might look like a PRF or a PRP, but that is something entirely different than a PRG. You can create a PRG from a PRF, but that is not what you are asking about.
– tylo
Apr 14, 2015 at 11:05
• Dear poncho in the question I asked "is not necessarily" so if $G_{2}(x)=G_{2}(y)$ so nobody can surely say that it is one-to-one Apr 15, 2015 at 5:20

Suppose $F \colon \lbrace 0,1 \rbrace^n \to \lbrace 0,1 \rbrace^{\ell(n)}$ is a secure PRG. Create $G \colon \lbrace 0,1 \rbrace^{n+1} \to \lbrace 0,1 \rbrace^{\ell(n)}$ as follows:

$$G(b ||s) := F(s), \quad b \in \lbrace 0,1 \rbrace, s \in \lbrace 0,1 \rbrace^n.$$

$G$ is as secure as $F$, and clearly $G(0||s) = G(1 || s)$.

To prove the "$G$ is as secure as $F$" part, consider the following proposition$^*$:

Proposition. If there exists a distinguisher $\mathcal{D}$ against $G$, then we can create a distinguisher $\mathcal{D}'$ against $F$, such that $$| \Pr[\mathcal{D}'(U_{\ell(n)}, 1^n) = 1] - \Pr[\mathcal{D}'(F(U_n), 1^n) = 1]| > \frac{1}{poly(n)}.$$

Proof. Distinguisher $\mathcal{D}'$ receives as input a string $z \in \lbrace 0,1 \rbrace^{\ell(n)}$. Then he simply forwards this string to $\mathcal{D}$ and outputs whatever it outputs. Since $z$ is distributed exactly like in the distinguishing game $\mathcal{D}$ expects, we have in particular $\Pr[\mathcal{D}'(F(U_n), 1^n) = 1] = \Pr[\mathcal{D}'(G(U_{n+1}), 1^n) = 1]$, and the proposition follows. $\blacksquare$

Note that the above proposition is intuitively correct when you realize that the bit $b$ is independent of the output of $G$. That is, one could think of $G$ as first running $F$ on some input $s \in \lbrace 0,1 \rbrace^n$, and afterwards drawing the bit $b$. Clearly, this shouldn't reduce the strength of $F$ as a PRG. It should probably also be emphasized that $G$ is as secure as $F$, not more secure. That is, if $F$ has a security level of $n$ bits, then $G$ also has a security level of $n$, not $n+1$ as the longer seed could maybe lead you to believe.

$^*$Technically the proposition does not hold for $\ell(n) = n + 1$, since then $G$ wouldn't actually be a PRG. But I have ignored this above, and simply assumed the more typical case of $\ell(n) >> n$.

• Probably correct if dropping bits of the input is allowed. I presume it is, but in general you would expect that a random number generator behaves differently for different seed input. Can anybody confirm? Apr 18, 2015 at 11:09
• @MaartenBodewes Please see the edit. Does that look OK? Apr 19, 2015 at 8:57
• Yeah, I guess it's OK - I'll have to check the proposition though. I don't often work with these kind of proofs. The * part seems clear enough. Apr 19, 2015 at 14:27