Re: What if all things computable are computable in polynomial time?
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
At 03:50 PM 08/06/2003 -0700, Major Variola (ret) wrote:
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?
No. NP is the set of problems which can be solved in poly time on a non-deterministic Turing machine, i.e. which can be solved in poly time if the magic oracle correctly tells them a poly number of answer bits. Not all exponential problems fit this model.
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
participants (3)
-
Bill Stewart -
John Kelsey -
Major Variola (ret)