Quick survey of PQCrypto

This document is a first draft and will deserve to be extended if relevant.

Impact of quantum algorithms in cryptography

Cryptography as we know it nowadays and on which all our information security systems are based is about to undergo major changes. As quantum computers emerge, the scientific community must revisit the algorithms we use to protect our data.

Although this field of research has been known for nearly 30 years and many algorithms have been proposed, the realization of quantum computers was not conceivable until the last few years. Many actors of the digital world are currently working on the design of such machines and they have even managed to design some with limited but functional capacities.

Shor’s algorithm

The Shor algorithm [ref.1], firstly introduced in 1997 by Peter Shor [ref.2], is the undeniable proof of the revolution that the quantum computer represents for the current cryptography. Most of our cryptographic algorithms are based on mathematical problems that are extremely complex to solve if one does not have all the parameters, those problems are easy to compute but hard to reverse. Almost all asymmetric cryptography algorithms are based on the assumption that factoring an integer of several thousand digits is practically impossible (the time required is sometimes greater than the number of atoms in the universe). In his work, Shor presents a quantum algorithm that solves the factorization problem (on which asymmetric cryptography is based) in polynomial time.

A recent study [ref.3] of Shor’s algorithm and integer factorization on quantum computers estimates that it would take about 20 million qubits to break a 2048 bit RSA private key in 8 hours. However, it should be noted that in recent tests, Google’s quantum computer only had 56 functional qubits. The implementation of this attack is not possible for the moment, however, the rapid progress in the field of quantum computers could render such an attack achievable in a few years.

Grover’s algorithm

Grover’s algorithm [ref.4], published in 1996 by Lov Grover [ref.5], is an algorithm which reduces a search complexity of $O(n)$ to $0(\sqrt{n})$. With the emergence of quantum computers, this algorithm will reduce the security level of many security algorithms, including AES.

The security level of AES is currently about $2^{n}$ where $n$ is the size of the key (128, 192 or 256). This means that where we had a security level of $2^{128}$ with AES-128, we would only have a security level of $2^{64}$ with a quantum computer, which is not sufficient for modern security needs. The AES-256 security level is also reduced to $2^{128}$ which is still correct according to modern security requirements. Therefore, the introduction of Grove’s algorithm as well as the appearance of quantum computers will have a minor but not negligible impact on symmetric cryptography algorithms. It is therefore critical to privilege the use of AES-256 in order to guarantee a reasonable level of security against post-quantum cryptanalysis.

NIST Position with PQCryptography

Since 2016 the NIST has set up a challenge [ref.6] to find out what the next encryption standards would be in a Post Quantum era. As of this writing, this competition is in the third round. The finalist algorithms are listed below. NIST intends to provide a recommendation of the algorithms to be used by 2024 [ref.7]. The scientific community is not yet unanimous on the robustness of these algorithms so it is best to wait for the final results of this third round and the establishment of a standard algorithm before making a transition to such algorithms.

Public-key Encryption and Key-establishment Algorithms

• Classif McEliece
• CRYSTALS-KYBER
• NTRU
• SABER

Alternate candidates:

• BIKE
• FrodoKEM
• HQC
• NTRU Prime
• SIKE

Digital Signature Algorithms

• CRYSTALS-DILITHIUM
• FALCON
• Rainbow

Alternate candidates:

• GeMSS
• Picnic
• SPHINCS+

NSA position and recommendations

The NSA still recommends the use of ’non-quantum resistant’ public key algorithms for the protection of TOP SECRET data [ref.8]. One recommendation for the industry is to ensure that products anticipate a post-quantum migration with similar properties (key sizes, encryption and signature) as the candidates for the third round of the NIST PQC standardization. The protocols currently under standardization are supposed to provide seamless replacement (or at least low constraints) with the current public key encryption and signature algorithm interfaces.

For the moment, here is a summary table of the NSA’s recommendations for the use of encryption algorithms [ref.8] :

Implementing cryptography

It is important to use cryptographic libraries that are robust and fully supported by cryptanalysis and side-channel analysis. The implementation of cryptographic primitives is an extremely complex task in both pre- and post-quantum cryptography. There are many reference libraries that have been extensively evaluated by the scientific community for current cryptography (we can for example cite OpenSSL [ref.9] or BouncyCastle [ref.10]).

The Open Quantum Safe project [ref.11] is currently working on the implementation of a library that integrates many adjustments to the post-quantum cryptography domain. This project proposes in particular an adaptation of OpenSSL ( more like an adaptation of Google’s BoringSSL [ref.12] which is itself a variant of OpenSSL) which could make this project an interesting candidate to follow for a transition to post-quantum cryptographic algorithms. It is nevertheless important to wait for the feedback of the various cryptanalysis on these algorithms in order to avoid introducing significant security flaws.

Other initiatives have emerged in recent years such as PQClean [ref.13] however the community is not yet ready to give an opinion on which reference implementation to use and which would be “production-ready”.

References

1. IBM Quantum. “Shor’s Algorithm.” Accessed June 21, 2022. https://quantum-computing.ibm.com/composer/docs/iqx/guide/shors-algorithm.
2. Shor, Peter W. “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer.” SIAM Journal on Computing 26, no. 5 (October 1997): 1484–1509. https://doi.org/10.1137/S0097539795293172.
3. Gidney, Craig, and Martin Ekerå. “How to Factor 2048 Bit RSA Integers in 8 Hours Using 20 Million Noisy Qubits.” Quantum 5 (April 15, 2021): 433. https://doi.org/10.22331/q-2021-04-15-433.
4. IBM Quantum. “Grover’s Algorithm.” Accessed June 22, 2022. https://quantum-computing.ibm.com/composer/docs/iqx/guide/grovers-algorithm.
5. Grover, Lov K. “A Fast Quantum Mechanical Algorithm for Database Search.” In Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing  - STOC ’96, 212–19. Philadelphia, Pennsylvania, United States: ACM Press, 1996. https://doi.org/10.1145/237814.237866.
6. Computer Security Division, Information Technology Laboratory. “Post-Quantum Cryptography | CSRC | CSRC.” CSRC | NIST, January 3, 2017. https://csrc.nist.gov/Projects/post-quantum-cryptography.
7. Post-Quantum Cryptography: The Good, the Bad, and the Powerful. Accessed June 20, 2022. https://www.nist.gov/video/post-quantum-cryptography-good-bad-and-powerful.
8. « Commercial National Security Algorithm Suite ». Text. NSA/IAD. Consulté le 21 juin 2022. https://apps.nsa.gov/iaarchive/programs/iad-initiatives/cnsa-suite.cfm.
9. “OpenSSL Cryptography and SSL/TLS Toolkit.” Accessed June 22, 2022. https://www.openssl.org/.
10. “Bouncycastle.Org.” Accessed June 22, 2022. https://www.bouncycastle.org/index.html.
11. Open Quantum Safe. “Open Quantum Safe.” Accessed June 22, 2022. https://openquantumsafe.org/.
12. “BoringSSL.” Accessed June 22, 2022. https://boringssl.googlesource.com/boringssl/.
13. PQClean. C. 2019. Reprint, PQClean, 2022. https://github.com/PQClean/PQClean.