$$G:\{0,1\}^n\rightarrow\{0,1\}^{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.
$\begingroup$
$\endgroup$
1
-
1$\begingroup$ In the unlikely case Yehuda Lindell’s answer wasn’t already an eye-opener for you, you could additionally check some related Q&As like – for example – “How can I prove/disprove that a construction yields a secure PRG?” $\endgroup$– e-sushiNov 1, 2016 at 2:58
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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...
answered Oct 31, 2016 at 22:17