2
$\begingroup$

$$\{G:\{0,1\}^n\rightarrow\{0,1\}^{2n+1}\}^\infty_{n=1}$$

If above function is a pseudorandom generator then is the same $G$ a one way function. I tried to prove this but failed a lot of time. Would be helpful if someone could provide some insight on this.

$\endgroup$
5
$\begingroup$

Prove by contradiction. Assume that it is not a one-way function and that it can be inverted with non-negligible probability. Use this to construct a distinguisher that can distinguish truly random from $G(s)$ with non-negligible advantage. I leave the rest to you...

$\endgroup$

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.