complexity classes and crypto algorithms

Leichter, Jerry leichter_jerrold at emc.com
Wed Jun 21 07:19:30 EDT 2006


| > 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 majordomo at metzdowd.com



More information about the cryptography mailing list