I will just like to contribute in light of what has been told above. There are few cryptosystems (just signature schemes as far as my knowledge goes) that are based on the hardness of solving a system of multi-variate polynomial. Solving a system of multi-variate polynomial is proved to be $\mathsf{NP}$-hard and just like the "hard" problems on lattices, they have resisted serious quantum attacks. Constructing a secure encryption scheme based on multi-variate polynomials is still an open problem.
People have also used abstract concepts like Fractal to construct cryptosystem based on Mandelbrot sets, but for some reason, it never attracted too much attention though it is considered to be secure against quantum attack.
A recent work that constructed public key primitives that are as secure as subset sum was proved in TCC 2010 by Lyubashevsky et. al. It is a good paper to read as it gives a very good description of the relation between hardness of some lattice based problem and subset sum. So, in light of recent works, you can count subset-sum as another problem on which cryptographic primitives are based.
Frankly, this list can go on and on forever, but I think these are the few that are worth mentioning in addition to the one that are already been mentioned, especially if you are interested in post-quantum cryptography.