What kind of encryption is difficult to decipher even with a quantum computer?
It is said that advances in quantum computing technology are making
Quantum Computers Are Not a Threat to 128-bit Symmetric Keys
https://words.filippo.io/128-bits/
Grover's algorithm , one of the algorithms for quantum computers, is a search algorithm that enables quantum computers to solve problems that would otherwise require brute-force searching for the correct answer in fewer attempts than classical computers. Mathematically, when the size of the input space is N, classical brute-force methods generally require N attempts, while Grover can find the correct answer in approximately π/4 × √N function calls. For this reason, it is said to be an algorithm that threatens symmetric encryption like AES-128.
However, Barsoda argues that 'the common perception that AES-128 is threatened by quantum computers and Grover's algorithm is inaccurate.' While Grover's algorithm can certainly be made faster, it doesn't work as straightforwardly as brute force on classical computers, especially when considering the ease of parallelization, which is crucial in real-world attacks.
Grover's algorithm requires the function being searched—that is, the process of determining whether 'this candidate is correct'—to be implemented within the quantum circuit itself, and its calls must essentially be stacked in series. Moreover, there seems to be no good way to parallelize Grover's algorithm, so ultimately the only option is to divide the search space. However, when the search space is divided, in classical computation the amount of work per machine decreases directly according to the number of divisions, whereas in Grover it is '√N', so the decrease is slower.
For example, if a brute-force attack on a 64-bit key is distributed across 2¹⁶ classical computers, the burden on each computer is reduced to 1/ 2¹⁶ . On the other hand, even if a Grover attack on a 128-bit key is distributed across 2¹⁶ quantum computers, the burden on each instance is only reduced to 1/ 2⁸ . As a result, while Grover is theoretically fast, it is not well-suited to the practical application of 'throwing the attack across a large number of computers to finish it all at once,' which is crucial for large-scale attacks in reality.
by
In short, Grover's algorithm is an important algorithm that demonstrates that quantum computers can theoretically perform brute-force searches much faster, but this does not necessarily mean that AES-128 will be half as powerful. While it looks powerful from a theoretical standpoint, in reality, it faces significant constraints such as the difficulty of quantum circuit implementation, seriality, parallelization, and the need for long-term operation.
Let's assume we have a high-speed quantum computer that can perform a single quantum gate calculation in just 1 microsecond, and that it can run almost continuously for 10 years. In this case, the maximum length of processing that a single quantum computer can stack, that is, the maximum length of serial computation, is approximately 2⁴⁸ gates.
If we were to incorporate AES-128 as a quantum circuit that could use Grover's algorithm, we would need to include a function f that determines whether the answer is correct as part of the Grover algorithm. However, even with the AES-128 optimization announced in 2025, this determination would require running 232 parallel 724 logic qubits for approximately 10 years. In other words, it would be a very large and complex quantum circuit.
In short, while Grover's algorithm can reduce the number of searches, the judgment process performed in each search is computationally intensive. Therefore, although theoretically it may only take 264 tries to find the answer to AES-128, in reality, each of those 264 tries has a circuit attached to it for the judgment. As a result, even though Grover is theoretically fast, the overall attack to actually break AES-128 is computationally very expensive.
by
Shor's algorithm , used to solve prime factorization problems on quantum computers, is said to be effective against public-key cryptography such as RSA and elliptic curve cryptography . Solving 256-bit elliptic curve cryptography with Shor's algorithm requires approximately 2 ^26 gates. If each gate takes about 10 microseconds, this calculation would be completed in just a few minutes.
Barsoda argues that the cost of cracking AES-128 with Grover's algorithm is approximately 278.5 times, or about 43 × 10²⁰ times, greater than the cost of cracking a 256-bit elliptic curve cryptography with Shor's algorithm. While it's easy to say that 'cryptography is vulnerable with the advent of quantum computers,' symmetric key cryptography using Grover's algorithm is far less practical than public-key cryptography using Shor's algorithm.
The U.S. National Institute of Standards and Technology (NIST) continues to consider AES-128 secure and has explicitly stated that AES-128, AES-192, and AES-256 can continue to be used. The German Information Security Agency (BSI) shares this position and recommends AES-128, AES-192, and AES-256 for new systems.
Cryptographer Samuel Jakes published a similar argument in 2024, stating that 'it's a mistake to think that the key length of AES should be doubled just because Grover's algorithm has made it faster.' He added that attacks that would run Grover's algorithm in parallel would be too costly, so AES-128 may never be broken, not even in a lifetime.
Furthermore, Barsoda expressed a negative stance towards the idea that 'just to be safe, we should make all symmetric key cryptography 256 bits.' He argued that what really needs to be addressed is replacing public key cryptography, which becomes vulnerable due to Shor's algorithm, and that making unnecessary changes would increase the workload and adjustments, hindering interoperability. Barsoda suggested that 'changing TLS key sharing and signing methods' and 'changing the key length of symmetric cryptography' are separate tasks, and that it would be better to concentrate resources on the necessary parts.
Related Posts:
