At 01:28 PM 8/6/03 -0400, Billy wrote:
At 01:18 AM 8/6/03 -0700, Eric Cordian wrote:
What if all things computable are computable in polynomial time?
You mean polynomials like O(n^10^10^10) ?
subset{P} !=> easy
There could still be some protection with some crypto schemes, in such a world, BUT the adversary is assumed to be much better funded, and poly work gives the adversary's algorithmicists (who can be rented cheaply when young) hope that much faster algorithms can be found, if not published :-) You really want the assurance of exponential work to break it, not just big constants. The problem is that, for public key crypto, we want functions which are easy "one way" (if you know the secret) and exponentionally tough in the length of the public key the other. If there is a "quick" (*non-expon*.) solution to your trap-door function then the adversary can reasonably do the extra work and your scheme is toast. For symmetric crypto, the same applies. You can always make *your* key longer, but the "leverage" you get --the extra work the adversary must do-- is much less if you can't demand exponential work by them (because as was suggested, presumably tongue-in-cheek, by EC, there might not be any exponential work problems) --- "The tragedy of Galois is that he could have contributed so much more to mathematics if he'd only spent more time on his marksmanship."