What if all things computable are computable in polynomial time?

[John Kelsey]

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 at ix.netcom.com
PGP: FA48 3237 9AD5 30AC EEDD  BBC8 2A80 6948 4CAA F259