Re: What if all things computable are computable in polynomial time?
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.
Re: What if all things computable are computable in polynomial time
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.
Re: What if all things computable are computable in polynomial time?
What if all things computable are computable in polynomial time? Lots of problems are only computable in exponential time, or at least superpolynomial time. The closest we'd get to your suggestion is that P might equal NP, or (for crypto) factoring might be in P. Sufficiently large polynomials are easier in theory than in practice - Karmarkar's polynomial solution to Linear Programming was something like N**12 or L*N**6 where L was a very large number. We would have to go back to paper and OTP, but we would also get to enjoy the excellent graphics, AI, number theory, etc, that we would win. 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. If the polynomial computability comes from quantum computers, some of the symmetric stuff seems to reduce from 2**N time to 2**(N/2) time, so we might need to upgrade from 3DES to 5DES or 7DES, but it's not big deal.
Re: What if all things computable are computable in polynomial time?
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, [EMAIL PROTECTED]
PGP: FA48 3237 9AD5 30AC EEDD BBC8 2A80 6948 4CAA F259
What if all things computable are computable in polynomial time?
At 01:18 AM 8/6/03 -0700, Eric Cordian wrote: An anonymous sender writes: Rely on math, not humans. What if all things computable are computable in polynomial time? RSA, Inc. stock would go down. We would have to go back to paper and OTP, but we would also get to enjoy the excellent graphics, AI, number theory, etc, that we would win.
