Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
2  
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 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 at 1:56

1 Answer 1

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.

share|improve this answer
1  
Well, this is the sledge-hammer proof. $\:$ One could just use a SAT algorithm to break the security of any candidate PRG. $\;\;\;\;$ –  Ricky Demer May 6 at 17:10

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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