About a year ago, on July 5, 2022, the U.S. National Institute of Standards and Technology (NIST) announced the first results of a procedure initiated in 2016 to select post-quantum cryptographic standards. One key exchange algorithm and three electronic signature algorithms were selected. Based on these algorithms, new cryptographic standards will be developed to provide resistance to possible future attacks carried out with quantum computers. The post-quantum cryptographic algorithms selected by NIST will gradually replace the current asymmetric cryptography algorithms, which are the basis for the security of communications on the Internet, in the coming years.
Why do we need post-quantum cryptography?
The quantum computers available today are far from being capable of effectively cryptanalyzing the encryption algorithms in use today. Nevertheless, such a threat, although pushed back in time, theoretically exists and should be taken into account in risk analysis. This problem mainly concerns public key cryptography algorithms (asymmetric cryptography), in which encryption and decryption are carried out using two different keys: private and public. Using quantum cryptanalysis, it becomes computationally efficient to recover the private key based on knowledge of the public key. Examples of public key cryptography include the RSA (Rivest-Shamir-Adleman) algorithm, Elliptic Curve Cryptography (ECC) algorithms, and the Diffie-Hellman (DH) key exchange protocol (also based on elliptic curves, the so-called Elliptic Curve Diffie-Hellman (ECDH)).
One of the main uses of these algorithms is the remote exchange of a secret key, which is then used to encrypt a message (plaintext), already using symmetric algorithms. With symmetric ciphers, the same key is used to encrypt and decrypt the message.
The described procedure is widely used in the secure exchange of information, including that which we can characterize as particularly sensitive. Moreover, some of this type of information may remain sensitive for a long period of time, counting in tens of years. Hence, there is a legitimate concern that this information (in encrypted form) may be stored for a period of even several decades, after which it will be successfully read using quantum cryptanalysis – breaking asymmetric ciphers and gaining access to the key encrypting the relevant information. It is worth mentioning that even the property of so-called forward secrecy, commonly used today in encrypting Internet traffic, will not help here.
In light of the potential crisis, such a situation could cause, the cryptography community has taken steps to develop a set of cryptographic solutions resistant to known attacks using quantum computers. It is this branch of cryptography that we refer to as post-quantum cryptography (PQC) [1].
While, in light of the current relatively slow rate of growth in the computational resources of quantum computers and the many technical hurdles associated with scaling quantum processors, the widespread implementation of post-quantum cryptography may give the impression of being somewhat premature, one should keep in mind the complexity and length of time involved in the development, testing, standardization and widespread utilization of post-quantum algorithms. Quantum physicist Michele Mosca put this problem within the framework of the following inequality [2]: x+y>z, where x is the time we require to ensure information security, y is the time it takes to implement new solutions to ensure security against quantum attacks, z is the time it takes to develop a computer capable of breaking current public key cryptography ciphers. If the above inequality is satisfied, then we must consider the situation problematic.
Of course, there is a lot of uncertainty in determining the value of the z parameter. In this article, I focus my attention on post-quantum cryptography, and this is not the place for an in-depth analysis of the physical and technical aspects behind predicting the value of the z parameter. A simplified analysis presented in my earlier article titled Technologie kwantowe a cyberbezpieczeństwo [3] (in Polish), indicates that the value of z may currently be around 25 years. Realistically, we can assume that widespread implementation of post-quantum standards will take about 10 years. Applying these values to Mosca’s inequality leads to the expression: x > 15 years. This means that exchanging information on the Internet that we would not want to share publicly for more than 15 years will no longer be secure at the end of the post-quantum cryptography adaptation period. Considering more optimistic scenarios for the development of quantum technologies, this value will decrease. However, the limitation already shown here is a serious warning in light of the exchange of medical, business, or government communications.
NIST competitions
In January 1977, the U.S. National Bureau of Standards, which was renamed NIST in 1988, published the first widely used standard for symmetric cryptography – the Digital Encryption Standard (DES). Despite the selection of the algorithm’s designer through a competitive process, which became IBM, the standardization process was not transparent, and the results quickly stirred up controversy in the cryptology community. This happened, in particular, due to the relatively short 56-bit key. Its length, as we know it today, was influenced by the US National Security Agency (NSA), which was involved in the process of developing the DES standard [4]. As a result, already twenty years after the introduction of the DES cipher, its breaking by brute force did not pose any major problems. DES thus became useless (except for its use in 3DES or DES-X algorithms, among others), and NIST began the procedure for selecting a block cipher, which is the new standard for symmetric cryptography. This time, however, to avoid previous controversies (also related to the origin of the so-called S-blocks, which are the building blocks of the DES algorithm), it was decided to have a fully open and transparent competition procedure. This is how the Rijndael algorithm emerged, which took the form of a new standard – Advanced Encryption Standard (AES), adopted in 2001 and still in force today. Moreover, its 256-bit key version is classified as a post-quantum algorithm.
Over the past two decades, NIST has developed dozens of standards and recommendations for cryptographic algorithms, including those for hash functions, electronic signatures, and key generators. NIST’s most recent cryptography standardization initiatives include lightweight cryptography standards dedicated to devices with limited computing resources (microcontrollers, IoT solutions, etc.) and the standardization of post-quantum cryptography discussed here [5].
The procedure for selecting post-quantum cryptography standards was initiated in December 2016. The competition announced by NIST concerned the selection of a post-quantum public key cryptography algorithm, Key Encapsulation Mechanism (KEM), and electronic signature. Five levels of security for post-quantum algorithms were specified, corresponding to security due to brute force attacks on block ciphers with key lengths of 128, 192, and 256 bits, and due to collision attacks on hash functions with hashes of 256 and 384 bits. The interested reader can find further detailed information on the requirements for candidates in [6].
It is worth noting, is that the new post-quantum cryptography standards move away from the DH key exchange protocol (KEX), which involves two communicating parties. Thus, a post-quantum version of the Diffie-Hellman protocol is not envisioned. Instead, the aforementioned key encapsulation mechanism (KEM), in which one party selects a secret key and encrypts it with a post-quantum asymmetric algorithm using a public key, is adopted as an alternative. The encrypted key is then retrieved by the other party using the private key. Such a solution was found to be simpler and easier to implement and analyze [7].
It is also worth adding that the NIST competition does not include new hash function standards. Those currently in use (e.g., SHA-3) are considered resistant to quantum attacks. As a result, they are also used in post-quantum algorithms for electronic signatures based on hash functions (Hash-based signatures).
Post-quantum winners
From the eighty-two proposals initially sent, four algorithms were selected after the third round was completed. In addition, four more were qualified for the next fourth round [8].
CRYSTALS-Kyber [9] has emerged as the public key cryptography algorithm. This algorithm also provides a key encapsulation mechanism (KEM). CRYSTALS-Kyber belongs to the class of lattice-based cryptography [10], in which operations are performed on multidimensional lattices, similar to crystal lattices. The lattices provide an opportunity to define a number of problems that are considered computationally difficult. One of them is the Learning With Errors (LWE) problem, which in 2005, was proposed by Israeli computer theorist Oded Regev. He was awarded the prestigious Gödel Prize in 2018 for his discovery. The CRYSTALS-Kyber algorithm is based on a variant of the LWE problem in which the lattice defining the problem has a certain imposed structure, the so-called Module-LWE. In justifying the choice of this algorithm, NIST emphasized, among other things, its speed and small key size, being of the order of a kilobyte.
The following have emerged as electronic signature algorithms: CRYSTALS-Dilithium [9], FALCON [11] and SPHINCS+ [12]. CRYSTALS-Dilithium, was designed by the same group as CRYSTALS-Kyber and is considered the main algorithm for post-quantum electronic signatures. The CRYSTALS-Dilithium algorithm was based on a modification of the LWR problem, the so-called Learning With Rounding (LWR). In this problem, instead of adding Gaussian noise (as in LWE), a rounding function is introduced, making it more difficult to recover the secret message. Moreover, like CRYSTALS-Kyber, CRYSTALS-Kyber uses an imposed lattice structure, which ultimately leads to the Module-LWR problem.
The future FALCON standard is based on the well-studied NTRU algorithm, which in its first version, was introduced in 1996 [13]. The algorithm is considered the protoplast of lattice ciphers. It is fast and easy to implement. While initially, its operation can be understood without referring to lattices – namely, it is based on operations performed on so-called quotient rings of polynomials – the essence of its security is already directly derived from the properties of lattices. Despite the relatively small size of the key, the weakness of the FALCON cipher is the lack of a constant-time implementation, which is resistant to extracting the private key from the timing of the algorithm. Another trouble is the required fast double-precision arithmetic, making the implementation of this cipher difficult [14].
Unlike previous cases, the SPHINCS+ cipher is not based on lattice mathematics. It was selected by NIST as a backup algorithm in case time unveiled previously unknown vulnerabilities of lattice ciphers. And I write about the fact that this may indeed happen later in this text. For now, it should still be added that the SPHINCS+ algorithm is based on well-known and cryptographically strong hash functions. The idea of using hash functions for signatures was proposed back in 1975 by American computer scientist Leslie Lamport. In this approach, a private key is consumed to create public keys by creating a hash function from part of its bits. Consequently, practical applications of electronic signature algorithms based on hash functions require the use of large keys, the size of which can reach tens of kilobytes. This is the main shortcoming of this approach. Besides, these algorithms are both secure and easy to implement, as they are based on well-tested and widely implemented solutions.
Controversy before the finish line
On April 4 last year, 3 months before NIST announced its results, cryptologists from the prestigious Center of Encryption and Information Security (MATZOV), which is Israel’s main cryptology facility, shook up the crypto world, or at least the post-quantum part of it, by releasing their report, the result of an audit of the main candidates for the post-quantum cryptography standard. The report is entitled “Report on the Security of LWE: Improved Dual Lattice Attack,” and focuses attention on approaches based on LWE and LWR [15]. The best-known cryptanalytic techniques for these types of ciphers are based on so-called primal lattice attacks and dual lattice attacks. Neither of these attacks has been considered a viable threat to date. In particular, the latter approach seemed impractical. However, the MATZOV report showed that there is room for improvement in the second type of attack, which clearly weakens the security of the CRYSTALS-Kyber, SABER and CRYSTALS-Dilithium algorithms. Specifically, the new cryptanalytic technique was shown to weaken the security of these algorithms slightly below the thresholds specified in NIST’s competition requirements. The reader interested in the discussion of the post-quantum cryptology community on the MATZOV report is referred to reference [16].
The results of the MATZOV report ultimately did not prevent the selection of the CRYSTALS-Kyber and CRYSTALS-Dilithium algorithms. However, they may have influenced the rejection of the SABER algorithm from the competition. It is worth clarifying at this point that we have no proof of the safety of the CRYSTALS-Kyber and CRYSTALS-Dilithium algorithms. The statements regarding their safety are related to the so-called Shortest Vector Problem (SVP) on lattices [17]. As proven, SVP is the so-called NP-difficult problem, which makes it impossible to solve it efficiently (in polynomial time). The LWE and LWR problems can be reduced to an approximate SVR problem. However, there is no proof that these are NP-hard problems. Thus, from the security side, the justification for using these problems in post-quantum cryptography is based on the lack of knowledge of algorithms that would allow efficient solutions to these problems. However, it cannot be guaranteed that such algorithms will not be discovered in the future.
The fourth round
The process of selecting post-quantum cryptographic standards by NIST did not end with the selection of the four algorithms discussed above. The game continues, and four more algorithms have qualified for the fourth round of evaluation, which still have a chance to join the ranks of NIST’s post-quantum standards. We are talking about the ciphers BIKE [18], Classic McEliece [19], HQC [20], and SIKE [21].
Let’s begin by presenting the second on the list, the Classic McEliece cipher, which belongs to the class of asymmetric ciphers based on correction codes. Such codes, through some redundant information, allow the correction of errors created during the transmission or storage of information. In 1978, Robert McEliece showed that correction codes could also be used to implement, introduced a few years earlier, asymmetric cryptography. Despite more than forty years of attempts and in-depth knowledge of the algorithm, launching a successful attack on it has not been possible. The weakness of the algorithm is the large key size – even on the order of a megabyte. The BIKE (Bit Flipping Key Encapsulation) algorithm is, like Classic McEliece, also based on correction codes. In this case, the so-called QC-MDPC (Quasi-Cyclic Moderate Density Parity-Check) code is used. Also, the HQC (Hamming Quasi-Cyclic) algorithm is based on correction codes.
The last of the ciphers, SIKE (Supersinguar Isogeny Key Encapsulation), uses a completely different approach than the previous three. Namely, it involves morphisms (certain relations) between elliptic curves to build an asymmetric cryptosystem. Despite being computationally demanding, this approach was recently considered secure and characterized by an extremely short key. This forecasted the usage of the SIKE algorithm in areas of special-purpose applications. To the great surprise of the cryptology community, on July 30, 2022, two cryptologists from the University of Leuven published a recipe for an effective attack on the SIKE algorithm [22,23]. Exploiting a previously unknown vulnerability, they managed, using a personal computer, to recover the private key. This algorithm, despite the hopes attached to it and the implementations already tested, will certainly not become a post-quantum standard. However, it is still possible that the vulnerability that enabled the attack will be eliminated in further incarnations of this algorithm.
What about symmetric cryptography?
Modern symmetric cryptography algorithms are considered invulnerable to quantum attacks. Their level of security is essentially determined by brute force attack, the feasibility of which is determined by the size of the key space. In the case of the AES algorithm with a 256-bit key, this space has a dimension of N=2256, which is comparable to the number of atoms in the observed Universe.
The best-known quantum strategy for power attacks is to use Grover’s algorithm. This algorithm makes it possible to search a quantum database containing N elements, not in an average of N/2 steps, as is classically the case, but in an average of N1/2 steps. For the AES-256 algorithm, this means a reduction in security from 256 to 128, a value that is still considered post-quantum secure. In addition, it should be noted that already from the theoretical side, the very implementation of the Grover search algorithm for a given symmetric algorithm poses a major challenge. Namely, one has to build a circuit of the so-called quantum oracle (oracle) for a given symmetric algorithm. This in itself is a complex task, requiring making a representation of a given symmetric algorithm in the form of a binary function and its further implementation as a quantum circuit. This poses a huge challenge already at the algorithmic level.
The algorithm proposed by Lov K. Grover in 1996 was considered by many to be the only quantum threat to symmetric algorithms. However, the outlook on cryptanalysis of symmetric algorithms gradually started to change since 2012, when Kuwakado and Morii have shown [24], that it is possible to achieve the so-called exponential acceleration for cryptanalysis of the symmetric Even-Mansour cipher. This is due to the clever use of Simon’s quantum algorithm, which is a simpler version of Shor’s algorithm. In turn, Shor’s algorithm poses a fundamental threat to asymmetric algorithms.
The use of Simon’s algorithm makes it possible to efficiently break the simple Even-Mansour algorithm as well as some other cryptosystems [25]. Although the Even-Mansour algorithm is too simple to find practical use, variants of it can be found in lightweight cryptography ciphers. In particular, these include the Chaskey and Elephant algorithms, which is one of the finalists in the NIST process for standardizing lightweight cryptography.
The caveat, however, is that the quantum oracle for the cipher Evena-Mansour must be implementable (the so-called Q2 case). It has recently been proven that if the quantum oracle is not available (the Q1 case), which is the typical situation in practice, the Even-Mansour cipher is post-quantum secure [26].
It should be noted that the quantum cryptanalysis of symmetric ciphers is becoming an increasingly active field of research. The issue of security of symmetric ciphers should, therefore, not be underestimated.
What’s next?
It could take another year to prepare ready-made standards based on the selected algorithms, NIST declares. In the meantime, the agency encourages learning about and testing the picked algorithms. NIST also suggests refraining from practical implementations at this stage since the final form of the standards may differ from the current specification of the algorithms. The time is undoubtedly also worth using to broaden awareness related to the implementation of post-quantum cryptography and to prepare for the activities that the announcement of the new standards will entail in the coming years. This applies, in particular, to IT departments of companies and institutions. Attention to the issue of new standards should immediately turn to those operating in the areas of network infrastructure, data storage, and cyber security. One should also be aware that in the next few years, every network administrator will have to become familiar with the new post-quantum versions of the Transport Layer Security (TLS) protocol and the post-quantum cipher suites they offer.
We are waiting, moreover, for the identification of possible additional standards that can play a reserve and special purpose role. Given the recent reports cited, the SIKE algorithm is most likely already out of the game.
The near future should also bring the initiation of a procedure for selecting a post-quantum standard for homomorphic encryption. Encryption of this type is gaining more and more interest due to the rapid development of cloud services. Namely, homomorphic cryptography allows performing arbitrary operations on encrypted data without having direct access to it.
References
[1] D. Bernstein, T. Lange, Post-quantum cryptography, Nature 549, 188–194 (2017).
[2] M. Mosca, Cybersecurity in an era with quantum computers: will we be ready ?, IEEE Security & Privacy, vol. 16, no. 5, pp. 38-41, (2018).
[3] J. Mielczarek, Technologie kwantowe a cyberbezpieczeństwo, CyberDefence24, (2019).
[4] T. R. Johnson, American Cryptology during the Cold War, 1945-1989 (The Complete Declassified Official Four-Volume History of the NSA), Center for Cryptologic History, Washington DC (1995) – Book III, Rozdział 19, Public Cryptography.
[5] https://www.nist.gov/cryptography
[7] https://blog.cloudflare.com/towards-post-quantum-cryptography-in-tls/
[10] https://itwiz.pl/czym-jest-szyfrowanie-kratowe-jak-zabezpiecza-czasach-quantum-computing/
[11] https://falcon-sign.info/
[12] https://sphincs.org/
[13] J. Hoffstein, J. Pipher, J. H. Silverman, NTRU: A ring-based public key cryptosystem. In: Buhler, J.P. (eds) Algorithmic Number Theory. ANTS 1998. Lecture Notes in Computer Science, vol 1423. Springer, Berlin, Heidelberg (1998).
[14] https://blog.cloudflare.com/nist-post-quantum-surprise/
[15] https://zenodo.org/record/6412487#.Yu2VuexBx4I
[16] https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/Fm4cDfsx65s/m/v5odfcpfBwAJ?pli=1
[17] http://www.deltami.edu.pl/temat/matematyka/kryptologia/2017/11/25/Kryptologia_postkwantowa/
[19] https://classic.mceliece.org/
[20] http://pqc-hqc.org/
[21] https://sike.org/
[22] W. Castryck and T. Decru, An efficient key recovery attack on SIDH (preliminary version) (2022)
[24] H. Kuwakado, and M. Morii, Security on the quantum-type Even-Mansour cipher, 2012 International Symposium on Information Theory and its Applications, Honolulu, HI, USA, 2012, pp. 312-316.
[25] M. Kaplan, G. Leurent., A. Leverrier, M. Naya-Plasencia, Breaking Symmetric Cryptosystems Using Quantum Period Finding. In: Robshaw, M., Katz, J. (eds) Advances in Cryptology – CRYPTO 2016. CRYPTO 2016. Lecture Notes in Computer Science, vol 9815. Springer, Berlin, Heidelberg (2016).
[26] G. Alagic, C. Bai, J. Katz, and C. Majenz, Post-Quantum Security of the Even-Mansour Cipher, In: Dunkelman, O., Dziembowski, S. (eds) Advances in Cryptology – EUROCRYPT 2022. EUROCRYPT 2022. Lecture Notes in Computer Science, vol 13277. Springer, Cham.
© Jakub Mielczarek
Jakub Mielczarek 