Guide to the Quantum Future: Countdown to Q Day
At the time of writing, about thirty years have passed since the world first learned that the foundations of modern cryptography were not as stable as had been previously believed. And in many ways the world was quite lucky that these results came out when they did, because for over three decades, we've known that these would one day be major issues, but the ability of attackers to take advantage of these developments has been removed by the lack of working quantum computing hardware. It was, in the words of one security researcher, "a zero day, foretold in advance."[1]
So, although the security world raised alarms, it was an issue for another day.
However, although nobody at the time, or for years since, was ever able to predict when that day would ultimately arrive, recent advances in quantum computing hardware have been making both sustained and relatively predictable progress.[2]
This both allows researchers to begin to tentatively extrapolate when quantum decryption might become practical and widespread and adds additional urgency to the questions of how to secure the post-quantum internet. So, with both the theoretical basis worked out and workable hardware on the near-term horizon, it’s worth asking what quantum computers will break, how fast, and how this will translate into practical consequences for security. To answer this, we'll look in turn at three major areas of modern cryptography that quantum computers of the near-term future appear likely to significantly impact. The first is the classical public-key cryptography algorithms based on prime factorization. The second is some of their proposed, supposedly more powerful replacements. And the third is symmetric encryption.
RSA and Classical Asymmetric Encryption
The foundations of modern public-key cryptography, despite having earlier predecessors such as the Diffie-Hellman algorithm, mainly lie with the invention of the RSA algorithm in the mid-1970s. RSA, still widely used today, relies on prime factorization, essentially meaning that its public and private keys security relied on a (previously believed to be) hard problem of breaking down a large number into its two unique prime factors. Since it is easy to take two sufficiently large numbers and get their product, but extremely difficult to take the product and get the two prime factors, this general approach worked very well for public-key cryptosystems for decades. However, this changed in 1994, with the discovery of Shor's algorithm.
Shor's algorithm, the first quantum algorithm with major applied potential, sent shock waves through the security world when it was first published. The algorithm, a "hybrid" algorithm that combined classical pre- and post-processing with a quantum subroutine which performed order-finding computations using a quantum superposition, dramatically reduced the time necessary to factor large composite numbers into their primes. Whereas previously the best-known classical algorithm, the General Number Field Sieve (GNFS), would increase sub-exponentially in time and complexity with an increase in the bit-size of the composite number (or public key), Shor's algorithm reduced this to polynomial-time complexity. This essentially led to an enormous reduction in the theoretical time needed to factor a large number into its prime components, where the complexity would only grow at a rate of O(n^2), making adding larger keys a much less sustainable practice. Additionally, in 2023, mathematician Oded Regev discovered an optimization to Shor's algorithm which allowed for an even further complexity reduction, meaning that only n^1.5 gates or operations would be needed to break RSA with keysize n.[3]
To put it simply, these two algorithms completely break the security of public-key algorithms that rely on prime factorization. At the time of writing, in 2026, RSA-2048 (RSA algorithm with a 2048-bit key) is considered secure and is widely used, as for instance, many IoT devices ship with a maximum keysize of 2048 for RSA encryption.[4] However, Shor's algorithm, and its subsequent optimizations, have threatened to reduce the time needed to decrypt a 2048-bit key on a quantum computer to that of a 1024 public-key (or even less!) on a classical computer. While still computationally expensive, this puts data encrypted with RSA-2048 within the reach of nation-states and well-funded organizations. With some security researchers [1] postulating that a quantum computer containing several thousand logical qubits would be capable of tractably cracking even a 2048-bit RSA key, this is set to become insecure in the near-term future, likely within several years. As this is by far the most popular and widely used public-key encryption algorithm in use today, this poses an acute and urgent problem to the security of digital communications.
Eliptic-Curve Cryptography and Other "Quantum Resistant" Algorithms
Elliptic-curve cryptography (ECC) is an alternative to prime factorization for public-key cryptosystems that was first implemented in the 1990s with wide-scale adoption by the mid-2000s.[5] The major selling point of ECC when it was developed was that it allowed for similar-strength encryption, albeit with smaller keysizes (for instance, an ECC key of 224 would broadly correspond to an RSA key of 2048 in decryption difficulty).[6],[7] In this regard, it has advantages over the RSA algorithm, in that stronger encryption can be deployed to devices where power, latency, or storage space are at a premium, such as many real-time, embedded, or IoT devices. This was doubly important due to the rapid increase of power and computation costs when a key is increased in length; one estimate claimed that RSA-4096 required an eightfold increase in CPU usage.[8] However, despite its advantages, quantum computers pose a similarly severe threat to ECC.
Shor's algorithm, with minor modifications, can be deployed against ECC, where it achieves similarly impressive results. Although Shor's algorithm, with the subsequent optimizations discussed above, reduces the complexity of prime factorization to O(n^1.5), it only achieves O(n^3) for ECC.[9] However, this is still extremely damaging to the security of ECC, essentially reducing its complexity from exponential to polynomial time. Additionally, some security researchers speculate [1] that even a quantum computer with 2500 logical qubits can break ECC keys in use today. The largest quantum computer at time of writing has approximately 1100 physical qubits. Currently, it requires 1000 physical qubits to create one logical qubit. While we anticipate that number will decline in the coming years, there will be some time before such a quantum computer exists.
Grover's Algorithm, AES, and Symmetric Encryption
The predicted progress of advancements in quantum computing hardware looks likely to significantly accelerate the weakening of asymmetric-key cryptography. However, what will the impacts look like in the realm of symmetric-key encryption?
The current standard for symmetric encryption is, and has for several years been, the Advanced Encryption Standard (AES) algorithm, which is widely used today to encrypt data in transit and at rest. AES is incredibly widely used in government, industry, academia, and elsewhere. At time of writing it is considered the "gold standard" for symmetric encryption, with AES-256 considered secure for many sensitive applications.
However, despite its apparent strengths, AES is vulnerable to another quantum algorithm, Grover's algorithm, which was discovered in the mid-1990s, around the same time as Shor's algorithm. Unlike Shor's algorithm, Grover's algorithm is a "pure" quantum algorithm, as it uses only post-quantum and not classical algorithms. The quantum algorithm in question allows a quantum computer to perform a search on a given keyspace of size N in only N^(1/2) steps, drastically reducing search time. To consider the impact of this, a classical search algorithm in an unordered and high-entropy keyspace of 1,000,000 possible keys requires an average of 500,000 guesses. However, Grover's algorithm could theoretically perform this in 1,000 guesses. In terms of the impact on AES and symmetric-key cryptography, it would certainly weaken the strength of AES-encrypted data. With Grover's algorithm, AES-256 would likely be crackable in a similar length of time to AES-128 with classical techniques, certainly a major difference.
Despite the threat it poses, the real-world impact of Grover's algorithm may be less significant than in the case of public-key algorithms. This is mainly due to the comparative difference in increasing keysizes: RSA, ECC, and most public-key encryption algorithms require a steep and often polynomial increase in power and CPU usage as one increases the key length.[8] AES, in contrast, scales much more efficiently, with AES-256 requiring on average only 40% more power than AES-128, not even doubling the power requirements while doubling the keysize, meaning that in many cases it’s likely more possible to just make longer keys and somewhat mitigate the security threat.[10],[11] This implies (to the authors) that the impact to symmetric-encryption, while real, will not be as pronounced as in the case of public-key cryptography. This is especially the case as symmetric-key cryptography often has lower power and computing requirements more generally. For instance, in TLS 1.2, HTTPS uses an initial RSA handshake, before switching to an AES-encrypted "shared" symmetric-key after the handshake, in large part for computing and power savings. The quantum revolution will likely hit asymmetric encryption harder and faster as a result.
Impact on Information Security
In all three areas, significant questions do remain about the timing of quantum hardware developments, the ability of new proposed alternatives to provide serious resistance to quantum decryption, and the speed at which the world can adopt new encryption standards, among others. However, what seems clear from recent developments and historical analysis is that in the coming years, barring major unforeseen changes, quantum computing will significantly reduce the cost and increase the speed of decrypting existing asymmetric and symmetric-key cryptographic algorithms. This will have significant practical consequences. Although new quantum-resistant alternatives do currently exist, for instance the lattice-based cryptography system developed by Oded Regev, much research remains to be performed on their long-term robustness to quantum decryption.
Even if these algorithms do provide a measure of security against quantum decryption, threats remain. Most large organizations will likely be able to adopt the newer, quantum-resistant algorithms that are currently coming out by the time that quantum decryption becomes practical. However, ensuring that especially small organizations transition over successfully to using approved quantum-resistant algorithms will still require significant resources and managerial and technical expertise.
Similarly, although many devices such as servers, laptops, and other hardware will likely be able to run public-key algorithms with larger keysizes to offset the advances in quantum decryption, this strategy runs into significant limitations when looking at Internet-of-Things devices, real-time or embedded devices, or any common devices in low-power, low-latency domains. Many of these devices currently ship with a maximum RSA keysize of 2048 due to power and latency constraints.[4] While it is possible that future improvements may lead to greater power efficiency gains, unless significant and unlikely advances occur in the coming years, many devices will likely be very vulnerable to quantum decryption attacks.
Based on the technical properties alone, there are certainly many areas which may have worse security overall in the coming years if steps aren't taken to address their current limitations. However, serious zero days have been discovered many times before. Although these did significant damage, the world was also caught completely unawares by these vulnerabilities and had to scramble and quickly mobilize significant resources with no pre-existing plan to patch vulnerable systems. In contrast, quantum decryption, while undeniably a major challenge, is a challenge that the security community has had time to prepare for.
So, in the end, will the advent of quantum computing lead to major degradations in the broader internet's overall security? In many ways it appears so, although as the infosec community has had many years to anticipate and prepare for this event horizon, it is possible that adequate steps can be taken to prevent major breaches before they happen. As with everything in the chaotic and nonlinear world of security, we will ultimately just have to wait and see. But it seems likely that within five years, quantum computers with sufficient power to perform meaningful work will exist. If that happens, many foundational pieces of security infrastructure will become obsolete, requiring new strategies to mitigate threats. These include problems like the “Harvest Now, Decrypt Later” issue, the bureaucratic, economic, and technical issues with getting organizations large and small to adopt new encryption standards, and how different technologies such as embedded or IoT devices can keep up. In the next article, we will look at what might happen with these issues as quantum computers continue to improve.