Intro

As the era of quantum computers approaches, a significant threat emerges from this evolution. The encryption algorithms we rely on today will soon be vulnerable to quantum computers, due to their ability to perform some tasks exponentially better than conventional computers. This raises the question: How can we keep our data safe from this emerging threat?

Back in 2016, the National Institute of Standards and Technology (NIST) recognized this issue and launched a competition, calling upon cryptographers from all over the world to develop a new kind of encryption algorithm that could withstand quantum attacks. After receiving numerous submissions, NIST rigorously tested these algorithms and, in 2022, announced the first four quantum-resistant algorithms.

Join me as I delve into the realm of quantum computing and explore how these so-called quantum computers can break modern encryption, as well as uncover the inner workings of these quantum-resistant algorithms.

WTF is a "Quantum Computer"

Even though classical computers have enabled humans to achieve greatness, they might lag behind in some more complex and extensive tasks, like heavy simulations, material science, etc. That's where quantum computers come in. Instead of using traditional bits, quantum computers utilize quantum bits, or "qubits," which allow them to perform some tasks better and faster than traditional computers. Don't misunderstand, these computers won't be good at everything, primarily for specific use cases.

Though these computers are still in the early stages and as of now they are not capable enough to break encryption, it is widely assumed that some years down the line a sufficiently capable quantum computer could break RSA encryption in a matter of hours, a remarkable difference from the millions of years it would take for modern supercomputers to accomplish the same task.

How Exactly Encryption is Cracked

Before moving forward with the post-quantum algorithms, let's take a look at how exactly modern encryption works and how it can be cracked. Let's talk about one of the most commonly used encryption algorithms, RSA.

RSA utilizes prime numbers to encrypt and decrypt data. Here is how it works:

• First, each user has a set of two super large prime numbers, let's call them a and b, which they keep private.
• Next, these two numbers are multiplied to create another number, let's call it c; this one is publicly known.
• Now, if Bob wants to send a message to Alice, Bob will generate the encrypted data using Alice's publicly available c, and Alice can easily decrypt the message using c's two prime factors a and b.
• So, if any outsider were to break this encryption, they would be required to find out the two prime factors of c (i.e., a and b).

As a and b are super large numbers, c would also be extremely big, making it near impossible for a classical computer to factorize such a big number. But not quantum computers; they utilize an algorithm specifically designed for quantum computing through which one can easily factorize a large number. It's known as Shor's Algorithm. Using this, one can factorize c, and hence the RSA encryption can be cracked.

Lattice Based Cryptography

Now to solve the above issue, researchers came up with lattice-based encryption, and three of the first four post-quantum encryption algorithms use lattices to encrypt the data. Similar to RSA, this also has a public and a private key kind of concept. Let's look at how exactly these work:

First, imagine a 2-dimensional plane. In this plane, we have 2 vectors, let's call them v1 and v2, you can imagine these as the private key (like a and b in RSA); these will be kept private.

Second, we will generate a lattice using these two vectors.

Third, we will create another set of 2 vectors different from v1 and v2, which will generate the same lattice; let's call them x1 and x2. These 2 will act as the public key (like c in RSA) and will be publicly known.

Before moving forward, let's do a quick task. In the image shown below, I have given you a point p, your task is to find the closest point in the above lattice using v1 and v2, starting from the point o.

The solution is very simple: one time v1 and two times -v2. (see the image below)

1x(v1), 2x(-v2)

Now, do the exact same but with the vectors x1 and x2.

Finding the solution using x1 and x2 is much more difficult than finding it with v1 and v2. Here is the solution:

2x(x1), 2x(-x2), 1x(x1), 1x(-x2), 1x(x1)

This is the basis of the encryption algorithm. The vectors are purposely chosen like this so finding the nearest point in the lattice is hard with x1 and x2 but really easy with v1 and v2. Now that we are clear on the lattice and vectors section, let's move to how actually the encryption works.

Let's say that Bob wants to send something to Alice, like in the RSA example Bob has access to the publicly available c of Alice; here Bob will have access to Alice's two public vectors (i.e., x1 and x2). Note that only the x1 and x2 vectors are publicly available and not the whole lattice.

Now with some combination of these publicly available vectors, Bob arrives at a point in the lattice, let's call it t.

After arriving at t, Bob will add some random noise to t, which will give us another point, let's call it s; this is done so that the point that we are sending is no longer a lattice point and the person decrypting this would be required to find the closest lattice point to s which will be t.

As Alice has the good set of vectors (i.e., v1 and v2), she will be able to find the closest point to s (i.e., t) with no issues, but if any intruder wanted to decrypt the message, he/she would be required to find the closest point to s using the hard set of vectors (i.e., x1 and x2), which won't be possible.

And that is the basics of how these proposed encryption algorithms would work.

But hold on, you might think that these points can be easily found even with x1 and x2 on this 2-D lattice with some basic brute-force, and that would be correct. For our conventional computers, even 10-15 dimensions won't be an issue. But in the proposed solutions, they will be using around 1000 dimensions. Yes, good luck brute-forcing that. Not only for our conventional computers, this problem is close to impossible even for the quantum computers.

Conclusion

For now you can rest easy as the technology is not here yet and also many great minds are working on these types of solutions to assure that your data is secure and not in the wrong hands.