At 7:12 PM 02/12/95, Zachary wrote:

This touches on something I was thinking the other day: Most cryptosystems that we seem to use are based on the assumption that factoring large numbers is a Hard Problem. Isn't this putting all our eggs in one basket? Are there other Hard Problems crypto systems can be

Keep in mind that it's been mathematically proven that factoring is NP-complete. That is, it's in the set of problems including such things as discrete logs and the travelling salesman problem, such that if a polynomial time solution is found to _any_ of these problems, one can be found for all of them. Of course it hasn't been proven that none of the problems in NP can be solved in polynomial time, so it hasn't been proven that these are "hard problems". But I suspect that most problems suspected to be Hard Problems that one could base a crypto system off of, are also NP-complete, so it wouldn't be any better to use them then to use factoring. Logarithms, for instance, are used in some crypto systems, and are another suspected Hard Problem, but are also NP complete. So if factoring is solved, discrete logarithms will be solved too. At least that's how I understand it.