Quantum Computing is Going to Kill Classic Cryptography. But We Can Still Save it.
Cryptography is all around us. It secures our online communication and financial transactions, protects our cloud storage privacy and ensures the integrity of our mobile applications. It is rooted so deeply in our devices and applications that we hardly ever notice it.
This all-encompassing magic relies on hardness assumptions that prevent anyone without knowledge of the decryption keys from ever decrypting our data. In layman’s terms, even in a billion years, with the entire computing power available on our planet, we would not be able to decrypt if we do not know the key. While these assumptions hold for computers today, they collapse the moment physicists and engineers finish building the quantum computer they have been working on.
In this post I will explain this upcoming threat and why most people haven’t heard about it — yet. Most importantly, you can learn how to best prepare for it. (Spoiler alert: We already have new cryptographic algorithms to replace the ones that quantum computers break, but replacing them is more complicated than you might think).
A Quantum Computer is Unlike Any Computer You’ve Ever Seen
Quantum computers are a revolutionary new type of computer that use quantum mechanics principles to perform calculations at incredibly fast speeds. Unlike traditional computers, which use bits to represent information as either a 0 or a 1, quantum computers use quantum bits, or qubits, which can exist in multiple states simultaneously.
This capability allows them to perform multiple calculations simultaneously, making them exponentially faster than classical computers. A key benefit of quantum computers is the ability to solve complex problems that are impractical to solve using classical computers. For example, researchers can use simulations to model complex systems such as molecules or weather patterns, which can aid in developing new drugs or making more accurate weather predictions. However, one can also use them to break encryption algorithms.
Quantum Algorithms Can Break Modern Encryption
Two main quantum algorithms that break modern encryption were published as early as the 90s:
1) Shor’s Algorithm
Peter Shor developed Shor’s algorithm in 1994. It is a polynomial-time quantum algorithm for integer factorization, which can break many of the cryptographic schemes used for secure communication and data storage. Among those algorithms are RSA, DH, DSA, ECDH and ECDSA.
2) Grover’s Algorithm
Developed by Lov Grover in 1996, Grover’s algorithm is a quantum algorithm for searching an unsorted database. Using Grover’s algorithm, we can exhaustively search a decryption key with only a square root of the effort required on a classical computer. This makes finding a 128-bit AES key feasible on a quantum computer, as it only requires the effort it takes to break a 64-bits key on a classical computer.
Even though Shor’s and Grover’s algorithms have been around since the 90s, our classic cryptography still holds because, despite their potential, quantum computers are still in the early stages of development.
In other words, we have the software ready but don’t yet have the hardware to run it at scale. There are still many challenges to overcome, including creating enough stable qubits to maintain their quantum state for a long time. However, researchers are working on these challenges, and we will likely see significant progress in the coming years.
No one knows when we will have a quantum computer that can break modern encryption, but most experts believe it will happen within the next 20 years — probably sooner. Meanwhile, quantum computers of a small scale are already available today as a cloud service from companies like IBM and AWS.
So even after 40 years of research, we still expect at least a decade before we have an effective quantum computer. One may wonder: Why the sudden increase in attention now?
The first reason is the rapid technological advancement we’ve seen in the last few years. This started with Google’s announcement of achieving quantum supremacy — demonstrating a quantum computation that no classical computer could solve in any feasible amount of time in late 2019. Since then, we have also seen unprecedented investments, by governments and organizations — and this rapid progress will likely continue.
Time to Standardize New Cryptographic Algorithms
The second reason is that continuing to use cryptography seamlessly in the post-quantum era calls for standardizing the building blocks and protocols that secure our communication, which can take a while. Due to cryptographic standards, we securely connect to our bank account today both from our Android device and the web browser on our laptop. TLS protocol is the de-facto cryptographic standard for securing connections, and it uses standard algorithms such as RSA, Diffie-Hellman and AES as the cryptographic building blocks.
In response to the potential threat posed by quantum computers to current cryptographic algorithms, NIST (the U.S. National Institute of Standards and Technology) initiated a process in 2016 to standardize post-quantum cryptography.
This process involved soliciting and evaluating proposals for post-quantum cryptographic algorithms from the research community and then selecting a set of algorithms that NIST will standardize for use in secure communications. The goal is to ensure that post-quantum cryptographic algorithms are readily accessible and can be adopted by many in order to safeguard against both quantum and classical computer attacks.
In July 2022, at the end of the 3rd evaluation round, NIST announced the first four post-quantum algorithms to be standardized in two separate categories:
● Public-Key Encryption and Key-establishment Algorithms: CRYSTALS-KYBER
● Digital Signature Algorithms: CRYSTALS-DILITHIUM, FALCON and SPHINCS+.
Four additional candidates continued to the 4th round (BIKE, Classic McEliece, HQC, SIKE), but lately SIKE was broken by a classical computer and only three candidates remained
In August 2023 three of these algorithms were published as FIPS draft. NIST is also developing a FIPS that specifies a digital signature algorithm derived from FALCON as an additional alternative to these standards.
But… is it Already Too Late?
Another reason for the sudden focus on quantum computing is the discovery of mass surveillance of our communication. In 2013, Edward Snowden exposed the extent to which the NSA had been doing it, but it, of course, had been practiced — and continues to be practiced — by other organizations or entities around the globe. Our encrypted communication is recorded, and it will be decrypted once a quantum computer becomes available, even if it cannot be decrypted today.
This impending reality makes time a new dimension that we are not used to considering in security. When we encrypt our data, we believe it’s protected for years to come without an expiration date. For some applications, the fact that the information may be decrypted in ten years is not a problem. (Think about the financial results of a public company. A minute before they are announced, they are top secret. A minute later, they become public knowledge. In contrast, a nation’s military secrets need to remain a secret for many years).
Now that the risk is more evident and we finally have quantum-safe algorithms, why don’t we just switch our cryptography to a post-quantum one? Then everything would be fine.
Unfortunately, this is easier said than done. Experience shows that it takes years to switch cryptography, and things are even more complicated nowadays.
The Challenges of Replacing a Broken Algorithm
Let’s take RSA as an example. Since Shor’s algorithm breaks it, we need to replace every instance with one of the new algorithms.
But wait. We first need to answer three critical questions:
1. Where are all the places that we are using it?
2. Which algorithm should we use to replace it?
3. What about assurance that the new algorithm is secure?
These questions are far more complicated than they appear.
Let’s start with the first question. We hardly ever use RSA directly. We use it to sign certificates, encrypt session keys, etc. Finding all the places that RSA is used entails going over the source code and locating all the direct and indirect (e.g., TLS, 3rd party libraries) usages, including services that use it and the cloud infrastructure that relies on it.
As hard as it may be to find these instances, replacing them is even harder. Sometimes, it is not within our power to do so. For example, if our cloud infrastructure uses RSA, we must rely on them to switch to a post-quantum algorithm.
The second question is even trickier as there is no single drop-in replacement. RSA is used both for encryption and digital signatures, and if we want to do both, we need to pick two different algorithms from NIST’s list. These algorithms differ in the mathematical problems they are based on, and we do not know which of them will prove to be weaker and which will stand the test of time. They also vary in their performance, key sizes and ciphertext sizes. All these parameters must be considered, especially if legacy restrictions limit us.
The third question raises a genuine concern about switching sound algorithms with new ones that may end up broken even using algorithms that run on a classical computer. And it’s not just a hypothetical concern. During the evaluation process, some of the NIST candidates were broken using a classical algorithm. That’s why it’s recommended to use new algorithms in addition to classical ones, to ensure that the combination is at least as secure as current implementations against classical computers, and also provides post-quantum security. The new algorithms are also based on different hardness assumptions, so if one of them breaks (either by a classical or quantum computer), others will still hold.
Defending Against the Quantum Computing Threat
If you have reached this point, you are probably asking, “OK, so what should I do to protect myself?”
The first step is starting with mapping the cryptographic inventory. In addition to mapping the usage, one should also map the risk. First, ask yourself: What are the consequences of someone getting their hands on our encrypted data today and decrypting it in ten years?
The answer to this question will significantly affect the migration plan in terms of priority and timetables. Prioritizing one system over another for cryptographic transition highly depends on organizational functions, goals, and needs. A detailed list of the actions organizations should take is available from the European Telecommunications Standards Institute (ETSI) and the U.S. Department of Homeland Security (DHS). Organizations should follow their recommendation in their post-quantum preparation plan. President Biden created a sense of urgency when he recently signed a law that calls for agencies to run cryptography mapping by May 2023 and that, by July 2023, should begin moving toward implementing the NIST-approved cryptographic algorithms.
Even though we know that quantum computers will change cryptography as we know it, we can still prepare for it. We have new encryption algorithms, and we can start building our migration plan using the guidelines from the organizations above. However, we need to act now since changing our underlying cryptography will take a lot of time and effort and requires all stakeholders to cooperate.
Editor’s note: To learn more about quantum computing’s impact on classic cryptography, read Dr. Waisbard’s CyberArk post, “Quantum Computing Is Coming… Here are 4 Ways to Get Ready” and tune in to the Trust Issues podcast conversation on this topic on the Trust Issues Podcast
