That fragile foundation is the P versus NP question. Much of current cryptography is based on the NP problem Factoring which would have an efficient algorithm if P were equal to NP. If P = NP than no other method of public-key cryptography would be possible either. However, as I have argued before, the loss in public-key crypto would be greatly offset by the gain in efficiency of nearly every other aspect of our lives. Encryption's doom would be society's gain.
Factoring is not believed to be NP-complete and we could have the worst of all possible worlds with no cryptography and no new algorithms for problems we care about, one of five possibilities explored by Russell Impagliazzo.
Racing to dismantle is a bit of an overstatement. First of all we have nothing to worry about. As Juris Hartmanis once said, "We all know that P ≠ NP, we just don't know how to prove it." Remember too that all mathematics is based on unprovable assumptions about consistencies of logical theories. Doesn't seem to seriously bother anyone.
The article quotes Adleman as saying "From my perspective, we are no nearer to solving the problem now that we were when bell-bottom pants were cool." Adleman is an optimist; we do not even currently have a good approach to showing P ≠ NP. We are much further away from solving the problem than ever before.
The fact that "all mathematics is based on unprovable assumptions about consistencies of logical theories" is true but not really very relevant. It's inconceivable that Peano arithmetic or Euclidean geometry is inconsistent (if I thought anyone seriously believed that, not simply in the role of devil's advocate, I would consider that person insane). Even if ZFC were inconsistent it's hard to imagine that it would cause more harm than amending an axiom, leaving 99.99% of all mathematics unchanged, the same way the contradictions in Frege's axioms caused no global problems in mathematics. By contrast, nobody could claim that P != NP is as obvious as the consistency of PA, and the consequences could be far more dramatic. (If P=NP, then even if no practical algorithms ever came out of it, a lot of modern complexity theory would look like wasted effort. Perhaps much of it could be salvaged to deal with finer distinctions than simply P vs. NP, and of course much of it deals with unrelated questions in the first place, but the consequences would still be huge.)
ReplyDeleteHmmm... what are reasons why we "know" P!=NP. My basic intuition is that NP-complete is "more complex" than P - presumably according to some complexity measure - but given the negative results about the ability of complexity measures to seperate complexity classes, that intuition seems just wrong.
ReplyDeleteP!=NP and Con(ZF) are both useful assumptions allowing us to get on with practical cyptography and mathematics respetively. (Assuming P=NP would seem pretty useless - without an actual working algorithm, P=NP doesn't achieve anything).
It's tempting to suggest a purely psychological explanation for our belief in both P!=NP and Con(ZF) - that we tend to blur the distinction between useful and true.
That article is reporting the recent breaks of md4, md5, and sha-0, none of which are related to factoring. Our symmetric key cryptography is in some sense even shakier than our public key cryptography, because there's no simple mathematical primitive which it's based on.
ReplyDelete-Bram