# PRG existance and P versus NP

how can we prove that if there is a secure PRG then P!=NP or in reverse order?(is there any reduction?)

a secure PRG is a pseudo random generator that for every eficient (running in probabilistic polynomial time) statistical test algorithm A , A cannot distinguish PRG from a truly random generator with a non-neglogible advantage.

"Negligible" means "within $O(2^{-p})$" where p is a security parameter associated with the algorithm.

I know that we must use a reduction. reducing P!=NP to existance of PRG or reverse.but how to reduce?

suppose we have a secure PRG , then for every "eff" adversary A , A cannot distinguish PRG from a truly random function with a non-negligible advantage. so it implies that there is no polynomial time algorithm to solve it without having the key. and it shows that P!=NP.

Is my reduction correct?

• Is this homework? If so, we are happy to help with homework, but will not give the answer. We also expect some minimal effort on your part, please let us know what you have tried, etc. I'm not sure what the answer is. Existence of one-way functions implies P!=NP. That may help. – mikeazo May 5 '14 at 18:41
• no this is not a HW.I'm interested in it for myself. also I know that we must use a reduction ,e.g reduce (P!=NP) to existance of prg but how? – abdolahS May 6 '14 at 1:56

• Well, this is the sledge-hammer proof. $\:$ One could just use a SAT algorithm to break the security of any candidate PRG. $\;\;\;\;$ – user991 May 6 '14 at 17:10