Quantum computing could put secure communication at risk sooner than you think. Current research aims to solve the problem before it starts.

Post-quantum cryptography (alternatively, quantum-resistant cryptography) probably consumes more bandwidth than it should in quantum computing discussions. That’s because the potential to incrementally improve the efficiency of important but mundane tasks like optimizing logistics is a yawn for many people. Breaking today’s public key cryptography, on the other hand, is both a concrete objective and something that could be a unique capability of quantum computing.

Given the singular importance of security protocols in so many modern uses of the internet, this potential for future quantum computers to crack current encryption protocols is a matter of legitimate concern—and therefore worthy of our attention.

What’s the problem?

In their “Report on Post-Quantum Cryptography” NISTIR 8105, published in 2016, the US National Institute of Standards and Technology (NIST) offered the following background:

“In the last three decades, public key cryptography has become an indispensable component of our global communication digital infrastructure. These networks support a plethora of applications that are important to our economy, our security, and our way of life, such as mobile phones, internet commerce, social networks, and cloud computing. In such a connected world, the ability of individuals, businesses, and governments to communicate securely is of the utmost importance.

“Many of our most crucial communication protocols rely principally on three core cryptographic functionalities: public key encryption, digital signatures, and key exchange. Currently, these functionalities are primarily implemented using Diffie-Hellman key exchange, the RSA (Rivest-Shamir-Adleman) cryptosystem, and elliptic curve cryptosystems. The security of these depends on the difficulty of certain number theoretic problems such as Integer Factorization or the Discrete Log Problem over various groups.”

The problem is that a set of algorithms for quantum computers, developed by mathematician Peter Shor in 1994, could—on a sufficiently large and fast quantum computer—break current encryption schemes. This includes public key schemes such as RSA, ECDSA/ECDH (Elliptic Curve Cryptography), and DSA (an example of Finite Field Cryptography) in particular. However, quantum computing could also affect symmetric algorithms, including the security of the shared secret key exchange, and could force the use of larger key sizes.

Fundamentally, Shor’s algorithm—which usually refers to his algorithm for finding the prime factors of an integer—provides the ability to find the prime factors of any integer number in polynomial time on a quantum computer, rather than the exponential time that a classical computer algorithm takes. This could reduce the time to solve the problem from wildly unrealistic years to potentially hours. That’s a problem because public key algorithms rely on the fact that it’s quick to determine if a number is a valid prime factor, but this key cannot be found by brute force because it’s necessary to find the prime factors of integers that range from 1,024 to 4,096 bits. 

Why does it matter today?

However, none of today’s quantum computers are remotely capable of using Shor’s algorithm to factor the size of integers used by today’s cryptography standards. So, no problem, right?

Not exactly. For three reasons. 

The first is that changing cryptographic infrastructure takes a long time. NIST notes, “It has taken almost 20 years to deploy our modern public key cryptography infrastructure.” In the Fortune 500, transitioning from RSA to ECC has taken five to seven years. 

Second, many initial post-quantum cryptography proposals submitted to NIST were quickly broken; it’s reasonable to expect that other vulnerabilities may be found in the future. Although the draft algorithms have been extensively vetted, it will likely still take time to prove them out prior to deployment at scale.

The third is that data created today could be vulnerable to decrypting once sufficiently fast quantum computers become available. Even if the data is re-encrypted once post-quantum cryptography becomes available, it will still be potentially vulnerable if someone made copies prior to the cryptography migration. And data can be sensitive for decades. There is a wide range of expert opinions on when a quantum computer will be able to break RSA-2048 in 24 hours, but the general consensus is in the range of 15 to 20 years.

What are industry and governments doing?

A number of different standards and other organizations are working on post-quantum cryptography standards. For example, in the US, NIST has taken the lead. In 2016, they called for proposals, of which they received 82 from industry and academia. By 2020, there were 15 remaining candidates split between public-key encryption and key-establishment algorithms/digital-signature algorithms. Many used lattice-based encryption technology. Three draft standards came out in mid-2023, and the public comment period closed last November.

In Europe, the QUBIP project is one effort to address the transition to post-quantum cryptography of protocols, networks, and systems. The project, a global collaboration among businesses, universities, and NGOs,  kicked off in September of 2023. QUBIP’s main objective is to define a standard and replicable transition process involving the adoption of post-quantum cryptography in hardware, including constrained IoT devices, cryptographic libraries (such as OpenSSL, NSS, Mbed TLS), operating systems such as the Linux Fedora distribution initially, communication protocols (TLS and IPSec), and applications (Firefox browser and digital identity). Red Hat is a contributor at the library and OS level and is helping with standardization.

Starting from the transitions of these five building blocks, QUBIP addresses their integration into three real-world systems (IoT-based digital manufacturing, Internet browsing, and Telco operator software network environments) at the system level, considering all possible cascading dependencies.

Challenges faced during QUBIP’s first months have been:

• Transitioning the IoT component through the implementation of a secure element that provides a set of post-quantum cryptography implementations in hardware
• Transitioning cryptographic libraries through loadable modules to make post-quantum cryptography implementations available as part of the libraries’ capabilities and to enable post-quantum/traditional (PQ/T) hybrid schemes for TLS 1.3
• Dealing with several cascades of dependencies to make PQ/T hybrid TLS available at higher levels (operating systems and applications such as browsers and digital identity frameworks)
• Hybridizing post-quantum cryptography and Quantum Key Distribution (QKD) for key exchange in IPSec, often used to secure communications in telco operators’ software environments

To keep up with the QUBIP project, follow the QUBIP blog for updates. With the public comment period complete, NIST expects to announce that the three new algorithms are ready for use in 2024.

The QUBIP project is funded by the European Union under Grant Agreement No. 101119746. Views and opinions expressed are, however, those of the author(s) only and do not necessarily reflect those of the European Union or European Research Executive Agency. Neither the European Union nor the granting authority can be held responsible for them.