Lattice Cryptography: A game-changing unbreakable algorithm? 🔑

Secure algorithms can serve as a safeguard for present-day encrypted data against potential quantum hackers as the quantum computer revolution could compromise traditional cryptographic algorithms.

14 min readApr 9, 2023

Anh’s note: For around 8 months of studying the course, “Introduction to Quantum Computing” by QubitxQubit, besides exciting and intensive lessons on quantum computing from quantum error correction to algorithms like VQE, the courses also touched on various applications in the field such as cybersecurity. At the end of our course, we were tasked with various projects, and I decided to pursue a research project on lattice-based cryptography to further my learning on the intersection of cybersecurity with quantum computing. As this is a research article, I’ve used various sources and videos to further my understanding, and have linked them below. The article was for me to learn more about quantum computing, which is a side interest of mine aside from AI. Hope you’ll enjoy!

Cryptography is the use of codes and ciphers to protect secrets — dating back around 1900 BC in Egypt when a scribe used unexpected hieroglyphic characters instead of usual ones. As the years go by, cryptography has evolved into various forms relying on intuition and heuristic approaches. As it becomes more developed, series of complex mathematical formulas are used to secure the data, and the keys are only available to the intended parties.

Researchers at UMichigan working on research on lattice-based cryptography

Classical cryptographic schemes are based on mathematical problems that are computationally difficult for classical computers (meaning the one you’re probably reading this on!) to solve efficiently. These include the RSA, Diffie-Hellman, relying on the computational hardness of various mathematical problems, like factoring large integers and discrete logarithms. However, the power of quantum computers are said to be capable of solving them much more efficiently than classical computers.

Specifically, using the Shor’s algorithm ( an algorithm used to factor large integers by first encoding the integer intended for factoring into a quantum state, which is then manipulated using quantum gates to compute a periodic function in polynomial time which this is then used to find the factors of the integer — allowing it to break the security of many classical cryptographic schemes). For more on this algorithm, click here!

While it is unclear when quantum computers will become a reality, recent times have seen significant strides in this area and it is widely accepted that developing crypto-systems that are secure against quantum computers is crucial. Thus, there is a growing need for post-quantum cryptographic schemes, such as lattice-based cryptography, that are promising methods to resists against the attacks from quantum computers.

Number Theory

One of the sources of disadvantages is a branch of mathematics known as number theory, one of the oldest branches. One of the problems in this branch of mathematics plays a vital role in contemporary public-key cryptography, one of the simplest in basic school math terms is the factoring problem. Of which many public-key cryptographic schemes are designed based on the difficulty of factoring and similar problems like RSA, Diffie-Hellman Key Exchange and are used by most of the higher- level security applications like HTTPS and VPNs.

These fundamental cryptographic schemes has a security proof — a mathematical demonstration that breaking the security of the scheme is at least as difficult as solving one of the core mathematical problems, like factoring. These proofs are essential in creating confidence in the security of these basic cryptographic components.

So, what’s the issue? If we successfully build a large-scale quantum computer, this whole explanation collapses. Using Shor’s algorithm, the majority of other number-theoretic mathematical problem that were used in the last 40 years for security foundations could be easily solve with a quantum computer, usually using some variant of an algorithm called Grover’s search.

It is used for searching an unsorted database or list of N items, providing a quadratic speedup that can only perform the search in O(N) time. It is used to speed up the process of finding a secret key by searching through a large number of possibilities and can be used to crack encrypted messages or passwords by going through all of them simultaneously rather than individually. For more details on this, click here.

To simplify → with quantum computer → security proofs = meaningless.

What Are Lattices?

To understand what lattice-cryptography really is, let’s start by first exploring what lattices are.

Lattices: A lattice can be thought of as any regularly spaced grid of points stretching out to infinity. For example, here are 2 different, 2-dimensional lattices.

Mathematical definition of a basis. Given n linearly independent vectors b1, b2 … bn, lattice generated is defined as all the possible weighted sums of those vectors when scaled by integers. We refer to B1 through Bn as a basis of the latices.

This means that given a set of vectors that point in different directions and cannot be expressed as the scaled sum of any other vector in the set. We can take the scaled sum of these vectors to create other vectors that are also the less.

The only difference between a vector space from linear algebra and a lattice is that any vector in the basis of a lattice can only contain integers and when scaling a lot of spaces we can only scale by integers when they’re still positive , negative or zero

For example, a simple lattice is every XY integer pair and are two bases are not distinct but one such basis is vector v1 and vector v2.

Other bases in r2 do not have any other integer. For example, basis vector 2 0, 0, 2 do not include point 1 1 .

Vector: made up of numbers called coordinates. For example, a 2-D vector has two coordinates like (2, 3). A collection of evenly spaced vectors is called a lattice. The origin is a special vector with all its coordinates set to 0, like (0, 0, 0) in 3 dimensions. A vector is long when it’s far away from the origin, and short when it’s close to the origin. The points in the lattice are connected by vectors that are called basis vectors.

Vectors plays an essential role in lattice geometry as they provide a way to describe the geometric structure and symmetry of the lattice. By using vectors to describe the basis of the lattice, we can perform operations such as vector addition and scalar multiplication to understand how the lattice behaves under transformations, rotations, and translations.

Basis: Lattices are infinitely large objects but computers only have a finite amount of memory to work with. So, we need to find a way to represent them for its use, where the basis comes in place. This is a small collection of vectors that can be used to reproduce any point in the grid that forms the lattice.

In general, we organize its basis vectors into an M by n matrix. Manipulating these matrices are the core of lattice based cryptography.

Let’s examine the scenario of a 2-dimensional lattice, which is a network of points on a flat surface like paper.

Pick 2 points that do not exist on the same line passing through the origin. We could opt for (2,0) and (0,2). The following method can be used to create the third point:

Select 2 integers: 3 and -1.
Then, multiply the coordinates of the first point by 3, resulting in (6,0). Next, multiply the coordinates of the second point by -1, resulting in (0,-2).
Finally, add these two outcomes together to get our new point, which is (6,-2).

By utilizing this technique, we can utilize (2,0) and (0,2) to generate a complete grid of evenly spaced points, encompassing all coordinates (x,y) in which both x and y are even numbers, including 0 as an even number.

Vectors (2,0) and (0,2) establish the lattice points with even coordinates. By choosing a basis, we have selected an entire lattice, made of the points generated by the vectors in the basis.

Any given lattice doesn’t have just one basis — it has many. For example, instead of using (2,0) and (0,2) above we could have just as well chosen (-2,0) and (0, -2) or even (4, 2) and (2, 2). In each case, they end up generating the exact same grid of points.

A basis is short if it is made of of short vectors (blue basis in figure 1). A basis is long if it consists only of long vectors (green basis in figure 2). Short bases are much more useful than long ones when it comes to solving the types of hard lattice problems cryptographers are interested in.

If they are so similar to vector space, why bother?

Given the integer constraints of latices, we can define certain problems that are really hard to solve.

No technology can solve these problems in exponential time

Let’s take a closer look at the short vector problem.

Suppose we are given a long basis for some lattice L, this would ask us to find a grid point in L as close as possile but not equal to the origin point.

For example, finding the shortest vector can seem easy, but when given 1000+ entry vectors can be hard. Thus, finding an exact answer takes exponential time.

Example of Short Vector Problem

At first glance, this might seem like a relatively easy problem to solve. However, notice that the basis we are given consists of long vectors.

It’s quite challenging to combine them in order to create a short vector with small coordinates. This task becomes even more complicated in cryptography because the lattices involved have much higher dimensions, typically around 10,000 coordinates instead of just 2 as in the examples given earlier. It’s difficult to find a combination of basis vectors that can produce small coordinates for all 10,000 generated coordinates at the same time. This problem is so difficult that even with the help of a quantum computer, we still do not have a fast solution for it.

Bob wants to send Alice a message. First, Alice sets up a lattice with two different bases and both bases generate the same lattice. In one basis, the vectors are close to perpendicular and let’s name that a good basis. In the other basis, the vectors are much closer to parallel, let it be bad basis.

The closest vector problem is hard to solve with a bad basis > good basis. The bad basis are in a line and can almost cancel each other out, so the closest lattice point can come from adding and subtracting many vectors. Thus, Alive keeps the good basis as a secret but she tells Bob the bad basis. Bob uses it and embeds a message on a lattice.

He picks a point on the lattice — the yellow one. This will somehow represent the message. For example, the yellow point is 0 times the first red vector and two times the second blue vector, representing the message 02. Moving from the yellow point to create the green point to send Alice the coordinates.

Alice knows the secret good basis and she can use that to find the closest lattice point the — yellow one, and recover the message. An eves-dropper needs to find the closest lattice point with the bad basis, which is basically the closest vector problem. IT’S HARD!

Significance of Lattices

What are some of its attractive characteristics?

These families of difficult mathematical problems are widely studied and well-understood. Mathematicians have been studying lattices for centuries, with notable work done by Johann Gauss in the early 1800s.
Lattice problems are highly versatile and can be used to build various cryptographic schemes. These problems can replace most of the currently vulnerable cryptographic schemes, and they even enable the creation of new, highly effective cryptographic tools that cannot be based on factoring or other challenging mathematical problems. This includes hard problems that are still considered unsolvable with quantum computers.
The majority of scientific publications in the area of “post-quantum” cryptography focus on lattice-based cryptographic schemes. These schemes are designed to be secure against attackers who possess advanced quantum computers. For example, the US National Institute for Standards in Technology runs an international competition for new post-quantum secure cryptography.

Lattice-Based Cryptography — An Overview

Lattice-based cryptography is based on the mathematical concept of lattices as we have explored earlier. A lattice is a discrete set of points in n-dimensional space that are arranged in a periodic manner.

In lattice-based cryptography, encryption and decryption are based on the hardness of certain mathematical problems related to lattices. Specifically, lattice-based cryptography relies on the hardness of the shortest vector problem (SVP) and the closest vector problem (CVP) in lattices.

Lattice-based cryptography provides a secure encryption system that is difficult to break into due to the properties of a lattice, which has patterns that extend infinitely. This makes it a popular alternative to traditional encryption methods like RSA, which has shown to be vulnerable to attacks. It allows for encoding messages that can only be decoded with the correct key. For example, when using 2 lattices with different point counts, it would be challenging to match up corresponding points without the correct key. However, with the correct key, the points can be easily matched up and the message can be decoded.

Lattice-based ciphers, like Dilithium and Kyber, have shown promising resistance against attacks from quantum computing sources and are considered examples of quantum-proof encryption.

These algorithms can be divided into two main types: keyed and unkeyed algorithms. Keyed algorithms, such as the NTRUEncrypt algorithm, require a secret key to encrypt and decrypt messages. Unkeyed algorithms, such as the Dual EC_DRBG algorithm, do not require a private key.

Building Lattice-Based Cryptography

To do this, let’s look at the concept of learning with errors and how it can encrypt with unsolvable equations. To understand this, we will learn about the concept of “learning without error”.

Alice has a secret vector — a list of number and that is what is known as her private key. Her public key, a.k.a, the information that she shares with others is composed of a bunch of equations and when we plug in the secret numbers.

When we plug in the secret numbers, letting x = 10, y=82 , x=50 and w=5. The equations are all true and the secret vector is a solution to each of these equations.

It would only be a secret if the secret vector is hard to decipher. It should take a computer a long time to find the secret vector using public equations and in learning without error system, it is not true. Focusing on the first 4 line, they form a system of linear equations.

We can solve using manipulation or using a matrix or tools of algebra, but a computer can quickly solve for a secret vector using 4 of the public equations. That doesn’t sound like it’ll stay a secret for very long right?

However, what if we incorporate the errors in learning with errors?

Let’s pick random whole numbers that are close to 0 and add them to the right side of each equations. The numbers are the read errors and they are secret.

These equations are the public information and if we only have access to the public information, it is hard to pill apart the real system of linear equations. This error-filled system of linear equations almost doesn’t have a solution as it has more equations than variables as there are too many equations constraining the values of the variables.

We can manipulate the error-filled equations to get values to the variables that are close to the truth but takes a lot of equations to get the real solutions without the errors, making our secret is a secret.

In short, Learning with Errors (LWE) is a mathematical problem used in cryptography to hide secret information from attackers. It works by creating a pattern called a lattice, which is like a grid of points in space.

To hide the secret information, a special code is created using the lattice pattern. This code includes some random noise to make it harder for attackers to figure out the secret information. The noise is chosen in a special way to make it really hard for attackers to tell what the secret information is. To break the code and figure out the secret information, attackers have to solve a tricky puzzle. They have to figure out how to remove the noise from the code and find the secret information. But because the noise is random and hard to predict, it’s really tough for them to do this.

This method is used in different ways to protect information in things like secure messaging and online transactions. By using LWE, the information is kept safe from people who might try to steal or access it without permission.

For more details on this, watch this short 10 minutes video here.

Benefits?

1. Post-Quantum Security

Lattice-based cryptography is believed to be secure against attacks from quantum computers. This is because the underlying mathematical problems of lattices are believed to be hard even for quantum computers as we have explained above.

2. Faster Computation Times

Another benefit of lattice-based cryptography is that it can be computed much faster than other cryptographic algorithms. This is important because faster computation times can improve performance, especially in applications requiring real-time responses, such as streaming media or online gaming. This makes them more suitable for use in real-world applications.

3. Lower Energy Consumption

They consume less energy because they can be implemented in hardware that requires less power. Certain types of processors designed for cryptocurrency mining are up to many times more energy-efficient than traditional processors when running lattice-based cryptographic algorithms.

4. Robustness and Flexibility

Lattice-based cryptography is resistant to side-channel attacks, which are attacks that exploit weaknesses in the physical implementation of cryptographic algorithms. This makes them more robust and secure than other cryptographic schemes.

More importantly, lattice-based ciphers can be used for a number of different applications. For example, it can be used for digital signatures, password-based encryption, and key exchange. Additionally, there are several different ways to construct a lattice, which means that there is a lot of flexibility in how it can be used.

What Does The Future Look Like?

Lattice-based cryptography has various applications. Some of the most common applications of lattice-based cryptography include:

Public Key Encryption: In lattice-based public key encryption, the public key is a lattice that is generated by a secret key. The encryption process involves adding a random noise vector to the plaintext vector and rounding the result to the closest lattice point. The decryption process involves finding the closest lattice point to the ciphertext vector and subtracting the secret key to obtain the plaintext.
Digital Signatures: Lattice-based digital signatures use the hardness of the SVP to provide security. The signing process involves finding a short vector in the lattice that satisfies certain criteria, while the verification process involves checking that the lattice point obtained from the signature is close to the public key lattice.
Key Exchange: Lattice-based key exchange protocols use the hardness of the CVP to provide security. The key exchange process involves generating a shared secret by computing the closest vector to a linear combination of the public key lattices.

Conclusion

Lattice-based cryptography is a promising area of research that has the potential to provide secure and efficient cryptographic schemes that are resistant to attacks from quantum computers. With its high efficiency, robustness, and post-quantum security, lattice-based cryptography is expected to play an important role in the future of cryptography. As the field continues to develop, new and innovative applications of lattice-based cryptography can also emerge.