From: "James A. Donald" <jamesd@netcom.com>
Date: Sun, 12 Feb 95 17:09:06 PST
To: cypherpunks@toad.com
Subject: Re: Factoring - State of the Art and Predictions
Message-ID: <Pine.3.89.9502121608.A20084-0100000@netcom10>
MIME-Version: 1.0
Content-Type: text/plain


Zachary <zachary@pentagon.io.com> wrote:
 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 based on?

There is of course the discrete log problem - DH and all that.

Unfortunately, although the discrete log problem has not been
shown to be equivalent to the factoring problem, every 
factoring advance immediately leads to a corresponding
discrete log advance and vice versa, and the two problems
take a very similar length of time to solve, suggesting
that the two problems have some deep equivalence.

So far no one has found a way of applying NP problems to
Crypto.

And that pretty much wraps it up.

There are of course a lot of hard problems that are not NP,
yet probably take exponential time, but obviously you
want a well understood problem that is part of conventional
mathematics.

This narrows the field rather drastically.

Discrete log and factoring pretty much covers it.

Of course you can do discrete log on weird fields -- there
is a lot of research in that which I do not understand at all.

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