Lattice-based cryptography is the most important area of post-quantum cryptography. It is known for its efficiency and versatility, with use cases ranging from the foundational building blocks of cryptography to highly complex protocols.
The National Institute of Standards and Technology (NIST) is standardizing a collection of algorithms through the Post-Quantum Cryptography (PQC) Standardization Process, which will influence the landscape of digital security for the coming decades. NIST is currently in its third round of narrowing the candidate algorithms. The most prominent key establishment and digital signature candidates left in this standardization process are lattice-based.
What are the Advantages of Lattice-Based Cryptography?
Our dedicated team of researchers have scrutinized the lattice-based submissions to NIST’s post-quantum cryptography standardization process and have identified the most promising submissions. Our developers then worked hard to program efficient implementations of these algorithms. They have also integrated these algorithms into OpenSSL. This makes it easier for organizations to evaluate the use of lattice-based cryptography as part of their products and networks
We can visualize a lattice as a multi-dimensional grid, like the one in the following diagram.
How do these grids allow us to form a cryptographic algorithm? Generally, the security of a cryptosystem is based on one or more hard problems.
Hard problems are ones that can only be efficiently solved if you have some extra secret information. In the case of lattice-based cryptography all the hard problems involve lattices in some way.
One example of a lattice problem that cryptographers believe is hard to solve in general is the following:
Short Integer Solution Problem (SIS): Suppose we are given a random matrix A with entries between 0 and a number q. The problem is to find a “short” vector x that is a solution to the equation
Ax ≡ 0 (mod q).
You might wonder how the SIS problem is related to lattices. The set of vectors x that are solutions (of any length) to the equation Ax ≡ 0 ("mod" q) can be plotted in a grid-like structure, i.e., as a lattice. The SIS problem is to find a solution x that is close to, but not equal to, the origin. For example, consider the lattice diagram below. The challenge is to find a point that is within the red circle, but which is not the blue point.
Technical Aside: There are some extra conditions that are needed for this problem to be difficult to solve. For example, if the matrix has certain dimensions, then this problem is trivial to solve. Typically lattice problems are easy to solve in 2-dimensions but become harder to solve as the dimensions increase.
How can we use SIS to create a cryptosystem? It is possible to generate a matrix A together with secret information that makes SIS easy to solve for the owner of the secret information, and hard to solve for anyone else. Furthermore, finding the secret information is also difficult. This idea can be used to create signature schemes (for example, Falcon, a NIST PQC 3rd Round Candidate).
In terms of specific algorithms, Falcon and Dilithium (another NIST PQC 3rd Round Candidate) base their security on hard lattice problems which include the SIS problem.
Another hard problem is the following:
Learning With Errors Problem (LWE): Suppose we are given a random matrix A with entries between 0 and a number q. Further suppose there is an unknown vector s and an unknown “short” vector e. The problem is to find s given only the matrix A and the value sA+e ("mod" q).
The set of all the possible values of xA, where x is allowed to vary, forms a lattice (the blue and black points of the grid illustrated in the diagram below). We can think of the green point in the diagram below as a point of the form b=sA+e that is close to a particular lattice point sA (the blue point). The idea that these two points are close corresponds to the fact that e is a short vector, also known as an error vector.
The LWE problem can be intuitively thought as being given a point of the form b=sA+e (the green point) and being asked to find the point on the grid that is close to b (the blue point).
As with SIS, there is information that can make LWE easier to solve, but the information is difficult for anyone to obtain when A is a randomly chosen matrix. For example, the security of many of the NIST PQC candidate key encapsulation mechanisms (Kyber, Saber, and FrodoKEM) and signature algorithms (Dilithium) are based on problems that are related to LWE.
Technical Aside: Sometimes you might see a discussion of a Ring or Module version of LWE, SIS, or another lattice problem. These are basically the same hard problems instantiated over more complex mathematical structures (rings, modules, etc.) for efficiency.
Some of the other schemes (NTRU, NTRU Prime, and Falcon) use a problem called the NTRU problem. On the surface the NTRU problem looks a little different than the above lattice problems, however, the algebraic structures involved can be reinterpreted as lattices.
Overall, the candidates for the NIST post-quantum standardization process are based on many hard problems. However, those based on lattices seem the most promising so far. That being said, other areas of post-quantum cryptography will likely yield algorithms for special use cases which cannot be addressed as well by using lattice-based algorithms. For more details see our blog posts on hash-based cryptography and isogeny-based cryptography.