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?

Improve this question
$\endgroup$
2
  • 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, 2017 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, 2017 at 11:17

1 Answer 1

Reset to default
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$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I see, is it possible to prove this by the hybrid argument? $\endgroup$
    – Adi Ml
    Jan 26, 2017 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, 2017 at 13:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.