3 ms·
Is there actually much cryptography based on NP-hard problems? Neither integer factorization nor elliptic curves are known to be NP-hard, for example. The first
by _delirium 16y ago
Is there actually much cryptography based on NP-hard problems? Neither integer factorization nor elliptic curves are known to be NP-hard, for example. The first part of your statement is still true (if P=NP, then RSA would be breakable in polynomial time), but I don't think the second part is (proving P!=NP doesn't prove that integer factorization is outside P).
- eru 16y agoCryptography is usually in the intersection between NP and co-NP: NP means a yes-answer is easy to check, co-NP means a no-answer is easy to check. If you are trying to break some encryption you can usually tell quite easily whether you get the right key or not. It would be a major breakthrough (comparable to P=NP) if anyone could show that the intersection of NP and co-NP is equal to NP. Some people tried to make an encryption system out of the knapsack problem (http://en.wikipedia.org/wiki/Merkle%E2%80%93Hellman_knapsack_cryptosystem http://en.wikipedia.org/wiki/Merkle%E2%80%93Hellman_knapsack...). It makes a good read about how a promising cryptosystem was broken. Some interesting tid-bit: Even if P != NP, it could still be that most instances of NP-hard problems are easy to solve. (I.e. it's possible that even for NP-hard problems the expected running time is polynomial for all realistic probability distribution of instances. For certain definitions of `realistic'.)