PART 1 of the short series.
I will use these two names: CRYSTAL-Kyber and Kyber interchangeably.
There is a growing investment in the development of quantum computers, two of the latest examples:
- New EuroHPC Quantum Computern in Amsterdam.
- IBM opens its first quantum data center in Ehningen, Germany.
Quantum technologies are also developing in other regions of the world. It is predicted that the development of quantum computers capable of breaking through cryptography algorithms could take only 5–10 years, maybe less or more depending on the source ;)
Taking into consideration the above, it is a good time to consider future implementing post-quantum cryptography in our software.
Okay, but which ones?
NIST comes with help and has recommended CRYSTAL-Kyber for general encryption due to its speed and small encryption keys, and CRYSTAL-Dilithium, Falcon, and SPHINCS+ for digital signatures in applications as of August 13, 2024.
Okay, but what is CRYSTAL-Kyber for example?
Official definition
The Kyber algorithm is a post-quantum cryptographic algorithm, designed to be secure even against quantum computers. It's part of a class of encryption algorithms based on lattice-based cryptography, which uses the mathematical hardness of certain problems in lattice theory to protect data. Kyber is specifically a Key Encapsulation Mechanism (KEM), which means it's used to securely exchange keys between two parties, like Alice and Bob.
Ok, what is a lattice?
Think of a lattice like a grid. Imagine a vast, three-dimensional checkerboard that extends infinitely in every direction. Each point where the lines cross is called a lattice point, and these points are laid out in such a way that they form a repeating pattern. In CRYSTAL-Kyber, these lattice points aren't just arranged in 2D or 3D space, but in much higher dimensions (often hundreds of dimensions).
In simple terms, solving the lattice problem is similar to standing in a vast, intricate lattice and attempting to determine the precise position of a single point on the grid. However, if you only have vague information about the point's approximate location, it becomes exceedingly difficult to pinpoint exactly where it is, particularly as the dimensions of the lattice increase. This is the essence of the challenging problem that Kyber relies on - it is extremely difficult for both classical and quantum computers to solve.
How CRYSTAL-Kyber use lattice?
Kyber's security is based on the Learning With Errors (LWE) problem, which is a variation of the lattice problem. Here's an analogy to help explain it:
Imagine that you and a friend want to communicate using a secret code or key. To establish this code, your friend provides you with a point on a large grid, but they introduce some random "noise" to the location of that point. The noise represents small errors, similar to your friend telling you to meet at a spot on a map but providing slightly incorrect coordinates (they're off by a few meters). However, you can still decode the message because you understand that there's only a small error in the position and you can correct it.
However, an eavesdropper who intercepts this message only sees the noisy version of the location. They don't know how much error was introduced or where the original point was. Since the lattice is vast and multi-dimensional, determining the original point from the noisy one is nearly impossible without a secret piece of information. This is the "trapdoor" that ensures the encryption's security.
Okay, but how to use it?
It turned out that, as usual, we can rely on the open-source community in this regard, and there are libraries available in a few languages that utilize these algorithms. Be aware of these implementations of CRYSTAL-Kyber as each software has bugs and security flaws. For example, many implementations of CRYSTAL-Kyber have been or still are vulnerable to KyberSlash. (list of vulnerable libraries: link). These vulnerabilities, named KyberSlash1 and KyberSlash2, exploit secret-dependent division timings in Kyber implementations. Essentially, the time taken for certain division operations can depend on secret values, which can be exploited through timing attacks to recover secret keys. Additionally, only a few have been tested for compatibility with the algorithm. Of the examples listed below, at the time of writing this article, only the java/script library.
Example libraries:
Rust
JavaScript - crystals-kyber-js
Java - kyberJCE
Python - kyber-py
Sum-up
In this post, I briefly discussed the current status of quantum computer development and post-quantum cryptography, with a focus on the Kyber algorithm and the libraries available.
In the next part of this series, I will provide some examples of how the Kyber algorithm can be utilized.
I'm curious if you already use post-quantum cryptography in your projects, what libraries do you use? What do you think is worth testing, and implementing post-quantum cryptography today?
Let me know in the comments.
Top comments (0)