Why study Lattice-based Cryptography? There are a few ways to answer this question.

1. It is useful to have cryptosystems that are based on a variety of hard computational problems so the different cryptosystems are not all vulnerable in the same way.
2. The computational aspects of lattice-based cryptosystem are usually simple to understand and fairly easy to implement in practice.
3. Lattice-based cryptosystems have lower encryption/decryption computational complexities compared to popular cryptosystems that are based on integer factorisation or discrete logarithm problems.
4. Lattice-based cryptosystems enjoy strong worst-case hardness security proofs based on approximate versions of known NP-hard lattice problems.
5. Lattice-based cryptosystems are believed to be good candidates for post-quantum cryptography, since there are currently no known quantum algorithms for solving lattice problems that perform significantly better than the best-known classical (non-quantum) algorithms, unlike for integer factorisation and (elliptic curve) discrete logarithm problems.
6. Last but not least, interesting structures in lattice problems have led to significant advances in Homomorphic Encryption, a new research area with wide-ranging applications.

Let’s look at that fourth point in more detail.

Note first that the discrete logarithm and integer factorisation problem classes, which underlie several well-known cryptosystems, are only known to be in NP, they are not known to be NP-complete or NP-hard. The way we understand their complexity is by looking at the average run-time complexity of the current best-known (non-polynomial) algorithms for those two problem classes on randomly generated problem instances. Using that heuristic complexity measure, we can show that

1. there are special instances of those problems that can be solved in polynomial time but, in general, both problems can be solved only in sub-exponential time;
2. on average, most of the discrete logarithm and integer factorisation problem instances are as hard as each other.

So we believe these two problems to be average-case hard problem classes, but we cannot yet prove that. Interestingly, we know there are quantum algorithms that can solve these two problems efficiently (Bernstein et al. (2009)).