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

Question

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?

Explanation / Answer

First, note the following:

1. If one-way functions exist then P!=NP
2. Pseudorandom generators exist if and only if one-way functions exist

From there the proof is trivial.

Now, I wanted to explain (or at least try as this stuff is not my expertise) why the reduction you have in the question is not sufficient.

NP does not mean not-polynomial time, it means nondeterministic polynomial time. Your reduction argues that there is no poly time algorithm. That says nothing about whether or not there is a nondeterministic poly time algorithm. You would have to first show that there is a nondeterministic poly time algorithm, then show that there is not a poly time algorithm (or vice-versa). There may be other problems with the reduction in the question (again this is not my area of expertise). For example, the argument seems to be circular. Hopefully others can comment on this.

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.