At 02:16 PM 8/6/03 -0700, Bill Stewart wrote: >> >What if all things computable are computable in polynomial time? > >We wouldn't have to go back to OTP, just symmetric-key keyservers >which people used before public-key became well-known. > >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? ... Rambling Aside: RSA encryption is equivalent to spinning a marker on a modulus-sized wheel until it wraps, and decryption is equivalent to spinning the marker more until it points to the original message. "Spinning" is actually exponentiating, ie, advancing the marker some number of positions which depends on its current value. Beautiful stuff, only glimpses visible to this knave. Like IDEA, multiplication is avalanche. ------ "The generation of random numbers is too important to be left to chance." -Robert R. Coveyou ORNL mathematician
