At 03:50 PM 8/6/03 -0700, Major Variola (ret) wrote:
At 02:16 PM 8/6/03 -0700, Bill Stewart wrote: ...
While the public-key algorithms are based on math problems like factoring or discrete log, most of the symmetric-key algorithms are based on intractable ugliness, and on doing enough analysis to find out which kinds of ugliness and bit-twiddling are really intractable and which can be cracked.
Yes, but the cryptanalysis of symmetric ciphers involves exponentially-expanding "back trees". That is the whole point of "avalanche". If, somehow, "for any NP algorithm there were an equivalent P algorithm", then the block-cipher backtracking would be solvable in poly time. You could find the plaintext ASCII needle in the haystack of possibilities in poly time, no?
There's no reason to think those backtrees wouldn't get too hard to follow even without superpolynomial problems to solve. After all, finding a collision in SHA-512 is O(1), as is brute-forcing a 256-bit AES key. There's just a really big constant term. Honestly, I think for real-world cryptography, we need about an N^3 advantage or so between defenders and attackers--the defenders do 2^{25} work, and the attackers have to do 2^{75}, say, to break it. Merkle's puzzles and all the related schemes give you N^2, and that's not *quite* enough to be useful. ... --John Kelsey, kelsey.j@ix.netcom.com PGP: FA48 3237 9AD5 30AC EEDD BBC8 2A80 6948 4CAA F259