Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Has there been any progress about constructing strong pseudorandom generators?

I'm not an expert on this topic, basically everything I know is a definition of a pseudorandom generator, the idea that they are related to one-way functions, as well as other standard parts of complexity theory.

I'll appreciate any related information, e.g. what it is equivalent to.

share|improve this question
    
I think I'll prepare better and post a reworded question. –  Ilya Nikokoshev Oct 24 '09 at 17:21
    
Sorry, my previous comment was unnecessarily confrontational. I'll delete it. –  S. Carnahan Oct 24 '09 at 17:46
1  
I'm confused by what you're looking for exactly. Proving the (unconditional) existence of a pseudorandom generator would imply P ≠ NP. –  Richard Dore Oct 31 '09 at 20:12
    
That's a new thing for me! Would it be possible for you to post an answer containing a reference? I'll gladly accept it. –  Ilya Nikokoshev Nov 1 '09 at 8:13
add comment

1 Answer

up vote 8 down vote accepted

Ilya,

It's possible that I'm misinterpreting what you're asking (since complexity theorists, applied cryptographers, and combinatorialists all tend to use slightly different definitions of "pseudorandom"), but from a theory standpoint, I think the question is essentially solved and has been for a while.

As you mentioned, PRNGs are related to one-way functions. In particular it's easy to see that a PRNG immediately provides you with a one-way function; just plug in some initial parameters and run the generator! (Whence the implication to P \neq NP; a one-way function is clearly hard-on-average, and a hard-on-average function is clearly hard in the worst case.) It was a longstanding open problem whether the converse was true, whether you could build a PRNG from a one-way function. About a decade ago, Hastad, Impagliazzo, Levin and Luby answered this question in the affirmative in a massive and technically challenging paper. The HILL construction is hugely inefficient, but from a theory standpoint, it shows that the question of the existence of PRNGs is equivalent to the existence of one-way functions.

If you want a PRNG strong enough to derandomize BPP, the question actually becomes a bit easier, and certainly less technical. On the assumption that some problem in E requires exponential-size circuits, Impagliazzo and Wigderson construct such a generator. (The I-W paper is fantastic -- essential reading for anyone interested in derandomization.) It's also known that this is essentially the best we can do, in that derandomizing BPP requires either proving circuit lower bounds for E, or showing that one of several things no one really believes is true. (E.g., P = NP.) This is a result of I think Kabanets and someone in {Impagliazzo, Wigderson, Goldreich}, although I can't remember or find the paper.

share|improve this answer
    
Sorry, I was confused by a number of previous commenters --- you're replying on exactly the level I expected! Unfortunately, I can't undo Community Wiki mode. –  Ilya Nikokoshev Nov 1 '09 at 9:13
    
No problem -- this way someone can add the reference I can't find, anyway. –  Harrison Brown Nov 1 '09 at 9:15
    
So, there is a still one more open question: even assuming P != NP, it is not know whether one-way functions (= PRNG) exist? –  Ilya Nikokoshev Nov 1 '09 at 9:16
    
Right, that's open, and I think the current situation is that we're as clueless about how to approach it as we are to approaching P vs. NP itself. There are also some crypto questions relating to trapdoor OWFs useful in public-key systems, but I don't understand those very well (my interests are more toward derandomization.) –  Harrison Brown Nov 1 '09 at 9:30
    
One detail: there is a particular poly-time computable function that is one-way iff they exist. See cs.cornell.edu/courses/cs687/2006fa/lectures/lecture5.pdf –  Diego de Estrada Oct 21 '10 at 3:39
add comment

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.