# Are there asymmetric cryptographic algorithms that are not based on integer factorization and discrete logarithm?

In the computer security class (in which cryptography is a big chapter) that I took, I remembered the professor said about current asymmetric cryptography algorithms are based on integer factorization (i.e. prime numbers) and discrete logarithm.

So my question is, are there any asymmetric cryptographic algorithms that are not based on these two mathematical fields? Is it that hard to come up with a strong algorithm without using prime numbers and logarithm?

-

Yes there are other hard problems you can base asymmetric cryptography on.

Lattices. The NTRU systems is based on the shortest vector problem in ideal lattices. Lattice-based cryptography is of much interest these days for two reasons: (1) unlike factorization and discrete logarithms, there isn't an efficient algorithm for breaking these problems on a (still theoretic but should happen within our lifetime) quantum computer; (2) you can use lattice-based systems to do arbitrary operations on data while it is still encrypted (not with NTRU though but other lattice-based systems).

Coding Theory. The McEliece system is based on decoding linear codes. It is a very old system but recently has seen renewed interest for the same post-quantum reasons as lattice-systems.

Misc. There are other more obscure (research-level) cryptosystems based on things like learning parity with noise, learning with error (related to SVP in lattices), subset sum problem (including a famous broken example), solving multivariate or diophantine equations, etc.

In response to your second question, is it that hard to find alternatives, the answer is it is reasonably hard. For most cryptographic primitives, you need to find examples of functions that are hard to invert, and for asymmetric encryption specifically, you are generally interested in functions that have a specific value that allow them to be inverted (but only if you know that value). See trapdoor functions. It is difficult to find new candidates for trapdoor functions and to establish they are suitably hard.

-

"Discrete logarithm" is a wide class. Originally, this means that we work in a finite field (e.g. integers modulo a big prime) and, given $g$, $p$ and $g^x \bmod p$, it is computationally difficult to recover $x$ (it becomes impossible with today's technology once $p$ is big enough).

At some point, someone noticed that discrete logarithm was a special case of a larger situation, applied to a generic group. As such, we could use other kinds of group, in particular elliptic curves. Confusingly, this is also called "discrete logarithm" although the involved mathematics are quite distinct. There are generic algorithms for breaking discrete logarithm, which work on all groups but are expensive; and there are faster algorithms which only work in the original discrete logarithm group (integers modulo a big prime).

There is a fairly general theorem due to (I think) Gilles Brassard, which says that any hard NP problem (in short words, a problem for which no fast solving algorithm is known, but for which a given solution can be verified efficiently) is amenable to being turned into a zero-knowledge proof, which, when turned into a non-interactive zero-knowledge proof, can become a digital signature algorithm. The trick, however, is to find a problem such that the corresponding signature algorithm is tolerably fast; Brassard's theorem is about asymptotic behavior: given sufficiently large parameters, there is a wide enough performance difference between using the algorithm and breaking it, but nothing guarantees that the "using" part is actually doable on a computer which exists right now.

@PulpSpy talks about lattices and coding theory. The subset sum problem (also called "knapsack") is traditional but all the fast variants were broken by lattice reduction; one remaining unbroken knapsack cryptosystem is due to Naccache and Stern, but that algorithm uses multiplications where the older schemes used additions, and this makes it quite unattractive, performance wise. Another kind of problem which looks promising is multivariate quadratic equations; the corresponding asymmetric algorithms being HFE (encryption) and Quartz and Sflash (signature). They potentially allow very small signatures (e.g. 128 bits) but their security is still debated.

-

There is also the knapsack cipher. But using it well it even more challenging, as it is known that the knapsack is in some way breakable (which is unknown about the more general knapsack problem).

-