complexity classes and crypto algorithms

[leichter_jerrold at emc.com]

| What kind of problems do people run into when they try to make
| cryptographic algorithms that reduce to problems of known complexity?
| I'm expecting that the literature is full of such attempts, and one
| could probably spend a lifetime reading up on them, but I have other
| plans and would appreciate a summary.
| 
| In particular, it seems like you should be able to make a respectable
| one-way function out of 3SAT.
This is an idea that keeps coming up.

Suppose you had such a thing - for example, a one-way hash in which you
could prove that calculating a preimage inverse as NP-complete.

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.

So, suppose you take the obvious approach - all you'd get out of 3SAT -
and said that you had a family of hash functions H_i, each producing
an i-bit output; and you made an NP-completeness argument about that.
Then the family H_i' defined by:

		H_i'(X) = 0       for all i < 10^100 and all X
		H_i'(X) = H_i(X)  otherwise

would satisfy the same NP-completeness predicates, but would be of no
conceivable use to anyone.

Finally, even if you get around all of that, NP-completeness is a
statement about *worst case* behavior.  All it says is that *some*
instances of the problem are hard.  It could well be that "almost all"
instances are easy!  The simplex algorithm, for example, is actually
known to have instances that require exponential time, but is widely 
used because in practice it's "always" fast - an empirical
observation that has been confirmed by analysis which shows that
not only is it polynomial time on average (for some appropriate
notion of randomized inputs), but it's even true in a stronger sense 
("smoothed complexity", which beyond the description as being "somewhere 
between average- and worst-case complexity" I haven't looked at).

							-- Jerry


---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com