Re: Factoring - State of the Art and Predictions

[jrochkin@cs.oberlin.edu (Jonathan Rochkind)]

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.