The Idea behind Lattice-Based Cryptography
Or how can lattices be useful for cryprography?
The fear that a quantum computer might be able to crack our existing cryptographic standards is not new. As time goes by, this fear becomes more and more true.
“If large-scale quantum computers are ever built, they will be able to break many of the public-key cryptosystems currently in use. This would seriously compromise the confidentiality and integrity of digital communications on the Internet and elsewhere.” — NIST Post-Quantum Cryptography
Against this background, the need emerged to define new standards for cryptography that would still be secure even with the existence of quantum computers.
For that, the National Institute of Standards and Technology (NIST) has initiated a process to solicit, evaluate, and standardize one or more quantum-resistant public-key cryptographic algorithms. The submission process began in 2016 and ended in 2017, and since then there have been several rounds of evaluation (currently the third) in which the submitted algorithms have been analyzed for standardization. A draft of the standards should be available between 2022 and 2024. More infos here.
The field of lattice-based cryptography is one of the best analyzed areas of post-quantum crypto. The name derives from the fact that this crypto scheme is built on mathematical problems around lattices. But how does it work and, above all, what is the idea behind it?
Introduction
To understand the topic of lattice-based crypto, we need to look at some mathematical basics.
Vector
A vector represents a quantity that has both magnitude (distance) and direction. Vectors can have different dimensions. Most intuitive are vectors in two-dimensional or three-dimensional space.
Basis
A basis is a collection of vectors that can be used to reproduce any point in a given space. For the two-dimensional space, the combination of the following vectors forms a basis.
By combining the two vectors (linear combination), any point in the space formed by the basis can be created. To create the point (12, 8) by linear combination, the first vector must be multiplied by three and the second vector by two.
It is important to note that for a given space, the number of bases is not finite! For the above example, the basis of the unit vectors describes the same space and allows us to generate the identical points as before. Besides bases formed by multiples of unit vectors, all other combinations of linear independent vectors also form a base in the given space.
Lattices
In simple terms, a lattice can be considered as any regularly arranged grid of points. This grid is not finite in any way. Rather, a lattice describes a kind of pattern which continues into the infinite.
One of the most important properties of lattices are that all points of a given lattice consist of integer coordinates.
A lattice is described by a basis of vectors. In the following figure a two-dimensional lattice is visualized. The basis of the two vectors b1 and b2 form this lattice.
As already mentioned, there is no finite number of bases describing a lattice, the next picture shows the same lattice as above, but with a different basis.
Unlike the visulized images, the lattices can also have dimensions higher than two (three, four, up to n).
The Idea
Now that we know what lattices look like, we will take a closer look at the properties of lattices that make them so interesting for cryptography.
A Bad Basis
Consider the following basis for describing a particular lattice.
This basis can be called “bad basis”. But why is it bad? By having a look at the use case of approximation, we can understand why this is the case.
Given a point of the real numbers (11.6, 4.2). The approximation problem asks for the nearest point of a given lattice to challenge this point.
The problem can be solved using the Gaussian elimination for solving systems of linear equations.
The results of the system of linear equations are real numbers for a and b. The problem is that we cannot use these values to calculate the lattice point. As mentioned earlier, lattices consist only of points with integer values. Therefore, we need to round the real numbers up or down to integers. The decision is not easy, but intuitively we would round to the nearest integer, as this would give us the closest result.
By rounding 13.4 down to 13 and -22.9 to 23, the result for the closest lattice point is (9,-2).
Looking at the lattice generated with the given base, the calculated nearest point is far from the actual nearest point of the grid. The green triangle marks the point (11.6, 4.2) and the green dot marks the calculated point (9, -2).
The calculation can be improved by performing all possible options of rounding the real numbers with brute force. For the given example, there are four possible options of rounding. For each coordinate, we can round up or down. The number of variations can be calculated by two to the power of the number of coordinates. For the example, there are the following combinations:
- up, up
- up, down
- down, up
- down, down
Considering a lattice with a dimension of 100, the combinations that must be tested to find the closest point is equal to 1.267.650.600.228.229.401.496.703.205.376. The time to test all these combinations is too long to be practical for finding the closest point.
A Good Basis
The given basis can be considered as a “good basis”.
Compared to the “bad basis” from above, this basis consists of vectors of relatively short length (Euclidean distance), both of which have the property of being orthogonal to each other, i.e. they are perpendicular to each other.
By looking at the same approximation problem as before we can understand, why this basis is considered as good.
As before, the results are real numbers for a and b. Rounding to the nearest integer gives the point (12, 4) as the closest point of the lattice for the calculation with this basis.
This is actually the point of the lattice closest to the given point (11.6, 4.2). So the conclusion is that the quality of the given base (is the base “good” or “bad”) has a significant influence on the possibility to find the actual closest point in the lattice.
The approximation problem is also formally called the Closest Vector Problem.
Closest Vector Problem (CVP)
Given a “bad basis” for some lattice and a randomly chosen point P, the CVP asks to find the closest lattice point to challenge P
How to use this for crypto?
The following schema will demonstrate the idea behind lattice-based crypto systems. It is not secure in this form! This is only for illustration purposes!
The schema follows the pattern of asymmetric key encryption with a public key for encryption and a private key for decryption.
Keys
As a public key, we use a “bad basis” that describes a particular lattice.
For the private key, we use a “good basis” that describes the same lattice created by the “bad basis”.
Encryption
To demonstrate the functionality of encryption with the given scheme, the values 14 and -24 will be encrypted with the lattice-scheme. For better illustration you can think of 14 and -24 as encoding for some letters, e.g. 14 = “h” and -24 = “i”, so we will encrypt the message “hi”.
To encrypt the message “hi” (14, -24), we need to perform three steps.
- First, we need to encode our message in the given lattice space. To do this, we perform a calculation over the basis and the resulting point is the representation of our message in this particular lattice space.
- Second, a vector of small values must be created. These coordinates should be generated at random. This “error vector” is used to add an error to the representation of our message from step one.
- By adding the error vector, we create a point that is not part of the lattice, but is close to the original point. This point now forms the encrypted message that can be shared with the receiver.
For each new message, the error vector is generated anew and is thus different each time, so that there is no determinism in the procedure. Also, the error vector must be small or the decryption will not work properly. Imagine a lattice where each point has the same spacing, as shown in the figure below. Around each point is a space for which a non-lattice point is rounded to the corresponding lattice point. In the middle between two lattice points is an imaginary boundary that defines the mark where rounding changes the result of the nearest lattice point.
In this figure, all points in the red area, like the green triangle, are rounded to the green lattice point. If the point is outside the red rectangle, the closest lattice point changes. Therefore, the error vector must be so small that by adding it to the current lattice point, the resulting point is still part of the imaginary red rectangle.
Decryption
After encrypting the message it’s time to show, that the decryption is working as aspected. For the decryption we have to use the encrypted message and the private key (the “good basis”).
- First, we will calculate the closest lattice point for the given non-lattice point, which represents the encrypted message, using the private key. To do this, we need to solve the system of linear equations with Gaussian elimination.
- After rounding the results of a and b to the nearest integers, we can now calculate the actual closest lattice point.
- Now that we know the actual closest lattice point, we can use this information to decrypt the message. To do this, we need to solve another system of linear equations with the public key.
- The results for a and b of this system then form the decoded message. If we decode the values of the two letters back, we have correctly decoded the message “hi”.
Security
Security for lattice-based crypto in general, and thus for the example above, is based on the hardness of two problems. The fundamental problem of lattice-based crypto is the Shortest Vector Problem.
The Short Vector Problem (SVP) is about finding the closest, but not equal, lattice point with respect to a given point on the lattice.
A problem very closely related to Shortest Vector Problem is the Closest Vector Problem.
Given a “bad basis” for a given lattice and a random point P that is not in the lattice, the Closest Vector Problem (CVP) asks for the closest lattice point to the challenge P .
For a given “bad basis”, the Closest Vector Problem (CVP) is hard to solve. This is shown by two proofs. First, Miklós Ajtai showed that the shortest vector problem (SVP) is NP-hard. Later, Goldreich et al. showed that any hardness of the SVP implies the same hardness for the CVP.
To better illustrate, the difficulty of converting a “bad basis” into a “good basis” can be described by the Shortest Vector Problem (SVP). In order to convert a “bad basis”, which consists of long vectors that are not orthogonal to each other, into a “good basis”, which is defined by short vectors that are nearly orthogonal to each other, an algorithm must be defined that solves the conversion of a long vector into a short vector for the same basis. This algorithm would then also solve the Shortest Vector Problem. Finding an algorithm that determines the closest point of a given lattice with respect to a non-lattice point without converting the “bad basis” to a “good basis” would then solve the Closest Vector Problem (CVP).
