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

Question

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.

Answer 1

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.

Answer 2

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.