3 ms·
To say that something is reducible to a conjectured hard problem is what 'provably secure' means in cryptography. Also, cryptographic hardness is not trivially
by 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 agoGood 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.