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