3 ms·

Pardon me if I'm misinterpreting you, but isn't the existence of one-way functions equivalent to P != NP? So far we definitely haven't proved/disproved that one

Pardon me if I'm misinterpreting you, but isn't the existence of one-way functions equivalent to P != NP? So far we definitely haven't proved/disproved that one-way functions exist, so any primitive that relies on them is not provably secure. More generally, I don't think there are any CSPRNGs that are actually provably secure; please correct me if I'm wrong. The proofs all rely in some way on problems that are conjectured to be hard, which depends on P != NP. This isn't necessarily the case, if we could devise an algorithm that depends on a decidable problem harder than NP-complete, but I don't think we have proved if any such problems exist. 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.

swordswinger12 12y ago
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.
- AngrySkillzz 12y ago
  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.
Perseids 12y ago
> 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.

swordswinger12 12y ago

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.

AngrySkillzz 12y ago
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.

Perseids 12y ago

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