Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
For RSA and El Gamal (and most other public key cryptosystems), one of the key ideas is that factoring and finding discrete logarithms are hard. There are other systems that rely on certain properties of lattices.
What are the other one-way-ish functions that have cryptosystems designed around them?
The Merkle–Hellman knapsack cryptosystem was based on a variation of the subset sum problem. (It was broken by Adi Shamir a few years after it was developed.)
Given a set of numbers $A$ and a number b, find a subset of $A$, which sums to b.
The cryptosystem relies on the fact that in this form of the subset sum problem if the set $A$ is superincreasing (each element of the set is greater than the sum of all the previous elements), the problem is solvable in polynomial time. Also, you can transform the superincreasing set $A$ into a non-superincreasing set $B$ using a multiplier $r$ and a modulus $q$.
Solving the subset sum problem with a non-superincreasing set ($B$) is NP-complete, so you can use $B$ as a public key to encrypt messages, then use $A$, $r$, and $q$ as a private key to decrypt them.
Many lattice schemes are based on the shortest vector problem and it's variants. Elliptic curve crypto systems are based on something akin to discrete logarithms but it is different in its details. Some authentication schemes like HB are based on learning parity with noise and systems are based on the more general learning with errors. Subset sum was mentioned. Decoding information sets is the basis of McEliece. The conjugacy search problem is ostensibly the basis of some cryptography in braid groups.
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.
