1
$\begingroup$

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?

$\endgroup$
2
  • 2
    $\begingroup$ 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. $\endgroup$
    – mikeazo
    May 5, 2014 at 18:41
  • $\begingroup$ 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? $\endgroup$
    – abdolahS
    May 6, 2014 at 1:56

1 Answer 1

3
$\begingroup$

First, note the following:

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

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.

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

Your Answer

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

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