# Vagrant

Noah Berner

This is how Lattice-Based Cryptography and GGH works

- The algorithm is based on hard computational problems within the mathematical concept of lattices
- The problem of finding a closest lattice vector (CVP) for a given point is thought to be hard both on classical and quantum computers
- The concept of good and bad lattice bases is introduced
- The GGH protocol uses the CVP for asymmetric cryptography

In simple terms, a lattice can be described as an infinite number of points on a periodically spaced grid. Before giving a more rigorous definition, we will first look at few mathematical concepts.

A vector is a mathematical object that has a length and a direction, much like an arrow drawn on a piece of paper. For the purpose of this article, we will limit ourselves to two-dimensional space and two-dimensional vectors. These 2D-vectors are described by two numbers. For example the red vector can be described as (2, 1) and the blue vector can be described as (3.14, -0.5).

A basis is a set of vectors that allows us to reach any point in space by linearly combining them. For example, if we are given the basis:

B = {b_{1} = (2, 0), b_{2} = (0, 1)}

we can reach the point P = (4, -1.5) by linearly combining b_{1} and b_{2} in the following way:

P = 2 * (2, 0) – 1.5 * (0, 1) = (4, -1.5)

Note, that the number of bases for a given space is infinite. As long as two chosen vectors are linearly independent (one vector cannot be the result of a linear combination of the other), they can be used as a basis for the two-dimensional space.

Now that we have a basic understanding of what a vector and a basis is, we can properly introduce a lattice. It is the set of all integer linear combinations of vectors from a basis { b_{1},b_{2} } of ℝ^{2}, which can be summarised as:

L = { a_{1} b_{1} + a_{2} b_{2} : a_{i} ∈ ℤ}

This means, that while the basis vectors b_{1} and b_{2} can have arbitrary real numbers as elements, like 1.5, 8 and π, the factors of the linear combination a_{1} and a_{2} can only be integers, like -3, 0 and 7. This definition of lattices gives them their periodic behaviour.

Much like with two-dimensional space, there is an infinite number of basis vectors that describe a given lattice. Below is an image of the same lattice as above but with different basis vectors.

To use lattices as post-quantum-cryptographic tools, we must find problems that are hard to solve both on classical and on quantum computers. There are several such lattice problems, which are believed to be hard. We will look at the closest vector problem (CVP). In the CVP, the goal is to find the closest lattice point to a given point which is not necessarily on the lattice. To give further intuition on this problem, we will look at the concept of good and bad bases.

In this context, a bad basis is a lattice basis, for which it is hard to determine the closest point of a lattice for a given point. Consider the following basis:

B_{bad} = {b_{1} = (6, 21), b_{2} = (4, 15)}

Say we want to find the closest lattice point to the point P = (11.5, 8.4). Then we need to solve the following system of equations:

a_{1} * (6, 21) + a_{2} * (4, 15) ≈ (11.5, 8.4)

This can be solved by Gaussian elimination. The result of that calculation is a_{1} = 23.15 and a_{2} = -31.85. However, remember that we are looking for a lattice point and that lattice points only allow integer multiple of the basis coordinates. If we try to round to the nearest integer, we get a_{1} ≈ 23 and a_{2} ≈ -32. This gives us the approximative lattice point:

P_{L}’ = 23 * (6, 21) – 32 * (4, 15) = (10, 3)

This is not a great approximation for the actually closest lattice point P_{L} = (12, 9). This demonstration shows that our simple rounding algorithm is in general no good when using a bad basis.

A good basis is a lattice basis which has short and nearly orthogonal vectors. We will see, that for such a basis, it is easy to determine the closest lattice point for a given point. Let us use the same lattice as before, but this time defined by the good basis:

B_{good} = {b_{1} = (2, 0), b_{2} = (0, 3)}

We still want to find the closest lattice point to the point P = (11.5, 8.4) and solve the linear system of equations:

a_{1} * (2, 0) + a_{2} * (0, 3) ≈ (11.5, 8.4)

The result is a_{1} = 5.75 and a_{2} = 2.8. If we again round to the nearest integer we get a_{1} ≈ 6 and a_{2} ≈ 3 and the following approximate lattice point:

P_{L}’ = 6 * (2, 0) + 3 * (0, 3) = (12, 9)

which is equal to the actual nearest point P_{L} = (12, 9). Thus for good basis, the rounding algorithm provides an accurate result.

Notice the asymmetry in hardness of the same problem between the two given bases. This asymmetry will allow us to construct an asymmetric cryptography protocol.

We now present a simplified version of the GGH cryptosystem. It uses the CVP and the concept of good and bad bases to construct an asymmetric cryptography protocol.

The GGH cryptosystem has a public and a private key. The private key B = {b_{1}, b_{2}} is a good basis of the lattice L. The public key B’ = {b’_{1}, b’_{2}} is a bad basis of the lattice L.

To encrypt a message m = (m_{1}, m_{2}), we generate a ciphertext by multiplying the message with the public key and adding a small, random error e = (e_{1}, e_{2}):

c = m * B’ + e = (m_{1} * b’_{1} + e_{1}, m_{2} * b’_{2} + e_{2})

Note that the error is added, so that the ciphertext-point is not directly on the lattice. The error has to be small enough, so that the ciphertext-point is still closest to the original lattice point (without the error) in order to ensure correct decryption.

In the decryption phase, we calculate the closest lattice point to the given ciphertext-point. For this, the private key and good lattice basis B is necessary. We use Gaussian elimination just like before to solve the linear system of equation:

a_{1} * b_{1} + a_{2} * b_{2} ≈ c

Then we round a_{1} and a_{2} to their nearest integer which gives us the original message m = (m_{1}, m_{2}).

It was shown by Nguyen that the GGH encryption scheme has a design flaw where the ciphertext reveals information about the plaintext which then reduces the hardness of the CVP. Even though, the GGH scheme is not secure in practice, it is still an easy-to-understand example to show how the hardness of lattice problems can be turned into an encryption scheme.

So, is that it? Are we saved from the unnerving future where quantum computers break all our cryptography and everyone can read everything? If the history of classical cryptography has taught us anything, it is that finding and implementing a secure encryption scheme is really hard. Add to that, that these post-quantum cryptography schemes must be resilient to both quantum and classical attacks and that they have had less time to mature and be tested and you see why it might be a long journey to true post-quantum cryptography. Nonetheless, the field has gained traction in the last couple of years and NIST is making progress on the standardization of the algorithms. Another promising option is quantum key distribution (QKD), which uses quantum physics to produce information-theoretically secure keys that cannot be broken by any physical device.

This article is written for a broad audience and as such, some of the mathematical statements have been simplified and should not be used to derive further statements.

Our experts will get in contact with you!

×

Noah Berner

Our experts will get in contact with you!