What if the proof that P!=NP is wrong and it turns out that P=NP?<p>I've heard people say that this kills encryption, or at least public-key cryptography. But does it? Perhaps it wouldn't be as dreadful as people think.<p>Here is my take on why cryptography will survive even if P=NP:<p>1. One-time pads are provably secure. No matter what's discovered in mathematics, one-time pads will continue to give perfect secrecy for pre-arranged messages with people you know. Yeah, it's no good for online commerce, https, etc.<p>2. Quantum cryptography will still be secure. It needs new hardware and can't be implemented purely in software.<p>3. Focusing on RSA, P=NP implies that factoring has a polynomial-time solution. OK, so the fast algorithm must exist, but who's to say that it'll be found even within the next 100 years? It's the same situation as we have now and we manage to live with the uncertainty.<p>4. Sticking with RSA, maybe the "fast" factoring algorithm will turn out to have order n^1000. So factoring a 1000-bit RSA key will take up to 1000^1000 steps. In comparison, an exhaustive search for a 256-bit AES key takes around 2^256 steps. Since 1000^1000 is much greater than 2^256, and we consider AES to be secure, we should consider that RSA would remain secure as well.<p>5. Again with RSA, let's suppose that a fast factoring algorithm is found and that it is indeed fast -- say on the order of n^10. That means that a 1000-bit RSA key can be cracked in 1000^10 = 10^30 steps; that's about 2^100. That would be much better than DES (2^56) but much worse than any key size of AES.<p>But there's an obvious solution: just increase the RSA key size to 1,000,000 bits. Now the work factor is 1000000^10 = 10^60; that's about 2^200. Now you're back in the neighborhood of AES again -- not as good as AES256, but a lot better than AES128.<p>Million bit RSA keys shouldn't be a problem on any modern computer except maybe smartcards. A million bits is only 125 kilobytes; we're constantly loading 100 KB images when we're browsing, so a few 125 KB key exchanges during an https connection shouldn't pose a bandwidth problem either.<p>6. It might be possible to invent public-key cryptosystems that use complexity classes beyond P and NP. Does any already exist?<p>I'm certain about #1, but I'd like to know if I've made mistakes or wrong assumptions on the other points.