8
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • $\begingroup$ I think I'll prepare better and post a reworded question. $\endgroup$
    – Ilya Nikokoshev
    Commented Oct 24, 2009 at 17:21
  • $\begingroup$ Sorry, my previous comment was unnecessarily confrontational. I'll delete it. $\endgroup$
    – S. Carnahan ♦
    Commented Oct 24, 2009 at 17:46
  • 1
    $\begingroup$ I'm confused by what you're looking for exactly. Proving the (unconditional) existence of a pseudorandom generator would imply P ≠ NP. $\endgroup$
    – Richard Dore
    Commented Oct 31, 2009 at 20:12
  • $\begingroup$ 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. $\endgroup$
    – Ilya Nikokoshev
    Commented Nov 1, 2009 at 8:13

1 Answer 1

Reset to default
11
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ No problem -- this way someone can add the reference I can't find, anyway. $\endgroup$
    – Harrison Brown
    Commented Nov 1, 2009 at 9:15
  • $\begingroup$ So, there is a still one more open question: even assuming P != NP, it is not know whether one-way functions (= PRNG) exist? $\endgroup$
    – Ilya Nikokoshev
    Commented Nov 1, 2009 at 9:16
  • $\begingroup$ 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.) $\endgroup$
    – Harrison Brown
    Commented Nov 1, 2009 at 9:30
  • $\begingroup$ 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 $\endgroup$
    – didest
    Commented Oct 21, 2010 at 3:39
  • $\begingroup$ To be clear, if general purpose pseudorandom generators exist, then we have $\mathbf{P}=\mathbf{BPP}$? $\endgroup$
    – Andrew
    Commented Oct 11, 2016 at 18:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .