[My Computational Complexity Web Log] Is Encryption Doomed?
Considerable Slashdot discussion about a Technology Review article Is Encryption Doomed? subtitled Our entire information society rests on a fragile foundation that mathematicians are racing to dismantle.
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 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.
Posted by Lance to My Computational Complexity Web Log at 9/2/2004 04:12:09 PM