Question

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.

Answer 1

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.