Not every quantum algorithm is a threat to encryption, and knowing which are important matters more than many think when signaling through the noise around quantum computing. There are only two algorithms that really deserve the hype: Shor’s and Grover’s. Both were imagined decades before the advent of quantum computers capable of running them at scale. Yet they already influence how security teams think about the future of every currently deployed cryptographic system that protects data.
Quantum algorithms and the risks of encryption provide a clear overview of why these two mathematical procedures, among all the quantum algorithms researchers have studied, have a direct bearing on cryptography.
Shor’s Algorithm and the Public-Key Problem
Peter Shor invented his algorithm (now known as Shor’s algorithm) in 1994, and it has proven to be one of the most impactful results in computer science ever published in an academic paper because of what it enables. Most importantly, the type of public-key cryptography that secures web traffic, digital signatures, and secure key exchange relies on mathematical problems that are extremely hard for classical computers to solve, namely factoring large numbers and computing discrete logarithms. On a sufficiently powerful quantum computer, Shor’s algorithm solves both of these problems with polynomial time complexity. It therefore renders the mathematical underpinnings of crypto systems like RSA (numbers), Diffie–Hellman (discrete logarithms), and elliptic-curve cryptography irrelevant once such a machine is built.
A large part of this speedup traces back to a subroutine called the quantum Fourier transform, which has itself spurred continuing research even beyond cryptography. In Coverage explaining this one root mechanism, the quantum heart of Shor’s algorithm shows how the mathematical operation below remains central to breakthroughs in Shor’s algorithm and has been adaptive for decades since his original invention, spurring new research in quantum study.
Why Shor’s Algorithm Is A Break, Not a Weakness
Unlike competing cryptographic threats, what makes Shor’s algorithm so different is precisely the type of break it fears. The majority of cryptanalytic breakthroughs weaken security by small degrees, requiring a switch to somewhat larger keys or slightly modified parameters. Shor’s algorithm does something distinctly different: When a quantum computer, scaled to run Shor in practice, exists, RSA and elliptic-curve cryptography cease to provide any meaningful security for any key size we might deem practical. That is unlike some other threats in cryptography, where one can simply double the key length as compensation.
This difference is precisely why public-key cryptography has been the main target of post-quantum migration activities. These algorithms, vulnerable to Shor’s algorithm, cannot be patched incrementally but instead require a shift to entirely new mathematical approaches to which Shor’s algorithm does not apply.
Grover’s Algorithm and the Symmetric Key Problem
A different type of problem is solved by Grover’s algorithm, which was developed by Lov Grover in 1996. This means brute-force key search in cryptography, which involves testing all possible keys until one works. Using Grover’s algorithm, one can achieve a quadratic speedup over classical brute-force search, meaning that a quantum computer could search a symmetric key space in about 1/√(time required by its classical counterpart).
At first, this sounds scary, but the actual effect is far more limited than that of Shor’s algorithm. A symmetric key that would take an impractically long time to brute-force classically is effectively immune even with Grover’s quadratic speedup, again so long as the key is sufficiently large. It is this doubling in the key length that restores the original margin of security, so that AES-256 continues to be viewed as safe against Grover’s algorithm, despite research efforts focused on adequately preparing for a post-quantum future.
Reason for the grouping of these two algorithms
Loosely categorized, both Shor’s and Grover’s algorithms are often grouped when discussing quantum risk. Still, they should be considered two distinct classes of threat that require different responses to mitigate their effects. For public-key algorithms potentially threatened by Shor’s algorithm, it’s a full mathematical replacement: an entirely new class of problems on which quantum computers perform poorly, and that can be effectively used for cryptography. For symmetric algorithms that Grover’s algorithm threatens, it is simply a matter of larger key sizes. Many enterprises can achieve this much less drastic change without overhauling their entire cryptographic infrastructure.
It trains educators to create materials that make quantum algorithms widely accessible, suggests a beginner’s primer on quantum algorithms, and lists the core foundation of any serious discussion in the field, including cryptography: Shor’s factoring algorithm and Grover’s search algorithm.
What Does This Distinction Mean for Migration Priorities
The direct, practical implications that arise from a clear understanding of the nature of these two classes of threats inform how organizations should sequence their efforts to transition to using quantum-resistant functionality across their operations. The attack vector provided by Shor is particularly problematic for public-key algorithms used in systems that contain data to be protected, and that needs to remain encrypted for many years (the “harvest now, decrypt later” risk), and this cries out for action. Symmetric encryption against Grover’s algorithm is a little less urgent (because the mathematical problem it relies on has withstood previous forms of quantum attack, and ‘overlapped’ with brute-force attacks can be defended through basic scaling of key sizes), but still worth answering.
Properly prioritizing these two prevents the twin errors of running every cryptographic system through the same hourglass (spreading already-thin resources too far) or effectively dismissing quantum as an impending threat across the board, if symmetric encryption seems far afield from severe short-term danger and public-key systems aren’t viewed in this light.
Frequently Asked Questions
Does a quantum computer exist today that could run this?
Current quantum computers are not powerful enough to run Shor’s algorithm — and even if they were, they’d need error correction to operate on cryptographically relevant key sizes — although estimates of when such a machine might exist range widely among experts.
Should we give up asymmetric encryption like AES because of Gof Rover’s algorithm?
Answer: No, Grover’s algorithm only slightly lowers the effective strength of symmetric encryption (with AES-256 considered reasonably secure even against quantum brute-force attacks).
Why Does Shor’s Algorithm Non-Affect RSA but AES?
The nature of Shor’s algorithm also targets two main mathematical problems at the heart of public-key cryptography: factoring and discrete logarithms, which RSA depends on directly. AES is a symmetric algorithm with an entirely different mathematical basis, against which Shor’s algorithm does not work.
