What if all things computable are computable in polynomial time

[Major Variola (ret)]

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."