1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – mikeazo Jan 23 '17 at 18:48
  • $\begingroup$ 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. $\endgroup$ – Mok-Kong Shen Jan 24 '17 at 11:17
0
$\begingroup$

Well I think you can prove it by reduction:

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

$\endgroup$
  • $\begingroup$ I see, is it possible to prove this by the hybrid argument? $\endgroup$ – Adi Ml Jan 26 '17 at 11:12
  • $\begingroup$ 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$. $\endgroup$ – th3n3rd Jan 26 '17 at 13:18

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.