| > First off you have a basic problem in definition: You have to specify | > *one* hash with *one* output size, but NP-completeness has to do with | > asymptotic behavior. For any hash producing a fixed-size output string, | > there is a deterministic machine that runs in time O(1) that computes a | > pre-image. It's a rather large machine that does a table lookup. | | But that could be said of any algorithm, regardless of running time -- | you can precompute it and store it in a big table with O(1) lookup | (well, in reality I think it'd be O(log N) if the table was big | enough). Precomputing every input is brute force, time-shifted | backwards, and brute force is the metric we'd like to match... You missed the point. Yes, you can do this for any algorithm. But the security claims for, say, DES include the cost of doing the pre-computation.
NP-completeness, on the other hand, has "security claims" that are asymptotic: As n grows, the complexity grows more than any polynomial in n. The definition makes no sense for fixed n. Knowing the asymptotic complexity tells you nothing about the difficulty for any particular n. It simply makes no statements about difficulty for any particular n. That's why NP-completeness has no real cryptographic significance, except perhaps as a pointer to problems that you *might* be able to use as a basis for a cryptosystem. (In fact, I don't know of any cryptographic system in actual use that is based on an NP-complete problem. The best-known attempts in this direction - public-key systems based on the knapsack problem - failed. So even the heuristic approach doesn't seem to have borne fruit.) -- Jerry --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]