What if all things computable are computable in polynomial time?

Major Variola (ret) mv at cdc.gov
Wed Aug 6 15:50:35 PDT 2003


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





More information about the cypherpunks-legacy mailing list