Re: Factoring - State of the Art and Predictions

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.

On Sun, 12 Feb 1995, Jonathan Rochkind wrote:
> 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. i

This is news to me!

I am fairly sure that factoring and discrete log are *not*
NP complete, and indeed there is no known way to use
NP complete problems for crypto.


 ---------------------------------------------------------------------
                                          |  
We have the right to defend ourselves     |   http://www.catalog.com/jamesd/
and our property, because of the kind     |  
of animals that we are. True law          |   James A. Donald
derives from this right, not from the     |  
arbitrary power of the omnipotent state.  |   jamesd@netcom.com

Johnathan Rochkind writes:
>
>Keep in mind that it's been mathematically proven that factoring is
>NP-complete.
...

No it hasn't.  Factoring is believed to be hard, but no one has ever
shown it to be NP-hard (let alone NP complete).

...
>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.

Ditto for discrete log.

-matt