The attached file is a brief introduction to lattice theory (in group theory). It covers most of the essential parts that are related to lattice-based cryptography.

Lattices are useful mathematical tools for many applications ranging from combinatorics, number theory, theoretical computer science, to cryptography. The use of lattices in modern cryptography has shown a promising sign of building quantum secure encryption schemes in the era of post-quantum cryptography due to the high confidence that certain lattice problems are computationally hard even with quantum computers.

Lattices are different from vector spaces, but with many similar features. For one thing, given a basis (of a lattice), the lattice can be defined by the integer linear combination of the basis vectors, whilst the (real) linear combination of the basis vectors forms a vector space that spans the lattice.

Below are two examples of lattices. Note a lattice doesn’t always have an orthogonal basis like a vector space, as shown in the second example.

Table of content:

• The first section has some basic definitions of lattices including the important determinant and its invariant property under the choice of basis.
• The second section introduces dual lattice, whose immediate motivation isn’t obvious for now, but does play an important role for specific lattices that will appear in the ring learning with error problem (RLWE).
• The third section states some common lattice problems that are used as the security foundations of cryptosystems. The two most important ones are the shortest vector problem (SVP) and the closet vector problem (CVP).
• The last two sections discuss an important breakthrough in lattice-based cryptography, that is, Ajtai’s worst-case to average-case reduction. It enables later cryptosystems to be built upon worst-case lattice problems (rather than average-case problems whose hardness is often hard to prove).