PQC or Post Quantum Cryptography

A summary of the current state of play in the field of quantum computer-resistant cryptography, along with simplified explanations of attacks on current algorithms, overviews of problems, and the importance of individual technologies.

Quantum computer-resistant algorithms

It is quite challenging to understand the terms used to denote the current development in the field of cryptography. But it is necessary especially because of the imminent emergence of quantum computer technology. The development of these machines has given new impetus to the development of cryptography. At the same time, they are popularly referred to as cryptographic Armageddon, the death of classical cryptography and other catchy terms. Quantum computers can cause inconvenience to existing technologies which involve e.g. agreeing on encryption keys or digital signatures, but they can pose a threat to other current encryption techniques. The reason is simple, it is now possible to collect data and decrypt them when those machines become available (HNDL = Harvest Now, Decrypt Later). There are secrets, even of an economic nature, that need to be protected for a longer period of time. Longer period in that case means years or tenth of years.

Current cryptography has a powerful tool in its arsenal, asymmetric cryptography. Asymmetric, because the keys are used asymmetrically. Private key for encryption, public key for decryption (or vice versa, depending on the purpose). Those algorithms are known under names RSA, ElGamal, Schnor signature, DSA, or cryptography over elliptic curves (ECDH/ECDSA). The user always has a pair of private and public key, where the public key is derived from the private key. These methods are used for agreeing on shared secrets (protecting our communications within SSL/TLS, SSH, IPSec and other technologies) or for digital signatures. The first algorithms for asymmetric cryptography, which provides these areas, appeared in the 1970s. The first practical deployment was a decade later. Now, after 40 years of development, we have managed to eliminate the biggest problems, to start using these technologies. Although these are in most cases trivial procedures, based on elementary and high school teaching, some of the problems are extremely interesting and are still not unequivocally solved. With current asymmetric algorithms, the impact of quantum computers is devastating. This was caused by an idea by Peter W. Shor, who suggested using first the search for a modular base number for factorization. For this purpose, it is possible to use a quantum version of the Fourier transform (the mathematical version of "period measurement"). And the only defense option is to find new, quantum computer-resistant procedures.

Current symmetric cryptography (the key is used symmetrically = the same key is used for both encryption and decryption) is built over block ciphers such as AES, ARIA, CAMELLIA, or stream ciphers such as ChaCha20. To list them this article would not suffice. The algorithms listed represent a method of securing large volumes of data because they are relatively fast. Quantum computers bring inconvenience, these encryption algorithms may be threatened by a Groover attack if small keys are used (i.e. smaller than about 168b), but is this not a false alarm? The answer is simple, it is not. Although the Groover algorithm is nothing more than an effective way of searching unsorted databases. In the case of a quantum computer, there are two possible ways for an attack. Either create a huge database of all combinations of open text, keys and encrypted text, or combine the search and encryption algorithms into one more complex one.

If the Groover and encryption algorithms are combined, e.g. with the implementation of AES for quantum computers, we should get a powerful tool. Theoretically, such a solution should return the information immediately. Calculations vary, for a key of size 128b, it should be an interval from 8 minutes to 30 years (depending on the design of the whole device, whether it would be a specialized circuit or a general quantum computer with a program). But for a key of size 192b, it would be time consuming at least 40,000 years. Therefore, it is necessary to use a larger key material in order to move the attack from the practical to the theoretical level. Of course, this is a theoretical attack for now, because we do not have the equipment for it yet and only parts of the algorithm have been tested. The important thing is to choose the length of the key so that it protects secrets with reserve for the required time, e.g. several decades.

For the sake of interest. If we only want to create a database of keys and encrypted texts for a key the size of 128b, we are outside the technological and raw material possibilities. If a memory cell would require 100 silicon atoms (and some doping elements), without any other supporting circuits, the storage would have a radius of 5000 AU … and would immediately collapse into a black hole due to its weight and gravitational action. So this is not the way, such a solution can only be taken as a cryptographic attack and a mathematical game play.

Post-quantum cryptography competitions

Currently, in late 2024, the following competitions are taking place to select quantum-resistant algorithms. These are often referred to as PQCs – Post Quantum Cryptography.

The results of this competition are generally accepted in Canada, Europe, the Middle East, parts of Asia, Japan, Australia and other places. More information about this competition can be found at NIST Post Quantum Cryptography

This is a local matter, with experts such as Tanja Lange acting as independent gestors. Thanks to the export of scientific and cultural trends (soft power), this activity will probably have some, at present difficult to predict impact, but will certainly be used by Samsung, LG, KIA/Hyundai... More information about this competition can be found at KpqC competition

China is trying to demonstrate its independence in this area as well. Recently I came across information that Russia should be interested in cooperating on this development, but the information is scarce and for me it is difficult to read. More information about the competition can be found at CACR PQC standardization

Standards with an impact on Europe

Europe is determined by ETSI standardiation( European Telecommunications Standards Institute), it also has an interesting and generally accepted result of NIST PQC, which has already created three standards, the fourth is in the design stage. According to the current situation, there will be enough algorithms for a digital signature, but probably not enough to provide an alternative to agreeing on a shared secret. But this is necessary to maintain the possibility of agreeing on keys and to ensure the confidentiality of encrypted communication.
FIPS 203 ML-KEM (originally Krystal Cyber, Key Exchange Mechanism, SVP+LWE)
FIPS 204 ML-DSA (originally Krystal Dilithium, Digital Signature Algorithm, SVP+LWE)
FIPS 205 SHL-DSA (Stateless Hash Based DSA, Digital Signature Algorithm, uses stateless hash trees)
(Falcon - Fast-fourier transform over NTRU-lattice based DSA, Digital Signature Algorithm, uses stateless hash trees)

In addition, the listed algorithms have a recommended security level, called NIST Security level:
Security level 1, security equivalent 128b (AES-128, exhaustive key search)
Security level 2, security equivalent 128b (SHA-256, collision search)
Security level 3, security equivalent 192b (AES-192, exhaustive key search)
Security level 4, security equivalent 192b (SHA-384, collision search)
Security level 5, security equivalent 256b (AES-256, exhaustive key search)

More interestingly, what recommendations each organization makes about the given standards. In my opinion it is still unclear how to approach the given standards. Due to the difficulty of analyzing the complexity of an attack conversion to a security equivalent is still a problem. Here is an overview of the digital signature algorithms:

Digital signature is important for authentication, electronic communication, or from the point of view of the law as a manifestation of the will. But digital signature alone is not able to ensure the protection of transmitted information, or even to agree on key material (shared secrets). There are other algorithms for that, more precisely only one for now algorithm:

It is the Key Exchange Method (KEM) algorithms that can also force changes in current protection methods. SSL/TLS protocol is most often used, followed by SSH protocol. Both layers have a somewhat similar architecture and protocol structure. It is with SSL/TLS that there is a risk that certificates with key material signed by post-quantum algorithms may exceed the size of the record. This can be transmitted by multiple packets, but must be smaller than 18432B (2¹⁴ + 2048). If the certificate or certificate chain is longer, the connection will be interrupted. And some proposed KEM algorithms may have key material extremely extensive.

Beyond the above algorithms, so-called hybrid algorithms have emerged, more or less temporarily. These are built over a combination of classical and post-quantum algorithms and are intended to act as protection should any of the above mechanisms experience a significant security threat. They are currently used in SSL/TLS and SSH, these hybrid algorithms include:

Problems allowing the creation of asymmetric algorithms

In terms of methods used in the creation of classical asymmetric is available the following a set of problems. These are currently at their peak and will need to be replaced by another set in the foreseeable future, able to withstand quantum computers:

In the case of algorithms resistant to quantum computers, it was necessary to find a completely different set of problems. Previous the set of problems was not sufficiently resistant to new technologies, so it was necessary to look for something better. Such procedure is a normal part of development and of course cryptography does not remain stationary. Some of these procedures are about the same age as current asymmetric cryptography, some are part of the evolution of recent decades. For the new algorithms they used the following groups of interesting problems:

Conclusion

Current algorithms will be seriously compromised by 2030-2040 and it is necessary to prepare for the impacts that quantum computers bring. On the other hand, it is necessary to be careful, premature implementation can create a problem in itself. The reason for this precaution is simple. It took us 40 years to create functional asymmetric cryptography built over quite simple problems, actually over the curriculum of primary and secondary schools. New approaches require substantially deeper mathematical knowledge, evidence of correctness and only developments in mathematics will answer the question whether they are the procedures chosen are correct. The individual steps should therefore, in my opinion, be approximately as follows:
1. Increase key size for symmetric algorithms to 192b (25% higher load than 128b), better to 256b (25% higher load than 192b). This makes it easy to avoid problems with the possibility of attack by Groover's algorithm.
2. Switch to hybrid algorithms by 2024 at the latest, unless switching directly to quantum-resistant algorithms. However, hybrid algorithms will not be suitable for use beyond 2030-2035 and at the latest must be replaced by tested quantum-resistant algorithms. This trip is for paranoids who either have concerns possible weaknesses of new algorithms, or kleptography (design allowing unauthorized access to information) for new standards.
3. Start within two years of standardization, or at most within five years of standardization to complete the transition on quantum-resistant algorithms. Both for the agreement on the keys and for the digital signature. In the case of digital signature, this will mean significantly more changes in different systems.

Attachments: List of libraries supporting quantum cryptography

Botan is an opensource library in C++. It supports Unix/POSIX and Windows systems. More information on GitHub
liboqs is an opensource library in C. It supports Linux, Mac and Windows through the "Open Quantum Safe Provider for OpenSSL" library. More information on GitHub
is an opensource library of interfaces in C. It supports Linux, Mac and Windows and provides OpenSSL library features from a support library providing PQC algorithms. GitHub
SymCrypt is a Microsoft library under an MIT license. It supports both the new CNG API, and the older CAPI we Windows. In Linux, you can call SymCrypt APIs directly or through interfaces, for example, the OpenSSL interface. GitHub

Attachments: List of algorithms in the NIST PQC

List of algorithms in the NIST competition, including their download, disable, merge, or standardization. This list is still incomplete and the goal is to fill in the missing data to allow a preview of the entire development.

Attachments: List of algorithms in the KpqC Competition

List of algorithms in the South Korean competition, including their details, similar to the NIST PQC competition. This overview is still not complete and the aim is to fill in the individual missing data to allow a preview on the whole development.

Attachments: List of algorithms in CACR contest PQC standardization

I am not able to add the table of algorithms in the Chinese contest yet. The contest was in two categories, the results are listed here:
1. AIGIS-SIG, LAC.PLE, AIGIS-ENC, LAC.KEX, SIAKE, SCloud, AKCN(AKCN-MLWE), OKCN(SKCN-MLWE), Fatseal, AKCN-E8, TALE, PKP-DSS, Piglet-1
2. uBlock, Ballet, FESH, ANT, TANGRAM, RAINDROP, NBC, FBC, SMBA, SPRING
The list of algorithms is complete, but details are missing for the time being. Therefore, it is not possible to get an overview of the whole development and to determine why some technologies were used and what type of technologies are involved. That will be added later.

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.