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