Quantum Computer-Resistant Cryptography - Key Exchange

Key encapsulation and digital signature algorithms were published as part of the NIST competition. In my opinion, it is appropriate to describe the behavior of these algorithms in a popularization form, i.e. without the use of mathematics. The idea of how these algorithms work can be important to someone. Each of these algorithms has its own specific properties, which may bring certain limitations, these are suitable to understand. A rash implementation of these algorithms or a misunderstanding of their principles can have significant impacts on overall data protection. The first article will deal with the KEM algorithms CRYSTALS-Kyber, HQC and CSIDH. The abbreviation KEM stands for Key Encapsulation Mechanism. The second upcoming article will then deal with the DSA algorithms Falcon, Sphincs++ and the algorithms using Merkle trees. The name DSA stands for Digital Signature Algorithm. This is a family of algorithms and must not be confused with the obsolete standard for the digital DSA signature. Which were built over the Schnorr signature (or, as some sources say, the El-Gamal algorithm,).

Key Encapsulation Mechanism ML-KEM

ML-KEM is the FIPS-203 standard. The principle of key negotiation is quite simple. By using asymmetrical cryptography one party uses the public key of the opposing party to encrypt sensitive data and then sends it to the opposing party. The opposing party can perform the reverse decryption operation because only the opposing party has a private key. As a result, both parties have sensitive data that can be used directly as encryption keys or inserted into the key derivation function (KDF, Key Derivation Funcion). The key can be provided for both parties in the same way. In this case, both sending and receiving communications uses the same key for symmetric ciphers. Another option is to provide two separate keys, one for sending, the other for receiving data. While a symmetric algorithm will still be used, each of the data streams will be encrypted with a different key material. The key exchange process is somewhat reminiscent of the RSA algorithm's functionality.

Functional principle of the ML-KEM aka CRYSTALS-Kyber algorithm (only for the curious)

The algorithm uses a mathematical structure known as grids. This structure is created by repeatedly adding the same vectors. For an example of a grid, you can use tiles. Imagine that you are in a huge tiled room. Each tile has the same size, i.e. length and width (the result is a rectangle). Repeating these tiles produces a regular network pattern on the floor or even on the wall. This pattern is generated by a private key, i.e. the length and width of the tile. If you want to create a public key, you need to use a new one based on the basic grid pattern. It does not have to be rectangular, the vectors can be at any angle. It is important that they do not meet the intersections of the private key network (the underlying grid). For a public key, you will use for example, transparent rhomboid tiles. The values of the length of the rhomboid sides will be the individual parts of the public key. Their derivation is possible just from the mentioned secret key, to which we add uncertainty (error).
In encryption, we take advantage of the complexity of two problems. The first is LWE (Learning with Error), the second is SVP (Shortest Vector Problem). These problems are necessary to know for understanding the whole structure of encryption, but the explanation of each problem must be separated from the other.
LWE is based on the difficulty of finding multiples and the corresponding error for the equation N=v*w+e. In this case, two numbers are multiplied and the error is added. In a similar way, it is possible to multiply the vectors, in the case of encryption on grids it is not in only two dimensions, but the dimensions can be tens or hundreds. A new value of random error is added to each result, which creates noise and makes the attack more difficult. In our example, however, we will still use only two dimensions. It is LWE that is behind the secrecy of private keys, which due to the error value e become murky. The error is different for each edge of the tile (for example, the values -1;0;1). So we don't really know their exact dimensions, transparent tiles in this case won't be that transparent. To make matters worse, transparent tiles (public keys) are derived from private keys, but the private key is kept. At this point, we lose confidence and have to rely only on the pattern we see.
SVP is based on the difficulty of finding out what the shortest path is between two grid points. Specifically, between the point specified by public keys and between the point specified by private keys. If you need to find the shortest vector (shortest distance) from a particular grid point formed by a public key to any point of the grid formed by a private key, through transparent tiles you could find them. But what if we only see a rhomboid image? To make matters worse, what if the tiles aren't two-dimensional, but have a hundred or a thousand dimensions? Suddenly, a quite simple problem becomes a nightmare.
In the case of encryption, the actual encrypted record is broken into small pieces, which are added as an error to each individual transparent tile. The result is irregularities that could be challenged. But mathematics here allows you to create a procedure that translates these irregularities into a shape that is extremely difficult to interpret. So there will be a creation encrypted text. It does not make sense for the attacker and it is not possible to decrypt it just using a public key. But the owner the private key is in a different situation, it can subtract both its errors and the size of the "tiles" that these pieces were used for stuck. The result will be small pieces of encrypted text that only need to be folded into the corresponding shape. This will give the original text before encryption and both sides share the same secret.

Key Size Table for ML-KEM

HQC key encapsulation mechanism, standard in preparation

Recently, in the fourth round of NIST's selection of quantum-resistant algorithms, the HQC algorithm was accepted as the next winner. This algorithm was approved in March 2025, with an estimated release date of the standard sometime next year, i.e. 2026. Again, the key exchange algorithm, i.e. one side generates the key and sends it to the other side. To some extent functionality Reminds the key exchange options using the RSA algorithm.

Functional principle of the HQC algorithm (only for the curious)

The algorithm uses the so-called general linear code decoding problem for data protection. Explanation again required a certain idea and a little trip to history. The first question is what are linear codes. This is a data encoding in ways that can correct errors when transmitting, this mean prevet noise which can intercepts communication. One of the amazing uses is the code for communication with the Voyager spacecraft (Golay [24,12,8] and Reed Solomon). The listed codes provide protection against connection errors while allowing data to be properly decoded. This would not be possible without the self-correcting code provided.
How does this happen? Imagine someone sending out the phrase "Quis custodiet ipsos custodes" in the Morse alphabet? A series of dots and the commas will look like this:
--.- ..- .. ... / -.-. ..- ... - --- -.. .. . - / .. .--. ... --- ... / -.-. ..- ... - --- -.. . ... ..--..
But what to do when radio transmissions are jammed? What if we get a text that looks like this, when will the interference be marked with an X? Will we be able to read the message?
--.XX..X ..XX..XXX-.X.X..- ... XX--- -.X .. . X / .XX.-X. ... XXXX... XX-.-XX..- X.. X ---XX.. XX... ..XX..
Deciphering such a message is challenging and impossible under certain conditions. The sender and receiver generate their private and public keys, where the private key is composed of two vectors. Most bits of each vector are zero and only a few places have ones (sparse structure). The public key is generated on the basis of these private keys it is a control matrix multiplied by the second of the vectors, to which the first vector and a random error value are added.
There are several steps in the encryption of the message. The first, the message is converted into one of the loop codes with self-correcting capability (Reed-Muller or Reed-Solomon) and two working vectors are generated (in the same way as the parts of the private key). The first vector is multiplied with the control matrix and the result is used as the first part of the encrypted data. The second part is formed as a multiple of the public key with the first vector to which the content of the message and the error values are added. The two vectors are sent to the receiver. The receiver can easily remove the noise based on the private key and the received vectors. It multiplies the first part of its private key by the first vector and the second part of its key with the second vector, adds the values and has a message with the self-correcting code. After, there are need to correct noise issues. For some people this is o mathematical spells, but the result is difficult to challenge.

Key Size Table for HQC

CSIDH key agreement algorithm

One of my favorite algorithms, which unfortunately was not selected, is built over a certain class of elliptic curves. Although for most people in the industry, elliptical curves are automatically vulnerable to quantum computers, this is not the case here. Depends on what kind problem provides data protection. On the other hand, the weaker brother of this algorithm (SIDH) was broken within a few hours on a common computer, so it is still necessary to verify its security for some time. But it has a huge advantage. Unlike the previous two algorithms, there is no one-party determination of the secret and subsequent transfer, there is a so-called key agreement. Both parties make a series of calculations and the result is a value equal on both sides. The key is not transferred anywhere, so we lack such algorithm. As will be mentioned below, it has certain security advantages. This sounds a bit like Diffie Helman over elliptic curves, but it is a very simplistic comparison.

Functional principle of the CSIDH algorithm (for the curious only)

As already mentioned here, this is an algorithm over elliptic curves. It sounds complicated, but in the case of cryptography on elliptic curves, modular arithmetic is used. This can be thought of as cropping the graph at a certain distance up and to the right, once this distance is crossed, it starts on the opposite side. In other words, it's as if I rolled the paper into a roll and turned the roll into a tire. Of course, the paper would have to be very flexible. This idea solves contemporary cryptography, but the one that is resistant to quantum computers is even more complicated.
In mathematics, there are so-called invariants. These denote a property that doesn't change. One example is elliptic curves, where their properties can be mutually invariant under certain conditions, so they have something constant and in common. In the case of SIDH/CSIDH, this is a so-called j-invariant (class of isomorphisms). So if we choose several curves that have the same invariant, and at the same time these curves have similar parameters, they can have the same number of points on the curve. In this case, it is possible to form relationships between these points, a kind of map of transitions. The whole principle is how we go through the curves. If we go from one to the other, we can get to the next point on the graph of the curve (on a given line around the circumference of that particular tire). We go to the next curve and we can find the next point again, or we can continue directly by changing the curve. Thanks to our passing key (I stand still, the transition between the curves, the change of a point on the curve), we make a specific map of the path. The paths listed can be complicated, but in the case of calculation, three points are important. The first, where we start. The second, which we change with the counterparty. And finally the third, on which we agree with the counterparty.
In the case of agreement on the keys, the initial curve and a specific point are determined. Each of the parties goes their own way until it gets after a predefined number of repetitions to the place where the key describing the passage through the curves ends. At this point, the two parties exchange their points with the counterparty. They then begin to insert their path map again, this time from the exchanged points. After the end, they must agree on the same result, because in fact, the passage map for the first and second sides has been composed. This algorithm still has a lot of open questions. These may or may not lead to its breaking. But we lack a mechanism capable of ensuring agreement on the keys without having to send the key material from one side to the other.

Key Size Table for CSIDH

Present and overall safety assessment

At the moment the accepted algorithms ML-KEM and HQC are safe, at least on the basis of current knowledge. The first problem is the connection based on current knowledge. As well as showing a possible threat to current algorithms in quantum computers, we may find other threats in the future. We can find other ways of attacking algorithms, or not. That's why why developments in cryptography need to be closely monitored.
Other threats are brought by surprisingly current technologies. The first is an operational threat, which lies in the structure of SSL/TLS. Each of the Record protocol must be smaller than 16384B, with additional values at the TLS level it is possible to extend another 2048B. (TLS Record protocol)+2048B(TLS Overhead)=18432B. If the record is larger, the connection is unlikely to be and will result in an error. This is because of the way the connection is established. In the TLS Handshake, the certificate is transmitted at the same time. And algorithms resistant to quantum computers simply have too large keys and signatures. If the message containing the certificate overflows over the specified value, the connection may not occur. This problem is partly solved by the fragmentation of the certificate (multiple records), but not every implementation supports it. The recommendation is to stick to a maximum of three records, sometimes it is possible to hit several hundred KB. Here, as a rule, TLS libraries supporting fragmentation also crash.
The second problem is the threat in the field of SSL inspection. As in the case of current algorithms, even in the case of quantum-resistant algorithms, SSL inspection protection depends on a suitable configuration. On the inspection system, the decoding of communication occurs thanks to the ability to falsify SSL certificates in an official way. In fact, there is a concatenated connection, where one encrypted communication is between the client and the inspection gate, the other between the inspection gate and the target system. The only reliable protection is the use of mTLS (mutual TLS). This allows to verify both the client and server certificate and at the same time to check the relationship between the client certificate and the user name. Quantum-resistant algorithms do not protect against this threat and it is not their goal. Thus, even in the case of their use it is possible to obtain decrypted data thanks to SSL inspection. Despite all the errors, the inspection has its justification in a large number of cases. Network protection, communication control to exfiltrate data and other purposes are understandable. But it is like any tool, even SSL inspection can be misused.
Thus, overall system security depends not only on the supported algorithms and methods of protection of the transferred data. Current algorithms are safe according to the available data. From an operational point of view, it is extremely important that we have a second algorithm available for key exchange resistant to quantum computers. Better when more are available, ideally with support for key agreement. But these matters must not be rushed and the background mathematics must ripen. Only then will it be possible to deploy other upcoming ones.
From a preventive point of view, it is advisable to consider even one obsolete option. What to do in the event of a technological breakthrough. In such a case, it is advisable to use alternative methods of key distribution at least temporarily. And as a fallback solution can still be served by … couriers. It is perhaps a crazy idea. This is a worst-case scenario, which I do not think will happen. But who is forewarned is also forewarned (Praemonitus, praemunitus.).

Conclusion

From a safety point of view, it is desirable to have several proven alternatives for switching to hybrid or pure post-quantum cryptography. It is excellent that we have different methods of protection at our disposal, but there is still a long way to go to be able to ensure the confidentiality of information in an appropriate manner. That is, including backup alternatives. All mechanisms it is necessary to examine and ensure not only their mathematical but also their implementation safety. It's just a matter of natural development. And it cannot be rushed. In the next part, I will deal with digital signature algorithms and differences, that occur in quantum-proof cryptography.

Autor článku:

Jan Dušátko

Jan Dušátko has been working with computers and computer security for almost a quarter of a century. In the field of cryptography, he has cooperated with leading experts such as Vlastimil Klíma or Tomáš Rosa. Currently he works as a security consultant, his main focus is on topics related to cryptography, security, e-mail communication and Linux systems.