To say that something is reducible to a conjectured hard problem is what 'provably secure' means in cryptography. Also, cryptographic hardness is not trivially relatable to P vs. NP, especially for hardness assumptions used to build public-key systems. For example, a poly-time factoring algorithm would not prove P == NP, but it would break RSA.

Good point, thanks. It looks like a few of them, including factorization and the discrete log problem, are conjectured to be NP-intermediate; that is, NP but neither P nor NP complete. However, this class may actually be empty, and is only non-empty if P != NP.

If P = NP, NP-intermediate is necessarily empty, so problems like factorization would be P = NP = NP-complete. You're right, though: the existence of a (classical) polynomial-time factorization algorithm doesn't solve P = NP.

> Edit: On reflection, I think the parent is saying that there was never a proof published that Dual_EC_DRBG is reducible to a hard problem, and without that we cannot even say whether Dual_EC_DRBG is as secure as other PRNGs that can be shown to be related to hard problems.

Yes, that was what I meant to say. There are elliptic curve PRNGs for which it is proven that breaking their security properties allows you to calculate the discrete logarithm on the elliptic curve. IIRC, no such proof is publicly known for Dual_EC_DRBG, even under the assumption that both points P and Q were chosen at random.

If you have specifically crafted the points (you know the logarithm of Q to base P), then breaking Dual_EC_DRBG is trivial. And by "breaking" I mean recovering the internal state of the PRNG out of its output.