How much of a threat are quantum computers to our encrypted data — and where are their mathematical limits?
256 Bits — How Secure Is That?When we visit a website, send a message, or access our online banking, we rely on encryption to protect our data during transmission.
Yet quantum computers are often described as machines that will one day break encryption systems that would take classical computers an almost unimaginable amount of time to defeat.
How serious is this threat?
To find out, let’s consider a specific example: An attacker has recorded the encrypted traffic of an internet connection. The data was encrypted using AES-256. The attacker does not know the encryption key and wants to recover it using a quantum computer.
256 Bits — How Secure Is That?
AES stands for Advanced Encryption Standard and is one of the most widely used encryption algorithms in the world.
With AES-256, the secret key consists of 256 bits. Each bit can have one of two values: 0 or 1.
This gives us a total of:
2 ²⁵⁶ possible keys.
That is a number containing 78 digits.
If our attacker does not know the correct key, one possible approach is to try different keys and check whether they correctly decrypt the recorded data.
For a randomly generated key, a classical brute-force search requires, on average, approximately half of all possible attempts.
That would mean roughly 2 ²⁵⁵ key tests.
To put this into perspective, imagine a hypothetical supercomputer capable of testing one quintillion keys every second.
One quintillion is 10 ¹⁸, or one billion billion.
Even at that speed, an exhaustive search would take approximately 3.7 × 10 ⁵¹ years.
For comparison, our universe has existed for approximately 13.8 billion years.
The search would not merely be time-consuming. With classical computing technology, it would be practically impossible.
But our attacker has a quantum computer.
What Changes With a Quantum Computer?
A quantum computer processes information differently from a classical computer.
While a classical bit has a definite value of either 0 or 1, a quantum bit, or qubit, can exist in a superposition of both states.
Multiple qubits can form a quantum state whose mathematical description includes many possible combinations simultaneously.
This often leads to the simplified claim that a quantum computer can try every possible key at once.
But that is misleading.
When we measure such a quantum state, we obtain only one result.
Measuring an equal superposition of all possible keys would simply return a randomly selected key.
The probability of finding the correct AES-256 key this way would be just as small as making a single random guess on a classical computer.
The real advantage comes from using an appropriate quantum algorithm.
And for our example, such an algorithm exists.
Grover’s Algorithm
In 1996, computer scientist Lov Grover developed an algorithm that allows a quantum computer to search an unstructured set of possibilities significantly faster than a classical computer.
In a classical search, the amount of work grows in proportion to the number of possible solutions.
Grover’s algorithm reduces this to approximately the square root of that number.
If we had one million possible keys, a classical computer might have to examine all one million in the worst case.
A quantum computer using Grover’s algorithm would need only around a thousand search iterations, apart from a constant factor.
That is already an impressive improvement.
The difference becomes even more striking with our AES-256 key.
The classical search space contains 2 ²⁵⁶ possibilities.
Grover’s algorithm reduces the theoretical search complexity to:
√(2 ²⁵⁶) = 2 ¹²⁸
This reduces the theoretical security strength from 256 bits to 128 bits.
In cryptography, we therefore often say that Grover’s algorithm halves the security strength.
But there is an important distinction: The number of search steps is not simply cut in half. It is reduced to approximately its square root.
And 2 ¹²⁸ is still an enormous number.
How Does Grover Find the Correct Key?
Our attacker first needs a quantum computation capable of checking whether a particular key matches the recorded encrypted data.
This verification is implemented as part of a quantum operation called an oracle.
The oracle does not simply reveal the correct key. Instead, it changes the phase of the quantum state representing the desired solution.
Grover’s algorithm then applies another operation known as diffusion.
This changes the probability amplitudes of the possible solutions by reflecting them about their mean.
Together, these two operations form a Grover iteration.
We can think of the process as a system of overlapping waves.
Through repeated operations, quantum interference occurs: The amplitude associated with the correct solution increases, while the amplitudes of the other possibilities collectively decrease.
After a sufficient number of iterations, measuring the quantum state has a high probability of revealing the correct key.
The quantum computer is therefore not reading out all possible keys simultaneously.
Instead, it gradually transforms the quantum state so that measuring the correct key becomes increasingly likely.
That is the fundamental advantage of Grover’s algorithm.
However, this process still requires an enormous number of consecutive iterations.
How Long Would the Attack Take?
For our AES-256 key, the theoretical search complexity is on the order of ²¹²⁸ Grover iterations.
Written out, that number is:
340,282,366,920,938,463,463,374,607,431,768,211,456
A number containing 39 digits.
Now imagine that our attacker possesses a quantum computer capable of performing one trillion complete Grover iterations every second.
At that speed, performing 2 ¹²⁸ iterations would take approximately 10.8 quintillion years.
Taking into account the more precise iteration count required by Grover’s algorithm, approximately π/4 × 2 ¹²⁸ for a single marked solution, the calculation time would be reduced to around 8.5 quintillion years.
For comparison, the universe has existed for approximately 13.8 billion years.
The calculation would therefore take more than 600 million times the entire age of the universe so far.
And remember: We have already granted our attacker a hypothetical quantum computer operating at a speed far beyond today’s technological capabilities.
Why an Iteration Is Not a Simple Operation
Our calculation assumes that one complete Grover iteration can be performed in one trillionth of a second.
This is a purely hypothetical assumption.
In reality, each iteration requires a sequence of complex quantum circuits.
In particular, testing an AES key must be implemented as a reversible quantum computation.
This involves numerous quantum gates that must be executed in a specific order.
Furthermore, qubits are highly sensitive to disturbances. A quantum computer capable of performing such a long calculation reliably would require quantum error correction.
The additional qubits and operations needed for error correction significantly increase the hardware requirements.
Researchers have already investigated the resources required to implement Grover-based attacks against AES.
Their studies show that there is a substantial difference between the theoretical speedup of a quantum algorithm and its practical implementation on quantum hardware.
Our assumed rate of one trillion iterations per second is therefore not a realistic performance prediction. It serves only to illustrate the mathematical scale of the problem.
Could the Attack Be Parallelized?
Our attacker might try to use multiple quantum computers searching for the key simultaneously.
This is possible in principle.
However, Grover’s algorithm cannot be parallelized arbitrarily without sacrificing part of its quantum advantage.
The iterations within an individual Grover search depend on one another. They cannot simply be executed independently.
If the search space is divided among multiple quantum computers, each machine can examine a separate subset.
With P equally sized subsets, however, the number of iterations required per quantum computer decreases by only approximately a factor of √P.
By contrast, a classical brute-force search can distribute its workload almost linearly across independent processors.
Additional quantum computers can therefore accelerate an attack, but the relationship between additional hardware and reduced execution time is less favorable than one might initially expect.
There are also the substantial hardware requirements of every individual quantum computer.
Simply adding more machines does not make the astronomical scale of our AES-256 example disappear.
Does That Mean Internet Encryption Is Safe?
For our specific example, the answer is clear: A direct attack against a correctly generated AES-256 key remains practically out of reach, even with Grover’s algorithm.
The theoretical quadratic speedup is remarkable, but it is not sufficient to overcome the enormous size of the remaining search space.
However, this does not mean quantum computers pose no threat to internet security.
In a real internet connection, an AES key is not used in isolation.
The communicating parties must first securely establish shared secrets and verify the identity of the server.
These tasks rely on additional cryptographic mechanisms, some of which are vulnerable to sufficiently powerful quantum computers.
If an attacker can compromise the key establishment process of an internet connection, they may not need to attack AES directly.
The security of a connection therefore depends on more than the strength of its data encryption alone.
Our example answers one specific question: How resistant is AES-256 to a direct quantum-assisted key search?
It does not establish whether every component of today’s internet connections is already quantum-safe.
That is precisely why new quantum-resistant cryptographic methods for key establishment and digital signatures are being introduced.
Conclusion
Quantum computers are changing the security requirements of the internet. But they do not automatically make every encryption algorithm insecure.
AES-256 demonstrates that even a mathematically impressive speedup does not necessarily translate into a practically feasible attack.
Grover’s algorithm reduces the theoretical search complexity dramatically, yet the remaining task is still enormous.
The future security of the internet will depend not only on the capabilities of quantum computers, but also on our ability to distinguish which cryptographic systems actually need to change.
Sources and Further Reading
NIST — Post-Quantum Cryptography FAQ
https://csrc.nist.gov/projects/post-quantum-cryptography/faqs
Grassl et al. — Applying Grover’s Algorithm to AES: Quantum Resource Estimates (2016)
https://arxiv.org/abs/1512.04965
NIST — Post-Quantum Cryptography Standards
https://csrc.nist.gov/projects/post-quantum-cryptography
NASA — What Is the Universe?
https://science.nasa.gov/exoplanets/what-is-the-universe/
Can Quantum Computers Break 256-Bit AES? Grover’s Algorithm Explained
https://www.youtube.com/shorts/VqSMXXiZIWo
Top comments (0)