Tim wrote: > It would be nice to have crypto > systems based on at least problems which have been shown to be > NP-complete.
Even here, one has to be careful. The knapsack cryptosystem, based on the NP-Complete problem Subset Sum, crashed and burned spectacularly a number of years back. The world is replete with NP-Complete problems whose random instances have a near-zero probability of being difficult to solve. I think what you want here, at least for key exchange, is something along the lines of a well-designed message digest function, which has the magic property that f(g(x)) = g(f(x)) so you can do Diffie-Hellman. This would be a lot more difficult to break than either factorization or discrete log, neither of which is likely NP-Hard, and when all the chips have settled, perhaps as weak as N^2. -- Eric Michael Cordian 0+ O:.T:.O:. Mathematical Munitions Division "Do What Thou Wilt Shall Be The Whole Of The Law"
