1
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ Remove one bit of the output? $\endgroup$
    – Aleph
    Apr 12, 2015 at 11:17
  • $\begingroup$ 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? $\endgroup$
    – abbas
    Apr 12, 2015 at 11:36
  • $\begingroup$ @ebad: no, that idea doesn't work: why would you expect that $G_2(x) = G_2(y)$ for some $x \ne y$? $\endgroup$
    – poncho
    Apr 13, 2015 at 14:10
  • $\begingroup$ 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. $\endgroup$
    – tylo
    Apr 14, 2015 at 11:05
  • $\begingroup$ 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 $\endgroup$
    – abbas
    Apr 15, 2015 at 5:20

1 Answer 1

2
$\begingroup$

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$.

$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$
    – Maarten Bodewes
    Apr 18, 2015 at 11:09
  • $\begingroup$ @MaartenBodewes Please see the edit. Does that look OK? $\endgroup$
    – hakoja
    Apr 19, 2015 at 8:57
  • $\begingroup$ 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. $\endgroup$
    – Maarten Bodewes
    Apr 19, 2015 at 14:27

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.