> 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

> 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.