# Proving Pseudo Random Generator from other Pseudo Random Generator?

How can I prove that if $G$ is a Pseudo Random Generator, then other generator is a PRG (while the range's size is different)?

For example: for the PRG $G$ (from $n$ to $t(n)$ where $n < t(n)$), the generator $G'$ (from $n$ to $n+1$), where $G'$ returns the first $n+1$ bits of $G$) is PRG too?

Is the fact that the ranges are different affect the indistinguishability between the PRGs?

• For questions like these we require that you give us a better indication on where you are stuck in solving it yourself. Please edit to provide those details. – mikeazo Jan 23 '17 at 18:48
• It is IMHO often the case that with a "practical" PRNG, that delivers n bits on each invocation, one doesn't have the n bits of the same statistical quality. – Mok-Kong Shen Jan 24 '17 at 11:17

If there exist an efficient predictor $P$ that given the first $n$ bits of $G'$ is able to predict the $n+1$ bit then we can construct a distinguisher $D$ for $G$ defined as an elementary wrapper of $P$, that can distinguish $G$ from a truly random generator. Since by assumption $G$ is a (secure?) pseudo-random generator there is not such a $D$.
• I am not completely sure on how to prove it by the Hybrid argument but from the definition of computational indistinguishability you have that $G_{t(n)} \approx_p R_{t(n)}$ then for every $m < t(n)$ the truncation of $G$ to the first m bits is indistinguishable from the truncation of $R$ to the first m bits, since you have that $G'_m \equiv G_m$ for $m=n+1$ then by transitivity $G'_m \approx_p R_m$. – th3n3rd Jan 26 '17 at 13:18