# Why does most cryptography depend on large prime number pairs, as opposed to other problems?

Most current cryptography methods depend on the difficulty of factoring numbers that are the product of two large prime numbers. As I understand it, that is difficult only as long as the method used to generate the large primes cannot be used as a shortcut to factoring the resulting composite number (and that factoring large numbers itself is difficult).

It looks like mathematicians find better shortcuts from time to time, and encryption systems have to be upgraded periodically as a result. (There's also the possibility that quantum computing will eventually make factorization a much easier problem, but that's not going to catch anyone by surprise if the technology catches up with the theory.)

Some other problems are proven to be difficult. Two examples that come to mind are variations on the knapsack problem, and the traveling salesman problem.

I know that Merkle–Hellman has been broken, that Nasako–Murakami remains secure, and that knapsack problems may be resistant to quantum computing. (Thanks, Wikipedia.) I found nothing about using the traveling salesman problem for cryptography.

So, why do pairs of large primes seem to rule cryptography?

• Is it simply because the it is currently easy to generate pairs of large primes that are easy to multiply but difficult to factor?
• Is it because factoring pairs of large primes is proven to be difficult to a predictable degree that is good enough?
• Are pairs of large primes useful in a way other than difficulty, such as the property of working for both encryption and cryptographic signing?
• Is the problem of generating problem sets for each of the other problem types that are difficult enough for the cryptographic purpose itself too difficult to be practical?
• Are the properties of other problem types insufficiently studied to be trusted?
• Other.
• First, I am pretty sure elliptic curve cryptography is used in practice, though I cannot remember in which situation. Yet you're right that RSA is used a lot more than other cryptosystems. I think the reason is mainly because RSA encryption is some kind of standard for years now, with a lot a (buggy, of course!) software implementing it, and with people used to it. Other encryption systems (based for instance on elliptic curves or lattices) are sometimes usable, but it needs people to acquire them, and this takes time! Change of habits... – Bruno Oct 31 '14 at 13:56
• @Bruno Bitcoin for example uses elliptic curves to sign transactions. – Martin Berger Oct 31 '14 at 15:28
• – Kaveh Nov 1 '14 at 7:14

Boaz Barak addressed this in a blog post

My takeaway from his post (roughly speaking) is that we only know how to design cryptographic primitives using computational problems that have some amount of structure, which we exploit. With no structure, we don't know what to do. With too much structure, the problem becomes efficiently computable (thus useless for cryptographic purposes). It seems that the amount of structure has to be just right.

• Reading that article, I thought of another possible reason that factoring pairs of large primes remains the method of choice for public key cryptography: it's really difficult to find a replacement. The number of mathematicians who understand any given alternative is small, which (1) limits the number of people who can propose alternatives and (2) limits the number of people who can credibly analyze proposals to determine whether they're workable. Primes may not work forever, but they work for now, so inertia keeps them in use. – Steve Nov 5 '14 at 8:27

All of what I am going to say is well-known (all the links are to Wikipedia), but here it goes:

1. The approach used in RSA using pairs of primes can also be applied in a more general framework of cyclic groups, notably the Diffie-Helmann protocol that generalizes $\left(\mathbb{Z}/pq\mathbb{Z}\right)^{\times}$ to an arbitrary group, notably elliptic curves which are less susceptible to the attacks that work on integers. Other group structures have been considered which may be non-commutative but none are in widespread use AFAIK.

2. There are other approaches to cryptography, notably lattice-based cryptography that rely on certain hard problems on lattices (finding points with small norm on the lattice, for example) to implement public-key cryptography. Interestingly, some of these systems are provably hard, i.e. can be broken if and only if the corresponding hard problem in lattice theory can be solved. This is in contrast with, say RSA which does not offer the same guarentee. Note that the lattice based approach is conjectured to not be NP-hard (but seems harder than integer factoring for now).

3. There is a seperate concern to key sharing, namely secret revealing, which has very interesting complexity theory properties. I don't know the details, but the theory of zero-knowledge protocols allows Alice to reveal to Bob her knowledge of a secret which is NP hard to compute (Graph Hamiltonian) without revealing the secret itself (the path in this case).

Finally, you might want to check the page on post-quantum cryptography to see some alternative approaches to public-key cryptosystems that rely on hard problems.