Re: Factoring - State of the Art and Predictions

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

"James A. Donald" says:
> So far no one has found a way of applying NP problems to
> Crypto.

Further than that, it has been shown that a large class of ways to
apply NP complete problems to crypto are insecure -- this being
generalizations of the break of the knapsack problem based
cryptosystems...

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

Most of the eliptic curve stuff maps pretty straightforwardly into
the "normal" case and vice versa.

.pmm