Quantum Cryptography Apocalypse: A Timeline and Action Plan

There is a potential dark side to quantum computing, one that is a threat to how we secure data. Back in 1994, Peter Shor developed an algorithm for factoring large numbers using a quantum computer, which could be used to break encryption. Today, RSA encryption relies on the difficulty a classical computer has with such factorization. With Shor’s algorithm in mind, nation-states and nefarious actors started harvesting data packets, dreaming of a future where they would be able to decrypt those packets using a fault-tolerant quantum computer.

Currently, there are about three dozen quantum computers in the cloud. These quantum computers are error-prone and lack enough quantum bits (qubits) to run Shor’s algorithm against RSA encryption. Some experts claim quantum computing will not be a threat for at least 30 years. However, those claims may be based upon outdated information and there is evidence that quantum computing will have the power to crack encryption sooner than we thought.

Identifying Quantum Threats

The day is coming when a quantum threat (Y2Q) to encryption becomes a reality. Y2Q proves similar to a combination of the Y2K bug and the 2014 Heartbleed attack, where it will affect almost every system on the planet and severely affect data in motion.

Y2Q affects two types of general cryptography: symmetric and asymmetric. Symmetric encryption is used for data at rest and functions like a locked box with a key. Shor’s algorithm cannot attack symmetric encryption ciphers such as AES, however Grover’s search algorithm can weaken it. To combat Y2Q in this situation, we can increase the symmetric key size and make it even more difficult to attack via brute force.

Data in motion on a network is protected by asymmetric encryption, which is commonly called public key cryptography, and its most prevalent example is via a cipher known as RSA. RSA is vulnerable to Shor’s algorithm, allowing a quantum computer to reverse private keys and read messages. Blockchain also uses a type of public key encryption called ECC, which means the crypto economy is also threatened by quantum computing.

Preparing for Y2Q begins with conducting a post-quantum crypto (PQC) agility assessment. Crypto agility is the ability to introduce new cryptography to an organization’s hardware and software without being disruptive to infrastructure. However, identifying those primary threats is not easy. It is a matter of determining what ciphers are used throughout an organization, including in third-party hardware and software. Further complicating the process is that some elements may not have a path forward for post-quantum cryptography.

Exploring the PQC Threat and Timeline

It may be too late to protect certain types of data. Mosca’s theorem states that you must add the number of years it takes your organization to migrate to new cryptographic standards and primitives to the shelf life of your secret. For example, three years to migrate plus a regulatory requirement of 10 years of maintenance would equal 13 years.

Using the implementation example of Shor’s algorithm called Toffoli-based modular multiplication, we can estimate that quantum computers will have enough power (high-fidelity qubits) to crack encryption by the end of this decade.

However, the quantum world is constantly making observations on its denizens, including qubits, which causes them to decohere and become “classical” or unable to compute with quantum algorithms. System builders must account for this noise and resolve engineering challenges to make qubits near perfect with 99.99% fidelity. We also need to run error correction, which requires sacrificing some physical qubits to create a logical, error-corrected qubit.

Qubit growth can be accelerated by using a few modest-size, quality quantum computers that work together using a technology called interconnect, which allows quantum computers to entangle qubits to behave as one quantum computer. If we get interconnect right, we could take, say, four 1,100-qubit quantum computers and instantly have a 4,400-qubit machine capable of doing damage to encryption.

IBM has a grim prediction that it will take 1,000 physical qubits to yield one error-corrected qubit. However, IonQ thinks it is closer to 16 to 1. An estimate between those two extremes indicates that if we get close to 1 million physical qubits this decade, we will quickly surpass current predictions.

NIST is aware of the looming threat and has been working to develop a new standard of PQC with ciphers to replace RSA. We expect a new standard by the end of 2024.

In May 2022, the White House released the National Security Memorandum on Promoting United States Leadership in Quantum Computing While Mitigating Risks to Vulnerable Cryptographic Systems. That memo has action demands on federal entities to be taken after NIST finalizes the new standard.

We can expect regulators and other industries in the private sector to mirror these expectations closely. Simply put, organizations must become crypto-agile and introduce hybrid PQC solutions for today’s most critical data flows.